HNSW的基本原理及使用

本文首发于：http://xzyin.top/hnsw/
转载请注明出处:http://xzyin.top/

关注微信公众号：【charlie_mouse】进入技术交流群。

1. Small world vs. Random graph

在正式的介绍NSW和HNSW之前，先来了解一下小世界和随机图的概念方便后续理解为什么NSW能够做近邻查找。

1.1 Regular graph vs. Random graph

在图论中对正则图的定义如下:

正则图是指每个顶点都有相同数目邻居的图，即每个顶点的度相同。若每个顶点的度均为 $k$ ，称为 $k$ -正则图。

正则图

随机图是指在随机过程的生成的图，也就是节点和节点之间的连接是随机建立的。

随机图和正则图的对比

在正则图中，当聚类系数接近饱和的时候，聚类系数比较高，平均路径也比较短，但是此时节点的度比较高。

随机图节点的聚类系数比较低，并且节点的度也比较低。

1.2 Small world

在介绍完了随机图和正则图，我们再来看一下小世界网络。

在1967年Stanley Milgram从Kansas和Nebraska两个州招募了一批志愿者，
请他们分别将一封信转寄给一个住在Cambridge神学院学生的妻子和一个住在Boston郊区的股票经纪人。
他给志愿者们这样的要求：

虽然有寄信目标的相关信息，如果不是私人关系，不能把信直接寄给TA.
每次只能把信寄给最有可能知道这个人的熟人。
原始信封里有15张追踪卡片，每次转寄都要回寄一张给实验者，其他的放在信封里寄给下一个人，这样研究员可以随时追踪这些信函的路径。

在到达的信函中，Stanley Milgram计算信函平均到达的节点为5个，也就是我们和一个陌生人建立连接只需要6步。

Stanley Milgram基于他的实验提出了著名的六度分离理论，这个理论指出:

现实世界中的短路径是普遍存在的。
人们可以有效地找到并且利用这些短路径。

在小世界网络中，可以把点与点之间的关系可以分为两种：

同质性:同质性也就是相似的点会聚集到一起，相互连接具有邻接边。
弱连接:弱连接是指从每一个节点上，会有一些随机的边随机连接到网络中的节点上，这些节点是随机均匀的。

1.3 三者之间的关系

有研究表明，小世界网络介于正则图和随机图之间，正则图随着随机性的增加具有小世界的特性。

在这里插入图片描述

我们可以这么理解：小世界在局部同类节点的连接呈现出规则，从全局来看不同类节点的连接呈现出随机性。
这两种性质也就是上面我们所说的同质性和弱连接。

2. Navigable Small World

可导航小世界的原理很简单，其基本原理如下图所示:

[图片上传失败...(image-f07fbb-1602403656206)]

在NSW算法中通过构建一个小世界网络，希望通过黑色相似的近邻边来检索最近邻节点，
通过红色长边(高速公路)来实现不同类节点之间的快速检索。

这里我们不妨考虑一下，为什么regular graph不能做近邻检索? 为什么random graph不能做近邻检索，为什么small world
可以用来做近邻检索?

2.1 图的检索

在了解完NSW的基本思路之后，接下来我们看一下NSW当中，如何对整个图中的节点查找K个最近邻节点。

K 近邻查找

在NSW中K近邻检索的过程如下:

随机选择1个元素，放入到candidates当中

从candidates中选取最近邻节点c，将这些元素的邻居节点放置到q当中

从candidates中移除最近邻节点c

如果c的距离远大于result中的第k个节点，跳出循环

否则，对于c的每个邻居节点，遍历其邻居，如果没有在visited set里面。

将e加入到visited set， candidates， tempRes

遍历完成candidate中所有的节点后，把tempRes的结果传入到result

重复执行上述步骤m遍, 返回result中最优的k个近邻结果。

具体的伪代码描述如下:

K-NNSearch(object q,integer:m,k)
1   TreeSet[object]tempRes, candidates, visitedSet, result
2   for(i<-0; i<m; i++) do:
3       put random entry point in candidates
4       tempRes<-null
5       repeat:
6           get element c closest from candidates to q
7           remove c from candidates
8           #checks to p condition:
9           if c is further than k-th element from result
10          than break repeat
11          #update list of candidates:
12          for every element e from friends of c do:
13              if e is not in visited Set than
14                  add e to visited Set, candidates, tempRes
15
16      end repeat
17      #aggregate the results:
18      add objects from tempRes to result
19  end for
20  return best k elements from result

2.2 图的构建

基于NSW的原理，我们希望NSW的局部节点之间的在距离上具有同质性(也就是近邻节点能够相互连接)。从而使得当我们检索
到一个近邻节点时，其大部分近邻节点都是近邻节点。同时也希望保留一些随机边，能够在不同区域之间快速跳转。

那么我们需要怎么样构建一个，具有同质性同时又具备随机性的小世界网络呢？

