标题：使用分层导向性小世界图（HNSW）进行高效且稳定的最近邻搜索

编者的总结

1. 本文的核心贡献就是把NSW做成多层的，各层的节点个数是服从几何分布的，在理论和实验上，都将KNN的复杂度从降低到了。不仅在欧式空间中，一般的空间也适用本文的算法。
2. 从实验和之后的文章评估上来看，HNSW算法的效果和效率都非常棒，这一点是毋庸置疑的。

编者的思考

1. 本文的一大问题就是构建速度和内存占用都不太好，而且只能基于内存；
2. 第二大问题，就是参数很难调，各个参数之间存在着微妙的平衡，也有彼此的互相依赖，使用不当就会性能退化；
3. 第三大问题，是proximity graph类型算法的通病，只能对结果做概率性上的保证，这在实际使用中比较玄学；
4. 第四个问题是作者提出的，是不易分布式，不过这倒是有可能解决的。

1 INTRODUCTION

proximity graph的方法在受power-low法则制约，使得在低维或聚集数据时性能有退化。
本文的主要贡献如下：

1. 显式选择entry-point；
2. 根据尺度不同分隔链接；
3. 启发式方法选择邻居。

3 MOTIVATION

（编者注：这一章节作者是讲整体研究思路，讲的比较抽象，难以理解；编者对相关工作目前了解还不足够深入，只根据有限的论文阅读量，试图解读作者的思想，其中不对之处，欢迎读者在评论区讨论、指正）

3.1 NSW中的缩小与放大

作者调研发现，提升NSW系列算法的根本在路由，就是NN搜索到达local minimum的路径。这个路径可以分为两部分，缩小和放大。

• 缩小：参照下图，缩小是指路由从一个低度点开始（任一个enter point），游走这个图同时增长点的度数（是指路径上的别的点），直到当前节点的边的特征半径和节点与query之间的距离到达同一个级别。这里指的是到达那种中心节点（hub）。然而在到达中心节点之前，节点的度数都很小，很容易方向跑偏，走到一个local minimum就不再走了，这就导致结果质量很差。
• 问题避免：避免这个问题也很容易，就是直接选那种大度数的点（比如最开始插入的就不错），略过缩小过程，直接进入放大过程。实验也表明，初始enter points对结果质量影响非常大。

• 放大：放大是指从中心节点出来，进一步到小的局部节点上去，最终找到精确NN节点附近。

  
  
  image.png

3.2 普通贪心算法的复杂性分析

接下来，作者对这种贪心算法的复杂性进行分析，认为这是多项式对数级别的复杂度。

• 复杂性分析：一次贪婪搜索中距离计算的次数和两个值的乘积成正比。一个值是平均跳数（即经过了多少节点达到local minimum）；另一只是路径上的节点（即每一跳）的平均度数是多少。
  • 平均跳数是对数的，这个在我另一篇博客中讲解的论文已经通过实验证明了；
  • 平均度数也是对数的，作者基于两个事实给出结论：
    • 贪婪算法总是会在路径中经过一些hub（中心节点）；
    • 这些hub的平均度数也是对数的。

3.3 HNSW的思路

主要思路是将链接根据它们的长度不同放在不同的层级（各个层级有长度限制）上，每个层级一张近邻图（仍然是近似Delaunay图），搜多层图。
这样在搜每个层级的时候，每个节点的度数都有固定的常量上界，以此来实现对数复杂度。
在构建图的时候，节点的所在的最大层数是指数衰退的（几何分布），因此层数的期望是对数的。也因为这种随机性，所以输入的顺序，不显著影响图的构建。
在这样的结构上，首先从最上层开始搜，搜长边，但节点很少，然后逐层向下递进。下一层的enter point是上一层的local minimum。

3.4 插入节点邻居选择

邻居的选择其实就是插入哪些边。一般来说，我们找一轮近似KNN然后把指定数量最近的边当做邻居即可。但是为了避免聚簇现象导致的local minimum，会在邻居选择时，优先选择那些相比于和插入节点的距离，和插入节点的邻居距离更远的作为邻居，如图的e2，后面算法会详细描述。

image.png

4 ALGORITHM DESCRIPTION

4.1 单层搜索算法

这个算法和之前讲NSW索引算法时用到的算法基本一致，只不过不循环m次重复随机选enter point了，这里把enter point当做输入来看待。
算法的最终结果仍然是一个local minimum。
2013IS-(NSW索引算法)Approximate nearest neighbor algorithm based on navigable small world graphs

image.png

4.2 最佳邻居选择算法

这里是说，假设我们要新插入一个点x，在某一层，也找到了这一层x的KNN，但是这一层有其最大度数限制M，所以要从这一层的KNN中找到合适的几个点做邻居，建立链接。
作者提供了两种算法，第一种无比简单，直接把KNN中M个最近的点当做邻居。
另外一种算法是一个启发式的算法。启发式算法首先还是将KNN个邻居按照和x的距离进行递增排序，然后依次出队，假设当前出队的是节点A。最终的结果集合是R，初始化为空。

