2021TPAMI-High Dimensional Simil

2021-08-20 本文已影响0人 Caucher

标题：用卫星系统图进行高维相似性搜索：效率、可扩展性和非索引查询的兼容性
本文作者来自浙江大学和阿里达摩院，解决的问题仍然是高维近似KNN。
算法代码：https://github.com/ZJULearning/SSG

编者的总结

本文的一个贡献是量化研究了模拟RNG时的角度问题，得出 $\leq30^o$ 时完全满足递增属性， $>30^o$ 但 $\leq60^o$ 时，虽然递增属性变成一个概率上的事情（度数越大，概率越低），但是也不会走回头路，只会走向local optimum
本文另一个贡献是发现了过多的长边对搜索性能的帮助其实不大，所以适当删除长边是可行的；
在图索引的构建方面，相比于NSG，有两个创新点：
1. 直接在KNN图上剪枝，即不需要做搜索，找到邻居和邻居的邻居做候选集，再根据角度和最大出度剪枝；
2. 找了一组导航点（而非一个），最后利用构造一组DFS生成树造long link，保证最低连通性，在对所有点赋边时则彻底不考虑连通性。
效果、效率，相较于NSG,HNSW有进一步提升（不过在Wang et.al.的benchmark中结果相反，说明方法鲁棒性不高）。

编者的思考

缺少磁盘版本的高效索引，作者在讨论中也提出了这个问题。但是解决方法绝不仅仅是把内存索引映射到磁盘那么简单，需要更精细的设计，正如之前的diskANN设计的那样，那时搜索的性能主要取决于IO。
索引时间太长，索引100M，96维的数据点，恐怕只有几十GB，耗时3个小时，同等水平的数据库方法，10分钟左右就可结束战斗，差距太大。
内存消耗太高，对于数据集再大一些，超过几十GB的大小，作者给出的解决方案就是升级机器，这间接说明了，该方法并无可扩展性。

Abstract

目前做近似KNN最好的方法是NSG，这种基于图的算法，仍然有一些缺陷：

当query没有被索引的情况下，是没有理论上的保证的；
过于稀疏影响搜索性能；
索引构建复杂度太大。

本文提出的SSG（Satellite System Graph），是MSNET的一个新家族。每个节点的出边分布在各个方向，因此导出了对于有索引/无索引query查询的理论性质。

1 INTRODUCTION

对于基于图的方法来说，连接节点的方式极大地影响了搜索的性能。
由于搜索是贪婪的，所以复杂度不好分析。但是由于每一步都可以使得途径的节点距离query更近（递增属性），使得理论上的复杂度较低。
本文是对2019年VLDB的淘宝高维KNN搜索算法（NSG）的改进版。
首先说上一版的问题：

NSG图过于稀疏，成为了搜索效果的瓶颈。之前使图更为稀疏是处于效率考虑，但是效果受到了影响。
如果query没有在图中被索引，效果差距会非常大，尽管对于基于树、PQ的、LSH的差距都没有很大。
赋边的复杂性限制了图的可扩展性。

2 BACKGROUND

2.2 From NNS to ANNS

作为基于图的算法，本文第一次提出 $\epsilon -NN$ 的问题定义，即寻找到的1NN距离不超过真实1NN距离的( $1+\epsilon$ )倍。
同时还定义了 $\epsilon-KNN$ 问题。

2.3 Non-Graph Based Methods

其他三大类方法，树、PQ、LSH，作者认为都不行。NSG那一篇已经解释了，基于图的方法可以搜索不到10%的点，同时达到同样的精度。

2.4 Graph-Based Methods

基于图算法的搜索性能可以归纳为 $ol$ ，o是节点最大出度，l是搜索路径长度。要想提升效率，就从这两方面着手，即稀疏图和缩短搜索路径。
HNSW通过多层来缩短路径；FANNG和HNSW都用RNG（Relative Neighborhood Graph）来稀疏图。
MRNG基于上述方法，将节点度数控制在一个上界之内，路径长度也被保证限制。NSG作为MRNG的变形，减少了索引构建的复杂度。
作者总结，NSG是目前最好的方法。

2.5 Closely Related Works