Delaunay 三角剖分

为了使得相邻的点在空间距离上相近，我们引入Delaunay三角剖分，相关的定义如下

Delaunay 边

在点集 $V$ 中存在两点 $a$ 和 $b$ ，圈内不包含点集 $V$ 中的任何其他点。这个特质被称为空圈特质个。
节点 $a$ 和节点 $b$ 连接起来的边称为Delaunay边。

Delaunay 三角剖分

如果一个点集 $V$ 的三角剖分 $T$ 都只包含 Delaunay边，那么该三角剖分称为Delaunay剖分。

[图片上传失败...(image-90a97d-1602403656206)]

NSW节点的插入

构建图的时候，理论上来说我们对所有的点做Delaunay三角剖分，然后添加一些随机的长边构建快速检索通道，
就构建了一个可导航的小世界网络。

由于构建Delaunay三角剖分的复杂度太高实际的代码实现过程中是通过节点随机插入来引入随机性，利用已有节点构建Delaunay边来引入同质性。

NSW的网络构建过程如下:

在候选节点 $V$ 里面随机挑选一个节点 $v_i$
将节点 $v_i$ 插入到已经构建好的图中，并构建边。
边构建的规则：找到节点 $v_i$ 最近邻的 $f$ 个邻居，建立 $v_i$ 和这些邻居的边连接。

对应的伪代码如下:

Nearest_Neighbor_Insert(object: new_object,integer:f, integer:w)
1 SET[object]:neighbors<-k-NNSearch (new_object, w, f);
2 for(i<-0; i<f; i++) do
3   neighbors[i].connect(new_object);
4   new_object.connect(neighbors[i]);

在构建NSW图结构的时候，在局部通过寻找 $f$ 个最近邻来建立类似于Delaunay三角剖分的结构，
在全局通过随机顺序插入，引入随机边从而使得所以具备可导航小世界的特性。

3. Hierarchical Navigable Small World

在NSW中，构建图的阶段通过节点的随机插入来引入随机性，构建出一个类似于小世界的网络结构。在NSW中很明显地会存在
几个问题。

对于最先插入的节点，其连接的邻居节点，基本都比较远(弱连接属性较强)
对于最后插入的节点，其连接的邻居节点，基本都比较近(弱连接属性较弱)
对于具有聚类效应的点，由于后续插入的点可能都和其建立连接，对应节点的度可能会比较高。

等等

如果继承NSW基于long link快速检索，short link具有聚类特性的思想。怎么样能够使得查找更为稳定，
或者怎么样能够把long link的查找和short link查找有效区分。在此基础上引入了分层图的思想。

基于这些问题在NSW的基础上我们来看一下HNSW。

在这里插入图片描述

根据上图可以直接看出HNSW在NSW基础上所作的优化。

在HNSW中，引入Layers的概念，总体思想如下:

在Layer = 0 层中，包含了连通图中所有的点。
随着层数的增加，每一层的点数逐渐减少并且遵循指数衰减定律
图节点的最大层数，由随机指数概率衰减函数决定。
从某个点所在的最高层往下的所有层中均存在该节点。
在对HNSW进行查询的时候，从最高层开始检索。

3.1 HNSW的查询

在HNSW的查询阶段，包括以下几个算法。

SEACHER-LAYER: 在指定层查询K个最近邻节点。
SELECT-NEIGHBORS-SIMPLE: 简单的查找某一层最近的邻居节点。
SELECT-NEIGHBORS-HEURISTIC: 探索式查找某一层最近的邻居节点。
K-NN-SEARCH: 从所有候选结果中找出K个最近邻结果。

接下来，我们来具体看一下这几个算法和对应的具体查询逻辑。

3.1.1 SEACHER-LAYER

算法伪代码

在这里插入图片描述

传入参数

q:表示需要查找的节点

eq: 固定的起始节点，如果Layer是最顶层，有固定的入口节点。如果不是最顶层则是上一层查询到的最近邻。

ef: 查找的邻居节点数目

lc: 查询的层数

输出 :

q元素最近邻的ef个节点。

功能:

SEARCH LAYER算法的功能是在给定一个节点q和起始查询节点eq、查询的层lc的情况下，查找出
节点q在层lc下的ef个最近邻。

查询步骤：

首先根据ep 初始化visited set V, candidate set C, 以及动态最近邻W

当 candidate set 不为空的时候执行:

2.1) 从candidate set C中选取离q最近的点c,

2.2) 从动态最近邻中选取最远的点f,

2.3) 比较distance(c,q)和distance(f,q)

2.4) 如果distance(c,q) > distance(f,q)执行步骤 3 否则继续执行 2.5

2.5) 对在lc层中c节点的每个邻居e。如果e在visited中，重新执行步骤 2, 否则继续执行 2.6

2.6) 将e节点加入visited set

