相似性搜索，第 4 部分：分层导航小世界（HNSW）

欢迎大家来到IT世界,在知识的湖畔探索吧!

了解如何构建高效的多层图，以提高海量数据的搜索速度

维亚切斯拉夫-叶菲莫夫

13 分钟阅读

6 月 16 日

欢迎大家来到IT世界,在知识的湖畔探索吧!

相似性搜索是一个给定查询的问题，其目标是在所有数据库文档中找到与之最相似的文档。

导言

在数据科学中，相似性搜索经常出现在 NLP 领域、搜索引擎或推荐系统中，在这些领域中，需要为查询检索最相关的文档或项目。在海量数据中，提高搜索性能的方法多种多样。

分层导航小世界(HNSW) 是用于近似搜索近邻的最先进算法。HNSW 构建了优化的图结构，这使得它与本文系列前面讨论的其他方法截然不同。

HNSW 的主要思想是构建这样一种图，在这种图中，任何一对顶点之间的路径都可以用少量步骤遍历。

关于著名的 六次握手规则与此方法有关：

所有人之间的社会关系都在 6 个或更少的范围内。

在了解 HNSW 的内部工作原理之前，让我们先讨论一下跳过列表和可导航的小词–HNSW 实现中使用的重要数据结构。

跳过列表

跳过列表是一种概率数据结构，允许在排序列表中插入和搜索元素，平均耗时为 O(logn)。跳转列表由几层链表构成。最底层是包含所有元素的原始链表。越往上层，跳过的元素数量越多，从而减少了连接数。

在跳转列表中查找元素 20

对某个值的搜索过程从最高层开始，并将下一个元素与该值进行比较。如果该值小于或等于该元素，则算法进入下一个元素。否则，搜索程序会下降到连接更多的下一层，并重复相同的过程。最后，算法下降到最底层，找到所需的节点。

根据以下资料 维基百科跳转列表的主要参数 p 定义了一个元素在多个列表中出现的概率。如果一个元素出现在第 i 层，那么它出现在第 i + 1 层的概率等于 p（p 通常设置为 0.5 或 0.25）。平均而言，每个元素出现在 1 / (1 – p) 个列表中。

我们可以看到，这一过程比在链表中进行普通线性搜索要快得多。事实上，HNSW 继承了相同的理念，但它使用的不是链表，而是图。

可导航的小世界

可导航的小世界是一个搜索复杂度为多对数 T = O（logᵏn）的图，它使用贪婪路由。路由指的是搜索过程从低度顶点开始，以高度顶点结束。由于低度顶点的连接很少，算法可以在它们之间快速移动，有效地导航到最近的邻居可能所在的区域。然后，算法逐渐放大并切换到高度顶点，在该区域的顶点中寻找最近的邻居。

顶点有时也称为节点。

搜索

首先，搜索是通过选择一个入口点来进行的。为了确定算法下一个（或多个）移动的顶点，算法会计算查询向量到当前顶点邻近节点的距离，然后移动到最近的节点。当算法找不到比当前节点更接近查询的邻近节点时，就会终止搜索过程。该节点将作为对查询的响应返回。

可导航小世界中的贪婪搜索过程。节点 A 被用作入口点。节点 D 有三个邻居 C、E 和 F。

这种贪婪策略并不能保证找到精确的近邻，因为该方法仅使用当前步骤的局部信息来做出决定。过早停止是该算法的问题之一。尤其是在搜索过程的开始阶段，当没有比当前节点更好的邻居节点时，就会出现这种情况。在大多数情况下，这种情况可能发生在起始区域有太多低度顶点时。

提前停止。当前节点的两个邻居都离查询点较远。因此，尽管存在离查询更近的节点，算法还是会返回当前节点作为响应。

使用多个入口点可以提高搜索精度。

构建

新南威尔士图是通过将数据集点洗牌并逐个插入当前图来构建的。插入一个新节点后，该节点会通过边与最近的 M 个顶点相连。

按顺序插入节点（从左到右），M = 2。每次迭代都会在图中添加一个新顶点，并将其与 M = 2 个近邻节点相连。蓝线代表新插入节点的连接边。

在大多数情况下，远距离边可能会在图构建的开始阶段创建。它们在图导航中发挥着重要作用。

在构建之初插入的元素的近邻链接随后会成为网络中心之间的桥梁，从而保持整个图的连通性，并允许在贪婪路由过程中按对数缩放跳数。- 于A. 马尔科夫、D. A. 亚舒宁

从上图的示例中，我们可以看到一开始添加的远距离边 AB 的重要性。试想一下，如果有一个查询需要从位置相对较远的节点 A 和 I 之间穿越一条路径，那么有了 AB 边，就可以直接从图的一侧导航到另一侧，从而快速完成查询。

随着图中顶点数量的增加，新连接到新节点的边长变小的概率也会增加。

HNSW

HNSW基于与跳过列表和可导航小世界相同的原理。它的结构是一个多层图，顶层的连接较少，底层的区域较密集。

搜索

搜索从最高层开始，每当在各层节点中贪婪地找到本地最近的邻居时，就向下搜索一层。最终，在最底层找到的近邻就是查询的答案。

