2019VLDB-(淘宝的图像搜索算法)Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph

标题：基于导向型的向外传播的图进行快速近似最近邻搜索
本文作者来自浙江大学和阿里巴巴，据作者在文中写道：本文的NSG算法已经在淘宝的电商场景中，被整合进10亿级别的搜索引擎。
图像通过特征抽取，实际上以高维向量表示，如SIFT,GIFT等表示法，因此图像搜索算法，就是高维向量的（近似）最近邻搜索。
代码地址：https://github.com/ZJULearning/nsg

编者的总结和思考：

本文的亮点第一个是（隐晦地）引入了角度问题（60°），完成了图的多方向扩展，也就是基于MSNET图设计了MRNG图，虽然这个在之前有DPG做思路导引，但是这是第一次做完善。
第二个重要的贡献是为graph-based ANNS提供了理论保障，虽然是在理想情况下，比如严格的 MRNG, NNG就都是MSNET（单调图），通过现在的贪心搜索算法，可以在一定步数之内，达到另一个点。（文中原话：图中任意两点一定存在一条（严格）递增路径，这条递增路径可以由贪心算法得到。）虽然：a) 事实上目前所有的graph-based ANNS都是对于基本图的一种近似；b) 对于路径长度上界的推导基于均匀分布的数据但是这个理论保障提供了一个重要的优化方向。
第三个亮点是固定入口导航点，之前的工作中，入口点到底怎么选是一个很重要的问题，HNSW，FANNG等工作都在这里做过工作；在NSG中，固定了一个接近于质心的点做入口点（即导航点），在构建时，直接考虑从导航点直接搜过去，然后把路径上的边作为候选集进行赋边（有长有短）。
第四个点（弥补策略）是从导航点开始做一棵最小生成树来保证连通性。起因在于节点的出度有限制，这样就不能保证NSG的导航点（和某些密集区域）有足够的连通度。为了保证最起码的可导航性，做了一颗DFS树来补边，但其实又可能超过了出度限制，这一点在glove, wordvec数据集上体现非常明显。
编者认为，NSG给予唯一的导航点过大压力，入口单一，又是从这个入口开始建图的，直接影响图索引的形状，可能会让算法在不同的数据分布（数据集）上表现差异很大。
后面Wang et.al.证明了NSG的选边策略其实和HNSW的是等同的，但是二者对于边的候选集其实不一样：HNSW是在已经建了一部分的图上做贪心KNN搜索，获得候选集；NSG把KNN图的邻居，以及在已有图上做近似搜索找到的最近邻做候选集。
问题角度方面，考虑到了索引大小和构建速度，这也将这一问题引入了一个新方向（AI领域）。尽管如此，本文的超线性构建速度，相比于DB领域的构建速度，在大数据集上慢了几乎100倍，最后的实验数据也证明了这一点。那么在10亿级别的大数据上，该方法还不足够实用。2019年NIPS发表的一篇基于磁盘的方法，反而在这一点上做的更好：https://www.jianshu.com/p/07ed2202f107。
此外，方法仍然是memory-based（虽然比HNSW，FANNG之类的要节省很多），不是disk-based的，扩展性仍然存在问题，不可能把大数据集都放进内存。如果没有至强机器作为依托，这种算法就缺乏更通用的价值。

ABSTRACT

基于图的KNN算法虽然搜索速度快，效果好，但是索引的构建速度太慢了。
本文进一步提升了基于图的KNN算法的搜索效率，同时提升了可扩展性，可以达到10亿级别数据的索引构建，主要有4个层面：

确保图的连通性；
降低图的平均出度；
缩短搜索路径；
减少索引大小。

提出了两种图结构，一种称为MRNG(Monotonic Relative Neighborhood Graph，单调相关邻居图)，可以保证非常高的搜索效率；基于MRNG，设计了NSG（Navigating Spreading-out Graph，导向性的向外传播图），可以实现较低的索引构建复杂度。

