2022WSDM-GraSP: Optimizing Graph

2022-12-02  本文已影响0人  Caucher

标题:Grasp:用子图采样和剪枝优化基于图的最近邻搜索

编者的总结

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

编者的思考

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

ABSTRACT & INTRODUCTION

3 OBSERVATIONS AND OPPORTUNITIES

Optimizing graphs based on heuristics?

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代表学习率。

image.png

Search-efficiency-aware objective function

对于某个query,移除部分边后(即得到G')的损失定义为在G'上找到的1-NN和精确1-NN之间的距离比值,如下式。


image.png

总的来说,算法迭代K轮,每一轮首先得到采样率,然后对边的权重做正则化,然后按照概率随机采样,得到子图,用query集在子图上查询,如果查不到原来的1-NN,要对路径边增长权重。


image.png

5 EVALUATION

所有查询性能的比较只用了1M的数据集。
和HNSW、NSG的查询性能比较有较稳定的提升。


image.png
image.png

query不同分布时有明显退化


image.png
上一篇 下一篇

猜你喜欢

热点阅读