在 HNSW 中搜索

与 NSW 类似，HNSW 也可以通过使用多个入口点来提高搜索质量。与在每一层只寻找一个近邻不同，HNSW 会寻找与查询向量最近的 efSearch（一个超参数）近邻，并将这些近邻中的每一个作为下一层的切入点。

复杂性

原论文作者 原论文 称，在任何一层上找到最近邻所需的操作数都以一个常数为界。考虑到图中所有层的数量都是对数，我们得到总搜索复杂度为 O(logn)。

构建

选择最大层数

HNSW 中的节点一个接一个地按顺序插入。每个节点都被随机分配一个整数 l，表示该节点在图中能出现的最大层数。例如，如果 l = 1，则只能在 0 层和 1 层找到该节点。 作者为每个节点随机选择 l，其概率分布呈指数衰减，并由非零乘数 mL 归一化（mL = 0 会导致 HNSW 中只有一层，搜索复杂度无法优化）。通常情况下，大多数 l 值应等于 0，因此大多数节点只出现在最底层。mL 值越大，节点出现在较高层的概率就越大。

每个节点的层数 l 是以指数衰减概率分布随机选择的。

基于归一化因子 mL 的层数分布。横轴表示均匀（0，1）分布的值。

要实现可控层次结构的最佳性能优势，不同层邻域之间的重叠（即属于其他层的元素邻域百分比）必须很小。- 俞.A. 马尔科夫、D. A. 亚舒宁

减少重叠的方法之一是减少 mL。但需要注意的是，减少 mL 也会导致在每一层进行贪婪搜索时平均遍历次数增加。这就是为什么必须选择一个能平衡重叠和遍历次数的 mL 值。

论文作者建议选择 mL 的最佳值，即等于 1 / ln(M)。该值对应于跳转列表的参数 p = 1 / M，即各层之间的平均单元素重叠。

插入

节点被赋值 l 后，其插入分为两个阶段：

• 该算法从上层开始，贪婪地寻找最近的节点。然后将找到的节点作为下一层的入口点，继续搜索过程。一旦到达第 l 层，就进入第二步。
• 从第 l 层开始，算法在当前层插入新节点。然后，该算法与步骤 1 相同，但不再只寻找一个最近的邻居，而是贪婪地寻找efConstruction（超参数）最近的邻居。然后，从efConstruction 近邻中选出 M 个，并建立从插入节点到它们的边。之后，算法进入下一层，每个找到的 efConstruction 节点都是一个入口点。新节点及其边插入最底层 0 后，算法结束。

在 HNSW 中插入节点（蓝色）。新节点的最大层数被随机选择为 l = 2。因此，节点将被插入第 2、1 和 0 层。 在每一层上，节点将与其 M = 2 个最近的邻居相连。

选择参数值

原论文就如何选择超参数提供了一些有用的见解：

• 根据模拟结果，M 的 理想值介于 5 和 48 之间。M 值越小，越适合低召回率或低维数据，而 M 值越大，越适合高召回率或高维数据。
• efConstruction 的 值越大，意味着搜索的深度越深，因为会探索到更多的候选方案。不过，这需要更多的计算。作者建议选择这样一个 efConstruction 值，即在训练过程中召回率接近 0.95-1。
• 此外，还有一个重要参数 Mₘₐₓ–顶点可拥有的最大边数。除此以外，还有相同的参数 Mₘₐₓ₀，但分别用于最底层。建议选择 Mₘₐₓ 接近 2 * M 的值。同时，Mₘₐₓ = M 会导致高召回率时性能低下。

候选人选择启发式

上文指出，在节点插入过程中，会从 efConstruction 候选节点中选择 M 个节点来为其建立边。让我们讨论一下选择这 M 个节点的可能方法。

天真方法会选择 M 个最接近的候选者。然而，这并不总是最佳选择。下面是一个示例。

试想一个结构如下图所示的图形。如图所示，图中有三个区域，其中两个区域互不相连（左侧和顶部）。因此，举例来说，从 A 点到 B 点需要穿过另一个区域，路径很长。如果能以某种方式将这两个区域连接起来，导航效果会更好。

节点 X 被插入图中。目标是以最佳方式将其与其他 M = 2 个点连接起来。

然后，一个节点 X 被插入图中，并需要与 M = 2 个其他顶点相连。

在这种情况下，最简单的方法是直接选取 M = 2 个近邻（B 和 C）并将 X 与它们连接起来。虽然 X 与其真正的近邻相连，但这并不能解决问题。让我们看看作者发明的启发式方法。

启发式不仅考虑了节点之间的最近距离，还考虑了图中不同区域的连通性。

启发式算法会选择第一个最近的邻居（本例中为 B），并将插入的节点（X）与之相连。然后，算法按照排序顺序依次选择另一个最近的邻居（C），只有当该邻居到新节点（X）的距离小于该邻居到所有已连接顶点（B）到新节点（X）的距离时，才与其建立一条边。之后，该算法会继续下一个最近的相邻节点，直到建立 M 条边为止。