1. INTRODUCTION

论文的背景介绍部分，2021年TPAMI期刊中写的更为详细，在我的博客中已有讲述：https://www.jianshu.com/p/029be522fa89。其中相关的方法的典型论文在本文集中大部分都有讲述。

有递增属性（在图中从起点到query的路径上每一个点都离query更近一些）的图包括MSNET图、泰森图等。有递增属性，但是递增的级别没有明确表示。

近期提出的RNG图，搜索复杂度是多重对数级别；
NSWN图，仅平均路径长度就是多重对数级别的；

更别说这些个索引的构建复杂度极高，至少也是 $O(n^2)$ 的，对大数据集来说没有实践意义。
【编者注：上面这部分举的例子年份都很早，都在10年以前，参考价值有限。】

既然完整构建这种递增属性图很困难，那么可以只构建近似的就可以了。很多工作就是这样做的。KNN图是泰森图的一种近似表示。

GNNS,IEH,Efanna算法就是基于KNN图来设计的；
NSW是基于NSWN的算法；
【编者注：实际上是基于狄洛尼图】
FANNG近似了RNG图；
HNSW本质上是一个大杂烩，结合了泰森图、NSWN和RNG图的优势。
【编者注：实际上基于狄洛尼图和RNG】

上述这些近似方法很多都是基于直觉在做，缺乏严格的理论支撑。为了做出提升，作者首先研究了近似KNN算法在图中是如何运行的。
无论图是何种形式的，搜索都是贪婪算法，类似A*-搜索。因此要想加速搜索，需要缩短搜索路径，同时减少图的出度。因此有了摘要中所说的4个层面。

IEH,Efanna,HNSW，或者用随机树，或者是多层图来加速，然而内存占用就会非常高，这也是不可接受的。【编者注：不仅引入了新的结构，数据也被复制了多次】

2. PRELIMINARIES

2.1 Problem Setting

2.2 Non-Graph-Based ANNS Methods

2.3 Graph-Based ANNS Methods

几乎和期刊中一模一样，具体内容在https://www.jianshu.com/p/029be522fa89。
补充一些期刊中没有的讨论内容：

Delauney图：
- Delauney图上的高维搜索复杂度非常高；
- Delauney图在高维上几乎是全连接的，使得搜索效率严重退化；
- KNN图是Delauney图的一种近似，构建速度仍然极慢。
- DPG算法基于KNN图做了角度的改良，然而降低了搜索效率，索引也变的更大。
Relative Neighborhood Graphs (RNG)：
- RNG的出度通常非常低，是一个和维数相关的常量；
- RNG没有递增属性，因此也就没有了搜索路径长度保证；
- MSNET是RNG的一个改良，有搜索长度保证，但是总构建复杂度是 $O(n^3)$ ，太高了；
- FANNG和HNSW采取了一些边选择策略降低了图的出度，但是也没有一些理论分析。
Navigable Small-World Networks：
- 基于小世界模型，度数和邻居均基于概率分布来赋予；
- 搜索路径是多重对数级别的（经验上来看）；
- 构建复杂度是O(n^2);
- NSW和HNSW均为近似NSW图。【在本文集中，有这两种方法的详细介绍】

3. ALGORITHMS AND ANALYSIS

3.1 Motivation

摘要中提到本文要从4个层面入手，改良基于图的算法。其中第一点：确保图的连通性，具体来说，如果起始位点不固定，图就必须是强连通的；如果固定，就要保证所有点都在起始点为根的DFS-Tree上。

3.2 Graph Monotonicity And Path Length

本文首先讨论有关Monotonic Search Networks (MSNET)的性质。

