# Entropic Gromov-Wasserstein Distances: Stability and Algorithms

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 May 2023.

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

- [GENOT: Entropic (Gromov) Wasserstein Flow Matching with Applications to Single-Cell Genomics](https://mlsanity.com/paper/2310.09254/) (2023)
- [Lower Complexity Adaptation for Empirical Entropic Optimal Transport](https://mlsanity.com/paper/2306.13580/) (2023)
- [Structured Transforms Across Spaces with Cost-Regularized Optimal Transport](https://mlsanity.com/paper/2311.05788/) (2023)
- [Structure-Aware E(3)-Invariant Molecular Conformer Aggregation Networks](https://mlsanity.com/paper/2402.01975/) (2024)
- [On Robust Cross Domain Alignment](https://mlsanity.com/paper/2412.15861/) (2024)

## Abstract (arXiv)

The Gromov-Wasserstein (GW) distance quantifies discrepancy between metric measure spaces and provides a natural framework for aligning heterogeneous datasets. Alas, as exact computation of GW alignment is NP hard, entropic regularization provides an avenue towards a computationally tractable proxy. Leveraging a recently derived variational representation for the quadratic entropic GW (EGW) distance, this work derives the first efficient algorithms for solving the EGW problem subject to formal, non-asymptotic convergence guarantees. To that end, we derive smoothness and convexity properties of the objective in this variational problem, which enables its resolution by the accelerated gradient method. Our algorithms employs Sinkhorn's fixed point iterations to compute an approximate gradient, which we model as an inexact oracle. We furnish convergence rates towards local and even global solutions (the latter holds under a precise quantitative condition on the regularization parameter), characterize the effects of gradient inexactness, and prove that stationary points of the EGW problem converge towards a stationary point of the unregularized GW problem, in the limit of vanishing regularization. We provide numerical experiments that validate our theory and empirically demonstrate the state-of-the-art empirical performance of our algorithm.