NSG和本文的SSG，都是基于MSNET来构建图的，主要源于其优良的理论性质。

2.5.1 MSNET

MSNET的优良性质，是其搜索过程中的递增性质。
NSG中证明了，基于MSNET的搜索，其复杂性为 $O(n^{1/d}logn/\Delta r)$ ，其中 $\Delta r$ 可以认为是常量。
最小MSNET图的构建前人也有方法，但是复杂度是高级别的多项式复杂度。

2.5.2 RNG(Randomized Neighborhood Graph) and RNG(S)

RNG*的搜索复杂度 $O(log^3n)$ ，然而空间复杂度，索引构建复杂度都极其高，维度较高时搜索复杂度也高。
RNG*(S)是其稀疏化的版本，尽管如此，也有着 $O(n^3)$ 的索引构建复杂度，没法用。
但这两个都被证明有递增性质。

2.5.3 RNG*(S), MRNG and NSG.

MRNG和RNG*(S)是类似地，只是拓展了理论，MRNG的构建复杂度也有 $O(n^2logn)$ ，因此NSG被提出。
NSG基于一个预先构建好的近似KNN图，然后从中通过“搜索-剪枝”选择一些边。搜索时固定起点，以单向路径通向query。

2.5.4 DPG

Diversiﬁed Proximity Graph (DPG)首次从KNN图中筛选一半的边，考虑到边的多向性和角度的定义，另外还构建了一个无向图。
【编者注：此篇具体讲解在博客另一篇：https://www.jianshu.com/p/2376873f6b4f】

2.5.5 Differences regarding this work

本文的SSG虽然也是MSNET图，但是并非最小的，相比之下更为稠密；
SSG的构建和RNG*的构建类似，都是将空间分解为若干圆锥，但是没有任何随机性；
SSG把角度的思想也引入到赋边过程中，而并非仅仅是边的长度。

3 METHODOLOGY

3.1 Motivation

稀疏图or稠密图：之前基于图的索引大多是从完全图或者KNN图经过边选择而生成的。一般来说他们都会使图更稀疏，来达成更高的搜索效率。而本文发现了对于给定数据集，有一个最佳节点度数才能达成最高搜索效率。
距离and角度：目前只有DPG那一篇考虑到了角度的问题，本文会继续同时考虑距离和角度，正如通信卫星那样（SSG名字的由来）。
有索引的query和无索引的query的区别问题。

3.2 Satellite System Graph

首先给出MSNET图的定义（70年代论文定义的）：
图中任意两点都要有一条路，这条路满足增长属性。（路径上每一点都和终点越来越近。）
已知SSG图是MSNET图，我们给出它的构造方式：
对于一个节点p，我们把p所有剩下的邻居按距离增序排序；对于p的任意两条出边，如果夹角大于 $\alpha$ ，移除长的那条边。按照此方法，对所有节点进行剪枝。
从直觉上来看，SSG图将是在每个节点周围分布均匀的，只剩下一个接近最小的邻居覆盖，类似于卫星。
下面我们给出SSG图的定义：
如下图，对于图中任一点p，和有向边pq，以pq为中轴， $\alpha$ 为顶角画圆锥（二维情况下是等腰三角形），再以p为球心，pq为半径画球（二维即圆），在圆锥和球的相交空间内，p不能指向任何点为边。 $0°<\alpha<=60°$ .
- 解释：如果在此空间内有点r，使得SSG图存在边pr，那么pq应该被删除，形成矛盾。
  
  image.png

关于SSG图有以下几个定理（证明略）：

SSG是MSNET图；
对于在欧式空间随机分布的数据集S，如果q∈S，则搜索复杂度为 $O(Dn^{1/d}log(n^{1/d})/\Delta r)$ ，D是图中节点度数的上界，d是数据维数。
接2.，如果q∉S，则搜索路径具备递增属性的概率为 $0.5+\epsilon$ 。如果 $\alpha<=30°$ ，则 $\epsilon=0.5$ 。

解释：

