层次化可导航小世界（HNSW）

HNSW（层次化可导航小世界）是一种高效的最近邻搜索算法，在大规模向量检索中表现优异。它通过构建多层图结构，在保持高查询精度的同时，显著降低了搜索时间复杂度，从 O(n) 优化到近似 O(log n)。这篇文章将深入介绍 HNSW 的核心原理、实现方法以及实际应用场景。

算法背景

在大规模向量检索领域，如何快速准确地找到最近邻是一个关键问题。传统的精确最近邻搜索算法（如KD树、R树等）在处理高维数据时往往会遇到”维度灾难”的问题，其性能会随着维度的增加而急剧下降。为了解决这个问题，近似最近邻搜索（Approximate Nearest Neighbor, ANN）算法应运而生，而HNSW就是其中表现最优秀的算法之一。

近似最近邻搜索问题定义

给定一个包含n个d维向量的数据集合 $S \subset \mathbb{R}^d$，对于任意查询点 $q \in \mathbb{R}^d$，找到一个点 $p \in S$，使得：

\[d(p,q) \leq (1+\epsilon) \cdot d(p^*,q)\]

其中，$p^*$ 是真实的最近邻点，$\epsilon > 0$ 是近似因子，$d(\cdot,\cdot)$ 是距离度量函数。

NSW的基础概念

在深入HNSW之前，我们需要理解NSW（Navigable Small World）图的概念。NSW是一种基于小世界网络理论的图结构，它具有以下特点：

短平均路径长度：任意两个节点之间的平均跳数较小
高聚集系数：节点的邻居之间也倾向于相互连接
度分布呈现幂律分布：少数节点具有较多连接，大多数节点具有较少连接

为什么需要层次化结构

虽然NSW图能够提供高效的搜索路径，但在大规模数据集上，单层图结构的搜索效率仍然不够理想。HNSW通过引入层次化的结构，将搜索空间进行分层，实现了更高效的搜索策略。这种层次化结构的主要优势在于：

在高层图中可以进行快速的粗粒度搜索
随着层级下降，搜索范围逐渐缩小，实现精确定位
通过控制每层的连接度，平衡了搜索效率和内存开销

数据结构设计

HNSW的核心是其独特的多层图结构设计，这种设计直接决定了算法的性能和效率。让我们详细了解其设计思想和具体实现。

多层图结构

HNSW将数据点组织成一个层次化的结构，包含多个层级的图：

最底层（第0层）包含所有数据点
上层图逐渐稀疏，节点数量呈指数衰减
每个节点在不同层级都保持相同的标识

图的形式化定义为：

\[G_l = (V_l, E_l), l = 0,1,...,L\]

其中：

$G_l$ 表示第l层图
$V_l$ 是第l层的节点集合
$E_l$ 是第l层的边集合
$L$ 是最大层数

层级划分策略

HNSW采用概率分层策略，每个节点的最大层级是通过随机函数确定的。具体来说：

对于每个新插入的节点，其最大层级 $#l_{max}#$ 通过以下概率分布确定：
\[P(l_{max} = l) = p^l(1-p)\]
其中 $p$ 是一个常数（通常取0.5），这将产生一个几何分布。
这种分层策略确保了：
- 节点数量随层级增加呈指数衰减
- 平均而言，第 $l$ 层的节点数约为 $n \cdot p^l$
- 最高层级期望为 $O(\log_{1/p} n)$

节点连接规则

HNSW的每层图都是一个近似最近邻图（Approximate k-NN Graph），其连接规则如下：

邻居数量控制：
- 每层设置最大出度 $M$
- 底层可以设置更大的最大出度 $M_0$
- 实际实现中通常 $M_0 = 2M$
邻居选择策略：
- 使用启发式算法选择最优邻居
- 通过距离和已有连接关系进行筛选
- 保持图的连通性和搜索效率

核心算法流程

构建过程

网络构建算法通过将存储的元素一次插入图结构中进行组织。

构建算法在原始论文的Algorithm 1中给出，伪代码如下：

INSERT(hnsw, q, M, Mmax, efConstruction, mL)
输入：

multilayer graph hnsw: 多层图 hnsw
new element q: 新元素 $q$
$M$: 已建立连接的数量 $M$
$M_{\text{max}}$ : 每层中每个元素的最大连接数 $M_{\text{max}}$
size of the dynamic candidate list efConstruction: 动态候选列表的大小 $efConstruction$
normalization factor for level generation $m_L$: 层级生成的归一化因子 $m_L$

输出：

update hnsw inserting element q: 更新后的 hnsw，插入了元素 q

W ← ∅ // 当前找到的最近邻元素列表
ep ← get enter point for hnsw // 获取 hnsw 的进入点
L ← level of ep // ep 的层级（hnsw 的顶层）
l ← ⌊-ln(unif(0..1))∙mL⌋ // 新元素的层级
for lc ← L … l+1
    W ← SEARCH-LAYER(q, ep, ef=1, lc) // 在层 lc 中搜索
    ep ← get the nearest element from W to q // 从 W 中获取与 q 最近的元素
for lc ← min(L, l) … 0
    W ← SEARCH-LAYER(q, ep, efConstruction, lc) // 在层 lc 中搜索
   neighbors ← SELECT-NEIGHBORS(q, W, M, lc) // 使用算法3或算法4选择邻居
   add bidirectionall connectionts from neighbors to q at layer lc // 在层 lc 中从 neighbors 到 q 添加双向连接
   for each e ∈ neighbors // 如果需要，收缩连接
       eConn ← neighbourhood(e) at layer lc // e 在层 lc 中的邻域
       if │eConn│ > Mmax // 如果 e 的连接数超过 Mmax，收缩 e 的连接
           // 如果 lc = 0，则 Mmax = Mmax0
           eNewConn ← SELECT-NEIGHBORS(e, eConn, Mmax, lc) // 使用算法3或算法4选择新的连接
           set neighbourhood(e) at layer lc to eNewConn // 将 e 在层 lc 的邻域设置为 eNewConn
   ep ← W // 更新进入点 ep
if l > L
   set enter point for hnsw to q // 将 hnsw 的进入点设置为 q

搜索过程

算法分析

时间复杂度分析
空间复杂度分析
实际应用场景

代码实现

数据结构设计
算法实现
实现细节

总结与参考

算法优势总结
原始论文引用
扩展阅读资料

Tags: ANN HNSW vector quantization ai machine learning