论文简介

High Dimensional Similarity Search with Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility 是一篇发表于 JOURNAL OF IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2020 （TPAMI 2021）的期刊论文

@article{fu2021high,
title={High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility},
author={Fu, Cong and Wang, Changxu and Cai, Deng},
journal={IEEE Transactions on Pattern Analysis and Machine Intelligence},
volume={44},
number={8},
pages={4139–4150},
year={2021},
publisher={IEEE}
}

高维空间中的近似最近邻搜索（ANNS）在数据库和信息检索中至关重要。最近，人们对探索有效的基于图的索引来解决 ANNS 问题产生了浓厚的兴趣。其中，导航展开图（NSG）提供了精细的理论分析并实现了最先进的性能。然而，论文发现 NSG 存在一些局限性：1）当查询未在数据库中建立索引时，NSG 对最近邻搜索没有理论上的保证； 2）NSG太稀疏，损害了搜索性能。此外，NSG 还存在索引复杂性高的问题。为了解决上述问题，论文提出了卫星系统图（SSG）和实用的 NSSG 变体。具体来说，论文提出了一种新颖的修剪策略，从完整的图中生成 SSG。 SSG 定义了一个新的 MSNET 系列，其中每个节点的外边缘均匀分布在各个方向。图中的每个节点都与其邻域建立全方位的有效连接，由此论文得出了 SSG 对于索引和非索引查询的出色理论特性。论文可以使用超参数自适应地调整 SSG 的稀疏性，以优化搜索性能。此外，提出NSSG是为了降低大规模应用中SSG的索引复杂度。提供理论和广泛的实验分析来证明所提出的方法相对于现有代表性算法的优势。论文的代码已发布在 https://github.com/ZJULearning/SSG。

作者的知乎解读：https://zhuanlan.zhihu.com/p/100716181

内容

1、INTRODUCTION

论文首先介绍了 ANNS 和图近邻索引的背景，接着介绍了几种经典图 Monotonic Search Networks (MSNET) [30], Randomized Neighborhood Graph (RNG*) [22], and Monotonic Relative Neighborhood Graph (MRNG) [27] ，然后论文介绍了单调图的查询特性，并指出了三点 NSG 的重大问题：

1、NSG索引算法产生的图过于稀疏，这是其搜索性能的瓶颈

2、NSG 的理论属性源自未声明的假设，即查询在图中建立了索引。用人话来讲就是，没有被编制到索引中的数据，在查询时会严重影响搜索行为，也就是搜索的路径。

3、NSG选边的高时间复杂度限制了其可扩展性。即构建时间过长。

2、BACKGROUND

论文在这部分主要讲了一些基本概念：

From NNS to ANNS

Non-Graph Based Methods

Graph-Based Methods

对于这些比较简单的概念，这里就不过多赘述了。由于都是一个作者团队的论文，而且 NSSG 这篇论文是基于 NSG 这篇论文的后续研究，所以 NSSG 这篇论文的整体结构与 NSG非常相似，尤其是 INTRODUCTION 与 BACKGROUND 两章。

唯一有些差别的是， NSSG 这篇论文额外加了一小节 Closely Related Works, 主要补充了一些用到的图。

MSNET

RNG* and RNG*(S)

RNG*(S), MRNG and NSG

DPG

3、METHODOLOGY

3.1 Motivation

本小节主要描述了论文的优化动机：

1、图稀疏度对查询效率的影响”

如上图所示，图 a 是一个 NSG 图，而图 b 和 c 是在图 a 上添加了边的额外图。

从蓝色点查询红色点，图 a,b,c 分别需要 7,5,8 次距离计算。因此，过于稀疏 a 或者过于紧密 c 的图，都会导致搜索性能下降。

2、查询点的微小不同，可能会极大地影响查询过程的导航路径“

如上图，论文用查询点在不在数据集中来描述这个现象，但是我认为用查询点与最近节点的偏移量来描述更为合适。即使节点不在数据集中，也有可能走向相同的道路。如下图：

紫色的为我拟定的查询q，以单步最近的贪婪算法为路由算法，仍然会选择上上图a中的红色路径。

读了作者的知乎，发现他这么归类可能是从业务的发现来的。阿里的相邻近邻查询，query往往都不是数据集中的数据。而 NSG 可能存在比较大的退化问题，因此作者才会有优化的动机。

3.2 Satellite System Graph

首先论文再次重复了 MSNET 图的定义。也就是从任何一个点开始，到任何一个节点，都有至少一条单调路径。

接着论文描述了 Satellite System Graph （SSG）系统卫星图的定义，这是论文最有价值的地方：

首先要了解两个指标，即上图中标色的两个。

