导言
为什么需要向量相似性检索？前人已有很多优秀的回答：参考1，参考2，参考3。总之，向量检索是很多AI应用的一个基础模块，它是与AI领域的发展共荣共损的。近年来，学术界和工业界提出了很多优秀的算法以及后续优化来应对高维向量的检索问题，这些方法旨在为向量检索提供一个更好的解决方案。然而，无论从算法设计和优化还是从工业应用考虑，当前都迫切需要对这些代表性的方法进行统一实验评估和比较分析。
我们的工作面向上述需要，聚焦实现效率和精度最优权衡的近邻图索引。论文全文arXiv地址：这里（Researchgate地址：这里）。最近，该论文已被国际数据库顶级会议VLDB2021收录。论文综述了13种具有代表性相关算法，实验在大量数据集上执行。我们的贡献可总结如下：
- 基于图索引的特征给近邻图向量检索算法做了一个分类（便于梳理算法的发展脉络）；
- 根据算法的执行流程打破每一个算法为7个组件（更细粒度的划分，实现算法优化的更公平评估）；
- 大量的算法，大量的数据集，大量的实验（让结论更具说服力）；
- 算法推荐，优化导向，当前最优的算法，有希望的研究方向，一些挑战（类似tutorial？）。
综述论文的动机
在近邻图上是怎么做向量检索的呢？前人已有非常形象的解释：参考1，参考2。
目前在学术届和工业界经常提到的近邻图算法大概10多种，它们需要一个实验综述的原因可主要总结为以下几条：
- 这些算法缺乏一个合理的分类和比较分析。尽管已有很多近邻图算法，但它们的索引结构都可归结为4个经典的近邻图。从这个角度来看算法的话，我们可能会产生一种感觉：近邻图算法也不过这么点东西。举个例子，当前很多算法都涉及对相对邻域图（RNG）优化，比如HNSW，DPG，NGT，NSG，SPTAG。
- 很多论文评估近邻图算法是从“分子”角度（类比，二氧化硫和二氧化碳），我们发现这些算法有一个统一的“化学表达式”（类比，$A_{x}B$），它们还可再分为“原子”（类比，A, B），从“原子”角度分析产生了一些新发现。
- 对用于向量检索的近邻图算法而言，搜索效率和精度的权衡最受关注。然而，近邻图算法的其它特征（包括索引构建和搜索）也在间接影响着最终的搜索性能。在搜索性能逐渐达到瓶颈的情况下，索引构建效率，内存消耗等指标也越来越受重视。
- 一个算法的优越性并不是一成不变的，数据集的特征在其中起着至关重要的作用，想更全面的了解算法，数据集的多样性是必然。
近邻图算法综述
在分析近邻图向量检索算法之前，先给大家介绍4个经典的近邻图结构，不负责任的说，当前的近邻图向量检索算法的索引都逃不过这4个结构，即德劳内图（DG）、相对领域图（RNG）、K近邻图（KNNG）、最小生成树（MST）。相信大家通过图1可领会它们各自的特征以及之间的差异。
下面就基于图1中的4个近邻图结构来简单给大家理一下13个近邻图向量检索算法。为了避免翻译不尽如人意，算法名就直接用英文简称，然后也会给出算法的原论文链接，如果有比较好的或仅有的中文介绍的话，我也会放上链接。各算法之间更宏观的联系可参考论文中的表2和图3。
算法1：NSW（原文，中文介绍，代码）。NSW是对DG的近似，考虑到DG能确保从任意一个顶点出发通过贪婪路由获取精确的结果（即召回率为1）。NSW是一个无向图，这会导致某些顶点的出度激增（类似于“交通枢纽”），从论文的表11可知，NSW在某些数据集上的最大出度可达几十万。NSW通过增量插入式的构建，这确保了全局连通性（论文表4中可知，NSW的连通分量数均为1）。NSW具有小世界导航性质，在构建早期形成的边距离较远（“高速公路”），这将提升搜索效率，在构建后期形成的边距离较近，这将确保搜索精度。
算法2：HNSW（原文，中文介绍，代码）。HNSW在NSW的基础上有两个优化：一是层次化；二是选边策略。层次化很直观，不同距离范围的边通过层次呈现出来，这样可以在搜索时类似于跳表结构，效率更高。选边策略优化简单的说：如果要给某个顶点连接K个邻居的话，NSW选择K个距离最近的，而HNSW从大于K个最近的顶点里面选出更离散分布的邻居（详细：参考）。因此，HNSW是对DG和RNG（从选边策略考虑）的近似。
算法3：FANNG（原文）。FANNG的选边策略与HNSW是一样的（都是对RNG近似）。从发布时间上来说，FANNG是比HNSW更早提出的算法，不过当前得到普遍应用的是HNSW。可能的原因是：（1）FANNG的选边策略是在暴力构建的近邻图的基础上实现的，构建效率很低；（2）HNSW通过增量式构建且引入分层策略，构建和搜索效率都很高；（3）HNSW开源了代码，FANNG没有。
算法4：NGT（原文1，原文2，代码）。NGT是雅虎日本开源的向量检索库，核心算法是基于近邻图索引的。NGT在构建近邻图时类似于NSW，也是对DG的近似，后续有一些度调整优化，其中最有效的路径优化也是对RNG的近似（论文的附件B也给出了证明）。
算法5：SPTAG（原文1，原文2，原文3，中文介绍1，中文介绍2，代码，代码使用）。SPTAG是微软发布的向量检索库，它的构建过程基于分治策略，即迭代地划分数据集，然后在每个子集上构建近邻图，接着归并子图，最后通过邻域传播策略进一步优化近邻图。上述过程旨在构建一个尽可能精确的KNNG。在搜索时，SPTAG采用树索引和图索引交替执行的方案，即先从树上获取距查询较近的点作为在图上搜索的起始点执行路由，当陷入局部最优时继续从树索引上获取入口点，重复上述操作直至满足终止条件。
算法6：KGraph（原文，中文介绍，代码）。KGraph是对KNNG的近似，是一种面向一般度量空间的近邻图构建方案。基于邻居的邻居更可能是邻居的思想，KGraph能够快速构建一个高精度的KNNG。后续的很多算法（比如EFANNA，DPG，NSG，NSSG）都是在该算法的基础上的进一步优化。
算法7：EFANNA（原文，中文介绍，代码）。EFANNA是基于KGraph的优化。两者的差别主要体现在近邻图的初始化：KGraph是随机初始化一个近邻图，而EFANNA是通过KD树初始化一个更精确的近邻图。此外，在搜索时，EFANNA通过KD树获取入口点，而KGraph随机获取入口点。
算法8：IEH（原文）。类比EFANNA，IEH暴力构建一个精确的近邻图，在搜索时，它通过哈希表获取入口点。
算法9：DPG（原文，中文介绍，代码）。在KGraph的基础上，DPG考虑顶点的邻居分布多样性，避免彼此之间非常接近的邻居重复与目标顶点连边，最大化邻居之间的夹角（论文的附件4证明了DPG的选边策略也是对RNG的近似）。此外，DPG最终添加了反向边，是无向图，因此，它的最大出度也是非常高的（见论文附件表11）。
算法10：NSG（原文，中文介绍，代码）。NSG的设计思路与DPG几乎是一样的。在KGraph的基础上，NSG通过MRNG的选边策略考虑邻居分布的均匀性。NSG的论文中将MRNG的选边策略与HNSW的选边策略做了对比，例证了MRNG的优越性。本文在附件1证明了NSG的这种选边策略与HNSW选边策略的等价性。NSG的入口点是固定的，是与全局质心最近的顶点。此外，NSG通过DFS的方式强制从入口点至其它所有点都是可达的。
算法11：NSSG（原文，中文介绍，代码）。NSSG的设计思路与NSG、DPG几乎是一样的。在KGraph的基础上，NSSG通过SSG选边策略考虑邻居分布的多样性。NSSG认为，NSG过度裁边了（更低的平均出度，见论文表4），相比之下，SSG的裁边要松弛一些。NSG与NSSG另一个重要的差异是，NSG通过贪婪路由获取候选邻居，而NSSG通过邻居的1介拓展获取候选邻居，因此，NSSG的构建效率更高。
算法12：Vamana（原文，中文介绍）。简单总结一下Vamana：KGraph、HNSW和NSG三者的结合优化。在选边策略上，Vamana在HNSW（或NSG ）的基础上增加了一个调节参数$\alpha$，当$\alpha = 1$时，Vamana的选边策略即为HNSW的启发式选边。Vamana取不同的$\alpha$值执行了两遍选边。
算法13：HCNNG（原文，中文介绍）。HCNNG是目前为止唯一一个以MST为基本的构图策略的向量检索算法。它的构建过程是基于分治策略（类似SPTAG），在搜索时，HCNNG通过KD树获取入口点。
近邻图算法“原子”级分析
我们发现所有的近邻图算法遵循一个统一的处理流程框架，流程里面有几个公共的模块（如图2的C1–C7）。一个近邻图算法通过该流程“打破”之后，我们可以很容易了解该算法是如何设计组装的，这将给后续近邻图向量检索算法的设计带来很大的便利性。此外，我们也可固定其它模块完全相同，从而更公平地评估不同算法在某一模块实现上的性能差异。
下面以HNSW和NSG为例说明如何通过图2的流程框架分析算法，在此之前我们要先熟悉这两个算法的索引构建和搜索过程。
首先是HNSW，HNSW的构建策略是增量式的。因此，每插入一个数据点都要执行一遍C1–C3过程。
| 模块 | HNSW具体实现 |
|---|---|
| C1 | 生成新插入点所处的最大层；获取搜索入口点 |
| C2 | 新插入点作为查询点，从入口点开始，贪婪搜索，返回新插入点一定量最近邻作为邻居候选 |
| C3 | 启发式选边策略 |
| C4 | 无额外步骤，最高层中的顶点作为入口 |
| C5 | 无额外步骤，增量式构建已隐式确保连通性（启发式选边又一定程度破坏连通性） |
| C6 | 最高层的顶点作为入口 |
| C7 | 最佳优先搜索 |
下面是NSG的。
| 模块 | NSG具体实现 |
|---|---|
| C1 | NN-Descent初始化近邻图 |
| C2 | 顶点作为查询，贪婪搜索获取邻居候选 |
| C3 | MRNG选边策略 |
| C4 | 全局质心作为查询，贪婪搜索获取最近顶点作为入口 |
| C5 | 从入口开始，DFS确保连通性 |
| C6 | C4获取的入口 |
| C7 | 最佳优先搜索 |
由于HNSW的C3与NSG的C3是等价的，因此，从上面两个表格可知，HNSW与NSG这两个算法差别并不大。其实，论文涉及到的13种算法中很多算法之间都是很相似的，详见论文第4章。
实验和讨论
实验评估参考论文第5章。下面主要简单介绍一下根据实验观测结果的讨论。
一些推荐。NSG和NSSG普遍有最小的索引构建时间和索引尺寸，因此，它们适用于有大量数据频繁更新的场景；如果我们想要快速构建一个精确的KNNG（不仅用于向量检索），KGraph，EFANNA和DPG更适合；DPG和HCNNG有最小的平均搜索路径长度，因此，它们适合需要I/O的场景；对于较难数据集（LID值较高），HNSW，NSG，HCNNG适合；对于较简单数据集(LID值较低)，DPG，NSG，HCNNG和NSSG适合；NGT有更小的候选集尺寸，因此适用于GPU加速（考虑到GPU的内存限制）；当对内存消耗要求较高时，NSG和NSSG适合，因为它们内存占用更小。
算法设计向导。一个好的近邻图向量检索算法一般满足一下4个方面：（1）高的构建效率；（2）高的路由效率；（3）高的搜索精度；（4）低的内存负载。针对（1），我们不要在提升近邻图索引质量（一个顶点的邻居中真实的最近邻居所占的比例）花费太多的时间，因为最好的图质量不一定实现最佳搜索性能（结合论文中表4和图7，8）。针对（2），我们应当控制适当的平均出度，多样化邻居的分布，减少获取入口点的花费，优化路由策略，从而减少收敛到查询点的邻域所需的距离计算次数。针对（3），合理设计邻居的分布，确保连通性，从而提升对陷入局部最优的“抵抗力”。针对（4），优化邻居选择策略和路由策略，从而减小出度和候选集尺寸。
优化算法示例。基于上面的向导，我们组装了一个优化算法，该算法实现了当前最优的综合性能。
一些趋势。基于RNG的选边策略设计在当前近邻图向量检索算法的效率提升中起到了关键作用。在论文的评估中，唯一一个基于MST的算法HCNNG也表现出来很好的综合性能。在上述纯近邻图算法基础上，后续发展有三个主要方向：（1）硬件优化；（2）机器学习优化；（3）更高级的查询需求，比如结构化和非结构化混合查询。
一些挑战。（1）数据编码技术与图索引如何有机结合以解决近邻图向量检索算法高内存消耗问题；（2）硬件加速近邻图索引构建减少近邻图索引构建时间；（3）自适应算法选择。
