HNSW论文笔记
HNSW 层次化可导航的小世界
背景就不一一解释了， 主要是为了解决相似性查找的问题。
相关概念介绍
1. Proximity Graph
Proximity Graph 的主要思想是，随机选取一个开始节点， 从这个节点开始搜索它的邻居，找到邻居中和目标节点距离最近的一个， 再以这个邻居开始进行下一轮迭代。
思路很简单的同时，存在着非常多的问题，最为关键的就是搜索复杂度无法确定，孤岛效应难以解决，以及构建图的开销太高，复杂度达到了指数级别。
2. 可导航的小世界模型
Navigable small world models 的主要思想是：我们把库中的节点随机插入图中，每次插入节点的时候都找图中和被插入节点最近的M个每个节点连边，这样保证了图的连通性。
文章反复提到的对数多项式复杂度实际上是:
$$a_{k}log^{k}(n)+…+a_1log(n)+a_0$$
HNSW算法简单概述
NSW中单个贪心搜索的多对数复杂性的原因在于，总的距离计算次数大致与贪心算法跳转的平均次数与贪心路径上节点的平均度数的乘积成正比。
HNSW的主要思想是根据节点之间连接的长度尺度将图分为不同的层，然后再多层图中进行搜索。
自图1中的最上层开始，这一层有最长的连接(“zoom in”阶段)，算法会利用贪婪的思想，不断从当前层搜索，直至当前这一层中与目标距离最接近的；接着，算法会进入下一层，紧接着重复上面的步骤。不难想到，底层的子图中会包含有上层的节点，因为在跳转的过程中，下一层的搜索是从上一层的结束节点开始的。
最近忙着landing，今天正好周末了，更新一下笔记吧~ 2025.5.24
论文中提到，层与层之间的连接可以被设置为某一个常量。一种构造这种层次结构的措施是：对于图中的每一个节点，我们可以分配一个整型数字l，表示这个节点所在的层数。同时，如果我们设置一种有关l的指数衰减的概率，那么每一层的节点数大致就是以 2 -> 4 -> 8指数的形式来增长的，保证了算法的搜索效率(类似与跳表)。
与NSW不同的是，在节点插入之前，节点不需要被打乱，HNSW的随机性由随机的layer来实现。在节点插入的时候，采用了一种启发式的方法，考虑到所有节点之间的距离而不是仅仅选择距离最近的一个节点。
在图2中，如果插入的节点在Cluster 1的范围中，如果选取距离最近的一个节点来建立连接，那么会破环整个图结构的连接性，文章中说到的启发式的方法将这种情况也考虑到，这样整个图仍旧是一个Delaunay graph，同时防止插入节点与$e_2$的距离要小于Cluster 1中节点距离的情况。
Algorithm 1
图的构建过程是由连续的将候选元素插入到图中实现的：
INSERT(hnsw, q, M, Mmax, efConstruction, mL)
输入参数说明：
- 层次图 $hnsw$
- 新插入的元素$q$
- 已有的连接数$M$
- 每层每个元素的最大连接数$M_{max}$
- 动态候选元素的列表大小 $efConstruction$
- 用于层级生成的归一化因子$m_L$
输出：更新后的$hnsw$
算法流程：
1 $W \leftarrow Ø$ // 当前发现最邻近的节点列表
2 $ep \leftarrow hnsw 的入口节点$
3 $L \leftarrow 入口节点的层级$ // $hnsw$的最高层
4 $l \leftarrow [-ln(uniform(0..1))·m_l]$ // 新节点的层级
5 $for \space l_c \leftarrow L … l+1:$
6 $\quad W \leftarrow SEARCHLAYER(q, ep, ef=1, l_c)$ // searchlayer是Algorithm 2
7 $\quad ep \leftarrow$ 从$W$中获取距离$q$最近的节点
8 $end \space for$
9 $for\space l_c \leftarrow min(L,l)… 0:$
10 $\quad W \leftarrow SEARCHLAYER(q, ep, efConstruction, l_c)$
11 $\quad neighbors \leftarrow SELECTNEIGHBORS(q, W, M, l_c)$// Algorithm 3 或Algorithm 4
12 $\quad$ 添加从q到neighbors的双向连接
13 $\quad for \space each\space e \in neighbors:$
14 $\quad \quad eConn\leftarrow neighbourhood(e) \space (l_c层)$
15 $\quad \quad if \space |eConn| > M_max:$
16 $\quad \quad \quad eNewConn \leftarrow SELECTNEIGHBORS(e, eConn, M_max, l_c)$
17 $\quad \quad \quad 将l_c这一层的neighbor(e)设置为 eNewConn$
18 $\quad \quad end \space if$
19 $\quad \quad ep \leftarrow W$
20 $\quad end \space for$
21 $if \space l > L$
22 $\quad 将hnsw的入口设置为q$
23 $end\space if$
ps: 2025/9/4
后续也没有再看这个东西了，咕咕咕…