HNSW介绍

Reading time ~1 minute

Yu. A. Malkov等人在paper《Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs》中提出了HNSW,我们来看下:

介绍

随着信息资源的快速增长,在可扩展和高效相似搜索数据结构方面的需求越来越大。信息搜索的一种常用方法是:K-Nearest Neighbor Search(K-NNS)。K-NNS假设你具有一个已定义好的关于数据元素之间的距离函数(distance function),目标是:为一个query从数据集中寻找K个具有最小distance的elements。在许多应用中使用这样的算法,比如:非参数化机器学习算法、大规模数据集中的图片特征匹配、语义文档检索。K-NNS的一种naive方法是:计算query与数据集中的每个element的距离,并选择具有最小距离的elements。不幸的是,naive方法的复杂度与所存储的elements的总数是成线性增长的,这使得它在大规模数据集上是不可行的。因而,需要开发更快、可扩展的K-NNS算法。

由于“维数灾难”,当只有考虑相对低维的数据时,K-NNS的exact方法可以提供一个较大的搜索加速。为了克服该问题,提出了近似最近邻搜索(Approximate Nearest Neighbors Search (K-ANNS) ),它允许存在一小部分的错误(errors),从而放宽exact search的条件。inexact search(recall)的质量被定义成(true NN数目/K数目)的比值。最流行的K-ANNS解法有:基于树的近似版本[6,7]、LSH[8,9]、以及PQ(乘积量化:product quantization)[10-17]。在高维数据集上,邻近图K-ANNS算法由于良好的表现最近变得流行起来。然而,在低维或聚类数据上,邻近图路由(proximity graph routing)的幂律扩展(power-law scaling)会造成严重性能下降。

在本paper中,我们提出了Hierarchical Navigable Small World(Hierarchical NSW, HNSW),一种基于增量K-ANNS结构的新的完全图,可以提供更好的对数复杂度扩展(logarithmic complexity)。主要贡献有:

  • 图的入点节点(enter-point node)的显式选取(explicit selection)
  • 通过不同尺度(scales)将连接(links)进行分离
  • 使用一个高级的启发法(heuristic)来选择neighbors

可选的,HNSW算法可以被看成是一种使用邻近图(proximity graphs,而非链表)的概率型跳表结构(probabilistic skip list structure)的扩展。效果评估表明,针对常用指标空间(general metric space)提出的该方法,效果要好于只应用于向量空间的state-of-the-art方法。

2.相关工作

2.1 近似图技术

图算法的大多数研究中,搜索(searching)会采用在kNN graphs中的贪婪路由(greedy routing)的形式。对于一个给定的邻近图(proximity graph),我们会从某些enter point(可以随机、或者由一个独立算法提供)上开始搜索,并迭代遍历该graph。在遍历的每个step上,算法会检索query和当前base node的neighbors间的距离,接着选择可以最小化该距离的adjacent node作为下一个base node,并可以继续跟踪最好的已发现neighbors。当满足一些停止条件时(比如:距离计算的数目),该search会终止。链接到一个k-NN graph中最近的neighbors,作为Delaunay graph(它可以保证一个基础的贪婪图遍历的结果总会是最近邻)的一个简单近似。不幸的是,如果没有先验信息,Delaunay graph不能被有效构建,但可以通过只使用在所存elements间的距离来得到最近邻从而进行近似。结果表明,使用这样的近似的邻近图(proximity graph)方法,效果完全要好于其它k-ANNS技术(比如:kd-trees和LSH)

k-NN graph方法的主要缺点有:

  • 1) 在routing过程期间,steps的数目与dataset size成幂律(power law)比例
  • 2) 全局连通(global connectivity)的一个可能loss,在聚类数据上会导致很差的搜索结果。

为了克服这些问题,提出了许多混合方法,它们使用只适用于vector data的辅助算法(auxiliary algorithms),通过一个粗粒度搜索(coarse search),来为enter point寻找更好的candidates。

