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

* 首页: <https://arxiv.org/abs/1603.09320>
* PDF: <https://arxiv.org/pdf/1603.09320.pdf>
* 引用: 2323(2025-09-20)
* 组织: 
    * 俄罗斯科学院应用物理研究所

## 总结

**总结方式**
* From Deepseek:
    * Prompt
    * 论文标题《xxxxx》地址：https://xxxx 给我讲解下这篇论文主要讲了哪些内容？
* From Deepseek 全文总结
    * 帮我理解下这篇论文（请按章节分段讲解）：<全文内容>





## From Deepseek


### 1. 研究背景

*   **K-近邻搜索（K-NNS）**：给定一个距离函数，找到与查询最接近的 K 个元素。它是许多AI应用（如推荐系统、图像检索、语义搜索）的核心基础。
*   **问题**：
    *   **朴素做法（线性扫描）**：需对所有元素计算距离 → **线性复杂度 O(N)**，对于百万、十亿级别的大规模数据，计算成本完全不可接受。
    *   **精确方法（树结构等）**：如KD-Tree、R-Tree等在低维空间有效，但在高维场景下因 **“维度灾难”（Curse of Dimensionality）** 而效果急剧下降，其性能甚至退化为接近线性扫描。
*   **解决方案**：近似最近邻搜索（K-ANNS） → 牺牲少量精度以换取巨大的速度提升。用 **召回率（recall）**（即算法找到的最近邻中有多少是真正的最近邻）来衡量质量。
*   **已有方法**：
    *   **树结构（KD-tree, Annoy等）**：在高维空间分割效率低。
    *   **LSH（Locality-Sensitive Hashing）**：通过哈希函数将相似点映射到同一桶中，但为了达到高召回率需要构建多个哈希表，内存消耗大。
    *   **PQ（Product Quantization）**：通过向量量化压缩数据，减少距离计算成本，但是一种有损压缩，精度有上限。
    *   **基于近邻图（proximity graph）** 的方法：如NSW（Navigable Small World），在高维表现好，但其**搜索路径可能很长**，且在**低维或具有聚类结构的数据下性能不够稳定**，容易陷入局部最优。

---

### 2. HNSW 的提出

*   论文提出 **Hierarchical Navigable Small World (HNSW)**，旨在解决NSW等图的局限性：
    *   它是一种**完全基于图的结构**，将 coarse search 和 fine search **统一在了同一个图结构框架内**，无需额外的第一步粗筛。
    *   核心创新是在 NSW 的基础上引入了 **分层（hierarchy）** 和 **更智能的邻居选择策略（heuristic neighbor selection）**。
*   **核心思想**：
    1.  构建一个 **多层次（multi-layer）的近邻图**。底层（第0层）包含所有数据点，上层则像“高速公路”网络，点越来越稀疏。
    2.  每个元素存在的最高层由 **随机选择** 决定，服从指数衰减分布（参数为 `mL`）。这意味着只有少数点能出现在高层（类似 skip list），保证了高层的稀疏性。
    3.  高层包含**长程边（long-range links）**，用于快速、粗粒度的跳跃；低层包含**短程边（short-range links）**，用于精细、准确的搜索。这形成了 **尺度分离（scale separation）**，是性能提升的关键。
    4.  **查询时（自上而下的贪婪搜索）**：
        *   从最高层的某个入口点开始，利用“高速公路”快速定位到查询点所在的大致区域。
        *   然后**逐层往下**，以上一层找到的最远点作为本层的搜索起点。
        *   在每一层内，采用**贪婪搜索算法**（寻找更近的邻居），直到无法更近为止。
        *   这种策略将复杂度降低到了 **对数级（logarithmic scaling）**。

---

### 3. 算法原理

*   **分层结构（详细说明）**
    *   **上层（如L3, L2）**：点稀疏，边多为长程连接。作用类似于“机场航线”，实现跨区域的快速移动，**主要负责搜索速度**。
    *   **中层（如L1）**：点和边的密度适中，起到承上启下的作用，逐步缩小搜索范围。
    *   **下层（L0）**：包含所有点，边非常稠密，连接着最近邻。作用类似于“城市道路”，进行最终的精细搜索，**主要负责搜索精度**。
