Graph Matching Relaxations and Amortization for Supervised Graph Prediction
Abstract
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.
Related
- Multiscale Supervised Unbalanced Optimal Transport Flow Matching
- Regularized Coupling Maps on Matrix Polytopes: From Assignment to Graph Matching and Optimal Transport
- Self-Supervised Pretraining of Molecular Graph Encoders with LeJEPA
- Alignment Matters Inside and Out in Equivariant Graph Flow Matching
- Beyond Reachability: When Edit Order Preserves Couplings in Graph Flow Matching
BibTeX
@misc{mendez2026graph,
title = {{Graph Matching Relaxations and Amortization for Supervised Graph Prediction}},
author = {Federico Méndez and Paul Krzakala and Gabriel Melo and Charlotte Laclau and Rémi Flamary and Florence d'Alché-Buc},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15437},
eprint = {2609.15437},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15437},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Graph Matching Relaxations and Amortization for Supervised Graph Prediction
AU - Federico Méndez
AU - Paul Krzakala
AU - Gabriel Melo
AU - Charlotte Laclau
AU - Rémi Flamary
AU - Florence d'Alché-Buc
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.15437
UR - https://arxiv.org/abs/2609.15437
AB - 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.
ER -