# Semidefinite Relaxations of the Gromov-Wasserstein Distance

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 51 references that are in the map.
- First posted on arXiv 22 Dec 2023.

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

- [Flow Matching for Generative Modeling](https://mlsanity.com/paper/2210.02747/) (2022)
- [Flow Straight and Fast: Learning to Generate and Transfer Data with Rectified Flow](https://mlsanity.com/paper/2209.03003/) (2022)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Joint Distribution Optimal Transportation for Domain Adaptation](https://mlsanity.com/paper/1705.08848/) (2017)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019)
- [Sliced Gromov-Wasserstein](https://mlsanity.com/paper/1905.10124/) (2019)
- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation](https://mlsanity.com/paper/2009.04266/) (2020)
- [Learning Generative Models across Incomparable Spaces](https://mlsanity.com/paper/1905.05461/) (2019)
- [Online Graph Dictionary Learning](https://mlsanity.com/paper/2102.06555/) (2021)
- [Template based Graph Neural Network with Optimal Transport Distances](https://mlsanity.com/paper/2205.15733/) (2022)
- [Globally solving the Gromov-Wasserstein problem for point clouds in low dimensional Euclidean spaces](https://mlsanity.com/paper/2307.09057/) (2023)
- [Outlier-Robust Gromov-Wasserstein for Graph Data](https://mlsanity.com/paper/2302.04610/) (2023)
- [Moment-SoS Methods for Optimal Transport Problems](https://mlsanity.com/paper/2211.10742/) (2022)
- [A polynomial-time relaxation of the Gromov-Hausdorff distance](https://mlsanity.com/paper/1610.05214/) (2016)

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

- [Formation Shape Control using the Gromov-Wasserstein Metric](https://mlsanity.com/paper/2503.21538/) (2025)
- [A Provably Convergent and Practical Algorithm for Gromov--Wasserstein Optimal Transport](https://mlsanity.com/paper/2605.04175/) (2026)
- [Sliced Inner Product Gromov-Wasserstein Distances](https://mlsanity.com/paper/2605.08546/) (2026)
- [MIRROR: Aligning Semantic Relations from Language to Image via Gromov--Wasserstein](https://mlsanity.com/paper/2606.29462/) (2026)
- [Note on computational complexity of the Gromov-Wasserstein distance](https://mlsanity.com/paper/2408.06525/) (2024)
- [Gromov-Wasserstein and optimal transport: from assignment problems to probabilistic numeric](https://mlsanity.com/paper/2509.04089/) (2025)
- [Fused Gromov-Wasserstein Distance with Feature Selection](https://mlsanity.com/paper/2605.12161/) (2026)
- [Min Generalized Sliced Gromov Wasserstein: A Scalable Path to Gromov Wasserstein](https://mlsanity.com/paper/2605.13753/) (2026)
- [Convex Distance Operator Transport: A Convex and Geometry-Preserving Formulation](https://mlsanity.com/paper/2606.02047/) (2026)
- [Averaged Mirror Descent and Dual Gradient Methods: Convergent Algorithms for Entropic Gromov-Wasserstein Problems](https://mlsanity.com/paper/2609.31848/) (2026)

## Abstract (arXiv)

The Gromov-Wasserstein (GW) distance is an extension of the optimal transport problem that allows one to match objects between incomparable spaces. At its core, the GW distance is specified as the solution of a non-convex quadratic program and is not known to be tractable to solve. In particular, existing solvers for the GW distance are only able to find locally optimal solutions. In this work, we propose a semi-definite programming (SDP) relaxation of the GW distance. The relaxation can be viewed as the Lagrangian dual of the GW distance augmented with constraints that relate to the linear and quadratic terms of transportation plans. In particular, our relaxation provides a tractable (polynomial-time) algorithm to compute globally optimal transportation plans (in some instances) together with an accompanying proof of global optimality. Our numerical experiments suggest that the proposed relaxation is strong in that it frequently computes the globally optimal solution. Our Python implementation is available at https://github.com/tbng/gwsdp.