在[25,26,30]中,作者提出了称为NSW(Navigable Small World)一个邻近图K-ANNS算法(也称为MSW: Metricized Small World),它使用可导航图(navibable graphs)(比如:在贪婪遍历期间,hops数与network size成对数或多重对数比例)。NSW graph通过以随机顺序的方式连续插入元素,将它们与M个最近的neighbors(来自之前插入元素)进行双向连接。M个最近neighbors可以使用该结构的搜索过程被找到。到该elements最近neighbors的连接(links)会在构建开始时插入,并在network hubs间进行桥接(bridges),从而保持全图连通性,并允许在greedy routing期间,hops数成对数比例扩展。

NSW structure的构建阶段可以通过高效并行化,无需全局同步(global synchronization)以及在accuracy上的没有影响,对于分布式搜索系统是一个好的选择。NSW方法在一些datasets上能达到SOTA的效果,然而,由于整体的多项对数复杂度扩展(polylogarithmic complexity scaling),该算法仍被证实在一些低维数据集上效果会下降(在这些数据集上,NSW会输给tree-based算法)。

2.2 NSW模型

关于greedy graph routing成对数和多重对数比例的networks被称为:NSW networks。这样的networks是复杂网络理论中一个重要主题,目标是理解真实网络信息中的底层机制,以便将它们用于scalable routing和distributed similarity search。

第一项工作是,paper[34]的navigable networks的spatial models作为社交网络模型,用于著名的米尔格拉姆实验。…

另一个知名的navigable networks是:scale-free models,它可以复制真实网络的一些特性,可用于routing应用[35]。…

上述的NSW算法使用一个更简单的,之前未知的navigable networks模型,允许分散化图构建,很适合任意空间的数据。[44]中建议,NSW network的机制可以作为大规模神经网络的navigability:相似的模型可以描述small brain networks的增长,而模型会预测在大规模神经网络中观察到的high-level features。然而,NSW模型也会得到在routing过程中polylog的搜索复杂度。

3.动机

提升NSW搜索复杂度的方式,可以通过routing process的分析来标识,它在[32,44]中被研究。routing可以被划分成两个阶段:“缩小(zoom-out)”和 “放大(zoom-in)”。greedy算法在”zoom-out”阶段从一个低degree node开始遍历graph,同时node的degree会增加,直到该node links length的特征半径达到距离该query的scale。在后者发生之前,一个node的平均degree可以相对较小,这会产生一个停留在很远的(distant)false local minimum上的递增概率。

你可以在NSW上避免上述问题,它从一个具有最大degree的node(好的candidates是那些插入到NSW结构中的first nodes)开启搜索,直接到该搜索的”zoom-in”阶段。测试表明,该setting中心会像起始点一样,实质增加成功在结构内路由的概率,并能在低维数据上提供更好的性能。然而,在单个greedy search上它仍只有一个多项式复杂度的扩展,对比起Hierarchical NSW它在高维数据上表现更差。

在NSW中一个single greedy search的多项式复杂度扩展(polylog scaling)的原因是:距离计算(distance computation)的总数,与greedy算法的平均数目和greedy path上nodes的平均度跳数乘积成比例。hops scales的平均数目是对数扩展的,而在greedy path上的平均degree也是对数扩展的,因为:

  • 1) greedy search趋向于遍历和网络增长相同的hubs
  • 2) hub connections的平均数目会随网络size的增加而对数增长

因而,我们会获得关于结果复杂度的一个总多项式依存。

Hierarchical NSW算法的思想是:将links根据它们的length scale分离到不同的layers上,接着以multilayer graph的形式进行search。在该case中,我们只需为每个element评估一个固定数目的connections(独立于networks size),从而允许一个log scalability。在这样的structure中,搜索会从upper layer开始(它具有最长的links)(即:“zoom-in”阶段)。该算法会贪婪地遍历upper layer中的elements,直到到达一个local minimum(见图1的演示)。接着,该search会切换到lower layer(它具有更短的links);然后从在前一layer上具有local minimum的element进行restart,并重复该过程。在所有layers中的每个element上的connections的最大数目是常量,这样可以允许在NSW网络路由中进行一个log scaling复杂度。

图片名称