*   **邻居选择启发式（Simple Heuristic）**
    *   在插入新点`q`时，不是简单地连接最近的`M`个点，而是采用一种**贪心策略来最大化地覆盖空间**。
    *   算法会遍历已找到的候选邻居，仅当新点`q`到候选点`c`的距离小于`c`到当前已选邻居集合中任何一点的距离时，才将`c`加入连接列表。这保证了新连接的边能带来新的信息，**避免了图的边过度稠密和冗余**，提升了搜索效率。
*   **与 Skip List 的类比与区别**
    *   **高度相似性**：两者都通过指数分布随机分配节点层高，都利用高层结构加速搜索。
    *   **核心区别**：Skip List 的每一层是**有序的线性链表**，而 HNSW 的每一层是一个**近邻图（Graph）**。图结构比链表包含了更多的局部连接信息，因此在复杂的高维空间中导航能力更强、效率更高。

---

### 4. 实验与性能评估

*   **数据集**：使用了多个标准数据集以证明其普适性。
        *   **SIFT1M**：图像局部特征描述子。
        *   **GloVe**：文本词向量。
        *   **DEEP1B**：深度学习模型提取的图片特征（十亿级别）。
*   **对比方法**：与当时主流方法全面对比，包括**NSW（其前身）、FLANN（基于树）、Annoy（基于树）、LSH、PQ** 以及其变种。
*   **结果**：
    *   **全面领先**：在相同的召回率（Recall）下，HNSW 的**每秒查询次数（QPS）** 远高于其他竞争对手，实现了 **“高召回率 + 高速度”** 的最佳平衡。
    *   **鲁棒性验证**：即使在 NSW 性能表现很差的低维或特定结构数据集上，HNSW 凭借分层结构依然能取得优异性能。
    *   **增量构建**：支持动态插入新点，无需重建整个索引，非常适用于流式数据或在线学习场景。
    *   **副产品价值**：论文指出，在构建过程中，最底层的图本身就是一个高质量的**近似 k-NN 图**，而邻居选择过程则生成了**近似相对邻域图（RNG）**，这些图本身在其他机器学习任务中也有很大价值。

---

### 5. 讨论（优势 / 不足 / 改进方向）

#### ✅ 优势

1.  **性能卓越**：实验数据充分证明，其在**高维数据**上的综合性能（速度+精度）大幅超越同期SOTA方法，成为了新的性能标杆。
2.  **通用性与鲁棒性**：适用于任何**度量空间**（只需定义距离函数），不依赖于数据的特定分布或领域知识。
3.  **增量性**：支持动态插入数据，为在线应用提供了可能。
4.  **副产品价值**：构建过程天然生成近似 k-NN 图和 RNG 图。

#### ⚠️ 不足 / 挑战

1.  **内存消耗**：图结构需要存储大量指针（边），相较于纯量化方法（如PQ），内存 footprint 较高。
2.  **参数调优**：层间最大连接数 `M` 和搜索时的动态列表大小 `efConstruction`/`efSearch` 对性能和结果影响大，需要根据数据集进行微调。
3.  **分布式扩展性差**：搜索算法本质是**顺序的、逐层递进的**，必须从顶层开始，难以像LSH或倒排索引那样直接进行高效的并行化或分布式部署。

#### 🚀 未来改进方向 (后续研究的印证)

1.  **参数自适应**：后续研究（如DiskANN）提出了根据节点局部密度自适应调整`M`值的方法，以优化内存和性能。
2.  **超大规模验证**：论文呼吁在更大规模（如1B SIFT、1B DEEP）上验证，如今HNSW及其变种已成为处理十亿级数据集的主流选择。
3.  **支持删除**：原论文不支持删除，后续有一些研究工作（如设置“墓碑”标记）来实现软删除功能。
4.  **分布式方案**：借鉴 **跳表的分布式思路** 或与其他分布式索引结构结合（如将其作为每个分片内部的索引），是解决其分布式短板的方向。

---

### 6. 结论

