# Metric properties of partial and robust Gromov-Wasserstein distances

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 40 references that are in the map.
- First posted on arXiv 4 Nov 2024.

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

- [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019)
- [Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties](https://mlsanity.com/paper/1811.02834/) (2018)
- [The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation](https://mlsanity.com/paper/2009.04266/) (2020)
- [Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Model](https://mlsanity.com/paper/1506.00691/) (2015)
- [CO-Optimal Transport](https://mlsanity.com/paper/2002.03731/) (2020)
- [Generalized Spectral Clustering via Gromov-Wasserstein Learning](https://mlsanity.com/paper/2006.04163/) (2020)
- [Semi-relaxed Gromov-Wasserstein divergence with applications on graphs](https://mlsanity.com/paper/2110.02753/) (2021)
- [Generalized Dimension Reduction Using Semi-Relaxed Gromov-Wasserstein Distance](https://mlsanity.com/paper/2405.15959/) (2024)
- [The Z-Gromov-Wasserstein Distance](https://mlsanity.com/paper/2408.08233/) (2024)
- [Gromov-Wasserstein Averaging in a Riemannian Framework](https://mlsanity.com/paper/1910.04308/) (2019)
- [A New Robust Partial p-Wasserstein-Based Metric for Comparing Distributions](https://mlsanity.com/paper/2405.03664/) (2024)
- [Outlier-Robust Gromov-Wasserstein for Graph Data](https://mlsanity.com/paper/2302.04610/) (2023)
- [Partial Gromov-Wasserstein Metric](https://mlsanity.com/paper/2402.03664/) (2024)
- [Geometry of the Space of Partitioned Networks: A Unified Theoretical and Computational Framework](https://mlsanity.com/paper/2409.06302/) (2024)

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

- [Conic Formulations of Transport Metrics for Unbalanced Measure Networks and Hypernetworks](https://mlsanity.com/paper/2508.10888/) (2025)
- [Robust Alignment via Partial Gromov-Wasserstein Distances](https://mlsanity.com/paper/2506.21507/) (2025)

## Abstract (arXiv)

The Gromov-Wasserstein (GW) distances define a family of metrics, based on ideas from optimal transport, which enable comparisons between probability measures defined on distinct metric spaces. They are particularly useful in areas such as network analysis and geometry processing, as computation of a GW distance involves solving for registration between the objects which minimizes geometric distortion. Although GW distances have proven useful for various applications in the recent machine learning literature, it has been observed that they are inherently sensitive to outlier noise and cannot accommodate partial matching. This has been addressed by various constructions building on the GW framework; in this article, we focus specifically on a natural relaxation of the GW optimization problem, introduced by Chapel et al., which is aimed at addressing exactly these shortcomings. Our goal is to understand the theoretical properties of this relaxed optimization problem, from the viewpoint of metric geometry. While the relaxed problem fails to induce a metric, we derive precise characterizations of how it fails the axioms of non-degeneracy and triangle inequality. These observations lead us to define a novel family of distances, whose construction is inspired by the Prokhorov and Ky Fan distances, as well as by the recent work of Raghvendra et al. on robust versions of classical Wasserstein distance. We show that our new distances define true metrics, that they induce the same topology as the GW distances, and that they enjoy additional robustness to perturbations. These results provide a mathematically rigorous basis for using our robust partial GW distances in applications where outliers and partial matching are concerns.