# The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation

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

## Key facts

- Cited by 56 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Sep 2020.

## Built on by (most cited first, 30 of 56)

- [Unbalanced Optimal Transport, from Theory to Numerics](https://mlsanity.com/paper/2211.08775/) (2022)
- [Accurate Point Cloud Registration with Robust Optimal Transport](https://mlsanity.com/paper/2111.00648/) (2021)
- [Temporally Consistent Unbalanced Optimal Transport for Unsupervised Action Segmentation](https://mlsanity.com/paper/2404.01518/) (2024)
- [GENOT: Entropic (Gromov) Wasserstein Flow Matching with Applications to Single-Cell Genomics](https://mlsanity.com/paper/2310.09254/) (2023)
- [On Robust Optimal Transport: Computational Complexity and Barycenter Computation](https://mlsanity.com/paper/2102.06857/) (2021)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Aligning individual brains with Fused Unbalanced Gromov-Wasserstein](https://mlsanity.com/paper/2206.09398/) (2022)
- [Semi-relaxed Gromov-Wasserstein divergence with applications on graphs](https://mlsanity.com/paper/2110.02753/) (2021)
- [Quantized Gromov-Wasserstein](https://mlsanity.com/paper/2104.02013/) (2021)
- [A Fused Gromov-Wasserstein Framework for Unsupervised Knowledge Graph Entity Alignment](https://mlsanity.com/paper/2305.06574/) (2023)
- [Weisfeiler-Lehman meets Gromov-Wasserstein](https://mlsanity.com/paper/2202.02495/) (2022)
- [Entropic Gromov-Wasserstein between Gaussian Distributions](https://mlsanity.com/paper/2108.10961/) (2021)
- [Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsification](https://mlsanity.com/paper/2205.13573/) (2022)
- [A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data](https://mlsanity.com/paper/2303.06595/) (2023)
- [Aligning brain functions boosts the decoding of visual semantics in novel subjects](https://mlsanity.com/paper/2312.06467/) (2023)
- [Semidefinite Relaxations of the Gromov-Wasserstein Distance](https://mlsanity.com/paper/2312.14572/) (2023)
- [Gromov-Wasserstein Autoencoders](https://mlsanity.com/paper/2209.07007/) (2022)
- [Unbalanced Low-rank Optimal Transport Solvers](https://mlsanity.com/paper/2305.19727/) (2023)
- [Any2Graph: Deep End-To-End Supervised Graph Prediction With An Optimal Transport Loss](https://mlsanity.com/paper/2402.12269/) (2024)
- [Unbalanced CO-Optimal Transport](https://mlsanity.com/paper/2205.14923/) (2022)
- [Outlier-Robust Gromov-Wasserstein for Graph Data](https://mlsanity.com/paper/2302.04610/) (2023)
- [Uncovering Challenges of Solving the Continuous Gromov-Wasserstein Problem](https://mlsanity.com/paper/2303.05978/) (2023)
- [Cycle Consistent Probability Divergences Across Different Spaces](https://mlsanity.com/paper/2111.11328/) (2021)
- [Relative Translation Invariant Wasserstein Distance](https://mlsanity.com/paper/2409.02416/) (2024)
- [Unsupervised Learning for Optimal Transport plan prediction between unbalanced graphs](https://mlsanity.com/paper/2506.12025/) (2025)
- [Laplace Learning in Wasserstein Space](https://mlsanity.com/paper/2511.13229/) (2025)
- [Factored couplings in multi-marginal optimal transport via difference of convex programming](https://mlsanity.com/paper/2110.00629/) (2021)
- [Regularized Optimal Transport Layers for Generalized Global Pooling Operations](https://mlsanity.com/paper/2212.06339/) (2022)
- [Fast Gradient Computation for Gromov-Wasserstein Distance](https://mlsanity.com/paper/2404.08970/) (2024)
- [Metric properties of partial and robust Gromov-Wasserstein distances](https://mlsanity.com/paper/2411.02198/) (2024)

## Abstract (arXiv)

Comparing metric measure spaces (i.e. a metric space endowed with aprobability distribution) is at the heart of many machine learning problems. The most popular distance between such metric measure spaces is theGromov-Wasserstein (GW) distance, which is the solution of a quadratic assignment problem. The GW distance is however limited to the comparison of metric measure spaces endowed with a probability distribution. To alleviate this issue, we introduce two Unbalanced Gromov-Wasserstein formulations: a distance and a more tractable upper-bounding relaxation.They both allow the comparison of metric spaces equipped with arbitrary positive measures up to isometries. The first formulation is a positive and definite divergence based on a relaxation of the mass conservation constraint using a novel type of quadratically-homogeneous divergence. This divergence works hand in hand with the entropic regularization approach which is popular to solve large scale optimal transport problems. We show that the underlying non-convex optimization problem can be efficiently tackled using a highly parallelizable and GPU-friendly iterative scheme. The second formulation is a distance between mm-spaces up to isometries based on a conic lifting. Lastly, we provide numerical experiments onsynthetic examples and domain adaptation data with a Positive-Unlabeled learning task to highlight the salient features of the unbalanced divergence and its potential applications in ML.