# GOT: An Optimal Transport framework for Graph comparison

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

## Key facts

- Cited by 64 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2019.

## Built on by (most cited first, 30 of 64)

- [Graph Coarsening with Neural Networks](https://mlsanity.com/paper/2102.01350/) (2021)
- [Unbalanced Optimal Transport, from Theory to Numerics](https://mlsanity.com/paper/2211.08775/) (2022)
- [Does Graph Distillation See Like Vision Dataset Counterpart?](https://mlsanity.com/paper/2310.09192/) (2023)
- [Online Graph Dictionary Learning](https://mlsanity.com/paper/2102.06555/) (2021)
- [Unbalanced Optimal Transport through Non-negative Penalized Linear Regression](https://mlsanity.com/paper/2106.04145/) (2021)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Hierarchical Multi-Marginal Optimal Transport for Network Alignment](https://mlsanity.com/paper/2310.04470/) (2023)
- [Semi-relaxed Gromov-Wasserstein divergence with applications on graphs](https://mlsanity.com/paper/2110.02753/) (2021)
- [Partially Does It: Towards Scene-Level FG-SBIR with Partial Input](https://mlsanity.com/paper/2203.14804/) (2022)
- [Template based Graph Neural Network with Optimal Transport Distances](https://mlsanity.com/paper/2205.15733/) (2022)
- [Pave Your Own Path: Graph Gradual Domain Adaptation on Fused Gromov-Wasserstein Geodesics](https://mlsanity.com/paper/2505.12709/) (2025)
- [OST: Refining Text Knowledge with Optimal Spatio-Temporal Descriptor for General Video Recognition](https://mlsanity.com/paper/2312.00096/) (2023)
- [Collaborative Filtering with Attribution Alignment for Review-based Non-overlapped Cross Domain Recommendation](https://mlsanity.com/paper/2202.04920/) (2022)
- [DELFlow: Dense Efficient Learning of Scene Flow for Large-Scale Point Clouds](https://mlsanity.com/paper/2308.04383/) (2023)
- [Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More](https://mlsanity.com/paper/2107.06876/) (2021)
- [Joint Optimal Transport and Embedding for Network Alignment](https://mlsanity.com/paper/2502.19334/) (2025)
- [Generalized Sobolev Transport for Probability Measures on a Graph](https://mlsanity.com/paper/2402.04516/) (2024)
- [FGOT: Graph Distances based on Filters and Optimal Transport](https://mlsanity.com/paper/2109.04442/) (2021)
- [Riemannian block SPD coupling manifold and its application to optimal transport](https://mlsanity.com/paper/2201.12933/) (2022)
- [Structured Attention Composition for Temporal Action Localization](https://mlsanity.com/paper/2205.09956/) (2022)
- [Bures-Wasserstein Means of Graphs](https://mlsanity.com/paper/2305.19738/) (2023)
- [Computing Approximate Graph Edit Distance via Optimal Transport](https://mlsanity.com/paper/2412.18857/) (2024)
- [Multiscale Graph Comparison via the Embedded Laplacian Discrepancy](https://mlsanity.com/paper/2201.12064/) (2022)
- [Conflict-Aware Pseudo Labeling via Optimal Transport for Entity Alignment](https://mlsanity.com/paper/2209.01847/) (2022)
- [LICO: Explainable Models with Language-Image Consistency](https://mlsanity.com/paper/2310.09821/) (2023)
- [Wasserstein Gradient Flow over Variational Parameter Space for Variational Inference](https://mlsanity.com/paper/2310.16705/) (2023)
- [Schema-Guided Event Graph Completion](https://mlsanity.com/paper/2206.02921/) (2022)
- [Moreau-Yoshida Variational Transport: A General Framework For Solving Regularized Distributional Optimization Problems](https://mlsanity.com/paper/2307.16358/) (2023)
- [Graph GOSPA metric: a metric to measure the discrepancy between graphs of different sizes](https://mlsanity.com/paper/2311.07596/) (2023)
- [Multiple Wasserstein Gradient Descent Algorithm for Multi-Objective Distributional Optimization](https://mlsanity.com/paper/2505.18765/) (2025)

## Abstract (arXiv)

We present a novel framework based on optimal transport for the challenging problem of comparing graphs. Specifically, we exploit the probabilistic distribution of smooth graph signals defined with respect to the graph topology. This allows us to derive an explicit expression of the Wasserstein distance between graph signal distributions in terms of the graph Laplacian matrices. This leads to a structurally meaningful measure for comparing graphs, which is able to take into account the global structure of graphs, while most other measures merely observe local changes independently. Our measure is then used for formulating a new graph alignment problem, whose objective is to estimate the permutation that minimizes the distance between two graphs. We further propose an efficient stochastic algorithm based on Bayesian exploration to accommodate for the non-convexity of the graph alignment problem. We finally demonstrate the performance of our novel framework on different tasks like graph alignment, graph classification and graph signal prediction, and we show that our method leads to significant improvement with respect to the-state-of-art algorithms.