图1 HNSW思想的图解。search会从top layer的一个element开始(红色部分)。红色箭头表示greedy算法的方向,从entry point到该query(绿色部分)

生成这样一个分层结构(layered structure)的一种方式是:通过引入layers,使用不同length scales来显式设置links。对于每一个element,我们会选择一个整数level l:它定义了该element所属layer的最大layer。对于在一个layer中的所有elements,会增量构建一个邻近图(proximity graph)(例如:graph只包含”short” links,它近似于Delaunay graph)。如果我们设置一个关于l的指数衰减概率(例如:根据一个几何分布),我们会获得在该structure中layers的期望数目的一个log scaling。该search过程是一个迭代式greedy search:它从top layer开始,在zero layer完成。

当我们合并来自所有layers的connections时,该structure变得与NSW graph相似(在该case中,可以被放置的l相当于在NSW中的node degree)。对比NSW,HNSW构建算法不需要在插入前进行shuffle——因为它的随机化(stochasticity)可以使用level randomization来达到,从而真正允许增量索引(incremental indexing),即使数据分布随时间变化(尽管插入顺序的轻微变更会影响效果,这是因为只有部分determenistic construction过程)。

HNSW的思想与著名的1D概率跳表结构非常相似,可以使用它的术语进行描述。与skip list的主要不同是:我们可以通过使用proximity graphs替代linked list来生成结构。HNSW方法可以使用相同的方式来做出分布式近似搜索/重叠结构(distributed approximate search/overlay structures)。

对于element insertion期间邻近图的connections的选择,我们会利用一个启发法:它会考虑上候选elements间的距离,来创建不同的(diverse)connections(在SA-tree中使用相似的算法来选择tree children),而非只选择最近的neighbors。该启发法会从nearest element开始检查candidates(相对于插入的element);只有当该candidate比base element(已插入)更接近时(对比起任意已经连接的candidates),会创建到该candidatate的一个connection(详见第4节)。

当候选数目足够大时,该启发法允许获得exact relative neighborhood graph(精准的亲属邻居图)作为一个subgraph,通过只使用nodes间的距离来得到Delaunay graph的一个最小subgraph。relative neighborhood graph很轻易地保持全局连接的component,即使在高度聚类数据中(见图2)。注意,对比起exact relative neighborhood graph,启发法会创建额外edges,允许控制connections数目,这对于搜索性能很重要。对于1D数据的case,通过只使用与elements间距离相关的信息,启发法允许获得exact Delaunay subgraph,这使得从HNSW到1D probalilistic skip list算法有一个直接转换。

图片名称

图2 为两个孤立clusters选择graph heighbors所使用的heuristic启发法。一个新的element会被插入到Cluster 1的边界上。该element的所有最近邻都会属于Cluster 1, 从而忽略在clusters间的Delaunay graph的edges。当插入的element最接近时,对比起Cluster 1的其它element,该heuristic会从Cluster 2选择element ,来保持全局连通

HNSW proximity graph的基础变种也在[18]中被使用,对于proximity graph searching被称为“sparse neighborhood graph”。相似的启发法也是FANNG算法的一个关注点。

4.算法描述

网络构建算法(算法1)通过连续插入存储的elements到graph结构中来进行组织。对于每个插入的element,会随机选中一个integer maximum layer l,并使用一个指数衰减概率分布(通过参数归一化,详见算法1的第4行)。(说明:element更容易落到较高level上)

图片名称

算法1:

input:

  • hnsw: multilayer graph
  • q: 新的element
  • M: 已确立的connections数目
  • :每个payer上每个element的最大connections数目
  • efConstruction:动态候选列表(danamic candidate list)的size
  • :level generation的归一化因子

输出:

  • 插入element q更新后的hnsw

整个插入过程如下:

  • 1.插入过程的第一阶段:从top layer开始,并贪婪地遍历该graph,以便在该layer上找到与插入的element q最近的ef个neighbors
  • 2.之后,该算法从下一layer继续搜索,使用从前一layer已发现最近的neighbors作为enter points,重复该过程。

