小8万事屋
← 返回首页

SIGNAL · POST

HNSW算法与python实现

约 11 分钟阅读 bajiu AI

HNSW 基础

我们可以将 ANN 算法分为三个不同的类别：树、哈希和图。

HNSW 属于图类别中的一种。更具体地说，它是一种接近图(proximity graph)，其中两个顶点根据它们的接近程度（越接近的顶点之间有链接）进行连接，近似距离通常以欧几里德距离来定义。

更具体地说，它是一种**接近图(proximity graph)**，其中两个顶点根据它们的接近程度（越接近的顶点之间有链接）进行连接，近似距离通常以欧几里德距离来定义。

Small world vs. Random graph

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

Regular graph vs. Random graph

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

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

hnsw-1

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

随机图和正则图的对比

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

Small world

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

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

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

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

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

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

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

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

三者之间的关系

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

hnsw-2

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

NSW (Navigable Small World)

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

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

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

图检索

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

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

  1. 随机选择1个元素，放入到 candidates 当中
  2. 从 candidates 中选取最近邻节点 c ，将这些元素的邻居节点放置到q当中
  3. 从 candidates 中移除最近邻节点 c
  4. 如果 c 的距离远大于 result 中的第 k 个节点，跳出循环
  5. 否则，对于 c 的每个邻居节点，遍历其邻居，如果没有在 visited set 里面。
  6. 将 e 加入到 visited set ， candidates ， tempRes
  7. 遍历完成 candidate 中所有的节点后，把 tempRes 的结果传入到 result
  8. 重复执行上述步骤m遍, 返回 result 中最优的 k 个近邻结果。

代码描述：

coding

图构建

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

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

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

  • Delaunay 边 : 在点集 V 中存在两点 a 和 b，圈内不包含点集 V 中的任何其他点。这个特质被称为空圈特质个。 节点 a 和节点 b 连接起来的边称为Delaunay边。
  • Delaunay 三角剖分：如果一个点集 V 的三角剖分 T 都只包含 Delaunay边，那么该三角剖分称为Delaunay剖分。
coding

参考: https://baike.baidu.com/item/Delaunay%E4%B8%89%E8%A7%92%E5%89%96%E5%88%86%E7%AE%97%E6%B3%95/3779918

NSW 构建

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

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

NSW 的网络 构建过程如下:

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

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

HNSW (Hierarchical Navigable Small World)

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

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

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

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

hnsw-4

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

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

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

HNSW的查询

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

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

SEACHER-LAYER

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

步骤:

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

2.当 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 移除最大元素。

3.返回集合 W

SELECT-NEIGHBORS

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

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

  • SELECT-NEIGHBORS-SIMPLE

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

coding
  • SELECT-NEIGHBORS-HEURISTIC

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

coding

K-NN-SEACHER

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

HNSW的插入

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

coding

总结

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

节点插入过程:

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

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

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

3.对于 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 节点的邻居节点重新建立连接。

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

HNSW 要解决的问题：近似最近邻 ANN

目标是给一堆高维向量（embedding），每次查询都要找最相似的 Top-K：

  • 精确做法：全量计算距离，O(Nd)（N=库大小，d=维度）——大了就扛不住
  • ANN：允许一点点误差，换取极快检索（通常毫秒级）

HNSW 属于图索引 ANN：把向量组织成「可导航」的近邻图，查询时像在图上走捷径。

HNSW 的核心直觉：小世界图 + 分层