回到这个例子，启发式程序如下图所示。启发式选择 B 作为 X 的最近邻，并建立边 BX。然后，算法选择 C 作为下一个最近的邻居。但是，这次 BC < CX。这表明在图中添加边 CX 并不是最佳选择，因为已经存在边 BX，而且节点 B 和 C 相距很近。同样的类比也适用于节点 D 和 E。因此，新边 AX 和两个初始区域彼此相连。

左边的示例使用的是天真方法。右边的示例使用了选择启发式，结果是两个初始不相交的区域彼此相连。

复杂性

与搜索过程相比，插入过程的工作原理非常相似，没有任何可能需要非恒量操作的显著差异。因此，插入单个顶点所需的时间为 O(logn)。要估算总复杂度，应考虑给定数据集中所有插入节点 n 的数量。最终，HNSW 的构建需要 O(n * logn) 的时间。

将 HNSW 与其他方法相结合

HNSW 可以与其他相似性搜索方法一起使用，以提供更好的性能。最常用的方法之一是将其与本系列文章其他部分所述的倒排文件索引和乘积量化（IndexIVFPQ）相结合。

在这种模式下，HNSW 在 IndexIVFPQ 中扮演着粗量化器的角色，这意味着它将负责寻找最近的 Voronoi 分区，从而缩小搜索范围。为此，必须在所有 Voronoi 中心点上建立 HNSW 索引。当给出一个查询时，HNSW 将用于查找最近的 Voronoi 中心点（而不是像以前那样通过比较与每个中心点的距离来进行强行搜索）。然后，在相应的 Voronoi 分区内对查询向量进行量化，并使用 PQ 代码计算距离。

通过查找建立在 Voronoi 中心点之上的 HNSW 中的最近邻近点，选择最近的 Voronoi 中心点。

在只使用倒排文件索引时，最好不要设置过多的 Voronoi 分区数（例如 256 或 1024），因为要通过暴力搜索来找到最近的中心点。选择少量的 Voronoi 分区，每个分区内的候选中心点数量就会相对较多。因此，该算法可以快速确定查询的最近中心点，其大部分运行时间都集中在寻找 Voronoi 分区内的最近邻域上。

不过，将 HNSW 引入工作流程需要进行调整。考虑仅在少量中心点（256 或 1024）上运行 HNSW：HNSW 不会带来任何明显的优势，因为在向量数量较少的情况下，HNSW 的执行时间与原始的暴力搜索相当。此外，HNSW 还需要更多内存来存储图结构。

这就是为什么在合并 HNSW 和倒排文件索引时，建议设置比通常大得多的 Voronoi 中心点数量。这样，每个 Voronoi 分区内的候选数就会大大减少。

这种范式的转变产生了以下设置：

• HNSW 能在对数时间内快速识别最近的沃罗诺中心点。
• 然后，在各自的 Voronoi 分区内进行穷举搜索。这并不麻烦，因为潜在候选者的数量很少。

Faiss实现

Faiss(Facebook 人工智能搜索相似性）是一个用 C++ 编写的 Python 库，用于优化相似性搜索。该库提供不同类型的索引，这些索引是用于高效存储数据和执行查询的数据结构。

根据 文件中的信息我们将了解如何利用 HNSW 并将其与反转文件索引和乘积量化合并。

指数HNSWFlat

FAISS 有一个实现 HNSW 结构的 IndexHNSWFlat 类。通常，后缀 “Flat “表示数据集向量完全存储在索引中。构造函数接受 2 个参数：

• d：数据维度。
• M：插入时需要添加到每个新节点的边的数量。

此外，IndexHNSWFlat 还通过 hnsw 字段提供了几个有用的属性（可以修改）和方法：

• hnsw.efConstruction：施工期间需要探索的近邻数量。
• hnsw.efSearch：搜索时探索的近邻数目。
• hnsw.max_level：返回最大层数。
• hnsw.entry_point：返回入口点。
• faiss.vector_to_array(index.hnsw.levels)：返回每个向量的最大层数列表
• hnsw.set_default_probas(M：int，level_mult：float)：允许分别设置 M 和 mL 值。默认情况下，level_mult 设置为 1 / ln(M)。

Faiss 实现 IndexHNSWFlat

IndexHNSWFlat 设置 Mₘₐₓ = M 和 Mₘₐₓ₀ = 2 * M 的值。

IndexHNSWFlat + IndexIVFPQ

IndexHNSWFlat 还可以与其他指数相结合。上一部分介绍的 IndexIVFPQ 就是其中一个例子。创建该复合指数分为两个步骤：

• IndexHNSWFlat 初始化为粗量化器。
• 量化器作为参数传递给 IndexIVFPQ 的构造函数。

可以使用不同或相同的数据进行训练和添加。

FAISS IndexHNSWFlat + IndexIVFPQ

结论

在这篇文章中，我们研究了一种鲁棒算法，这种算法尤其适用于大型数据集向量。通过使用多层图表示和候选选择启发式，该算法的搜索速度得到了有效提升，同时还保持了相当高的预测准确率。值得注意的是，HNSW 还可以与其他相似性搜索算法结合使用，因此非常灵活。