2018TPAMI-(HNSW索引算法)Efficient an

2021-07-19 本文已影响0人 Caucher

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

编者的总结

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

编者的思考

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

1 INTRODUCTION

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

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

3 MOTIVATION

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

3.1 NSW中的缩小与放大

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

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

image.png

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

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

复杂性分析：一次贪婪搜索中距离计算的次数和两个值的乘积成正比。一个值是平均跳数（即经过了多少节点达到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个最优的邻居，建立双向连接。
第三步：注意到，由于新插入的节点会给其邻居多带来一条边，有可能导致这些邻居的度数溢出了超过 $M_{max}$ ，因此对于这些溢出的邻居，需要再次调用邻居选择算法，选择一次合适的邻居，某些不合适做邻居的边将会被删除。
另外，如果l比最大层L还要更大，那么就把当前这个q作为HNSW的enter point。

image.png

4.1 Inﬂuence of the Construction Parameters

$m_L$ 和 $M_{max0}$ 是能深刻影响图的导向性小世界特性的。

$m_L=0$ ， $M_{max0}=M$ ，如果采用算法3选择邻居，最终得到的就是KNN图；
$m_L=0$ ， $M_{max0}=\inf$ ，就是普通的NSW图。

$m_L$ 的选取是一个trade-off：

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

$M_{max0}$ 的选取是一个trade-off：

选的太大，内存占用太多，路径方向也会变多，降低搜索性能；
选的太小，容易导致进入错误方向，构建时也会频繁换邻居，降低性能。

image.png

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

image.png

4.2 Complexity Analysis

4.2.1 Search Complexity

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

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