论文标题
基于Wasserstein的图形对准
Wasserstein-based Graph Alignment
论文作者
论文摘要
我们提出了一种新的方法，可以根据各个图形laplacian矩阵诱导的图形信号分布之间的瓦斯汀距离进行比较不同大小的非对准图。具体而言，我们为一到一到一到的图形对齐问题施放了一个新的公式，该公式旨在将较小图中的节点与较大图中的一个或多个节点匹配。通过在我们的图形比较框架中集成最佳传输，我们既生成结构上的图形距离，又生成一个建模图数据结构的信号传输计划。通过随机梯度下降解决了所得的对齐问题，在那里我们使用新型的dykstra操作员来确保溶液是一种一对多（软）分配矩阵。我们证明了我们在图形对准和图形分类方面的新型框架的性能，我们表明我们的方法在每个任务中的最新算法方面都会取得重大改进。
We propose a novel method for comparing non-aligned graphs of different sizes, based on the Wasserstein distance between graph signal distributions induced by the respective graph Laplacian matrices. Specifically, we cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. By integrating optimal transport in our graph comparison framework, we generate both a structurally-meaningful graph distance, and a signal transportation plan that models the structure of graph data. The resulting alignment problem is solved with stochastic gradient descent, where we use a novel Dykstra operator to ensure that the solution is a one-to-many (soft) assignment matrix. We demonstrate the performance of our novel framework on graph alignment and graph classification, and we show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
