编者的总结

提供了两个发现，一个是SOTA图可能存在冗余边，另一个是边访问频率是非常倾斜的，大部分的访问集中在hub节点上，因而固定边的上界不是一个明智的做法。
设计了一个概率模型+退火算法给边赋权，而后裁剪冗余边。整体查询效果还不错。

编者的思考

训练时间太长，影响了本来就很漫长的构建时间。
当query和training set不同分布的时候查询有明显退化。
算法有好多超参。
数据集太小了，训练时间也没有报告。

ABSTRACT & INTRODUCTION

observation：边访问的频率分布是极度倾斜的;
SOTA: 现有的图设计都是启发式的，和搜索效率不直接对应，导致最终结果可能在一些数据集上是好的，在其他数据集上却变差。
核心idea：可不可以从之前的query中学习到一些知识以提升搜索效率？比如减掉一些冗余的边
本文贡献：
1. 做了一个概率模型，推理每条边被剪除而不影响查询精度的概率；
2. 利用这个概率模型可以对现有图进行裁剪优化，及理论证明

3 OBSERVATIONS AND OPPORTUNITIES

Optimizing graphs based on heuristics?

hnsw和nsg显著的比Effana要好，其原因是knn-graph在clustered data上面连通性很差，这时hnsw和nsg的裁边和补边技术就显得很重要了；
另一方面，hnsw和nsg比较时好时坏，说明二者虽然可达但都有一些冗余边，这些冗余边会带来一些负面影响。
因此作者推测，移除一些冗余边对搜索效率是有帮助的。

Highly skewed query distribution

作者用SIFT和DEEP的training set (100K)统计了下在HNSW上的边访问次数，如下图，其分布是极度倾斜的。大部分边只访问了一次，经常访问的边只占非常少一部分。作者进一步发现这是由于那些hub节点比其他节点更容易被访问到(much more likely to be visited)。

image.png

作者认为Query分布是很重要的信息，比如目前SOTA的M参数，即点的最大出度是定死的，然而这个参数不好设置，因为存在一个connectivity-efficiency trade-off。另外，对于hub节点给它定死最大出度也不合适，更合理的是每个点自适应选择出度。

4 GraSP: LEARNING TO OPTIMIZE GRAPHS

方法整体分三个阶段，第一个阶段构建概率模型，第二阶段给边赋权，第三阶段是裁边。

4.1 Subgraph Sampling and Iterative Refinement

Modeling edge importance

边的权重被定义为“移除掉这条边后的鲁棒性”。具体方法是：以 $p_e$ 的概率随机保留每条边，得到稀疏图G'；然后取训练集的Query，如果对于某个query能在原图找到精确1-NN (记号为p) 但是不能在G'中找到，那这个主路径中的边的权重就增加如下的量，其中p'是在G'中找到的1-NN， $\eta$ 代表学习率。