# Globally solving the Gromov-Wasserstein problem for point clouds in low dimensional Euclidean spaces

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 25 references that are in the map.
- First posted on arXiv 18 Jul 2023.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019)
- [Gromov-Wasserstein Alignment of Word Embedding Spaces](https://mlsanity.com/paper/1809.00013/) (2018)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [On a linear Gromov-Wasserstein distance](https://mlsanity.com/paper/2112.11964/) (2021)

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

- [Semidefinite Relaxations of the Gromov-Wasserstein Distance](https://mlsanity.com/paper/2312.14572/) (2023)
- [Gromov-Wasserstein-like Distances in the Gaussian Mixture Models Space](https://mlsanity.com/paper/2310.11256/) (2023)
- [Formation Shape Control using the Gromov-Wasserstein Metric](https://mlsanity.com/paper/2503.21538/) (2025)
- [Shape-of-You: Fused Gromov-Wasserstein Optimal Transport for Semantic Correspondence in-the-Wild](https://mlsanity.com/paper/2603.11618/) (2026)
- [A cutting plane algorithm for globally solving low dimensional k-means clustering problems](https://mlsanity.com/paper/2402.13595/) (2024)
- [Gromov-Wasserstein and optimal transport: from assignment problems to probabilistic numeric](https://mlsanity.com/paper/2509.04089/) (2025)
- [Gromov-Wasserstein Quantization and Clustering: Structure, Rates, and Algorithms](https://mlsanity.com/paper/2608.11016/) (2026)

## Abstract (arXiv)

This paper presents a framework for computing the Gromov-Wasserstein problem between two sets of points in low dimensional spaces, where the discrepancy is the squared Euclidean norm. The Gromov-Wasserstein problem is a generalization of the optimal transport problem that finds the assignment between two sets preserving pairwise distances as much as possible. This can be used to quantify the similarity between two formations or shapes, a common problem in AI and machine learning. The problem can be formulated as a Quadratic Assignment Problem (QAP), which is in general computationally intractable even for small problems. Our framework addresses this challenge by reformulating the QAP as an optimization problem with a low-dimensional domain, leveraging the fact that the problem can be expressed as a concave quadratic optimization problem with low rank. The method scales well with the number of points, and it can be used to find the global solution for large-scale problems with thousands of points. We compare the computational complexity of our approach with state-of-the-art methods on synthetic problems and apply it to a near-symmetrical problem which is of particular interest in computational biology.