在每个layer中,最近的neighbors会被算法2(greedy search算法的一个变种,它是[26]算法的一个更新版本)所发现。为了在一些layer 上获得近似的ef个最近的neighbors,会在搜索期间维护一个关于ef个已发现最近的elements(在enter points初始填充)动态列表W。该list会在每个step被更新:通过评估在list中之前未评估的最近的element的neighborhood,直到list中的每个element的neighborhood被评估。对比起限制distance计算的数目,HNSW的停止条件具有一个优点——它允许抛弃用于评估的candidates,从而避免搜索结构的膨胀。正如在NSW中,该list会通过两个优先级队列进行仿真来追求更好性能。与NSW的区别在于:

  • 1)enter point是一个固定参数
  • 2) 作为更换multi-searches的数目的替代,搜索质量会通过一个不同参数ef来搜索(它在NSW中被设为K)

图片名称

算法2

在搜索的第一阶段,ef参数被设置为1(简单贪婪搜索),以避免引入额外参数。

当搜索达到layer no.<=l的layer时,构建算法的第二阶段会被初始化。第二阶段在两点上有不同:

  • 1) ef参数会从1增加到efConstruction,以便控制greedy search过程的recall
  • 2) 在每一layer上,已发现的最近的neighbors也会被作为candidates,用于inserted element的connections

图片名称

算法3

从candidates中选择M个neighbors有两个方法可以考虑:

  • 简单法:到最接近的elements的简单连接(算法3),
  • 启发法:会考虑上candidate elements间距离,用来创建不同方向(diverse directions)的连接(算法4)。如第3节

图片名称

算法4

该heuristic具有两个额外参数:

  • extendCandidates:(缺省为false),它会扩展candidate set,只对极度聚集的数据有用
  • keepPrunedConnections:允许每个element具有固定数目的connection

当被插入的elements的connections在zero layer被确立时,插入过程终止。

在HNSW中所使用的这种K-ANNS search算法如算法5所示。它大致等价于对于layer l=0的一个item的插入算法。不同之处是,在ground layer发现的最接近的neighbors(被当成candidates用于connections)会随搜索结果返回。搜索质量通过ef参数控制(对应于construction算法的efConstruction)。

图片名称

算法5

4.1 construction参数的影响

construction参数会负责维护在所构建graphs的small world navigability。将设置为0、并且将设置为M会生成directed k-NN graphs,它具有幂律(power-law)的搜索复杂度。将设置为0、并且将设置为无穷大会导致生成NSW graphs,它具有polylog的复杂度。最终,将设置成非零值,会产生受控的hierarchy graphs,它通过引入layers允许log搜索复杂度。

为了达到最优的效果,不同layers上的neighbors间的overlap必须很小。为了减小overlap,我们必须减小。然而,同时,减小会产生在每层上的greedy search的平均hop数的增加,这会对效果产生负面影响。这会导致参数最优值的存在。

关于最优的,一种简单选择是1/ln(M),这对应于skip list参数,层间的overlap具有一个平均single element。在Intel Core i& 5930K CPU上模拟得到,的选择是个合理选项(见图3,在10M随机数据, d=4的vectors)。另外,该图展示了使用选择connections的heuristic,在低维数据上,当将从0开始增加时会有一个大的加速,

4.2 复杂度分析

5.性能评估

HNSW算法通过nmslib c++实现,它是一个功能性NSW实现。由于该library的限制,为了达到一个更好的性能,HNSW实现使用定制的距离函数以及C-style的内存管理,这避免了不必要的隐式寻址,并允许在图遍历时进行高效的硬件/软件prefetching。

5.1 与base NSW的对比

5.2 欧氏空间中的对比

5.3 在general spaces上的对比

5.4 使用PQ的对比

参考

https://arxiv.org/pdf/1603.09320.pdf

PAL position bias介绍

华为在《PAL: a position-bias aware learning framework for CTR prediction in live recommender systems》提出了一种解决position-bias方法。# 摘要在推荐系统中精准预测CTR...… Continue reading

facebook DLRM介绍

Published on November 01, 2019

feedback loops介绍

Published on October 28, 2019