相似度搜索，第四部分：分层可导航小世界（HNSW）

发现如何构建高效的多层图来提高在大量数据中的搜索速度

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

介绍

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

层级可导航小世界（HNSW）是一种用于近似搜索最近邻居的最先进算法。在其内部，HNSW构建了优化的图形结构，使其与之前讨论的其他方法非常不同。

• 卷积神经网络全面指南
• 相似性搜索，第三部分：融合倒排文件索引和产品量化
• 变分推断：基础知识

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

关于著名的六度分隔规则的一个众所周知的类比与这种方法有关:

所有人之间都有六个或更少的社交联系。

在继续讨论HNSW的内部工作之前，让我们首先讨论跳表和可导航小世界——HNSW实现中使用的关键数据结构。

跳表

跳表是一种概率数据结构，允许在排序列表中插入和搜索元素的平均时间复杂度为O(logn)。跳表由几层链接列表构成。最底层有原始链接列表，其中包含所有元素。向更高级别移动时，跳过的元素数量增加，从而减少连接数。

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

根据维基百科的信息，跳表具有定义元素在多个列表中出现概率的主要参数p。如果元素出现在第i层，则它将出现在第i + 1层的概率等于p（p通常设置为0.5或0.25）。平均每个元素出现在1 /（1-p）个列表中。

正如我们所看到的，这个过程比链表中的普通线性搜索要快得多。事实上，HNSW继承了相同的思想，但它使用的是图而不是链表。

可导航小世界

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

顶点有时也被称为节点。

搜索

首先，搜索是通过选择一个入口点进行的。为确定算法移动到的下一个顶点（或顶点），它计算从查询向量到当前顶点的邻居的距离，并移动到最接近的顶点。在某个点，算法终止搜索过程，当它无法找到比当前节点本身更接近查询的邻居节点时，返回该节点作为查询的响应。

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

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

构造

NSW图是通过对数据集点进行洗牌并逐个插入当前图中来构建的。当插入新节点时，它会与其M个最近顶点连接成边。

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

与开始构建时插入的元素的最近邻接链接后来成为网络中心枢纽之间的桥梁，它们保持整个图的连通性，并允许在贪婪路由期间跳数的对数缩放。– Yu. A. Malkov，D. A. Yashunin

从上面的图例中，我们可以看到在开始时添加的长距离边AB的重要性。想象一下需要从相对较远的节点A和I遍历路径的查询。拥有边AB可以通过直接从图的一侧导航到相反侧迅速实现。

随着图中顶点数的增加，连接到新节点的新连接边的长度更短的概率会增加。

HNSW

HNSW基于跳跃列表和可导航的小世界相同的原理。其结构代表具有较少连接的顶层和底层更密集区域的多层图。

搜索

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

与NSW类似，使用多个入口点可以提高HNSW的搜索质量。在每个层上不仅找到一个最近邻居，而是找到与查询向量最接近的efSearch（一个超参数）个最近邻居，然后在下一层上使用这些邻居中的每一个作为入口点。

复杂度

原始论文的作者声称，在任何层上找到最近邻居所需的操作次数都受到常数的限制。考虑到图中所有层数是对数级别的，我们得到总的搜索复杂度为O（logn）。

构建

选择最大层数

在HNSW中，节点按顺序一个接一个地插入。每个节点都随机分配一个整数l，表示该节点可以出现在图中的最大层数。例如，如果l = 1，则该节点只能在第0层和第1层上找到。作者使用指数衰减概率分布对每个节点随机选择l，该分布由非零乘数mL进行归一化（mL = 0会导致HNSW中只有单个层且未优化的搜索复杂度）。通常，大多数l值应等于0，因此大多数节点仅出现在最低层。 mL的较大值增加了节点出现在更高层的概率。

为了实现可控层次结构的最佳性能优势，不同层之间邻居之间的重叠（即属于其他层的元素邻居的百分比）必须很小。-Yu. A. Malkov，D. A. Yashunin。

减少重叠的一种方法是减少mL。但是，需要记住的是，减少mL平均会导致在每个层上进行更多遍历。这就是为什么选择一个既平衡重叠又平衡遍历次数的mL值是至关重要的。

该论文的作者建议选择最优的mL值，它等于1 / ln（M）。该值对应于跳过列表的参数p = 1 / M，这是层之间的平均单个元素重叠。

插入

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

1. 算法从上层开始贪婪地查找最近的节点。找到的节点然后用作下一层的入口点，搜索过程继续。一旦达到层l，插入过程进入第二步。
2. 从第l层开始，算法在当前层中插入新节点。然后，它与步骤1相同，但不是仅查找一个最近邻居，而是贪婪地搜索efConstruction（超参数）个最近邻居。然后从efConstruction个邻居中选择M个，并从插入节点到它们的边缘构建边缘。之后，算法降至下一层，并且每个找到的efConstruction个节点都作为入口点。在新节点及其边缘插入到最低层0后，算法终止。

选择构建参数的值

原始论文提供了几个选择超参数的有用见解：