1、字面直译：

Cone(pq→ , α) 是一个圆锥，其中心为向量 pq ，圆锥的半顶角为 𝛼 。圆锥半角是圆锥素线与轴线之间的夹角,等于圆锥角的一半称为圆锥半角。

B(p, δ(p, q)) 表示一个以点 𝑝 为中心，半径为 𝛿(𝑝,𝑞) 的开放球体。

2、GPT 的回答：

上面两个解释其实都很难理解，用人话来讲，Cone 是在点 𝑝 为中心，半径为 pq 长的球体中，截取了以 𝑝 为顶点、 pq 为高的一个圆锥，这个圆锥对圆的覆盖率（或者说占圆球体积的大小）由夹角 𝛼 决定。为什么 pq 不是母线呢，原因是 母线 + 夹角 不能唯一确定一个圆锥，而且与论文所谓的稀疏性毫无关系。

接着论文来看一下 SSG 的定义：

看起来很抽象对吧。我翻译一下：

SSG 的第一条规定，也就是用粉红色标识的部分：对于一个边pq，画出边 pq 的圆锥和球体。首先用球体与整个已经被编制索引的数据集做交集，拿到在球体内部的所有节点。要注意，这个球体是以边的起点为中心，以终点为球面上的边，以此划定界限。拿到了球体内部的点集，也就是 B(p, δ(p, q)) ∩ S 这部分。

接着，论文再用圆锥在这个点集里做交集，看看有没有被圆锥定位到的点。由于 p 决定了圆锥的顶点， pq 决定了整个圆锥的高，角度 𝛼 这个常量决定了圆锥的大小，所以论文可以确定得到一个唯一的圆锥。圆锥与刚刚的点集如果有交集，也就是有节点落入了这个圆锥空间中，就说明论文目前的 pq 边不适合当作 p 的边加入到索引中（其实这里用一个反向圆锥说明更好，对于已经存在的边 p 某，如果论文想保障稀疏性，那就得要求 p 某 的圆锥区域内不能有新的边，否则就会出现多个同向边，降低导航效率。因此，如果 pq 的圆锥包含了 某点 ，就说明 pq 是一定会被 p 某 划定的圆锥包含，因此pq 不应该被加入到索引中）。

读到这里，我认为这个球体和圆锥交集的定义有问题：
1、给定一个直线和一个夹角，如果想唯一确定一个圆锥，那么只能是让直线为高，夹角为圆锥夹角。因此，如果想看是否已经存在有效边，那么直接检测圆锥与编制的数据集是否有交点即可
2、如果想检测半径为pq的范围内是否有交点，那么就不应该使用圆锥来二次划分，而是应该使用开放射线（同样以向量 pq 为方向）为母线的圆锥与球体的交集。

书面版本的定义前，论文其实提供了构建的思想：

对于任何 p ∈ S，论文按 δ(p,·) 的升序列出剩余点。S是已经构建好的索引。对于任意两条边 −pq→ 和 −pr→，如果 ∠rpq < α（超参数），将其视为“冲突”并丢弃较长的边。重复这个过程直到所有点都被修剪（Alg. 2，Fig. 3）。直观上，每个节点周围的边缘均匀分布，并像卫星一样保持近乎最小的邻域覆盖。如下图：

这是构建的伪代码：

值得注意的是，这里描述采用了两重暴力循环来计算最近邻。实际上，论文并没有采用暴力循环，而是采用 NN-descent 来构建近似K近邻图。

因此 SSG 有以下的性质：

总结一下就是：

1、 SSG 仍然保留了单调图的性质，因为 SSG 是在单调图的基础上设计优化思想的。

2、从任意点为起始点，查询任何 q ，时间复杂度一定。

3、对于不存在数据集中的查询 q , 每步单调的可能性由参数夹角 𝛼 决定。

论文读到这里懵了一会：

1、SSG 为什么能够保障单调性？只是把 K 近邻图做了裁剪，如何保障单调？

2、为什么角度在 30 以下反而能保障单调性，如果基于一个原本的单调图，不应该是百分百单调吗。这部分的原因可能是， NSSG 在构建是并不保证百分百的单调，如果唯一的单调路径与已存在的边冲突，那么单调路径仍然不会被添加进索引。邻域角度越大，冲突概率越高，角度越小，越难以冲突。至于为什么小于 30° 能保障百分百单调，还得后面再接着看。

4、NAVIGATING SATELLITE SYSTEM GRAPH

4.1 From SSG to NSSG

为了实际使用，论文的目标是提出一种实用的变体（称为导航 SSG），它既具有时间效率又具有空间效率。当然，SSG 的理论特性不适用于该变体，但通过适当的启发式，实际性能接近理论分析。

