标题：基于图的近似最近邻搜索：一次回顾

编者的总结

1. 本文提出了裁边技术的一个trade-off，限制太松影响查询效率，限制太紧影响连通性，基于此作者提了个两阶段的裁边，第一阶段类似vamana，用一个参数放松裁边策略，第二阶段仍然通过RNG rule给边定权重然后排序进一步裁剪。
2. 提出了一些GPU查询算法。

编者的思考

1. trade-off很有趣，但方法创新性有限，第一阶段和vamana很像，第二阶段意义又不太明确（从GPU方面的动机较弱，从结果来看仅保留第一阶段也还可以（GD），如果连上反向边可能会更好）。最关键的是，这个方法如何match这个trade-off，是否达到了一个最优点并不明确，只能说经过6个小数据集的试验来看有稳定提升。
2. GPU搜索算法似乎和裁边技术有点割裂。

3 TWO-STAGE GRAPH DIVERSIFICATION

3.1 Preliminaries for Graph Diversification

作者认为，GD算法的配置存在一个trade-off，如果裁边太多，要求太严，会导致图的连通性不够；如果裁边太少，要求太松，会导致冗余比较太多，影响查询效率。
具体来说，按照现有的HNSW的裁边要求，即满足下式就会被裁。
这在L2空间中，会导致夹角60度的范围内，只保留最近的一条边；那如果有一些较远的区域正好在60度的范围内，可达性（连通性）就会收到损失。

image.png

本文的方法TSDG (two-staged diversified graph) 则针对性地保留了一些边，放松了裁剪的要求，同时给每条边加了一个occlusion factor，使得可以根据用户要求，有时候访问这些边，有时候则不访问。TSDG基于一个KNN-graph，分成两个阶段进行refine。
（编者注：自定义访问这里的motivation是描述在GPU上，大批量查询和小批量查询的case不一样，但编者觉得这个动机较弱，适用范围较小。）

3.2 Relaxed Graph Diversification

第一阶段和vamana类似，在裁边条件中引入了一个α参数来放松裁边限制。

image.png
通常大于1.1，根据作者在6个数据集上的实验，只有6%-26%的边可以活过裁边。

3.3 Soft Graph Diversification

第一阶段会得到一个稀疏过的kNN图，然后直接添加反向边（注意这个过程不再裁边了），得到一个无向图。
然后遍历每条边，为之赋权。具体来说，这条边会被几条其他边排斥（此时=1）他的权重就是几。（权重越小是越重要的）
最后按权重从小到大排序，权重大于一个参数的直接裁掉。

image.png

5 EXPERIMENTS

5.1 Experiment Setup

one IntelXeon Processor W-2123 (3.60 Ghz) and 32 GB of memory.
CPU实验时用单核。

image.png

5.2 The efficiency of Two-stage Diversification

所有方法用最快的GPU方法构建base的knn-graph。

• TSDG的构建速度还是不错的，甚至比SSG还要好；

• GD的裁边策略就是HNSW的，可以理解为TSDG的第一阶段；

  
  image.png

5.3 NN Search Performance on the CPU

• 在6个1M的数据集上，TSDG有着稳定的查询性能优势，但都不多。

• GD和DPG两个方法分别在1个数据集上有显著退化，可以淘汰。

  
  image.png