• 对于R中任意一个节点n，如果dist(A,n) < dist(A,x)，说明节点A和已有的结果集中的节点离的太近了，这样的节点会被丢弃，正如上文所说，要避免只有邻近的cluster被选中做邻居。

  • 【编者注：注意这样做虽然可以在一定程度上考虑分布，但是相比于标准RNG图仍有差距。标准RNG只规定dist(x,n)要么小于dist(A,x)，要么小于dist(A,n)；
  • 从几何意义上看，RNG描述的是以x,n为两个圆心的月牙形范围内，不能有其它的点；HNSW描述的是x,n连线的垂直平分线的n一侧，不能有其他的点；
  • 这个边剪枝规则和FANNG中的occlusion rule是非常相似的；FANNG的要求是RNG的下半个月牙不能有其它的点。

  • 我画了一个示意图来说明这个问题，各位不要嫌丑orz】

    
    
    image.png

• 如果R中的每个节点都和A离的比较远的话，A就可以进入R了。

算法有2个参数：

• extendCandidates：默认是不开启的。把KNN个Candidates的邻居也拉过来作为候选人，只在极度聚集化的数据中有效；
• keepPrunedConnections：这个是保证最后可以返回M个邻居。上述的算法可能淘汰太多候选人，为了保证最后能返回M个邻居，可以将那些被丢弃的节点中，距离x较近的节点再召回几个，作为邻居。

image.png

4.3 KNN搜索算法

在搜索最底层的第0层之前，每层都只返回1NN作为下一层的enter point。搜索第0层时，搜efNN作为备选结果，再从这ef个结果中选取K个最近的作为结果。
（编者注：这里ef-NN中选取K个最近的和直接去search KNN有什么不一样呢？举个例子，假设K=1，我们只找1NN。那么在Search的时候，如果令ef=1，它只会每次去找最近的邻居，沿着一个方向找到一个local minimum就到头了；但是如果ef=d，它就可能沿着更多方向，去寻找到更多local minimum，这样结果质量会更好。）
文中作者也讲到，ef是可以来控制结果质量的。

image.png

4.4 节点插入算法

有了以上的准备条件，我们就可以来看看插入具体是怎么做的。本文的图索引是逐个节点去插入的，因此只介绍一个单节点插入算法。
设新节点为q，我们按照几何分布（指数衰退概率），随机获得q的最大层数l。

• 第一步：从最大层L到 l+1层，我们从一个enter point开始，逐层去找一个local minimum，这个local minimum作为下一层的enter point。
• 第二步：从l层到0层，这(l+1)层我们要物理上把节点q插进去。每次我们找给定数量的local minimum，从中按邻居选择算法选择M个最优的邻居，建立双向连接。
• 第三步：注意到，由于新插入的节点会给其邻居多带来一条边，有可能导致这些邻居的度数溢出了超过，因此对于这些溢出的邻居，需要再次调用邻居选择算法，选择一次合适的邻居，某些不合适做邻居的边将会被删除。

• 另外，如果l比最大层L还要更大，那么就把当前这个q作为HNSW的enter point。

  
  
  image.png

4.1 Influence of the Construction Parameters

和是能深刻影响图的导向性小世界特性的。

• ，，如果采用算法3选择邻居，最终得到的就是KNN图；
• ，，就是普通的NSW图。

的选取是一个trade-off：

• 选的太大，各层之间同一节点邻居的overlap会很多，降低搜索性能；
• 选的太小，层数太少，每层搜索时的步数又会太多，降低搜索性能。
  
  image.png

的选取是一个trade-off：

• 选的太大，内存占用太多，路径方向也会变多，降低搜索性能；

• 选的太小，容易导致进入错误方向，构建时也会频繁换邻居，降低性能。

  
  
  image.png

启发式的邻居选择算法，在中低维数据，聚集性数据上有奇效，但是高维数据并不合适。

image.png

4.2 Complexity Analysis

4.2.1 Search Complexity

以下的分析基于是一个精确Delaunay图，虽然实际上构建的是一个近似Delaunay图。（后面作者做了个实验，简单推断了下，近似图的不准确性不太影响算法复杂度）

• 关键一点是要确保在每一层的搜索步数是常量。对于某一层节点，其同时属于上层节点的概率为。但是搜索的过程中，这样的节点一般不会碰到，因为如果碰到了，也应该早在上层就已经碰到过了。因此作者给出在第s步仍然不是目标节点的概率是。然后，每一层的步数期望就是。
  （编者注：这个式子我没有推出来，我根据概率分布推出的期望是，虽然也是常量，但是差了很多，希望有推导出来的朋友能在评论区指导一二。）
• 各层图中每个节点的度数都是上界，因此每一层都是常量的复杂度，仅和相关。而层数的期望是对数的（几何分布），因此最终复杂度也是对数的。

4.2.2 Construction Complexity

构建复杂度，相当于N个点依次做KNN搜索，所以复杂度为

5 COMPARISON TO STATE-OF-THE-ART

5.1 Comparison with Baseline NSW

这张图可以明显看出，二次方的曲线被换做了一次线性的scalability。

image.png

5.2&5.3 Comparison in Euclid Spaces & General Spaces

从这两张图上可以看出，在召回率和查询速度上，HNSW确实有独特的优势。

image.png

image.png

5.4 Comparison with Product Quantization Based Algorithms

从这张图可以看到HNSW的构建速度和内存使用都存在短板。

image.png