分层可导航小世界算法（HNSW）原理
引言
随着大语言模型（LLM）与检索增强生成（RAG）技术的普及，向量数据库的热度持续攀升。当前主流的向量数据库（如 Milvus、Weaviate、Chroma、Elasticsearch 等）均支持 HNSW 这一高效的向量检索算法。
正则图和随机图
在介绍 NSW 和 HNSW 之前，我们先来了解一下正则图和随机图的概念，这对于理解为什么 HNSW 能够加快向量检索效率是很有帮助的。
正则图（Regular Graph）
正则图是指各顶点的度均相同的无向简单图。在图论中，正则图中每个顶点具有相同数量的邻点，若每个顶点的度均为 k，称为 k-正则图。
随机图（Random graph）
随机图是指由随机过程产生的图，一个随机图实际上是将给定的顶点之间随机地连上边。
正则图 vs 随机图
- 聚类度衡量的是一个节点的邻居之间相互连接的比例
- 正则图具有较高的聚类系数，一个顶点的邻居节点之间有很多相互连接，任意两个节点之间的平均路径比较长
- 随机图具有较低的聚类系数，邻居节点之间的连接比较少，但任意两个节点之间的平均路径就可能比较短
小世界网络（NSW）
起源
在网络理论中，小世界网络是指一类特殊的复杂网络结构，在这种网络中大部分的节点彼此并不相连，但绝大部分节点之间经过少数几步就可到达。最早观察到小世界现象的是社会人际网络。将每个人作为节点，将人与人之间的人际关系（朋友，合作，相识等）作为链接，就建立起一个社会人际网络。有时你会发现，在这样一个社会网络中，某些你觉得与你隔得很'遥远'的人，其实与你'很近'。二十世纪 60 年代，美国哈佛大学社会心理学家斯坦利·米尔格伦做了一个连锁信实验。他将一些信件交给自愿的参加者，要求他们通过自己的熟人将信传到信封上指明的收信人手里，他发现，296 封信件中有 64 封最终送到了目标人物手中。而在成功传递的信件中，平均只需要 5 次转发，就能够到达目标。也就是说，在社会网络中，任意两个人之间的'距离'是 6。这就是所谓的六度分隔理论。
小世界网络具有以下性质：
- 基于规则图的随机重连过程
- 以一定概率随机重连规则图中的每条边
- 同时具备随机图与规则图的特性
- 高聚类系数
- 低平均路径
但小世界网络还存在以下的问题：
- 网络中的任意两个节点都存在最短路径，但我们怎么去找到这个最短路径呢？
- 为什么网络中两个相互独立的节点能够通过最短路径建立连接呢？
边的构建
在 NSW 中，我们希望局部节点之间能够互相连接，也就是说具有同质性，从而使得我们检索到的大部分节点都是邻近节点。但是也希望能够保留一些'长边'（随机边），使得能够在不同的区域之间快速的跳转。
节点 u 与节点 v 之间是通过一定的概率来建立连接的，dim（dimension of the euclidean space）为该空间中的网络维度：
$$P(u \to v) \sim \frac{1}{d(u,v)^r}$$
r 对搜索效率的影响：
- 当
r < dim时算法倾向于选择更远的邻居节点，搜索算法会快速的逼近目标区域，然后速度逐渐的衰减，但最终会找到目标节点 - 当
r > dim时算法会倾向于选择更近的邻居节点，搜索算法会快速的找到较近的目标节点；但目标节点若距离较远，搜索算法会寻找的比较缓慢 - 当
r==0时算法对长距离的连接是随机的，搜索算法不能保证找出最优路径 - 当
r==dim时算法效果最优
当 r==dim 时，节点上远程连接边的个数（n）对搜索的影响：
- 当
n==1时，节点上只有一个远程连接的边，此时的搜索复杂度为O(log² N) - 当
n==k时，节点拥有 k 条长程连接时，搜索成本在原来的最优基础上又降低了约 k 倍。这是因为在每个决策点，你有更多'候选路径'来尝试接近目标节点，搜索复杂度为
