标题：基于图的最近邻搜索：成功与失败
另一篇arxiv: A Comparative Study on Hierarchical Navigable Small World Graphs基本也是相同的内容
本文是一篇基于实验的分析和原理发现的文章，主要讲述三点发现，作者来自厦门大学。

编者的总结

本文提供了3点有意义的发现：

1. HNSW的裁边技术以及反向边补充是性能大幅提升的主要原因；
2. HNSW的层次化结构有前期快速导航的用处，但是这一阶段不是查询的瓶颈步，因此实际用处不大；
3. 图索引的查询最耗时的部分是在到达KNN的周围局部地区。

编者的思考

1. 数据集只用了1M的，难度有限，不知道更大的数据集上是否能复现同样的现象。
2. 同理，参数也可以多改一改再试一试去验证。

1. 层次化结构or扁平结构？

作者想验证HNSW的层次化结构在搜索中到底有没有用，于是只搜HNSW的第0层（随机设置入口点），和原版HNSW作对比。
结果显示：

• 在真实数据集和高维(≥32)数据集上，这个层次化的结构基本没有用，两种方法性能几乎一致。

• 在低维随机分布数据集上，层次化结构是有用的，整体性能更高。

  
  image.png

2. 裁边技术 (graph diversification) 有没有用？

为了验证裁边技术的有效性，作者对比了KNN-Graph和KNN-Graph+graph diversification两种方案，后者使用GD留下了至多一半的邻居，然后增加反向边。
结果显示：

• 在高维和真实数据集上，knn-Graph+GD能达到不输给HNSW的性能，但普通knn-graph有明显性能衰退，可以证明GD是提升检索性能的重要因素。

  
  image.png

3. 相似性搜索中的维度诅咒

• 从下图可以发现，HNSW在超低维条件下确实有快速导航的前期阶段；而在前期阶段可以快速收敛的低维数据集上（d<16）就能体现出优势；

• 而在维数偏高一些时，前期的快速导航占比很小，最耗时的是在knn周围的局部地区，在这些地区几乎退化成了暴力搜索，因此HNSW的前期快速导航的优势也没什么用了。

  
  image.png