Wasserstein-Based Graph Alignment

A novel method for comparing non-aligned graphs of various sizes is proposed, based on the Wasserstein distance between graph signal distributions induced by the respective graph Laplacian matrices. Specifically, a new formulation for the one-to-many graph alignment problem is casted, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. By incorporating optimal transport into our graph comparison framework, a structurally-meaningful graph distance, and a signal transportation plan that models the structure of graph data are generated. The resulting alignment problem is solved with stochastic gradient descent, where a novel Dykstra operator is used to ensure that the solution is a one-to-many (soft) assignment matrix. The performance of our novel framework is demonstrated on graph alignment, graph classification and graph signal transportation. Our method is shown to lead to significant improvements with respect to the state-of-the-art algorithms on each ofthese tasks.