# Wasserstein-based Graph Alignment

arXiv: https://arxiv.org/abs/2003.06048 · HTML: https://mlsanity.com/paper/2003.06048/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Mar 2020.

## Built on by (most cited first, 10 of 10)

- [Hierarchical Multi-Marginal Optimal Transport for Network Alignment](https://mlsanity.com/paper/2310.04470/) (2023)
- [FGOT: Graph Distances based on Filters and Optimal Transport](https://mlsanity.com/paper/2109.04442/) (2021)
- [Bures-Wasserstein Means of Graphs](https://mlsanity.com/paper/2305.19738/) (2023)
- [Alignment and Comparison of Directed Networks via Transition Couplings of Random Walks](https://mlsanity.com/paper/2106.07106/) (2021)
- [Sparse Partial Least Squares for Coarse Noisy Graph Alignment](https://mlsanity.com/paper/2104.02810/) (2021)
- [A Regularized Wasserstein Framework for Graph Kernels](https://mlsanity.com/paper/2110.02554/) (2021)
- [Graph Convolutional Neural Networks Sensitivity under Probabilistic Error Model](https://mlsanity.com/paper/2203.07831/) (2022)
- [A Simple Way to Learn Metrics Between Attributed Graphs](https://mlsanity.com/paper/2209.12727/) (2022)
- [UTOPIA: Unconstrained Tracking Objects without Preliminary Examination via Cross-Domain Adaptation](https://mlsanity.com/paper/2306.09613/) (2023)
- [Transfer Learning on Edge Connecting Probability Estimation under Graphon Model](https://mlsanity.com/paper/2510.05527/) (2025)

## Abstract (arXiv)

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.