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最接近\(e_2\)时，对比起Cluster 1的其它element，该heuristic会从Cluster 2选择element \(e_2\)，来保持全局连通。
HNSW proximity graph的基础变种也在[18]中被使用，对于proximity graph searching被称为“sparse neighborhood graph”。相似的启发法也是FANNG算法的一个关注点。
4.算法描述
网络构建算法（算法1）通过连续插入存储的elements到graph结构中来进行组织。对于每个插入的element，会随机选中一个integer maximum layer l，并使用一个指数衰减概率分布（通过\(m_L\)参数归一化，详见算法1的第4行）。(说明：element更容易落到较高level上)
算法1:
input:
- hnsw: multilayer graph
- q: 新的element
- M: 已确立的connections数目
- \(M_{max}\)：每个payer上每个element的最大connections数目
- efConstruction：动态候选列表(danamic candidate list)的size
- \(m_L\)：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 \(l_c\)上获得近似的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参数\(m_L\)和\(M_{max()}\)会负责维护在所构建graphs的small world navigability。将\(m_L\)设置为0､并且将\(M_{max()}\)设置为M会生成directed k-NN graphs，它具有幂律（power-law）的搜索复杂度。将\(m_L\)设置为0､并且将\(M_{max()}\)设置为无穷大会导致生成NSW graphs，它具有polylog的复杂度。最终，将\(m_L\)设置成非零值，会产生受控的hierarchy graphs，它通过引入layers允许log搜索复杂度。
为了达到最优的效果，不同layers上的neighbors间的overlap必须很小。为了减小overlap，我们必须减小\(m_L\)。然而，同时，减小\(m_L\)会产生在每层上的greedy search的平均hop数的增加，这会对效果产生负面影响。这会导致\(m_L\)参数最优值的存在。
关于最优的\(m_L\)，一种简单选择是1/ln(M)，这对应于skip list参数\(p=1/M\)，层间的overlap具有一个平均single element。在Intel Core i& 5930K CPU上模拟得到，\(m_L\)的选择是个合理选项（见图3,在10M随机数据, d=4的vectors）。另外，该图展示了使用选择connections的heuristic，在低维数据上，当将\(m_L\)从0开始增加时会有一个大的加速，
4.2 复杂度分析
5.性能评估
HNSW算法通过nmslib c++实现，它是一个功能性NSW实现。由于该library的限制，为了达到一个更好的性能，HNSW实现使用定制的距离函数以及C-style的内存管理，这避免了不必要的隐式寻址，并允许在图遍历时进行高效的硬件／软件prefetching。