HNSW & NGT-ONNG

2023-06-15 11:47:46

Hierarchical Navigable Small World GraphsSmall world是一种图：大多数节点并不互相连接，但又总能通过某个路径搜索到彼此，且搜索的

Hierarchical Navigable Small World Graphs

Small world是一种图：大多数节点并不互相连接，但又总能通过某个路径搜索到彼此，且搜索的成本相对网络节点数是log复杂度增长的。很多现实世界的图都表现出small world现象，比如社交网络，wiki，Internet，基因，深度特征。世界的本质是小圈子。

就KNN搜索而言，暴力算法复杂度随数据集大小线性增长，毫无疑问不适合大数据集。完全匹配的搜索方法在应用于低维数据时效果理想，高维则远不如近似搜索。

近似方法的召回率即为所找到的真正k近邻数与k的比值。常用近似方法包括近似版本的树算法、局部性敏感的哈希（LSH）、乘积量化（PQ）、临近图。图方法在高维数据上表现很好，但图的本质决定了它的路由复杂度是幂律增长的，这意味着它在低维数据上表现不好。

HNSW是一个比较新的求k近似近邻的纯粹图数据结构。它能提供log复杂度的增长。主要贡献包括：显式选择图的入口节点，根据不同尺度分离连接、用高级的启发式方法。HNSW可视为一种skip list的扩展——只不过把链表换成了临近图。

KNN临近图

所谓临近图，就是一种对图进行KNN搜索，并采样贪婪路由的方法：从某个起点开始，遍历图，每到一处就检验邻居到目标的距离，选择距离最小的作为下一站。

NSW是一种相对数据大小以polylog复杂度增长的临近图，是以谓之navigable。NSW在构建时通过连续以随机顺序插入元素，并双向连接到M个近邻(用一种从多个随机起点开始的贪婪搜索找到这M个近邻）。这一过程可以非常高效地并行化，且不需要全局锁，因此很适合分布式搜索系统。NSW在某些数据集上表现sota，但总体来说由于polylog复杂度，仍会在低维度数据上出现严重地性能下降（相对树方法）。

最早的NSW模型是克莱恩伯格发明，并用于著名的Milgram社会心理学实验（权威服从性测试）给社交网络进行建模的工具。Watts–Strogatz模型是生成随机small world图的模型，克莱恩伯格研究这个模型生成的网络，用一个d-维向量空间内的常规的栅格网络（lattice graph），外加长程连接的增强——这种长程连接的长度是符合(r^-d)分布的。这种方法虽然将路由复杂度降到了polylog（相对原来的power law），却必须事先知道数据的分布。此外polylog也不算特别好。

另一种著名的NSW模型是scale-free models，可复现现实世界网络的多种特征，但这种模型生成的网络搜索起来甚至比贪婪搜索的power law还慢，且与克莱恩伯格模型一样，scale-free模型需要知道数据分布知识——这也意味着不适合搜索应用。

HNSW：按粒度分层搜索

NSW路由可分为zoom-out和zoom-in两个阶段，贪婪算法起始于zoom-out阶段，从一个低degree点开始遍历图，同时增加节点的degree，直到该节点连接长度的特征半径落到到query距离的尺度内。在此之前，节点的平均degree往往维持在非常小的阶段，所以需要zoom-out。

想要跳过zoom-out，可以选一个最高degree的点开始，也就是要找个good candidate——hubs，可直接进入zoom-in阶段，大大提升路由成功率与低维数据上的效率。但这种NSW路由仍然只有最多polylog复杂度。在高维上还不如HNSW。

HNSW的思路是将link根据其长度尺度分离到不同的layer，然后在分层的图里进行搜素。在这种结构中，搜索从最上层开始，最上层只包含最长的links，这就相当于之前NSW路由中的zoom-in阶段。HNSW贪婪遍历上层，直到达到一个局部最小——之后切换到下层，从这个局部最小再开始遍历，只不过用的是更短的link，更细致地搜索这一层的局部最小，以此类推，总体复杂度降到log级别。这从本质上来说，就是skiplist在图上的推广，将链表改成临近图而已，运用简单有效的分层搜索的理念。因此skiplist可以做的分布式方法，同样适用于HNSW。

每次插入都会随机选择一个最大layer数。插入时也进行自顶层开始的搜索，找到每层的邻居，再进入下一层。

HNSW还有个优点：构造分层的随机化本质实际上已经让HNSW引入了随机性（stochasticity），因此不像NSW构造那样需要在插入前shuffle元素。这意味着即使数据分布临时改变，也能增量地对数据进行索引。

元素插入阶段的临近图连接选取，是基于一种启发式方法的：考虑候选元素间距离的多样性，而不简单地选取最近邻居。这算是政治正确在算法中的合理使用。该启发式方法从离插入元素最近的候选开始，只有检验出该候选离插入元素比其他所有已连接候选都近才会再建立连接。

当候选数目足够大，以至于启发式方法能够获得准确的相对邻域图作为Delaunay图（德劳内图）的最小子图，且只用两点间距离就可以进行推理——这在针对1D数据时直接让NSW转化成skip list。

一个图如果是平面内一些点集的德劳内三角剖分，则称为德劳内图；德劳内三角剖分是一种没有任意点位于欧氏空间三角形（完全可以从欧氏空间推广到度量空间）外接圆内部的三角剖分；三角剖分是覆盖点集凸包的simplicial complex；某个形状的凸包(convex hull/envelope/closure)是包含它的最小凸集(convex region/set)；凸集是与任意线段相交部分都是单个线段的欧氏空间子集。

NGT-ONNG

background

有两种类型的knn近似搜索方法：一类是用hash、quantization、permutation-based methods，在搜索过程中无需任何object来计算距离。另一类是基于树或者图的方法，需要object——也就需要更多的内存。前一类方法的准确度不如后一类。如果内存足够大或用高速SSD代替内存，那么用后一种方法会更好。

树类方法包括kd-tree、vp-tree，将整个搜索空间分层次且递归地分成子空间再搜，可提供准确的搜索结果，但效率很低，甚至可能不如bruteforce加并行优化。也有一些基于树的近似方法，ANN就是将近似施加于kd-tree。

基于graph的方法用邻接图做辅助索引。Arya用随机化的邻接图做搜索索引。Sebastian用knn graph(KNNG)作为搜索索引，KNNG中每个节点都有一个有向边到k个最近的节点。KNNG虽然简单，但准确率不错——事实上可以比LSH和kd-tree好。

DRNG将KNNG的degree降低，从而缩短查询时间。

KNNG的缺点是构建速度会随着数据增多而指数性地慢。SW-graph、KGraph和ANNG用approximagte neighborhood graphs解决这个问题。HNSW用多层approximate neighborhood，用长edge达到远处的节点。

PANNG又对ANNG优化，修剪每个节点的edge，从而缩短查询时间，效果击败了量化方法。