Graph comparison deals with identifying similarities and dissimilarities between graphs. A major obstacle is the unknown alignment of graphs, as well as the lack of accurate and inexpensive comparison metrics. In this work we introduce the filter graph distance. It is an optimal transport based distance which drives graph comparison through the probability distribution of filtered graph signals. This creates a highly flexible distance, capable of prioritising different spectral information in observed graphs, offering a wide range of choices for a comparison metric. We tackle the problem of graph alignment by computing graph permutations that minimise our new filter distances, which implicitly solves the graph comparison problem. We then propose a new approximate cost function that circumvents many computational difficulties inherent to graph comparison and permits the exploitation of fast algorithms such as mirror gradient descent, without grossly sacrificing the performance. We finally propose a novel algorithm derived from a stochastic version of mirror gradient descent, which accommodates the non-convexity of the alignment problem, offering a good trade-off between performance accuracy and speed. The experiments on graph alignment and classification show that the flexibility gained through filter graph distances can have a significant impact on performance, while the difference in speed offered by the approximation cost makes the framework applicable in practical settings.


翻译:图表比较涉及找出图表之间的相似性和不同之处。 一个主要障碍是图形的不为人知的对齐以及缺乏准确和廉价的比较度量。 在这个工作中,我们引入了过滤器图形距离。 这是一个最佳的基于迁移的距离,通过过滤器图形信号的概率分布驱动图形比较。这创造了一个高度灵活的距离,能够在观察的图表中排列不同的光谱信息,为比较度提供广泛的选择。我们通过计算图形对齐问题,从而最大限度地减少我们新的过滤器距离,从而解决图形对齐问题,这间接解决了图形比较问题。我们然后提出了一个新的近似成本功能,以绕过图形比较固有的许多计算困难,并允许在不严重牺牲性能的情况下利用镜像梯度梯度下降等快速算法。我们最后提出了一个新的算法,它来自镜像梯度梯度下降的随机版本,它能适应调和问题的非相容性能,在性能准确性和速度之间实现良好的权衡。 图形调整和分类实验表明,通过过滤式图形距离获得的灵活性可以对性能产生显著的影响,而实际的精确度则使框架在速度上产生差异。

0
下载
关闭预览

相关内容

【Google-Marco Cuturi】最优传输,339页ppt,Optimal Transport
专知会员服务
47+阅读 · 2021年10月26日
【图与几何深度学习】Graph and geometric deep learning,49页ppt
专知会员服务
25+阅读 · 2021年4月2日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
保序最优传输:Order-preserving Optimal Transport
我爱读PAMI
6+阅读 · 2018年9月16日
已删除
将门创投
3+阅读 · 2018年4月10日
Arxiv
0+阅读 · 2022年2月8日
Arxiv
19+阅读 · 2020年7月13日
VIP会员
相关VIP内容
【Google-Marco Cuturi】最优传输,339页ppt,Optimal Transport
专知会员服务
47+阅读 · 2021年10月26日
【图与几何深度学习】Graph and geometric deep learning,49页ppt
专知会员服务
25+阅读 · 2021年4月2日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
保序最优传输:Order-preserving Optimal Transport
我爱读PAMI
6+阅读 · 2018年9月16日
已删除
将门创投
3+阅读 · 2018年4月10日
Top
微信扫码咨询专知VIP会员