HNSW 分层可导航小世界图

Hierarchical Navigable Small World graphs (HNSW）分层可导航小世界图是是一种基于图的近似最近邻（ANN）搜索算法，出自论文“Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs”。

HNSW 和跳表（Skip List）、可导航小世界图（Navigable Small World, NSW）间的关系

HNSW 算法的核心思想是将节点间的链接根据其长度尺度分隔到不同的层级中，然后在多层图结构中进行搜索。通过这种方式，可以仅评估每个节点所需的一定数量的连接，而不受网络整体规模的影响，从而实现对数级的可扩展性。在这种结构中，搜索从具有最长链接的顶层开始（即“放大”阶段）。算法会贪婪地遍历顶层节点，直到达到局部最小值。然后搜索会切换到具有较短链接的下一层，并从上一层中达到局部最小值的节点重新开始，这一过程会重复进行。所有层级中每个节点的最大连接数可以保持恒定，从而使得在可导航的小世界网络中的路由复杂度能够实现对数级缩放。

为什么说 HNSW = Skip List + NSW？

跳表是一种能够快速搜索、插入和删除元素的数据结构。跳表是一个多层结构，每一层都是一个有序链表，除了第 0 层以外，每一层中仅包含整个链表表中的部分节点，每个节点除了有一个指向下一个节点的指针外，还可能被添加指向更高层级链表（节点所属层级基于特定概率分布随机生成）中下一个元素的指针。跳表通过引入“随机”的跨层级链接，使得在搜索过程中，能够跳过部分节点，从而加速搜索过程。HNSW 借鉴了 Skip List 的分层的概念，区别在于每一层都被替换为了一个 NSW 图。

可导航小世界（NSW）是一种基于“接近图”结构实现的近似最近邻搜索算法。NSW 图在构建过程中，首先随机的从待插入节点中选择一个节点 q，在插入 q 后通过特殊的搜索算法（一种具有多个随机入口节点的贪心搜索变体）找到 M 个先前插入的节点，在节点 q 和这 M 个节点间建立邻居关系。通过这种方式，在初期插入的节点的最近邻居间的链接成为整个图结构中的“桥梁”，这些桥梁能够保持了整个图的连通性，使得贪婪搜索过程中实现对数级的跳数缩放。要注意的是，在 HNSW 中，并不像 NSW 一样会以随机顺序插入节点，而是通过使用特定的概率分布将节点分配到不同的层级（类似跳表中的思路）来实现随机性。

HNSW 的实现

以下内容摘自论文：

插入目标节点 q

：

/**
 * 入参:
 *   hnsw: HNSW 结构
 *   q: 待插入节点
 *   M: 已建立的连接数量
 *   Mmax: 特定层级的节点的最大连接数量
 *   efConstruction: 动态候选节点列表
 *   mL: 确定节点所属层级的参数
 * 输出: 更新后的 hsnsw
 **/
INSERT(hnsw, q, M, Mmax, efConstruction, mL):
  W ← ∅ // 已找到的最近邻列表
  ep ← get enter point for hnsw // HNSW 的入口点
  L ← level of ep // HNSW 的顶层
  l ← ⌊-ln(unif(0 ... 1))*mL⌋ // 确定新节点所在的层级
  for lc ← L ... (l+1) // 从最高层级到节点所在层级的上一层级
    W ← SEARCH-LAYER(q, ep, ef=1, lc) // 从 ep 在 lc 层级中的邻居中寻找 q 的最近邻（ef=1，候选节点数量 1）
    ep ← get the nearest element from W to q // 将找到的节点作为新的入口点
  for lc ← min(L, l) ... 0 // 将节点插入其所在层级其下层级
    W ← SEARCH-LAYER(q, ep, efConstruction, lc) // 从 ep 在 lc 层级中的邻居中寻找 q 的最近邻（ef=efConstruction，候选节点数量 efConstruction）
    neighbors ← SELECT-NEIGHBORS(q, W, M, lc) // 从 W 中寻找 q 在 lc 层的邻居
    add bidirection all connectionts from neighbors to q at layer lc // 建立邻居关系
    for each e ∈ neighbors // 针对该层中 q 的邻居节点，确保这些邻居节点的最大邻居数量不超过 Mmax（第 0 层为 Mmax0）
      eConn ← neighbourhood(e) at layer lc
      if │eConn│ > Mmax
        eNewConn ← SELECT-NEIGHBORS(e, eConn, Mmax, lc)
        set neighbourhood(e) at layer lc to eNewConn
    ep ← W // 更新入口点
  if l > L
    set enter point for hnsw to q
📋

在特定层级中的搜索目标节点的邻居的候选节点

：

/**
 * 入参:
 *   q: 目标节点
 *   ep: 该层的入口节点
 *   ef: 返回的 q 的最近邻个数
 *   lc: 所属层级
 * 输出: q 的 ef 个最近邻
 **/
SEARCH-LAYER(q, ep, ef, lc):
  v ← ep // 已遍历的节点
  C ← ep // 候选节点集合
  W ← ep // 最近邻动态列表（最大节点个数为 ef）
  while │C│ > 0
    c ← extract nearest element from C to q // 从 C 中找到距离 q 最近的节点
    f ← get furthest element from W to q // 从 W 中找到距离 q 最远的节点
    if distance(c, q) > distance(f, q) // 比较 c 和 f 的距离，如果 c > q，则达到局部最小值，终止查找
      break // all elements in W are evaluated
    for each e ∈ neighbourhood(c) at layer lc // 针对节点 c 在 lc 层级中的所有邻居
      if e ∉ v // 如果没有检查过
        v ← v ⋃ e // 设置为已检查
        f ← get furthest element from W to q // 从 W 中找到距离 q 最远的节点（后面会讲更近的邻居插入，因此需要重新获取）
        // 如果 e < f 或者 W 的大小小于 ef 则将 e 加入到 C 和 W 中
        if distance(e, q) < distance(f, q) or │W│ < ef
          C ← C ⋃ e
          W ← W ⋃ e
          if │W│ > ef // 如果加入后 W 的大小大雨 ef，则将 W 中 q 的最远的邻居移除
            remove furthest element from W to q
  return W
📋

从候选节点中查找目标节点 q 的最近邻

：

/**
 *  入参:
 *    q: 目标节点
 *    C: 候选节点列表
 *    M: 需要选择的邻居的个数
 *    lc: 当前层级
 *    extendCandidates: 是否需要拓展候选节点列表
 *    keepPrunedConnections: 是否需要将“丢弃”的节点返回
 * 返回: 启发式搜索得到的 M 个节点
 **/
SELECT-NEIGHBORS-HEURISTIC(q, C, M, lc, extendCandidates, keepPrunedConnections):
  R ← ∅ // 返回的节点列表
  W ← C // 候选节点队列
  if extendCandidates // 将候选节点的邻居也加入到 W 中
    for each e ∈ C
      for each eadj ∈ neighbourhood(e) at layer lc
        if eadj ∉ W
          W ← W ⋃ eadj
  Wd ← ∅ // 被“丢弃”的候选节点列表
  // 遍历候选节点队列 W，并保证返回的列表 R 的大小小于 M
  while │W│ > 0 and │R│< M
    // 从 W 中寻找 q 的最近节点 e
    e ← extract nearest element from W to q
    // 如果 e 距离 q 的距离比 R 中所有的节点都近，则将 e 插入 R 中，否则将 e 丢弃
    if e is closer to q compared to any element from R
      R ← R ⋃ e
    else
      Wd ← Wd ⋃ e
  // 如果 R 的大小小于 M，则使用 Wd 中离 q 更新的节点填充 R
  if keepPrunedConnections
    while │Wd│> 0 and │R│< M
      R ← R ⋃ extract nearest element from Wd to q
  return R
📋

在 HNSW 中查找 q 的 K 个最近邻

：

/**
 * 入参:
 *   hnsw: 建立好的 HNSW 结构
 *   q: 带查找节点
 *   K: 需要返回的 K 个最近邻
 *   ef: 搜索过程中候选节点列表的最大大小
 * 返回: q 的 K 个最近邻节点
 **/
K-NN-SEARCH(hnsw, q, K, ef):
  W ← ∅ // 当前的最近邻
  ep ← get enter point for hnsw // HNSW 入口节点
  L ← level of ep // HNSW 的最高层级
  for lc ← L ... (l+1) // 从最高层级到节点所在层级的上一层级
    W ← SEARCH-LAYER(q, ep, ef=1, lc) // 从 ep 在 lc 层级中的邻居中寻找 q 的最近邻（ef=1，候选节点数量 1）
    ep ← get the nearest element from W to q // 将找到的节点作为新的入口点
  // 在第 0 层搜索最近邻
  W ← SEARCH-LAYER(q, ep, ef, lc=0)
  return K nearest elements from W to q
📋

一个 Rust 实现的示例代码（仅供参考）。