这里稍微解答了上面的疑惑，但是还是没能完全解决。

论文又做了比较实验：

论文在 sift10K1 数据集（10k 点，128 维）上设计了一个小型预实验，以展示图度与搜索路径长度之间的关系。比较中包括不同的 MSNET（MRNG 和不同的 SSG）。 MRNG是NSG工作中提出的理论图模型[27]。结果如表1所示。可以看到，虽然SSG上的平均搜索路径长度较小，但图的平均度太大。因此，搜索精确的 SSG 与 MRNG 相比没有优势。此外，论文在“截断”的 SSG 上进行了这项实验。截断的 SSG 是通过从精确的 SSG 中修剪边缘而获得的。例如，在本实验中，论文只保留 40 个最近邻居，并删除 SSG60° 中每个节点的较长边，以获得 SSG60° tr。论文发现它对搜索路径长度几乎没有影响，但图的稀疏性显着增加。换句话说，这说明了真正的 SSG 中的大多数长边对搜索路由的贡献很小。 “有效”边主要分布在每个节点周围的小邻域中。

对于一个近似 K 近邻图来说，长边的导航效果几乎没有。这与 NSW 图有很大的区别。

如果长边在 SSG 中“无用”，一开始就不需要访问它们。基于这一观察，可以通过以下步骤构建一个类似于 SSG 的低索引复杂度图：对于每个节点，1）生成有效覆盖近邻的候选邻居集； 2）通过与Alg2中相同SSG选边的策略选择该集合内的邻居。

步骤 1) 可以通过构建高质量的近似 K-NN 图来有效实现，可以轻松地获得每个节点的最近 k 个邻居。对于大多数现有的近似K-NN图构造算法来说，k(n)越小，速度越快。

对于k较小的K-NN图，可以通过检查邻居的邻居（2跳邻居）来扩展邻域覆盖范围以获得候选邻居集。足够的邻域覆盖是至关重要的，因为SSG边缘选择过程将拒绝候选集中的大多数节点，并且在选择之后，需要确保出边缘均匀分布在不同方向上以进行有效的搜索路由。

步骤 2) 与Alg2中的选择算法几乎相同，也就是 NSG 选边算法。不同于 Alg2 中对真实K近邻选择，步骤 2) 的选择是在每个节点和所有其余 n − 1 个节点之间的边上执行的。仅对步骤 1) 中的候选集进行选择。

考虑到步骤 1) 中的“邻居”可能不是邻域最有效的覆盖，提出反向邻居检查来细化图，这类似于[24]，[25]，[42]中使用的技术。动机是，对于两个节点 p 和 q，如果边 pq→ 在 p 的邻域中有效，则 qp→ 可能对节点 q 也有效。因此需要尝试将 qp→ 插入到 q 的邻居集中。如果 qp→ 与 q 的另一个出边冲突，则意味着在给定 α 的情况下，在该方向上已经存在有效边。

此外，采用[27]中的技术来确保图的连通性。具体来说，（随机）选择一些导航节点，并确保这些节点与所有其他节点的连接。与标准 SSG 不同， NSSG 不保证强连接。同时，将一般图转变为强连通图也非常耗时。相反，从数据集中随机选择一些导航节点，将它们视为根，并从中生成 DFS 树。这样，可以获得更加稳定的搜索性能。

上图是 NSSG 构图的算法伪代码。算法的不同部分我用不同颜色来标注。

1、构建 K 近似近邻图

2、绿色部分标识的代码，其实是用于处理 K 与 l 不同的情况。将每个节点最近的的 min(K, l) 个邻居，使用 NSG 选边策略进行筛选，把通过筛选的边建立到图 G 中。
这一步其实是从每个点 i 开始，选取其 K 近邻的一部分进行建边，创建一个 NSG 图。

3、粉色部分的代码，用于建立反向边。
针对刚刚拿到的由若干个 NSG 子图构成的大图 G。
再次针对每个节点，尝试将单向边转为双向边，同时还需要保障 NSG 特性，如果边太多了就裁剪掉冲突的更长的边。

4、蓝色部分的代码，用于 DFS 深度遍历，保障从多个入节点开始，能遍历到任何一个节点。

到这里，这篇论文的主要内容就读完了。 NSSG 的核心思想其实是做了一个角度优化，用于寻找在各个方向上更有代表性的邻居。这个思想在很多图结构上都有一定程度的意义，在不破坏原有原理的前提下（或者使用一些轻微的代价），都是可以考虑结合的。

5、EXPERIMENTS AND ANALYSIS

论文的实验部分主要从 索引效率、查询效率 方面进行。