作者来自东华、UNSW和天津科技大学。

Abstract

本文想要回答两个问题：

1. 为什么基于图的算法搜索性能这么好？
2. 什么样的数据特征会影响搜索性能，以及如何影响？

I. INTRODUCTION

针对于第一个问题：

1. ICML和SoCG各有一篇文章尝试从理论上对图算法的复杂度进行分析，然而结论的复杂度仅仅和最优情况的hash-based算法的复杂度差不多，这和预期是不符的。
2. 一些概念图，比如MSNET，Delauney Graph等，也不能完全解释这个问题
   • MSNET：不能解释不在数据集中query如何处理，且构建时间是
   • Delauney Graph：这个图可以从任意点找到到query NN的一条递增路径。但作者提出了一个问题，如果query就是base里的点，NN是query本身，那么找到的就是递增路径的倒数第二个点，这个点未必是距离NN最近的。
3. 本文提出：KNN图的聚类系数可以直接反应查询性能。聚类系数越大，查询性能越好。
4. 聚类系数可以反映全局连通性。然而作者发现，对于一个给定query，大部分的kNN构成的子图是一个强联通部分SCC。kNN可以构成的最大SCC越大（越接近k个点），query性能越好。

III. CLUSTERING COEFFICIENT OF KNN GRAPH AND ITS IMPACT ON SEARCH PERFORMANCE

• 聚类系数，顾名思义，就是度量图上节点如何聚集到一起

• 定义的方法有很多种，本文用的是通过局部聚类定义的

  
  image.png

• 一个点的邻居对中，有多少是互相连接的。整个图的聚类系数就是所有点的平均。

• 这个聚类系数既取决于KNN图的K取的多大，也取决于数据集的分布。

  
  image.png

• 作者发现，数据集的KNN图的聚类系数和它们的搜索性能正相关，如下表，最大出度都是70，efSearch控制到50

  
  image.png

• 接着作者针对一个给定query，找了它kNN子图的SCCs，统计覆盖率，和召回相关性也是很高：

  
  image.png

• 作者将Query分为两个阶段，第一个阶段导航到kNN中最大SCC的1个点，第二阶段是在搜这个SCC。

• 然后作者提出一个定理证明只要找到SCC中的一个点，其他点贪婪算法会找到，（需要一定条件）。

  
  image.png

• 从上面sample中看出，query的最大SCC基本决定了query的精度。

• 比如Random，这些query的最大SCC非常小，1或者2，那它精度也很一般。

• 第二阶段比第一阶段慢得多。