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

介绍

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

分层可导航小世界(HNSW) 是一种用于近似搜索最近邻居的最先进算法。在底层，HNSW 构建了优化的图结构，使其与本系列文章前面部分中讨论的其他方法非常不同。

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

著名的六次握手规则的一个著名类比与此方法有关：

所有人之间的社会关系距离不超过 6 个。

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

跳跃列表(Skip List)

skip list是一种概率数据结构，允许在排序列表中插入和搜索元素*O(logn)*一般。跳跃列表由多层链表构成。最底层有原始链表，其中包含所有元素。当移动到更高级别时，跳过的元素数量会增加，从而减少连接数量。

img

在跳跃列表中查找元素 20

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

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

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

可航行的小世界(Navigable Small World)

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

顶点Vertex有时也称为节点Node。

搜索

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

img

可导航的小世界中的贪婪搜索过程。节点 A 用作入口点。它有两个邻居 B 和 D。节点 D 比 B 更接近查询。因此，我们移动到 D。节点 D 有三个邻居 C、E 和 F。E 是距离查询最近的邻居，因此我们移动到 D。最后，搜索过程将导致节点 L。由于 L 的所有邻居都比 L 本身距离查询更远，因此我们停止算法并返回 L 作为查询的答案。

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

img

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

通过使用多个入口点可以提高搜索准确性。

建造

NSW 图是通过打乱数据集点并将它们一一插入到当前图中来构建的。当插入一个新节点时，它会通过边链接到距离它最近的M 个顶点。

img

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

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

在构造开始时插入的元素的最近邻居的链接后来成为网络集线器之间的桥梁，保持整体图的连接性并允许在贪婪路由期间对跳数进行对数缩放。——于。A.马尔科夫，DA Yashunin

从上图中的例子我们可以看出一开始添加的远程边AB的重要性。想象一下，一个查询需要从相对较远的节点A和 I 遍历一条路径。有了边AB，可以通过直接从图的一侧导航到另一侧来快速完成此操作。

随着图中顶点数量的增加，新连接到新节点的边的长度变小的可能性也随之增加。

HNSW

HNSW基于与skiplist 调表和navigable small world (NSW) 可导航小世界相同的原理。它的结构代表了一个多层图，顶层的连接较少，底层的区域更密集。

搜索(Search)

搜索从最高层开始，每次在各层节点中贪婪地找到局部最近邻时，都会向下一级进行搜索。最终，在最低层找到的最近邻居就是查询的答案。

img

在HNSW中搜索

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

复杂度

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

建造(Construction)

选择最大层数

HNSW中的节点是按顺序一一插入的。每个节点都被随机分配一个整数l，表示该节点可以出现在图中的最大层。例如，如果l = 1，则只能在第 0 层和第 1 层上找到该节点。作者为每个节点随机选择l ，其具有由非零乘数 mL 归一化的指数衰减概率分布(exponentially decaying probability distribution)（mL= 0导致HNSW 中的单层和未优化的搜索复杂度）。通常，大多数l值应等于 0，因此大多数节点仅存在于最低级别。mL的较大值增加节点出现在较高层的概率。

img

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

img

基于归一化因子 mL 的层数分布。水平轴表示均匀(0, 1) 分布的值。

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

减少重叠的方法之一是减少mL。但重要的是要记住，减少mL平均也会导致在每层的贪婪搜索期间进行更多的遍历。这就是为什么必须选择一个能够平衡重叠和遍历次数的mL值。

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

插入(Insertion)

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

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

img

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

选择构造参数值(Choosing values for construction parameters)

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

  • 根据模拟，M的最佳值在 5 到 48 之间。较小的M值往往更适合较低召回率或低维数据，而较高的 M 值更适合高召回率或高维数据。
  • efConstruction的值越高，意味着随着探索的候选者越多，搜索就越深入。然而，它需要更多的计算。作者建议选择这样一个efConstruction值，使训练期间的召回率接近0.95-1。
  • 此外，还有一个重要参数Mₘₐₓ——一个顶点可以拥有的最大边数。除此之外，还存在相同的参数Mₘₐₓ₀，但对于最低层Lay 0是单独的。建议为Mₘₐₓ选择接近2 * M的值。大于2 * M的值可能会导致性能下降和内存使用过多。同时，Mₘₐₓ = M导致在高召回率下表现不佳。

候选者启发式选择(Candidate selection heuristic)

