# Gromov-Wasserstein Quantization and Clustering: Structure, Rates, and Algorithms

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 37 of its 78 references that are in the map.
- First posted on arXiv 11 Aug 2026.

## Builds on (most cited first, 30 of 37)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Pruning Filters for Efficient ConvNets](https://mlsanity.com/paper/1608.08710/) (2016)
- [A Simple and Effective Pruning Approach for Large Language Models](https://mlsanity.com/paper/2306.11695/) (2023)
- [Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networks](https://mlsanity.com/paper/2102.00554/) (2021)
- [Model Fusion via Optimal Transport](https://mlsanity.com/paper/1910.05653/) (2019)
- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (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)
- [Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties](https://mlsanity.com/paper/1811.02834/) (2018)
- [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)
- [Generalized Spectral Clustering via Gromov-Wasserstein Learning](https://mlsanity.com/paper/2006.04163/) (2020)
- [Online Graph Dictionary Learning](https://mlsanity.com/paper/2102.06555/) (2021)
- [A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening](https://mlsanity.com/paper/1902.09702/) (2019)
- [Gromov-Wasserstein Factorization Models for Graph Clustering](https://mlsanity.com/paper/1911.08530/) (2019)
- [Quantized Gromov-Wasserstein](https://mlsanity.com/paper/2104.02013/) (2021)
- [On a linear Gromov-Wasserstein distance](https://mlsanity.com/paper/2112.11964/) (2021)
- [On the existence of Monge maps for the Gromov-Wasserstein problem](https://mlsanity.com/paper/2210.11945/) (2022)
- [A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening](https://mlsanity.com/paper/2306.08854/) (2023)
- [Neural Pruning for 3D Scene Reconstruction: Efficient NeRF Acceleration](https://mlsanity.com/paper/2504.00950/) (2025)
- [Gromov-Wasserstein Averaging in a Riemannian Framework](https://mlsanity.com/paper/1910.04308/) (2019)
- [Multi-Marginal Gromov-Wasserstein Transport and Barycenters](https://mlsanity.com/paper/2205.06725/) (2022)
- [A Novel Sliced Fused Gromov-Wasserstein Distance](https://mlsanity.com/paper/2508.02364/) (2025)
- [On Assignment Problems Related to Gromov-Wasserstein Distances on the Real Line](https://mlsanity.com/paper/2205.09006/) (2022)
- [From Optimal Transport to Discrepancy](https://mlsanity.com/paper/2002.01189/) (2020)
- [Globally solving the Gromov-Wasserstein problem for point clouds in low dimensional Euclidean spaces](https://mlsanity.com/paper/2307.09057/) (2023)
- [Sketching and Clustering Metric Measure Spaces](https://mlsanity.com/paper/1801.00551/) (2018)
- [Slicing Wasserstein Over Wasserstein Via Functional Optimal Transport](https://mlsanity.com/paper/2509.22138/) (2025)

## Abstract (arXiv)

Clustering is a fundamental class of data analysis techniques with the most important representatives being centroid-based methods like k-means. Such methods are strongly connected to quantization problems, which aim to approximate general probability measures with discrete ones. For example, k-means corresponds to quantization with respect to the Wasserstein distance. While Wasserstein quantization clusters points within a fixed space, this paper studies Gromov-Wasserstein (GW) quantization, which additionally aims at clustering the ambient geometry of the space. We show existence of solutions to the GW quantization problem and give a characterization that justifies an analogue to the k-means algorithm (Lloyd's algorithm) to approximate them numerically. We further calculate the quantization rate for usual Euclidean geometries that are used in the GW context, and relate it to standard Wasserstein quantization rates. Finally, numerical experiments show that GW quantization opens up many modeling possibilities beyond normal clustering methods (e.g., for geodesic distances of 3D shapes or structured pruning of neural networks) and that the introduced algorithm leads to useful numerical solutions with approximation quality often in line with theoretically optimal rates.