定义：MSNET的定义是一个有向图，在这个图上任意两点之间都存在一条递增路径（每一步都距离终点更近）。
- 这也就意味着，MSNET是一个强连通图，因为任两点之间都有一条路。
之前定义MSNET的文章认为，在此图中，用贪婪算法从一个点寻找到另一个点，不需要走“回头路”。“回头路”是说到达某一个local optimal之后，返回历史轨迹，然后调转一个方向。当时没有给出严格证明，本文给了一个严格证明，即用贪婪算法，不走“回头路”，就能找到一条递增路。
一个等价定义：MSNET还可以这样定义：对于一对点p,q，在以q为球心，pq为半径的球内，必然存在一个点r使得有向边pr是MSNET中的边。
- 证明：如果p的所有边都不指向球内，则p->q的路径必然不是一个递增路径，充分性得证。如果每一条边都可以往以q为球心的，半径更小的球上指向，则此指向路径，就是一个递增路径，必要性得证。
  
  image.png
路径长度：在数据随机分布，排除极端情况（直线分布）下，MSNET图任意两点的递增路径的长度为。d是维数，的定义比较复杂，看不出物理意义，当做是常量就可以了。
- 【证明略】。
- MSNET图的路径长度是有保障了，但是度数却没有任何保障。

3.3 Monotonic Relative Neighborhood Graph(MRNG)

本文提出一种新的MSNET图，称为MRNG。

HNSW和FANNG为了使图稀疏一些都转而使用RNG，然而RNG并不足够称为MSNET。RNG出度有保障，但是路径长度没保障（因为不一定是递增路）。
RNG图的定义：在RNG图（无向图）中，对于任意边pq，分别以p和q为球心，pq为半径画球相交得到一个月牙形状的空间 $lune_{pq}$ ，这个空间里不能有其它点。如下图a。下面这个例子p->q就没有增长路径。

image.png

作者发现问题在于RNG的赋边策略。受此启发，作者设计了图结构叫做MRNG（Monotonic Relative Neighborhood Graph）。

MRNG：MRNG是一个有向图，对于图中任意一个有向边pq，不能有另一个点，使得有向边pr也是图中的边。反过来定义，如果中没有其它点和p相连了，pq这条有向边就要连起来。
- 这相当于泛化了RNG的定义。RNG彻底不允许 $lune_{pq}$ 中有点，MRNG允许，只不过不能和p相连。如上图3，MRNG有更多的边，且设计为有向边。
MRNG最好的一点是：它是一个MSNET图，虽然不是最小的吧，但是也足够稀疏。这意味着图上的任意两点，greedy algorithm可以通过递增路径找到。
- 因为一个点的两条出边夹角必然大于60°，因为lune是两个等边三角形拼成的。
- 这也就暗示我们，构造MRNG图，要从近距离到远距离为某一点选边，否则容易白选（被短边替换掉）【编者注：正如HNSW的做法那样】。
NNG定义：NNG是一个有向图，对于每个点，只有一条出边，指向1NN。
- 显然，无论是MRNG，还是RNG，必然都包含NNG。因为最短距离为中心的lune肯定不包含其他点，否则就不是最短距离。
- MRNG包含NNG，是非常重要的性质，否则即使按照选择策略，也非常容易构造出非递增路径。
MRNG度数性质：MRNG中节点的最大度数是个常量。
- 有数学定理可以证明，对于有限维空间 $E^d$ ，固定一个顶点，可以通过有限个圆锥覆盖整个空间。圆锥个数只和d有关。

到此为止，我们可以确定，MRNG的搜索总复杂度，是近似对数的 $O(cn^{1/d}logn/\Delta r)$ 。

3.4 MRNG Construction

虽然搜索性质如此漂亮，但是构建代价不容乐观。
构建从完全图开始剪枝选边。对于每个点p，和各个其他点的距离都要算一次，并排序，排好序，该列表表示为R。首先将距离p最近的点加入到邻居集L中。然后每次从R中取一个点r，如果r和L中任意一个点l构成的三角形prl,pr不是最长的那条边，就把r放进L里。
- 可以通过几何证明这构造的是MRNG图。
- 由于距离计算，排序，验证，最终复杂度为 $O(n^2+n^2logn+n^2c)$ ，c是平均出度。尽管这比之前的MSNET图构建要好半个量级，但还是无法实际应用的。