*   HNSW 通过巧妙地结合 **分层结构** 和 **启发式邻居选择**，成功改进了 NSW，实现了**对数级的搜索复杂度**和**极高的鲁棒性**。
*   它在 **高维、复杂结构、多样化的数据集** 上都展现出了最优或接近最优的性能，很好地解决了高维近似最近邻搜索的核心痛点。
*   其思想简洁而强大，尤其适合 **大规模实际应用**（图像检索、文档检索、机器学习特征匹配、推荐系统等），至今仍是工业界和学术界广泛采用的基准算法和首选方案之一。
*   其最大的不足在于 **原生分布式能力**，但这为其后续的发展和完善提供了明确的方向。




## From Deepseek 全文总结

### 摘要 (Abstract)
*   **核心贡献**: 论文提出了一种新的近似K近邻搜索方法，称为**分层可导航小世界图**。
*   **核心思想**: 该方法完全基于图结构，不需要像其他图方法那样依赖额外的辅助搜索结构（如kd-tree）进行粗搜索。
*   **结构构建**: HNSW**增量地**构建一个**多层**结构，每一层都是存储元素的一个子集的近邻图。一个元素出现在哪一层是**随机选择**的，其概率分布呈**指数衰减**。
*   **优势**:
    1.  **链接分离**: 将不同距离尺度的链接分离到不同层。
    2.  **搜索策略**: 从顶层（长链接）开始搜索，利用尺度分离，相比之前的NSW方法性能更高。
    3.  **复杂度**: 实现了**对数级**的搜索复杂度。
    4.  **启发式策略**: 采用了一种选择近邻的启发式方法，在高召回率和数据高度聚类的情况下显著提升性能。
*   **性能**: 评估表明，这个通用的度量空间搜索索引**显著优于**之前开源的、仅适用于向量空间的先进方法。
*   **分布式**: 该算法与跳表结构相似，可以很容易地实现**分布式**部署。

### 1. 引言 (INTRODUCTION)
*   **背景**: 信息量的不断增长对可扩展、高效的相似性搜索数据结构提出了高需求。K近邻搜索是常用方法，但暴力搜索（计算查询点与所有点的距离）的复杂度随数据量线性增长，无法用于大规模数据集。
*   **现有方法**:
    *   **精确方法**: 仅在低维数据中有效，受“维度灾难”限制。
    *   **近似方法**: 放松精度要求，允许少量错误。主流方法包括：
        *   近似树算法
        *   局部敏感哈希
        *   乘积量化
        *   **近邻图算法**: 在高维数据集上表现更好，但其路由过程遵循幂律分布，在低维或聚类数据上性能会急剧下降。
*   **本文方案**: 提出HNSW，一种全新的、完全基于图的、增量式的K-ANNS结构，能提供更好的**对数级复杂度**。
*   **主要创新点**:
    1.  显式选择图的入口点。
    2.  按不同尺度分离链接。
    3.  使用先进的启发式方法来选择邻居。
*   **另一种视角**: HNSW也可以看作是**跳表结构**的扩展，用近邻图代替了链表。
*   **性能**: 在通用度量空间中，性能**强于**之前仅适用于向量空间的开源方案。

### 2. 相关工作 (RELATED WORKS)
*   **2.1 近邻图技术**:
    *   大多数图算法都是在k-NN图上进行**贪婪路由**。搜索从一个入口点开始，迭代地移动到当前节点的最近邻，同时记录遇到的最佳邻居，直到满足停止条件。
    *   k-NN图是对Delaunay图（能保证贪婪搜索总能找到最近邻）的近似，但Delaunay图难以直接构建。
    *   k-NN图方法的**缺点**:
        1.  路由步数随数据集大小呈**幂律缩放**。
        2.  可能失去全局连通性，在聚类数据上表现差。
    *   **NSW (Navigable Small World)**:
        *   通过按**随机顺序**插入元素来构建图，每个新元素与之前已插入元素中的M个最近邻双向连接。
        *   最早插入的元素之间的连接后来成为连接网络中枢的“桥梁”，保持了图的全局连通性，实现了路由步数的**对数缩放**。
        *   易于并行化，无需全局同步。
        *   但复杂度仍然是**多对数级**，在低维数据上性能可能比树方法差几个数量级。