上面注意到，在节点插入期间，选择efConstruction候选者中的M个来为它们构建边。让我们讨论选择这M 个节点的可能方法。

朴素方法采用M个最接近的候选者。然而，它并不总是最佳选择。下面是一个演示它的例子。

想象一个具有下图结构的图表。如您所见，共有三个区域，其中两个区域未相互连接（左侧和顶部）。因此，例如，从A点到B点需要穿过另一个区域的很长的路径。以某种方式连接这两个区域以实现更好的导航是合乎逻辑的。

img

​ 节点 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进行相同的类比。之后，算法检查节点A。这次，它满足BA > AX 的条件。结果，新边AX和两个初始区域彼此连接。

img

​ 左边的例子使用了朴素方法。右侧的示例使用启发式选择，这会导致两个初始不相交区域相互连接。

复杂度

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

将 HNSW 与其他方法相结合

HNSW 可以与其他相似性搜索方法一起使用，以提供更好的性能。最流行的方法之一是将其与倒排文件索引和乘积量化 ( IndexIVFPQ ) 结合起来，这在本系列文章的其他部分中进行了描述。

在此范例中，HNSW 扮演IndexIVFPQ 粗量化器(coarse quantizer)的角色，这意味着它将负责查找最近的 Voronoi 分区，因此可以缩小搜索范围。为此，必须在所有 Voronoi 质心上构建 HNSW 索引。当给出查询时，HNSW 用于查找最近的 Voronoi 质心（而不是像以前那样通过比较到每个质心的距离进行强力搜索）。之后，查询向量在相应的 Voronoi 分区内进行量化，并使用 PQ 码计算距离。

img

​ 通过查找建立在 Voronoi 质心之上的 HNSW 中的最近邻居来选择最近的 Voronoi 质心。

当仅使用倒排文件索引时，最好将 Voronoi 分区的数量设置得不要太大（例如 256 或 1024），因为会执行强力搜索来找到最近的质心。通过选择少量的 Voronoi 分区，每个分区内的候选者数量会变得相对较多。因此，该算法可以快速识别查询的最近质心，并且其大部分运行时间都集中在查找 Voronoi 分区内的最近邻居上。

然而，将 HNSW 引入工作流程需要进行调整。考虑仅在少量质心（256 或 1024）上运行 HNSW：HNSW 不会带来任何显著的好处，因为在向量数量较少的情况下，HNSW 在执行时间方面与朴素的暴力搜索相对相同。此外，HNSW 需要更多内存来存储图结构。

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

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

  • HNSW 在对数时间内快速识别最近的 Voronoi 质心。

  • 之后，在各个 Voronoi 分区内执行穷举搜索。这应该不成问题，因为潜在候选人的数量很少。

注： 这种HNSW+IndexIVFPQ方式是最常用的方式，常结合场景数据结合硬件训练，调优，刷榜。来处理B级别以上的embedding向量数据；需要关注 recall 召回率， 内存使用率 和 搜索速度， 根据场景对这三方面进行取舍。（详情见： faiss复合索引 faiss_composite_indexes.ipynb）

FAISS实现

根据Faiss 文档中的信息，我们将了解如何利用 HNSW 并将其与倒排文件索引和乘积量化合并在一起。

IndexHNSWFlat

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

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

此外，通过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)。

img

IndexHNSWFlat 的 Faiss 实现 (注：图中的efConstruction 和 efSearch 注释弄反了)

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

IndexHNSWFlat + IndexIVFPQ

IndexHNSWFlat也可以与其他索引组合。其中一个示例是上一部分中描述的IndexIVFPQ 。该综合索引的创建分两个步骤进行：

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

训练和添加可以通过使用不同或相同的数据来完成。

img

IndexHNSWFlat + IndexIVFPQ 的 FAISS 实现

结论

在本文中，我们研究了一种鲁棒算法，该算法特别适用于大型数据集向量。通过使用多层图表示和候选启发式选择，其搜索速度可以有效扩展，同时保持良好的预测精度。还值得注意的是，HNSW 可以与其他相似性搜索算法结合使用，使其非常灵活。

Reference

除非另有说明，所有图片均由作者提供。

原文地址：https://towardsdatascience.com/similarity-search-part-4-hierarchical-navigable-small-world-hnsw-2aad4fe87d37

附操作学习笔记:

faiss_hnsw.ipynb

faiss_vector_indexes.ipynb

faiss_composite_indexes.ipynb