Discrete Gromov-Wasserstein Duality: Algorithms and Isomorphism Testing
Abstract
The Gromov-Wasserstein (GW) distance provides a principled framework for aligning metric measure (mm) spaces based solely on their intrinsic structure. Its ability to identify isomorphic representations of distributions across spaces renders it valuable for comparing data where equality up to isomorphism occurs naturally such as in graphs or, more generally, distributions on graphs. Recently, a type of dual form for the GW distance between Euclidean distributions with the squared Euclidean or inner product costs was derived, spurring the development of new statistical and algorithmic results for this setting. This work furnishes a novel duality result for GW distances with and without entropic regularization that is applicable to all finitely supported mm spaces. Leveraging this result, we derive the sample complexity of empirical GW distances between finite mm spaces, as well as limit distributions under proper centering and scaling. Furthermore, we propose new algorithms for solving the regularized GW problem which are subject to formal convergence guarantees. These statistical and algorithmic advancements give rise to a principled and efficient framework for testing whether two distributions on the set of graphs with a fixed number of nodes are isomorphic based on samples.
Related
- Capacity-Constrained Wasserstein Barycenters: Existence, Duality, and Entropic Regularization
- Toland duality and particle approximations for signed Wasserstein barycenters
- Almost Tight Bounds for Isomorphism Testing and Basis Construction in Finite Abelian Groups
- Wasserstein accelerated proximal gradient algorithms
- Continuous-Time Wasserstein Distributionally Robust Control: Limits, Duality, and Stability
BibTeX
@misc{rioux2026discrete,
title = {{Discrete Gromov-Wasserstein Duality: Algorithms and Isomorphism Testing}},
author = {Gabriel Rioux and Joanna Marks and Riccardo Passeggeri and Ziv Goldfeld},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.03094},
eprint = {2609.03094},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.03094},
}
RIS
TY - UNPB
TI - Discrete Gromov-Wasserstein Duality: Algorithms and Isomorphism Testing
AU - Gabriel Rioux
AU - Joanna Marks
AU - Riccardo Passeggeri
AU - Ziv Goldfeld
PY - 2026
DA - 2026/09/02
PB - arXiv
DO - 10.48550/arxiv.2609.03094
UR - https://arxiv.org/abs/2609.03094
AB - The Gromov-Wasserstein (GW) distance provides a principled framework for aligning metric measure (mm) spaces based solely on their intrinsic structure. Its ability to identify isomorphic representations of distributions across spaces renders it valuable for comparing data where equality up to isomorphism occurs naturally such as in graphs or, more generally, distributions on graphs. Recently, a type of dual form for the GW distance between Euclidean distributions with the squared Euclidean or inner product costs was derived, spurring the development of new statistical and algorithmic results for this setting. This work furnishes a novel duality result for GW distances with and without entropic regularization that is applicable to all finitely supported mm spaces. Leveraging this result, we derive the sample complexity of empirical GW distances between finite mm spaces, as well as limit distributions under proper centering and scaling. Furthermore, we propose new algorithms for solving the regularized GW problem which are subject to formal convergence guarantees. These statistical and algorithmic advancements give rise to a principled and efficient framework for testing whether two distributions on the set of graphs with a fixed number of nodes are isomorphic based on samples.
ER -