Wasserstein-based Graph Alignment
This addresses the problem of graph comparison for researchers in machine learning and network analysis, offering a novel approach but likely incremental as it builds on optimal transport and graph Laplacians.
The paper tackles the problem of comparing non-aligned graphs of different sizes by proposing a Wasserstein-based method for one-to-many graph alignment, which shows significant improvements in graph alignment and classification tasks over state-of-the-art algorithms.
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.