论文阅读：NSG

# 作者的动机

作者的动机有 4 个：

（1）保证 graph 的连通性。

（2）降低 graph 的平均出度

（3）使得搜索 path 长度尽可能短。

（4）降低索引的尺寸。

# 贪婪算法

首先介绍一下贪婪算法，很多算法比如 HNSW 的查询方法就是使用了贪婪算法。那么它是如何实现需要最近 K 邻的呢？对于给定的查询 q，以及起始点 p（这个起始点也叫 seed）。

1）首先，把 p 放入候选池 S 中，侯选池的尺寸是固定的为 l。

2）第二步，从侯选池中找到没有 check 过的节点（为什么要没有 check 过呢，因为砍掉重复路径）

3）如果发现侯选池中都已经 check 过了，说明已经没法找到更近 q 的节点了。注意筛选条件放到了 S 的 resize 哪里。直接把 neighbors 放入侯选池，抛弃掉比 q 远的节点。

# 提高 ANNS 的性能

提高 ANNS 性能可以从四个方面进行考虑，1）保证图的连通性。2）更低的平均出度。3）减少查询路径长度。4）降低索引的尺寸。

ANNS 的查询性能实际上就是（step 次数）* （每次比较 distance 的次数）。

# 基于图 ANNS 算法

# Delaunay Graphs

这里有一篇文章，写的很好：

基于 Delaunay 图的快速最大内积搜索算法 - 张雨石的文章 - 知乎 https://zhuanlan.zhihu.com/p/133526632

首先，定义沃罗诺伊块 (Voronoi cell):

每个沃若罗块内的坐标点离决定沃若罗块的 element 的距离比离其他 element 的距离是最近的。这是沃若罗块的性质。

如果把相邻沃若罗块的 element 相连接就形成了 DG 图。DG 图是一个单调图，这里有一篇文章解释了为什么 DG 图是单调图：

https://whenever5225.github.io/2021/03/12/proximity-graph-monotonicity/

DG 图实际上性能很差，因为 DG 图在高维情况下很容易变成全连接。

# MRNG（全华班怎么说

RNG 就是 Relative Neighborhood Graphs

RNG 并不是单调搜索网络（MSNET，Monotonous Search Network），因此需要在 RND 中加入额外边，这种图这叫做 minimal MSNET。

FANNG 和 HNSW 都采用了 RND 的边选择策略。

# 关于单调搜索图的定义

# 单调路径

如果 q 和 p 之间的一条路径，并且这个路径满足 $dis(v_i, q) > dis(v_{i+1} , q)$ ，那么说明这是一个单调路径。

# 单调搜索图

当且仅当图 G 中任意两个节点之间都存在一条单调路径，那么说明这是一个 MSNET。

# 定理以及证明

# 定理一

# 定义

在 MSNET 的使用算法一，也就是非回溯的贪婪算法，那么通过这个算法找到 q 和 p 之间的路径，一定是一条单调路径。

# 证明

对于 t 次迭代，如果满足这个$\forall i \in\{1, \ldots, t-1\}, \delta\left(v_{i}, q\right)>\delta\left(v_{i+1}, q\right)$ 条件，那么说明找到的路径就是一条单调路径。通过数学归纳法进行证明。

1）如果 t=1，因为 MSNET 的定义就是任意两个点都能够找到一个单调路径，所以对于 p 和 q 两个点（v1=p）。存在一个路径 $v_1 \rightarrow r \rightarrow q$，这个路径是单调路径有 $dis(v_1, q) \geq dis(r, q)$。那么 r 一定是 v1 的邻居节点，因为算法是一个非回溯贪心算法，v2 一定是选择最接近 q 的 v1 邻居节点（这是算法的定义）。那么就有 $dis(v_2,q) \leq dis(r,q) \leq dis(v1, q)$ ，即说明了 t=1 时，非回溯贪心算法找到的是单调路径。

2）假设 t = m 时，$v_1, \dots , v_m$ 是一条单调路径。当 t = m+1 时，我们按照 t=1 进行分析，于是可以得出结论 t=m+1 也是单调路径。

# 定理二

定理二指出，对于 MSNET，任意两点之间的路径长度为$O\left(n^{1 / d} \log \left(n^{1 / d}\right) / \Delta r\right)$，d 是样本的维度，$\Delta r$ 随着样本 n 的增大非常缓慢地减小。

# 索引构建算法

这个构建索引但是看挺惊艳的，但是现在一看其实和 HNSW 的边选择策略一样。

也是从构建类似 RNG 的角度出发，贪心搜索得到候选邻居（这里的候选邻居不再是 HNSW 中的 W，而是整个搜索中 visit 得到的 E），然后用 RNG 选边策略进行邻居选择。

最后在使用一个 tree build 算法，保证 root 节点到所有节点都是可寻的，也就是使得图强连通。每次检索 q 都是从 root 节点开始。

# 实验部分

作者说，因为不是每个算法都支持并行查询，所以只是用单线程来测试。

作者使用的对比算法：

数据集上索引构建耗时：

结果：

# 问题

为什么 NSG 在实际的使用中并没有 enable increment Index 功能？明明它可以使用查询插入的方法？

# 提供的启发

要减少搜索的时间，两个方向，一个是减少平均度，一个是查询的 step 长度。