1603.09320_HNSW: Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs¶

总结¶

简介

这篇论文是近似最近邻（ANN）搜索领域的一篇里程碑式的著作，它提出的 HNSW（Hierarchical Navigable Small World） 算法极大地影响了工业界和学术界，至今仍是性能最好的ANN算法之一。
核心内容是：提出了一种名为HNSW的图结构，用于高效、鲁棒地进行近似最近邻搜索
这篇论文是ANNS领域必读的经典论文，其提出的HNSW算法至今仍是许多实际应用的首选方案。
缩略
- ANNS: Approximate Nearest Neighbors Search
- HNSW: Hierarchical Navigable Small World
- LSH: locality-sensitive hashing

在高维空间中，精确最近邻搜索（“找到绝对最近的点”）的计算成本非常高，被称为“维度灾难”。因此，实际应用中通常使用近似最近邻搜索（ANNS），其目标是“以极高的概率找到足够近的点”，同时牺牲一点点精度来换取巨大的速度提升。

在HNSW之前，主流ANNS方法包括：

论文指出，这些方法在查询效率、内存使用、鲁棒性（对不同数据分布的适应性）和易用性（需要调优的参数多少）之间难以取得最佳平衡。

HNSW并非完全从零开始，它是对 NSW（Navigable Small World） 图的重大改进。其核心创新在于引入了层次化结构。

NSW（可导航小世界图）是什么？ NSW受启发于人类社会的“六度分隔理论”。它构建的图同时具有短链（连接邻近节点的边，保证局部精度）和长链（连接遥远节点的边，保证全局搜索能力，避免陷入局部最优）。搜索时，从一个或多个入口点开始，像“贪婪的登山者”一样，沿着图不断走向更接近查询点的邻居，直到无法更接近为止。
NSW的缺点： 为了应对各种查询，NSW需要足够多的“长链”，但这使得图的平均度数变高，增加了计算复杂度。对于所有数据点都放在同一层的图，搜索路径可能很长，效率不够极致。
HNSW的解决方案：分层 HNSW的核心是将一张图变成了多层结构（类似于跳表SkipList的思想）。
- 第0层：包含所有数据点。
- 更高层（第1, 2, …层）：是下面一层的随机子集，数据点越来越少。层数越高，图中的“长链”作用就越明显。
- 构建规则：一个新元素以指数衰减的概率exp(-ln(M))被插入到上层中（M是一个参数）。这意味着大多数点只在底层，越往上点越少。
（这是一个简化的HNSW结构示意图，展示了从顶层到底层的搜索路径）

查询过程是HNSW高效性的最佳体现。

这种策略的妙处在于：高层结构用很少的点快速定位到查询目标所在的大致区域，避免了在底层进行漫长的全局遍历。底层则负责在这个小区域内进行精细搜索。这大大减少了需要访问的节点数量，显著提升了搜索速度。

构建图的过程与搜索过程类似，也是分层进行的。

为新元素q随机一个最高层l（根据指数衰减概率）。
从顶层开始，找到该层中离q最近的入口点。
沿着层次结构向下，在每一层执行搜索，找到q的efConstruction个最近邻（efConstruction是一个构建参数）。
到达指定的层l后，将q插入到图中，并在每一层（从层l到第0层）为它建立连接。连接的原则是使用启发式连接算法（论文中称为邻居选择启发式），从搜索到的候选集中选择最优的M个邻居进行连接，而不是简单连接最近的几个。这保证了图的良好导航特性（即同时具有短链和长链）。

极高的效率：达到了当时（2016年）的State-of-the-Art（SOTA）性能。查询复杂度可达对数级别（O(log N)），比许多竞争对手快数个数量级。
出色的鲁棒性：对多种数据分布（均匀、聚类、高维等）都能表现良好，不需要针对特定数据集进行大量的参数调优。
强大的通用性：不仅适用于欧氏距离（L2），也适用于余弦相似度、汉明距离等多种度量方式。
简单易用：虽然算法背后理论复杂，但实际需要调节的参数较少（主要是M和efConstruction），易于上手。
丰富的理论分析：论文不仅提出了算法，还提供了详细的理论基础，将其与SkipList和NSW联系起来，并分析了其复杂度和搜索效率。

总而言之，这篇论文的主要内容是：

应用：HNSW因其卓越的性能，被广泛应用于：