• 根据模拟，M的良好取值在5和48之间。M值较小的情况下适用于低召回率或低维度数据，而M值较大的情况下适用于高召回率或高维度数据。
• 较高的efConstruction值意味着进行更深入的搜索，因为会探索更多候选项。但是，这需要更多计算。作者建议选择efConstruction值，以便在训练期间召回率接近0.95-1。
• 此外，还有另一个重要的参数Mₘₐₓ-顶点可以拥有的最大边数。除此之外，还有一个单独用于最低层的参数Mₘₐₓ₀。建议将Mₘₐₓ的值选择为接近2 * M。大于2 * M的值可能会导致性能下降和过多的内存使用。同时，Mₘₐₓ = M会导致高召回率时性能不佳。

候选选择启发式

如上所述，在插入节点时，从efConstruction个候选项中选择M个来构建与它们的边缘。让我们讨论选择这些M个节点的可能方法。

朴素的方法选择最接近的M个候选项。然而，这并不总是最优选择。下面是一个演示它的示例。

想象一下具有下图结构的图。如您所见，有三个区域，其中两个区域彼此不连通（在左侧和顶部）。因此，例如从点A到B需要通过另一个区域的长路径。逻辑上来说，应该以某种方式连接这两个区域以更好地导航。

然后在图中插入一个节点X，并需要将其连接到M = 2个其他顶点。

在这种情况下，朴素的方法直接选择最近的M个邻居（B和C），并将X连接到它们。尽管X与其真正最近的邻居相连，但它并没有解决问题。让我们看看作者发明的启发式方法。

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

启发式方法选择最近的第一个邻居（在我们的情况下为B），并将插入的节点（X）连接到它。然后，算法按排序顺序逐个选择另一个最接近的邻居（C），仅在其到新节点（X）的距离大于任何邻居到所有已连接顶点（B）到新节点（X）的距离时才构建与之的边缘。之后，算法继续到下一个最接近的邻居，直到构建M个边缘。

回到例子，启发式过程如下图所示。启发式方法选择B作为X的最接近的邻居，并构建边缘BX。然后，算法选择C作为下一个最接近的邻居。然而，此时BC < CX。这表明将边缘CX添加到图中并不是最优的，因为已经存在边缘BX，节点B和C非常接近。节点D和E也是同样的情况。之后，算法检查节点A。这次，它满足条件，因为AC > AX。因此，新的边缘AX和两个初始区域彼此连接。

复杂度

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

将HNSW与其他方法结合使用

HNSW可以与其他相似性搜索方法结合使用，以提供更好的性能。其中一种最流行的方法是将其与倒排文件索引和产品量化（IndexIVFPQ）相结合，这些方法在本文系列的其他部分中进行了描述。

相似性搜索，第3部分：混合倒排文件索引和产品量化

在本系列的前两部分中，我们讨论了信息检索中的两种基本算法：倒排…

小猪AI.com

在这种范式中，HNSW扮演着IndexIVFPQ的粗量化器的角色，这意味着它将负责找到最近的Voronoi分区，以便可以减少搜索范围。为此，必须在所有Voronoi质心上构建HNSW索引。给定查询后，HNSW用于查找最近的Voronoi质心（而不是通过比较到每个质心的距离来进行暴力搜索）。之后，使用PQ代码在相应的Voronoi分区内量化查询向量并计算距离。

当仅使用倒排文件索引时，最好不要设置Voronoi划分的数量过大（例如256或1024），因为要执行暴力搜索来查找最近的质心。通过选择较小的Voronoi分区数，每个分区内的候选项数变得相对较大。因此，该算法迅速识别出查询的最近中心点，并且其大部分运行时集中在查找Voronoi分区内的最近邻居上。

但是，将HNSW引入工作流程需要进行调整。考虑仅在少量质心（例如256或1024）上运行HNSW：由于向量数量较少，HNSW的执行时间相对于天真的暴力搜索而言相对一致。此外，HNSW需要更多的内存来存储图形结构。

这就是在合并HNSW和倒排文件索引时建议将Voronoi质心数量设置得更大的原因。通过这样做，每个Voronoi分区内的候选项数量变得更少。

这种范式的转变导致以下设置：

• HNSW以对数时间快速识别最近的Voronoi质心。
• 之后，在相应的Voronoi分区内执行详尽的搜索。这不应该是一个问题，因为潜在的候选项数量很少。

Faiss实现

Faiss（Facebook AI Search Similarity）是用于优化相似性搜索的用C++编写的Python库。该库提供了不同类型的索引，这些索引是用于有效存储数据和执行查询的数据结构。

基于 Faiss 文档中的信息，我们将了解如何利用 HNSW 并将其与倒排文件索引和产品量化合并。

IndexHNSWFlat

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

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

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

• 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)。

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

IndexHNSWFlat + IndexIVFPQ

IndexHNSWFlat 还可以与其他索引组合使用。其中一个示例是前面描述的 IndexIVFPQ。创建这个复合索引需要经过两个步骤：

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

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

结论

在本文中，我们学习了一种强大的算法，特别适用于大型数据集向量。通过使用多层图形表示和候选选择启发式方法，它的搜索速度在维持良好的预测准确性的同时高效缩放。值得注意的是，HNSW 可以与其他相似度搜索算法结合使用，使其非常灵活。

资源

• 六度分隔 | 维基百科
• 跳表 | 维基百科
• 使用分层可导小世界图进行高效且鲁棒的近似最近邻搜索。Yu. A. Malkov，D. A. Yashunin
• Faiss 文档
• Faiss 存储库
• Faiss 索引摘要

除非另有说明，所有图像均为作者拍摄。