3.5 NSG:Practical Approximation For MRNG

既然精确的MRNG构建太复杂，那么就考虑构造一个近似的。引出本文的索引方法NSG（Navigating Spreading-out Graph）。

3.5.1 NSG构建过程

首先构造一个近似KNN图；
寻找质心点：
- 首先计算整个数据集的中心位置；
- 然后把这个位置当做query，在KNN图上找到和它（近似）最近的点，作为导航点；
- 之后这个导航点就作为所有查询的入口点。
为每个点p赋边：
- 把p作为query，从导航点开始，在KNN图上做贪婪搜索，路径上的点都作为备选集；
- 从备选集中选择至多m个点，选择策略即MRNG选择策略。
构建DFS树：
- 以导航点为根，做DFS，形成DFS树，如果有节点在DFS结束之后仍然没有在树中，则补充边，将它们链接到近似最近邻上（贪婪算法）。

3.5.2 Motivations

MRNG要求任两点之间都有递增路径，这太严格了。在NSG中，我们只尝试从导航点开始，到任何点都有递增路径。搜索时我们也从导航点开始，这样搜索的复杂度不变，但是构建复杂度大大降低了。
赋边时候候选集太大了。相反，NSG的候选集非常小，只包含两部分：
- kNN：上面我们提到过，NNG在MRNG中的作用非常大，必须包含。但是找精确的NNG太麻烦了，因此就用近似的kNN图来代替。作者解释，稍微拆一点应该没关系。
- 搜索路径：因为NSG的搜索就是从导航点开始的，因此我们构建时就把p当做Query，从导航点开始找搜索路径做候选集。这样能更加逼近真实情况。
NSG的构建方法可能导致导航点和密集区域点的出度爆炸问题。因此在构建过程中强制限制为一个超参m。但是连通度又成了问题。为了保证至少从导航点开始是连通的，构建DFS树来解决这个问题。
- 但是，可想而知，此时搜索路径必然会相对长一些。
  【编者注：有种最小生成树的感觉】

到此为止，我们回顾摘要了提到的四个层面：

确保图的连通性：DFS树
降低图的平均出度：m超参
缩短搜索路径：NSG可近似MRNG
减少索引大小：仅仅一个稀疏图

就都可以有一个解决方案。

3.5.3 Indexing Complexity of NSG

构建索引的复杂度包含两部分，KNN图的构建和NSG图构建。
KNN图的构建可以用nn-descent（小图，复杂度 $O(n^{1.16})$ ），Faiss（大图，复杂度 $O(nlogn)$ ），不在本文讨论范围内，复杂度称f(n)
由于KNN图是泰森图的近似，泰森图也是一种MSNET图，所以搜索复杂度 $O(kn^{1/d}logn/\Delta r)$ 。

由于对所有点都做了一次搜索，所以复杂度为 $O(kn^{1+d/d}logn/\Delta r)$ ；
候选集选择是非常快的， $O(nlm)$ ，l是候选集大小，这个候选集只有路径上的点，不会很大；
DFS树的构建基本也是线性的。

因此总的复杂度为 $O(kn^{1+d/d}logn/\Delta r+f(n))$ 。基本上是超线性的一个水平。
这里的d不是维数了，可以理解为一个常量，这个复杂度也是从具体的数据集和实验里模拟出来的，并不是数学推导而来，详细过程见下图：

image.png

3.6 Search On NSG

搜索就是从导航点开始，贪婪搜索，因为是MRNG近似，所以搜素复杂度也近似为对数级别。

4. EXPERIMENTS

4.1 Million-Scale ANNS

1M的数据集机器配置：i7-4790K CPU and 32GB memory.
5M的数据集机器配置：Xeon E5-2630 CPU and 96GB memory.

数据集为：