  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.