2.7) 从W中获取最远的节点f

2.8) 如果distance(e,q) < distance(f,q) 或者 |W| < ef 将 e分别加入 candidate set C和动态最近邻W

2.9) 如果 |W| > ef 移除最大元素。

返回集合W

3.1.2 SELECT-NEIGHBORS

在select neighbors主要分为两个部分由SELECT-NEIGHBORS-SIMPLE以及SELECT-NEIGHBORS-HEURISTIC两个算法组成。

SELECT-NEIGHBORS-SIMPLE和SELECT-NEIGHBORS-HEURISTIC两个算法都是用在图构建的过程中，而不用在KNN的近邻
检索，与SIMPLE不同HEURISTIC方法添加了更多的随机性，从而同一层节点之间的连接随机性更强。

SELECT-NEIGHBORS-SIMPLE

算法伪代码

[图片上传失败...(image-44c55a-1602403656206)]

参数输入

q:表示需要查询的节点。

C:表示查询的候选节点集合。

M:表示返回最近邻居的个数。

输出

q在C中的M个最近邻居

功能

选取出节点q在候选集C中的M个最近邻居。

SELECT-NEIGHBORS-HEURISTIC

算法伪代码

在这里插入图片描述

参数输入

q:表示我们需要查询的节点

C:表示candidate 节点

M:表示返回的最近邻节点的个数M

lc:表示返回的层的编号

extendCandidates:表示是否需要扩展candidate

keepPrunedConnection:表示是否需要把废弃节点加入到返回结果中

返回结果

通过探索式查找返回最近邻的M个结果。

3.1.3 K-NN-SEACHER

KNN查询的逻辑很简单，从固定的enter节点进入，在顶层开始检索。
在每一层检索到唯一一个最近邻然后作为下一层入口节点。最后在底层检索top K个最相似节点。

算法伪代码

在这里插入图片描述

3.2 HNSW的插入

在HNSW中，通过插入算法来构建整个图结构并在此基础上进行检索。HNSW的插入算法如下。

算法伪代码

在这里插入图片描述

算法参数

hnsw: 节点所需要插入的目标图结构
q: 需要插入的节点
M: 每个节点需要与其他节点建立的连接数，也就是节点的度。
efConstruction: 用来设置查询网络节点集合的动态大小
mL: 用来选择节点q的层数的时候所需要用到的归一化因子。

算法输出

插入节点q后的hnsw网络结构。

节点插入过程

在整个HNSW的insert的过程中包含以下几个部分。

初始化当前最近邻集合W，初始化固定节点ep，获取顶层编号L，获取新插入节点的层l

对于属于L->l+1的每一层查找出q的最近邻节点。

对于lc <- min(L,l)..0的每一层执行以下步骤:

3.1) 每一层查找出最近的efConstruction个节点得到集合M。

3.2) 在每个节点中查找到最近的M个neighbors。(采用算法3,或者算法4)

3.2) 将在层lc中的所有neighbors和节点q建立连接。

3.3) 对于neighbors中的每个节点e重新判断一下节点个数，然后减少e节点的邻居节点重新建立连接。

如果 l > L，将q设置为hnsw的enter point

在上述伪代码中对于每个新节点而言获取器layer id的公式如下。

$l = \lfloor -ln(unif(0,1)) \cdot mL \rfloor$

HNSW通过一个随机函数，将所有的点划分到不同层次，越往上节点数越少，边越少。这种情况下节点和节点之间寻找最近邻居的
距离也就越远。因此在从上到小检索的过程中，先通过Long Link找到全局可能的最近节点，然后往下层以该节点为入口
进一步做局部检索。

4 总结

在这篇文章中，主要介绍了NSW和HNSW的算法原理。NSW算法基于六度分离理论将小世界的特性用于近邻检索，
提出了基于图结构的检索方案。

在NSW的基础上，HNSW利用多层的图结构来完成图的构建和检索，使得通过将节点随机划分到不同的layer，
从上层图到下层图的检索中，越往下层节点之间的距离越近, 随机性也越差，聚类系数越高。
HNSW通过从上到下的检索，完成了NSW中Long Link高速公路快速检索的作用，通过最后底层的近邻检索，
完成局部最近邻的查找。

参考资料

[1] Navigable Small-World Networks

[2] 一文看懂HNSW算法理论的来龙去脉

[3] HNSW学习笔记

[4] 近似最近邻算法 HNSW 学习笔记（一）介绍

[5] 近似最近邻算法 HNSW 学习笔记（二）主要算法伪代码分析

[6] 近似最近邻算法 HNSW 学习笔记（三）对于启发式近邻选择算法的一些看法

[7] Delaunay三角剖分实践与原理

[8] Hierarchical Navigable Small World

[9] Small-World Experiment or Just Six Steps Away off Loneliness…

[10] Navigable Small-World Networks

[11] HNSW学习笔记