# Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenters

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 73 references that are in the map.
- First posted on arXiv 8 Feb 2022.

## Builds on (most cited first, 30 of 36)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Automatic chemical design using a data-driven continuous representation of molecules](https://mlsanity.com/paper/1610.02415/) (2016)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Deep Learning on Graphs: A Survey](https://mlsanity.com/paper/1812.04202/) (2018)
- [Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation](https://mlsanity.com/paper/1806.02473/) (2018)
- [GraphAF: a Flow-based Autoregressive Model for Molecular Graph Generation](https://mlsanity.com/paper/2001.09382/) (2020)
- [Grammar Variational Autoencoder](https://mlsanity.com/paper/1703.01925/) (2017)
- [Molecular De Novo Design through Deep Reinforcement Learning](https://mlsanity.com/paper/1704.07555/) (2017)
- [Efficient Graph Generation with Graph Recurrent Attention Networks](https://mlsanity.com/paper/1910.00760/) (2019)
- [Learning Deep Generative Models of Graphs](https://mlsanity.com/paper/1803.03324/) (2018)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Learning with a Wasserstein Loss](https://mlsanity.com/paper/1506.05439/) (2015)
- [MoFlow: An Invertible Flow Model for Generating Molecular Graphs](https://mlsanity.com/paper/2006.10137/) (2020)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [Multi-Objective De Novo Drug Design with Conditional Graph Generative Model](https://mlsanity.com/paper/1801.07299/) (2018)
- [The Predictron: End-To-End Learning and Planning](https://mlsanity.com/paper/1612.08810/) (2016)
- [Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties](https://mlsanity.com/paper/1811.02834/) (2018)
- [Retrosynthetic reaction prediction using neural sequence-to-sequence models](https://mlsanity.com/paper/1706.01643/) (2017)
- [Structured Prediction Energy Networks](https://mlsanity.com/paper/1511.06350/) (2015)
- [Differentiable Dynamic Programming for Structured Prediction and Attention](https://mlsanity.com/paper/1802.03676/) (2018)
- [Differential Properties of Sinkhorn Approximation for Learning with Wasserstein Distance](https://mlsanity.com/paper/1805.11897/) (2018)
- [Online Graph Dictionary Learning](https://mlsanity.com/paper/2102.06555/) (2021)
- [A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings](https://mlsanity.com/paper/2002.05424/) (2020)
- [A Consistent Regularization Approach for Structured Prediction](https://mlsanity.com/paper/1605.07588/) (2016)

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

- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Implicit Graphon Neural Representation](https://mlsanity.com/paper/2211.03329/) (2022)
- [Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsification](https://mlsanity.com/paper/2205.13573/) (2022)
- [The quest for the GRAph Level autoEncoder (GRALE)](https://mlsanity.com/paper/2505.22109/) (2025)
- [Any2Graph: Deep End-To-End Supervised Graph Prediction With An Optimal Transport Loss](https://mlsanity.com/paper/2402.12269/) (2024)
- [Gromov-Wasserstein-like Distances in the Gaussian Mixture Models Space](https://mlsanity.com/paper/2310.11256/) (2023)
- [Structure-Aware E(3)-Invariant Molecular Conformer Aggregation Networks](https://mlsanity.com/paper/2402.01975/) (2024)
- [Distances for Markov Chains, and Their Differentiation](https://mlsanity.com/paper/2302.08621/) (2023)
- [Deep Sketched Output Kernel Regression for Structured Prediction](https://mlsanity.com/paper/2406.09253/) (2024)
- [Conformal Graph Prediction with Z-Gromov-Wasserstein Distances](https://mlsanity.com/paper/2603.02460/) (2026)
- [Exploiting Edge Features in Graphs with Fused Network Gromov-Wasserstein Distance](https://mlsanity.com/paper/2309.16604/) (2023)
- [An Optimal Transport Approach for Network Regression](https://mlsanity.com/paper/2406.12204/) (2024)
- [A Fused Gromov-Wasserstein Approach to Subgraph Contrastive Learning](https://mlsanity.com/paper/2502.20885/) (2025)
- [MSAlign: Aligning Molecule and Mass Spectra representations for Metabolite Identification](https://mlsanity.com/paper/2605.19752/) (2026)
- [Estimation of the Sample Frechet Mean: A Convolutional Neural Network Approach](https://mlsanity.com/paper/2210.07401/) (2022)
- [COTET: Cross-view Optimal Transport for Knowledge Graph Entity Typing](https://mlsanity.com/paper/2405.13602/) (2024)
- [An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph](https://mlsanity.com/paper/2502.00739/) (2025)
- [Subgraph Gaussian Embedding Contrast for Self-Supervised Graph Representation Learning](https://mlsanity.com/paper/2505.23529/) (2025)
- [Generalized Sobolev IPM for Graph-Based Measures](https://mlsanity.com/paper/2510.25591/) (2025)
- [Fused Gromov-Wasserstein Distance with Feature Selection](https://mlsanity.com/paper/2605.12161/) (2026)
- [Graph Matching Relaxations and Amortization for Supervised Graph Prediction](https://mlsanity.com/paper/2609.15437/) (2026)
- [Averaged Mirror Descent and Dual Gradient Methods: Convergent Algorithms for Entropic Gromov-Wasserstein Problems](https://mlsanity.com/paper/2609.31848/) (2026)

## Abstract (arXiv)

This paper introduces a novel and generic framework to solve the flagship task of supervised labeled graph prediction by leveraging Optimal Transport tools. We formulate the problem as regression with the Fused Gromov-Wasserstein (FGW) loss and propose a predictive model relying on a FGW barycenter whose weights depend on inputs. First we introduce a non-parametric estimator based on kernel ridge regression for which theoretical results such as consistency and excess risk bound are proved. Next we propose an interpretable parametric model where the barycenter weights are modeled with a neural network and the graphs on which the FGW barycenter is calculated are additionally learned. Numerical experiments show the strength of the method and its ability to interpolate in the labeled graph space on simulated data and on a difficult metabolic identification problem where it can reach very good performance with very little engineering.