DB 论文阅读：Hierarchical Navigable Small World
本文介绍向量近似最近邻（Approximate Nearest Neighbor，ANN）的另一经典算法：HNSW（Hierarchical Navigable Small World，HNSW）。HNSW 工业界使用最多的 ANN 算法之一，得到了 Milvus、Elasticsearch、Fasis、pgvector 等系统或库的广泛支持。原文： Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs 。
摘要
本文提出了一种具有可控层次的基于可导航小世界图的近似 k 近邻算法。所提出的解决方案完全基于图而无需任何额外的搜索结构，这些结构通常用于大多数邻近图技术的粗搜索阶段。HNSW 逐步构建一个多层结构，由嵌套的接近图集合（层）组成，用于存储元素的子集。元素所在的最大层数是随机选择的，遵循指数衰减的概率分布。这允许生成类似于之前研究的可导航小世界（NSW）结构的图，同时额外具有按其特征距离尺度分离的连接。与 NSW 相比，HNSW 从上层开始搜索并利用尺度分离可以提高性能，实现对数复杂度。额在高召回率和高度聚集的数据情况下，使用启发式方法选择邻近图近邻显著提高了性能。性能评估表明，所提出的通用度量空间搜索索引能够明显优于之前开源的仅用于向量空间的方法。该索引结构与跳表相似，允许直接、平衡的分布式实现。
1. 动机
由于 HNSW 是 NSW 的改进，因此首先需要分析 NSW 有什么问题。
NSW 在进行 ANN 搜索时，采用贪心策略从一个节点跳转到下一个距离最近的邻居节点，这一寻找下一个节点的过程称为“路由”，和网络中的路由概念类似。NSW 的贪心搜索算法可以分为两个阶段，即：
- zoom-out
- zoom-in
搜索算法的起始阶段是 zoom-out，从一个低度节点开始遍历图，直到：the characteristic radius of the node links length reaches the scale of the distance to the query。这句英文很关键，但是不太好翻译，不过其表达的意思就是：随着搜索过程的进行，从当前节点到其邻居节点的连接长度（即特征半径，characteristic radius ）降低到与查询点到这些邻居节点的距离相当的程度。也即，当搜索过程中节点的连接长度降低到与查询点到这些节点的距离相近时，搜索算法会遇到问题，因为它可能会陷入到一个局部最小值，而不是继续向更远的节点扩展搜索范围。
这一问题可以通过直接从度数最大的顶点开始搜索解决，直接进入 zoom-in 阶段。尽管在低维空间中，这样设置提供了更好的性能，但是 NSW 查询算法仍然是 \(\log^{p}\) （polylogarithmic，严谨定义参考：Polylogarithmic function ）复杂度，即对数的次幂复杂度。
NSW 查询算法之所以是 \(\log^{p}\) 复杂度，是因为总的距离计算数大致与贪婪算法步数（跳数）的平均值乘以贪婪路径上节点度数（度数）的平均值成比例。平均跳数随数据集规模呈对数增长，平均度数也随数据集规模呈对数增长。因此，最终的算法复杂度是 \(\log^{p}\) 。
HNSW 算法的思想是根据连接的长度尺度将连接分到不同层，然后在多层图上进行搜索。在这种情况下，我们可以独立于网络大小，仅评估每个元素所需的固定部分的连接，从而实现对数复杂度。在该数据结构中，查询从仅具有最长连接的最上层开始（zoom-in 阶段）。算法贪婪地从上层遍历元素，直到达到局部最小值。之后，搜索切换到下一层（该层的连接较短），从上一层中的局部最小元素重新开始，然后重复这个过程。在所有层中，每个元素的最大连接数可以保持恒定，从而允许在可导航小世界网络中进行对数复杂度的路由扩展。搜索过程如下图所示：
形成这种分层结构的一种方法是通过引入层来明确设置具有不同长度尺度的连接。对于每个元素，我们选择一个整数层级 \(l\)，该层级定义了元素所属的最大层。对于一个层中的所有元素，会逐步构建一个近似 Delaunay 图的邻近图（即只包含“短”连接的图）。如果我们设置 \(l\) 的指数衰减概率（即遵循几何分布），我们将得到结构中预期层数的对数缩放。搜索过程是一个从顶层开始，以零层结束的迭代贪婪搜索。
如果我们将所有层的连接合并，结构就会变得类似于 NSW 图（在这种情况下，\(l\) 可以与 NSW 中的节点度数相对应）。与 NSW 不同的是，HNSW 的构建算法不需要在插入元素之前对元素进行洗牌——随机性是通过使用层级随机化来实现的，从而允许在数据分布暂时变化的情况下进行真正的增量索引（尽管由于构建过程只是部分确定性的，插入顺序的改变会轻微影响性能）。
在元素插入过程中，为了选择邻近图的连接，我们利用一种启发式方法，该方法考虑了候选元素之间的距离以创建多样化的连接，而不仅仅是选择最近的邻居。这种启发式方法从距离插入元素最近的候选元素开始检查，并仅当候选元素比任何已连接的候选元素更接近基础（插入的）元素时，才创建到该候选元素的连接。
当候选元素的数量足够大时，启发式方法允许获取精确的相对邻域图作为子图，这是一个仅使用节点间距离就可以推导出的 Delaunay 图的最小子图。相对邻域图允许即使在高度聚类的数据情况下也能轻松保持全局连接。如下图所示：
注意，与精确的相对邻域图相比，启发式方法创建了额外的边，允许控制连接的数量，这对于搜索性能很重要。对于一维数据的情况，启发式方法允许通过仅使用元素间距离信息来获取精确的 Delaunay 子图（在这种情况下与相对邻域图重合），从而使得从 HNSW 直接过渡到一维概率跳表成为可能。
2. 算法描述
2.1 INSERT算法
插入算法伪代码如下：
各个参数含义如下：
- \(hnsw\) ：HNSW 索引数据结构
- \(q\) ：插入向量
- \(M\) ：建立连接的数量
- \(M_{max}\) ：每层每个元素的最大连接数
- \(efConstruction\) ：动态候选列表的大小
- \(m_{L}\) ：用于层级生成的标准化因子
算法主要执行流程如下：
- 从顶层开始使用贪心算法遍历图，以找到该层距离插入元素 \(q\) 最近的进入点 \(ep\) ；
- 使用从前一层找到的最近邻作为进入点，继续从下一层搜索，并重复该过程。直到搜索到达小于等于 \(l\) 的层，插入算法进入第二阶段；
- 依次在剩余层，调用
SEARCH-LAYER函数获取候选列表，从候选列表中选择 \(M\) 个邻居，可使用算法 3 或 算法 4； - 当插入元件的连接在零层上建立时，插入过程终止。
注意，第二阶段中调用的 SEARCH-LAYER
函数相比第一阶段有以下不同：
SEARCH-LAYER函数中的参数 \(ef\) 从 1 改变为 \(efConstruction\) ，以控制贪心搜索的召回率；- 在每一层上找到的最近邻也被用作插入元素连接的候选者。
2.2 SEARCH-LAYER 算法
插入算法中用到的 SEARCH-LAYER 算法伪代码如下：
参数含义如下：
- \(q\) ：查询元素
- \(ep\) ：进入点
- \(ef\) ：距离 \(q\) 最近的元素数量，即 k 近邻中的 k
- \(l_{c}\) ：层数
该算法是 NSW 中贪心查询算法的改进，其与 NSW 中查询算法不同点在于：
- 进入点是固定的
- 搜索的质量是由一个不同的参数 \(ef\) 控制，而不是 NSW 的改变多重搜索的数量
2.3 SELECT-NEIGHBORS-SIMPLE 算法
算法伪代码描述如下：
该算法非常简单，参数及流程不再介绍。
2.4 SELECT-NEIGHBORS-HEURISTIC 算法
算法伪代码描述如下：
启发式算法的两个额外参数含义如下：
- \(extendCandidates\)
：用于标识是否扩展候选集合的
bool值，仅对极度聚集的数据有用 - \(keepPrunedConnections\) ：标识每个元素是否使用固定数量的连接
每层元素所能拥有的最大连接数由参数 \(M\) 确定（最底层需额外参数 \(M_{max0}\) 单独指定）。如果一个节点在建立新连接时已经满了，那么它的扩展连接列表将通过用于选择邻居的相同算法进行缩减。
2.5 K-NN-SEARCH 算法
近似 k-ANN 查询算法伪代码如下：
查询算法类似于 \(l = 0\) 的插入算法，与插入的不同之处在于在最底层找到的最近邻居(用作连接的候选者)现在作为搜索结果返回。查询质量由参数 \(ef\) 控制。
2.6 构造参数的影响
参数 \(m_{L}\) 和 \(m_{max0}\) 用于维持图的可导航小世界属性，当对这两个参数设置不同值时得到具有不同特性的图：
- \(m_{L} = 0, m_{max0} = M\) 时，产生有向 K-NN 图
- \(m_{L} = 0, m_{max0} = \infty\) 时，等价于 NSW
- \(m_{L} \gt 0\) 时，HNSW
为了实现可控层次结构的最佳性能优势，不同层之间邻居之间的重叠（即元素邻居中也属于其他层的比例）必须小。这需要减小参数 \(m_{L}\) ，但同时，减小 \(m_{L}\) 会增加每层贪婪搜索的平均跳数，给性能带来负面影响。因此，存在一个最优的 \(m_L\) 值。一个简单的最优 \(m_L\) 选择是 \(1/\ln(M)\)，这对应于跳表参数 \(p=1/M\) ，其中层之间有平均单个元素的重叠。
通过模拟实验，作者发现在低维数据上增加 \(m_L\) 会导致显著的性能提升，而在高维数据上，增加 \(m_L\) 的效果则不那么明显。此外，使用启发式方法选择图连接（而不是简单地连接到最近的邻居）可以显著提高性能，尤其是在低维数据、高召回率、中维数据和高度聚类数据的情况下。
\(M_{max0}\) 参数也会显著影响搜索性能，尤其是在高召回率的情况下。作者通过模拟，推荐设置 \(M_{max0} = 2 \times M\) 。
参数 \(M\) 的合理范围是 \([5, 48]\) 。模拟表明较小的 \(M\) 适用于较低的召回率 和/或 低维数据；较大的 \(M\) 适用于高召回率 和/或 高维数据。该参数还影响占用的存储大小。
\(efConstruction\) 参数值的选择比较直接。正如在 NSW 中所建议的那样，它必须足够大，以便在构建过程中产生接近 1 的 K-ANNS 召回(0.95 对于大多数用例来说已经足够了)。这一参数可通过采样数据自动设置。