如果 $\alpha<=30°$ ，则无论q是否属于数据集，递增属性都存在；
如果 $60°>=\alpha>30°$ ，则仅当q属于数据集时，递增属性才存在；否则不存在。
仅当递增属性存在时，可以保证搜索复杂度是近似对数的。
即使是 $60°>=\alpha>30°$ 和q不属于数据集时，搜索路径也不会折返，只会向次最优化方向前进。
当q不属于数据集时，如果搜索到了某个p，发现和邻居的距离都比和q要远，那么此时就中止搜索。

讨论：

SSG图并非是唯一的，是随 $\alpha$ 而变的。
图的稀疏度和搜索路径长度是一对trade-off。 $\alpha$ 越大，图越稀疏。理论上甚至可以给每个节点赋予不同的 $\alpha$ 达成最优。
上述理论性质只针对1NN，本文对KNN没有做太多工作。

4 NAVIGATING SATELLITE SYSTEM GRAPH

4.1 From SSG to NSSG

上面我们讲到，SSG有优良的搜索性质，但是仍然有两个致命问题：

构建索引的时间比以往更长了，达到 $O(n^3)$ ；
图的度数也比以往更多了。

为了解决这个问题，作者做了一组预实验，结果如表中所示，其中AOD是平均出度，MOD是最大出度， $L_{index}$ 是索引过的query的搜索路径，另一个是没索引的。有tr下标的，表示的是限制了最大出度，删除较长的边。
从结果来看：

SSG虽然搜索路径略短一些，但是度数增加太多，搜索性能反而要下降；
如果删除了出度中较长的边，度数可以降低，搜索路径长度也不会太大。
- 这就间接证明了，长边在搜索过程中并不能贡献多少作用，删去一些影响不大。
  
  image.png

基于这个发现，我们就可以改良索引构建过程，使之减少对长边的访问。
具体的策略：

首先构建KNN图，把每个点在KNN图中的邻居，以及二跳邻居（邻居的邻居）作为候选集；
- 选择二跳邻居是为了让候选集在邻居覆盖上更丰富一点，包含更多的角度选择。
在候选集中以SSG的赋边策略进行选择；
为了进一步补充节点在邻居处的覆盖，在第2步赋边结束之后，尝试对有向边的反向边尝试进行赋边，但不能违背角度剪枝策略；
- 注意到如果只在KNN图中选邻居，那么很有可能选到的全是短边，这个Small World Model的属性是相矛盾的，因此下面补充长边。
随机选一组导航节点，为其赋边保证这组导航节点到其它所有节点的连通性。
- 搜索时的起点，设为距离query最近的导航节点。
  
  image.png

4.2 Analysis

性质丢失：NSSG虽然对SSG的搜索效率进行了改良，但要注意到，我们之前讨论的，关于SSG的相关性质，在NSSG中已经不复存在，NSSG最多也只是在实验中发现和SSG的性质是接近的。
复杂度分析：索引构建时间包含两方面，KNN图的构建，和赋边过程。KNN图构建不在本文考虑范围内。
- 赋边过程包括候选集生成： $O(nk^2)$ ，候选集排序： $O(nk^2logk^2)$ ，候选集剪枝： $O(dn(k^2+rk^2))$ ，r是最大出度，反向赋边过程最多是前三项的和，因此总的复杂度，仍然是线性的。至于导航节点的赋边，复杂度是 $O(nrv)$ ，v是导航节点个数。也就是说，本文提出的算法复杂度是线性的。
- 但是，KNN图的构建，复杂度可远远不是线性的。
- 在后续的实验中发现，NSSG的搜索复杂度接近 $O(n^{1/d}logn)$ ，接近于SSG的性质。
最差情况下，搜索要迭代很多次，但最终总是可以搜到的，因为导航节点是连通图中所有其他节点的。但是这个最差，可能要搜图中的全部节点了。这种最差情况，非常极端，实际使用中基本不会出现。

5 EXPERIMENTS AND ANALYSIS

Intel i9-7690XE至强CPU，128GB内存，还有4个1080Ti的GPU.
索引是用36个线程并行构建的。

6.1 Search Performance.

搜索速度和质量上都有提升。
【编者注：这里可能是搜前100个结果，是否包含1NN】

image.png

6.2 Indexing Performance.

比KNN-graph还要慢上一些。