速度约为NSG的两倍？基于图的快速索引构建：RNN-Descent

论文链接：

https://dl.acm.org/doi/pdf/10.1145/3581783.3612290

本篇论文由东京大学的团队提出，发表于 ACM Multimedia 2023。

基于图的 ANNS 方法可分为两种类型。首先是基于细化的方法，这些方法首先构建一个初始图，然后利用算法对 K-NN 图进行细化，最终得到最终的图。然而，初始 K-NN 图的构建需要耗费大量时间。第二种是直接方法，它直接构建图索引，但构建一个高性能的图需要精确的神经网络。这两种方法共同的问题是索引构建时间较长。尽管许多研究人员致力于改善搜索过程中准确性和速度之间的平衡，但在加速索引构建方面的研究相对较少。

论文提出了一种迅速构建图索引的算法 Relative NN-Descent（RNN-Descent），结合了构建近似 k 最近邻图（K-NN图）的 NN-Descent 算法和选择有效搜索边的 RNG 策略算法。该算法不依赖于人工神经网络，能够直接构建基于图的索引。

该方法的贡献主要包括：

• 解决了图索引的快速构建问题。

• 同时解决了传统基于图的方法中基于细化的方法和直接的方法的问题。

• 实验证明 RNN-Descent 是最快的构建算法，其构建的索引具有与传统方法兼容的搜索性能。
  

NN-Descent 是一种快速构建近似 K-NN 图的算法。其基本思想是邻居的邻居很可能再次成为邻居。该算法首先通过随机初始化图来启动。然后，通过重复进行“join”步骤以发现新的邻居候选人，并通过重复进行“update”步骤从候选人中选择邻居。图1(a)展示了连接操作的示例。为提高速度，连接操作检查任意顶点周围的所有对，而不仅仅是检查相邻点的相邻点。在图1(a)中，顶点1、2和3是通过相邻点连接的邻居。因此，连接算法在每个顶点对（vi，vj）（1≤i<j≤3）之间添加一条双向边，如图1(a)所示。

图1 构造图索引的方法比较

RNG 策略是一种选择对神经网络有效的图边的方法。图1(b)显示了 RNG 策略的图像。RNG 策略减少边，使每个顶点的任意两个邻居满足以下不等式：

其中 𝛿(u, v) 是 u 和 v 之间的距离：

例如，图1(b)中的顶点1和顶点2不满足𝛿(u, v2) <𝛿(v2, v1) ，因此算法删除 u 到 v2 的边。从直观上看，当 v 和 w 彼此太接近时，v 和 w 之间很可能已经存在一条边。然后，如果有一条边从能从 u 到 v 或 w 的其中一个，那么另一个也是可到达的。

该方法的技术核心在于将 NN-Descent 和 RNG 策略两种算法融合。类似于 NN-Descent，RNN-Descent 通过逐步改进一个随机初始化的图来构建基于图的索引。RNN-Descent 的更新算法同时执行了 NN-Descent 派生的加边操作和基于 RNG 策略的去边操作。这一方法能够直接构建图，无需通过神经网络寻找相邻候选点。此外，提出的更新算法自然地确保了图的连通性，这对搜索性能至关重要。

首先，算法随机初始化图，后续循环中的每一步都逐步改进初始化的图形。然后使用领域更新算法更新边缘集2次，并且添加反向边防止图陷入次优状态。按照这个步骤执行，算法便会输出最终的图。

RNN-Descent 并不限制构造图的出度。相反，搜索算法限制了度数。该算法允许用户在不重构图的情况下改变最大输出度。最优度取决于数据集，但在构造之前很难知道。相比之下，该方法可以在搜索过程中动态确定最优出度。

该算法同时执行 NN-Descent 的邻域更新算法和 RNG 策略的边缘选择算法。图1清晰展示了该算法的工作原理。我们以一个顶点的邻居为例。Normal NN-Descent 在任意两个邻域之间都添加一条边。例如，在图1(a)中，NN-Descent 在1、2和3之间添加了双向边。然而，在每个邻居对之间添加边在构建基于图的索引时是无用的，因为一些边缘可能会被 RNG 等算法消除，正如传统的基于细化的方法所做的那样。 

因此，本文提出的方法引入了 RNG 策略的概念，只添加必要的边。根据 RNG 策略，由于𝛿(u,v2)>𝛿(v2,v1)的不等式存在，图1(b)中的边(u,v2)是不必要的。我们的方法在图1(c)中删除了多余的边(u,v2)，同时插入了适当的边(v2,v1)，即结合了 NN-Descent 和 RNG 策略。邻域更新算法也保持了图的连通性，这对提高神经网络的性能至关重要。例如，在图1(c)中，v2在更新算法之前和之后都可以到达。

图1 构造图索引的方法比较

更新算法的一个问题是，所构建的图很可能陷入局部最优状态，从而导致性能下降。这里的局部最优指的是所有邻居都满足 RNG 策略的条件，使得更新算法不再更新边。次优图的平均边缘距离较长，从而降低了搜索性能。 

为解决这一问题，论文提出在次优图上添加反向边的解决方案。通过添加一个不满足公式2的新边，更新算法得以重新启动。此外，由于图的反向边可能比随机选择的边更短，它们有助于将图收敛到一个更好的解。这一策略有效地避免了陷入次优状态，提高了搜索性能。

本实验测量了每种基于图的方法的构造时间和搜索性能。搜索精度指标是 Recall@1 (R@1)，其中R@1 是找到正确近邻的查询的百分比。论文还使用每秒查询次数(QPS)来衡量搜索速度。一般来说，神经网络方法在搜索过程中有指定的参数，这些参数控制着速度和精度之间的平衡。在改变搜索参数的同时，通过在平面上绘制 R@1 和 QPS 来评估每种方法。

实验结果表明，RNN-Descent 在保持与现有最先进方法相当的性能的同时，显著加速了索引构建过程。在 GIST1M 数据集上的实验显示，RNN-Descent 的索引构建速度约为 NSG 的两倍。此外，RNN-Descent 的搜索性能与 NSG 相当。总体而言，RNN-Descent 是一种快速且高效的图形近似最近邻搜索索引构建算法。