*   **2.2 可导航小世界模型**:
    *   介绍了复杂网络理论中的**可导航小世界网络**（路由步数为对数或多对数级）。
    *   **Kleinberg模型**: 在规则网格上添加遵循特定分布的长链接，当分布参数α等于维度d时，网络是可导航的。但需要预先知道数据分布。
    *   **无标度模型**: 具有现实网络的一些特征，但路由复杂度是幂律的，同样需要全局知识。
    *   **NSW模型**: 使用了一种更简单、未知的模型，允许去中心化图构建，适用于任意空间。但其搜索复杂度仍是多对数级。

### 3. 动机 (MOTIVATION)
*   **NSW的搜索过程分析**: 分为“放大”和“缩小”两个阶段。
    *   **放大阶段**: 从低度节点开始，遍历图，同时节点度数逐渐增加，直到链接的特征长度尺度接近到查询点的距离。在此阶段，平均度数较低，容易陷入局部极小值。
    *   **从Hub开始**: 从高度数节点（Hub）开始搜索可以直接进入“缩小”阶段，提高成功率，但复杂度仍为多对数级。
*   **HNSW的改进思路**:
    *   **问题根源**: NSW的总计算量 ≈ 平均跳数 × 路径上节点的平均度数。两者都随网络规模对数增长，导致多对数复杂度。
    *   **解决方案**: 将链接按长度尺度**分离到不同的层**，在多层图中搜索。这样每层只需评估固定数量的连接，与网络大小无关，从而实现**对数复杂度**。
    *   **搜索过程**: 从顶层（只有长链接）开始贪婪搜索，找到局部极小值后，**下降到下一层**，并从该点重新开始搜索，如此往复，直到最底层。
*   **层分配**: 为每个元素随机分配一个整数层级`l`（遵循指数衰减的几何分布），这决定了它出现的最高层。这带来了**真正的增量索引**能力。
*   **与跳表的关联**: HNSW非常类似于**跳表**，只是用近邻图替代了链表。
*   **启发式邻居选择**:
    *   插入元素时，不是简单选择最近的M个邻居，而是使用一种**启发式方法**：从一个候选集中，仅当候选点比已连接的所有点都更接近插入点时，才将其连接。
    *   这种启发式方法有助于保持**全局连通性**，即使在高度聚类的数据中（如图2所示），类似于构建相对邻域图。

### 4. 算法描述 (ALGORITHM DESCRIPTION)
*   **算法1: INSERT (插入)**:
    *   为待插入元素`q`随机选择一个层级`l`。
    *   **自上而下的搜索**: 从顶层到`l+1`层，每层进行`ef=1`的贪婪搜索，找到该层离`q`最近的点，作为下一层的入口点。
    *   **自下而上的插入**: 从`min(L, l)`层到0层：
        1.  用`efConstruction`参数在该层搜索`q`的最近邻（候选集`W`）。
        2.  使用**算法3（简单）**或**算法4（启发式）**从`W`中选择`M`个邻居与`q`连接。
        3.  如果邻居的连接数超过`Mmax`，则对其进行“修剪”（同样用算法3或4）。
*   **算法2: SEARCH-LAYER (层内搜索)**:
    *   在指定层`lc`上搜索`q`的`ef`个最近邻。
    *   维护一个动态列表`W`（当前找到的最近邻）和一个候选集`C`。
    *   不断从`C`中取出离`q`最近的点`c`，检查其邻居，更新`W`和`C`，直到`C`为空或无法找到更近的点。
*   **算法3: SELECT-NEIGHBORS-SIMPLE (简单邻居选择)**:
    *   直接从候选集`C`中选择离`q`最近的`M`个点。
*   **算法4: SELECT-NEIGHBORS-HEURISTIC (启发式邻居选择)**:
    *   从候选集`C`中按距离顺序处理。
    *   仅当候选点`e`比结果集`R`中的所有点都更接近`q`时，才将其加入`R`。
    *   这样可以确保连接指向**不同的方向**，增加多样性。
    *   可选扩展候选集（检查候选的邻居）和保留被修剪的连接。
*   **算法5: K-NN-SEARCH (K近邻搜索)**:
    *   类似于插入过程，但只为`l=0`的元素搜索。
    *   从顶层开始，每层做`ef=1`的搜索，找到入口点。
    *   在底层（0层）进行`ef`参数较大的搜索，返回结果。
