← Back to all news
arXiv Statistics ML By Gabriel Rioux, Joanna Marks, Riccardo Passeggeri, Ziv Goldfeld

Discrete Gromov-Wasserstein Duality: Algorithms and Isomorphism Testing

Read the original on arXiv Statistics ML →

The paper presents a new duality formulation for the Gromov‑Wasserstein distance that applies to all finitely supported metric‑measure spaces, with and without entropic regularization. Using this duality, the authors derive sample‑complexity bounds and limit distributions for empirical GW distances, and introduce algorithms with formal convergence guarantees. These results enable a principled, efficient method for testing isomorphism between distributions on graphs with a fixed number of nodes based on samples.

Machine-generated by The Flow from the publisher's headline and feed description — not written or checked by a human. The full article lives at arXiv Statistics ML.

Related stories

arXiv Machine Learning
Jun 10

$k$-Nearest Neighbors in Gromov--Wasserstein Space

arXiv:2606. 10295v1 Announce Type: cross Abstract: The Gromov--Wasserstein (GW) distance provides a framework for comparing metric measure spaces, regardless of their underlying structure or geometry.

By Kaitlyn Hohmeier, Nicolas Fraiman, Caroline Moosmueller
rag
More like this →
arXiv Computer Vision
Oct 5

Unlocking Geodesic Gromov-Wasserstein Distances for 3D Modeling

The paper introduces EGGroW, efficient algorithms for computing geodesic Gromov-Wasserstein distances using entropic Sinkhorn-like methods, GenusSink techniques, and random features. It addresses the cubic time complexity of traditional GWD calculations on dense intra-space distance matrices, enabling scalable comparisons of probabilistic distributions on general geodesic manifolds and graph shortest‑path distances. The authors demonstrate EGGroW’s effectiveness in downstream tasks such as 3D pose estimation and partial 3D template recovery, showing accurate results where Euclidean‑based methods fail while maintaining a light computational footprint.

By Krzysztof Marcin Choromanski, Derek Long, Ananya Parashar, Dwaipayan Saha
computer-vision
More like this →
arXiv Machine Learning
Aug 18

The Observable Wasserstein Distance

arXiv:2605. 09916v2 Announce Type: replace-cross Abstract: We introduce the observable Wasserstein distance, a framework for deriving lower bounds on the Wasserstein distance between probability measures on Polish metric spaces, designed to bypass the computational intractability of exact optimal transport in large-scale, non-Euclidean datasets.

By Edivaldo Lopes dos Santos, Leandro Vicente Mauri, Washington Mio, Tom Needham
More like this →
arXiv Machine Learning
Oct 12

Linearized Wasserstein dimensionality reduction with approximation guarantees

The paper introduces LOT Wassmap, an algorithm designed to uncover low‑dimensional structures in the Wasserstein space without computing a full pairwise distance matrix. It leverages approximation schemes such as Sinkhorn distances and linearized optimal transport to accelerate computations, and provides theoretical guarantees on embedding quality even when only finite samples are available. Experiments show that LOT Wassmap achieves accurate embeddings that improve with larger sample sizes while significantly reducing computational cost compared to traditional pairwise‑distance‑based methods.

By Alexander Cloninger, Keaton Hamm, Varun Khurana, Caroline Moosm\"uller
rag
More like this →