# Optimal Transport for structured data with application on graphs

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

## Key facts

- Cited by 172 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2018.

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

- [Recent Advances in Optimal Transport for Machine Learning](https://mlsanity.com/paper/2306.16156/) (2023)
- [Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks](https://mlsanity.com/paper/2210.01906/) (2022)
- [Temporally Consistent Unbalanced Optimal Transport for Unsupervised Action Segmentation](https://mlsanity.com/paper/2404.01518/) (2024)
- [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)
- [GENOT: Entropic (Gromov) Wasserstein Flow Matching with Applications to Single-Cell Genomics](https://mlsanity.com/paper/2310.09254/) (2023)
- [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)
- [Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenters](https://mlsanity.com/paper/2202.03813/) (2022)
- [Optimizing OOD Detection in Molecular Graphs: A Novel Approach with Diffusion Models](https://mlsanity.com/paper/2404.15625/) (2024)
- [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)
- [Quantized Gromov-Wasserstein](https://mlsanity.com/paper/2104.02013/) (2021)
- [Using Optimal Transport as Alignment Objective for fine-tuning Multilingual Contextualized Embeddings](https://mlsanity.com/paper/2110.02887/) (2021)
- [Implicit Graphon Neural Representation](https://mlsanity.com/paper/2211.03329/) (2022)
- [On Structural Expressive Power of Graph Transformers](https://mlsanity.com/paper/2305.13987/) (2023)
- [Sobolev Transport: A Scalable Metric for Probability Measures with Graph Metrics](https://mlsanity.com/paper/2202.10723/) (2022)
- [Pave Your Own Path: Graph Gradual Domain Adaptation on Fused Gromov-Wasserstein Geodesics](https://mlsanity.com/paper/2505.12709/) (2025)
- [On Transportation of Mini-batches: A Hierarchical Approach](https://mlsanity.com/paper/2102.05912/) (2021)
- [A Fused Gromov-Wasserstein Framework for Unsupervised Knowledge Graph Entity Alignment](https://mlsanity.com/paper/2305.06574/) (2023)
- [Robust Attributed Graph Alignment via Joint Structure Learning and Optimal Transport](https://mlsanity.com/paper/2301.12721/) (2023)
- [A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening](https://mlsanity.com/paper/2306.08854/) (2023)
- [Fused Gromov-Wasserstein Graph Mixup for Graph-level Classifications](https://mlsanity.com/paper/2306.15963/) (2023)
- [DELFlow: Dense Efficient Learning of Scene Flow for Large-Scale Point Clouds](https://mlsanity.com/paper/2308.04383/) (2023)
- [RMS-FlowNet: Efficient and Robust Multi-Scale Scene Flow Estimation for Large-Scale Point Clouds](https://mlsanity.com/paper/2204.00354/) (2022)
- [Distributional Reduction: Unifying Dimensionality Reduction and Clustering with Gromov-Wasserstein](https://mlsanity.com/paper/2402.02239/) (2024)
- [The Z-Gromov-Wasserstein Distance](https://mlsanity.com/paper/2408.08233/) (2024)
- [Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More](https://mlsanity.com/paper/2107.06876/) (2021)
- [Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsification](https://mlsanity.com/paper/2205.13573/) (2022)

## Abstract (arXiv)

This work considers the problem of computing distances between structured objects such as undirected graphs, seen as probability distributions in a specific metric space. We consider a new transportation distance (i.e. that minimizes a total cost of transporting probability masses) that unveils the geometric nature of the structured objects space. Unlike Wasserstein or Gromov-Wasserstein metrics that focus solely and respectively on features (by considering a metric in the feature space) or structure (by seeing structure as a metric space), our new distance exploits jointly both information, and is consequently called Fused Gromov-Wasserstein (FGW). After discussing its properties and computational aspects, we show results on a graph classification task, where our method outperforms both graph kernels and deep graph convolutional networks. Exploiting further on the metric properties of FGW, interesting geometric objects such as Fr'echet means or barycenters of graphs are illustrated and discussed in a clustering context.