# Graph Matching Relaxations and Amortization for Supervised Graph Prediction

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 41 references that are in the map.
- First posted on arXiv 14 Sep 2026.

## Builds on (most cited first, 22 of 22)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [SegFormer: Simple and Efficient Design for Semantic Segmentation with Transformers](https://mlsanity.com/paper/2105.15203/) (2021)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [A Survey on Deep Graph Generation: Methods and Applications](https://mlsanity.com/paper/2203.06714/) (2022)
- [Relationformer: A Unified Framework for Image-to-Graph Generation](https://mlsanity.com/paper/2203.10202/) (2022)
- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [The Elements of Differentiable Programming](https://mlsanity.com/paper/2403.14606/) (2024)
- [MassSpecGym: A benchmark for the discovery and identification of molecules](https://mlsanity.com/paper/2410.23326/) (2024)
- [Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenters](https://mlsanity.com/paper/2202.03813/) (2022)
- [Improving Equivariant Networks with Probabilistic Symmetry Breaking](https://mlsanity.com/paper/2503.21985/) (2025)
- [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)
- [Unsupervised Learning for Optimal Transport plan prediction between unbalanced graphs](https://mlsanity.com/paper/2506.12025/) (2025)
- [Conformal Graph Prediction with Z-Gromov-Wasserstein Distances](https://mlsanity.com/paper/2603.02460/) (2026)
- [MSAlign: Aligning Molecule and Mass Spectra representations for Metabolite Identification](https://mlsanity.com/paper/2605.19752/) (2026)

## Abstract (arXiv)

End-to-end Supervised Graph Prediction (SGP) requires a permutation-invariant loss to compare predicted and target graphs with arbitrary node orderings. Such losses typically involve a costly graph-matching problem. We first study three Optimal Transport relaxations of this problem and show, theoretically and empirically, that the Gromov-Wasserstein (GW) objective is the most suitable for SGP. Then, to avoid solving the resulting inner optimization for every training example, we propose to amortize the graph matching (node alignment) problem. For each training sample, the loss function leverages a transport plan provided by a parametric matcher based on the differentiable Sinkhorn algorithm applied on empirical node distributions. The graph prediction module and the matcher are jointly learned. We showcase the efficiency of this approach on toy and real world SGP problems of increasing complexity including a novel Mass-spectra to Scaffold task that we introduce.