*   **4.1 构建参数的影响**:
    *   `mL`: 控制层级衰减概率。`mL = 1/ln(M)`是一个较好的经验值。增加`mL`在低维数据上提速明显，在高维数据上也有提升。
    *   `Mmax0`: 底层最大连接数。设为`2*M`效果较好。
    *   **启发式 vs 简单选择**: 启发式方法在低维、高召回、聚类数据上优势明显；在高维均匀数据上差异不大。
    *   `M`: 最重要的参数。较小的`M`适合低召回/低维数据；较大的`M`适合高召回/高维数据。也直接影响内存占用。
    *   `efConstruction`: 控制构建时的搜索范围，应设得足够大以保证构建质量（召回率~0.95）。
    *   **并行化**: 构建过程可以高效并行化，同步点少，对索引质量影响可忽略。

### 5. 性能评估 (PERFORMANCE EVALUATION)
*   **实现**: 基于**Non-Metric Space Library (nmslib)**用C++实现。
*   **5.1 与基线NSW比较**:
    *   在低维随机数据上，HNSW的距离计算次数远少于NSW，尤其在**高召回率**时。
    *   复杂度缩放显示，HNSW是**对数级**，而NSW是多对数级，HNSW在任何数据集大小下都优于NSW。
*   **5.2 在欧氏空间中的比较**:
    *   与多个开源先进算法比较：NSW, FLANN, Annoy, VP-tree, FALCONN。
    *   测试数据集：SIFT, GloVe, CoPhIR, 随机向量, MNIST, DEEP。
    *   **结果**: 在大多数数据集上，HNSW都**大幅领先**其他对手。
*   **5.3 在一般度量空间中的比较**:
    *   重复了之前NSW表现不佳的一组测试（非对称或违反三角不等式的距离）。
    *   数据集：Wiki-sparse, Wiki-8, Wiki-128, ImageNet, DNA。
    *   **结果**: HNSW**显著改善了NSW的性能**，在所有测试数据集上都成为领先者。特别是在最低维的wiki-8数据集上，比NSW快了近**3个数量级**，展示了其强大的鲁棒性。
*   **5.4 与基于乘积量化的算法比较**:
    *   与Facebook的**Faiss库**（PQ领域的state-of-the-art）在2亿规模的SIFT数据集上比较。
    *   **结果**: 尽管HNSW占用更多内存，但它能达到**更高的精度**，同时提供**更快的搜索速度**和**更快的索引构建速度**。

### 6. 讨论 (DISCUSSION)
*   **总结**: HNSW通过分解可导航小世界图的结构并使用智能邻居选择启发式，克服了NSW的几个主要问题，推动了K-ANNS的发展。
*   **优势**:
    *   **卓越的性能**: 在各种数据集上都是明显的领导者。
    *   **鲁棒性**: 适用于通用度量空间，无需为特定问题复杂地选择算法。
    *   **增量索引**: 支持连续增量构建。
    *   **副产品**: 可以高效地得到k-NN图和相对邻域图的近似。
*   **未来方向**:
    *   自动推断参数`M`。
    *   在更大规模数据集上测试。
    *   支持元素更新和删除。
*   **缺点与分布式**:
    *   与NSW相比，**失去了原生分布式搜索**的便利性（因为搜索总是从顶层开始，顶层元素需要被所有节点感知）。
    *   但可以借鉴**跳表的分布式技术**来实现HNSW的分布式版本，可能获得更好的性能。

### 7. 致谢 & 8. 参考文献
*   感谢参与讨论、提供帮助和评论的人员及机构。
*   列出了所有引用的相关文献。

---
### 核心总结
这篇论文提出了**HNSW**算法，其核心思想是通过构建一个**多层**的近邻图，将**长距离链接**（用于快速粗定位）和**短距离链接**（用于精细搜索）分离到不同层，并结合一种**启发式的邻居选择方法**来保持图的连通性和多样性。这使得算法同时具备了**极高的搜索效率（对数复杂度）**、**高召回率**、**强大的鲁棒性**（适用于各种维度和数据结构）以及**增量构建**的能力。大量实验证明，它在向量空间和一般度量空间中都显著优于其他先进的近似最近邻搜索算法。