Written by Shi Yinong
on 

NSW算法介绍

在向量检索那篇文章中提到了，基于图的向量索引是当前工业界中使用最多，更具体一点，其实使用的都是HNSW索引。HNSW其实是NSW的一个升级版本， 所以想了解HNSW，首先就要先了解NSW，本篇文章就来介绍下NSW。

一、NSW是什么

Navigable Small World(NSW)，严格来说并不是一种算法，而是图的一种特性，当一种图在使用贪心搜索算法进行搜索时，具有对数级别的时间复杂度， 那么就称这种图具有NSW特性。

二、如何构建NSW

构建NSW的算法有很多种，本篇文章基于一篇paper（Approximate nearest neighbor algorithm based on navigable small world graphs）来介绍， 之所以选择这篇paper，是因为HNSW正是在该paper上优化改进而来的，并且这两份work的作者也都是同一人。

1. 图结构

图中的边分为两部分：

  1. 短边：用于精确搜索，如下图中黑色边。
  2. 长边：用于维持图的NSW特性，能够加速搜索，如下图中的红色边。

构建图时，需要将节点逐个插入，在图结构中寻找待插入节点的邻居节点，并建立双向连接。在构建初期，节点数量较少，因此很容易形成长边。 随着图中节点不断增加，新插入节点形成长边的概率越来越低。

2. 搜索算法

伪代码如下所示：

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       // check stop condition:
9       if c is further than k-th element from result
10      then break repeat
111     // update list of candidates:
12      for every element e from friends of c do:
13          if e is not in visitedSet than
14              add e to visitedSet, 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

其实就是个简单的贪心搜索算法，有两个关键点：

entry point的获取

entry point是随机获取的，因此无法保证精度。所以作者建议要进行m次的搜索，以保证精度。

搜索的终止条件

我们称query point为点q，candidate list中距离q最近的点为点c，result list中距离点q最远的点为点r，如果 c和q的距离 大于 r和q的距离，那么搜索终止。该终止条件的理论依据是：candidate list中最优的点仍然比不上result list中最差的点， 因此就没有必要再去遍历candidate list的所有点了。

看到这里其实很多人会有疑问，点c与q的距离大于r和q的距离， 但c的邻接点与q的距离可能小于r和q的距离，甚至candidate list中其他节点的邻接点与q的距离，也可能小于r和q的距离， 在这里直接终止搜索，岂不是会丢弃一些更优的节点？

其实这正是该算法的精妙所在，如果不设置该终止条件，确实能够获取到更精确的topK结果，但该搜索算法也将会遍历图中所有的节点。 之所以称之为贪心算法，正是因为设置了终止条件，只能够找到局部最优解，虽然这并不是全局最优解，但仍能以牺牲小部分的精度为代价， 获得大幅的性能提升。

3. 插入算法

在上文中提到了，插入节点就是在图中寻找待插入点的F个邻居节点，然后给他们建立双向链接。搜寻待插入点的邻居节点的方法，直接使用上面提到的搜索算法即可。 这样构建出的图的边长分布，恰好符合指数分布。

4. 代码实现

这里给出一个golang版本的代码实现：

https://github.com/shiyinong/hnsw-go/blob/main/algo/nsw/nsw.go

三、我的理解

1. 时间复杂度

关于时间复杂度，论文中给出了实验数据如下所示，横坐标为数据集大小，左纵坐标为搜索时计算距离的次数，右纵坐标为m参数的取值， 固定dim=20; recall=99.9%：

横坐标为指数增长坐标轴，纵坐标为正常的线性坐标轴，观察黑色折线可以清晰的看到时间复杂度为$log^2(n)$

2. 边长分布

边长分布这一点是论文原文中没有提到的，这里我使用上面给出的golang版本实现进行实验，随机构造100万个8维向量，向量元素取值(0, 1)，使用欧氏距离作为长度的度量， 理论上的link长度应该在[0, 2.828]之间。实际边长分布如下图所示，横坐标为边长，纵坐标为边的数量：

可以看到长边和短边的数量是差不多的，可以认为是同时兼顾了搜索的精度和速度。

3. 节点类型

这一点论文原文中同样没有提到。因为插入新节点时，不断地在和老节点建立双向连接，因此会存在一些节点的邻接点数量特别多。 同样使用golang版本进行实验，随机构造100万的8维向量作为实验数据，得到的实际的临界点数量分布如下图所示，横坐标为邻接点数量，纵坐标为拥有该邻接点数量的节点个数：

f参数设置为2倍dim，即16，因此邻接点的数量最小是16。经统计，平均的节点邻接点数量为32，90%的节点的邻接点数量小于50，99%的节点邻接点数量小于100，

基于此，可以将节点分为两类：

  1. 普通节点：绝大部分节点都是普通节点，它的邻接点数量较少，可以快速的顺着一个方向找到局部最优解。
  2. 中心节点：极少数的节点是中心节点，它的邻接点数量较多，可以遍历很多个不同的方向，最终找到最优的搜索方向。

4. 高维退化

该算法仍然无法避免curse of dimensionality，论文原文中给出的实验数据如下，横坐标为数据集大小，纵坐标为搜索时遍历到的节点数量比例，固定recall=99.9%。

可以看到随着维度的增加，遍历节点的比例增长很大。100万的数据量，维度为5维时遍历节点比例为0.1%，而50维时遍历节点比例达到了8%，高维退化严重。

5. 节点插入顺序问题

注意到，图中的长边是在构建图的初期形成的，因为图中节点数的较少时，新插入的节点搜索邻居很容易搜索到比较远的节点，而随着图中节点数的增加，搜索到的邻居就越来越近了。当然，要想达到上面那种情况，所插入点的顺序必须是乱序的，否则就无法形成上面所述的长边了。

想象一下，在二维的向量空间中，我们插入点的顺序如果是从左到右从上到下这样按序插入，那么每次插入的新节点搜索到的邻居都是距离它非常近的节点，那这样构建的图显然无法具有NSW的特性。

四、总结

NSW图的搜索逻辑，很符合我们的直觉：

  1. 通过“中心节点”来寻找最优的搜索方向；
  2. 通过“普通节点”来顺着一个方向来深入搜索；
  3. 通过“长边”加速搜索；
  4. 通过“短边”精确搜索。

优点

  1. 算法本身非常简洁，只需要很少量的代码即可实现。
  2. 搜索效率和召回率都还可以，比基于树的算法要好很多。

缺点

  1. 构建图时，节点必须乱序插入，否则会导致无法生成长边，导致无法生成NSW特性。
  2. 随机获取entry point导致了查询精度无法保障，因此一次查询需要m次的搜索。
  3. 随着维度升高，性能衰退比较厉害。