# Quantized Gromov-Wasserstein

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 38 references that are in the map.
- First posted on arXiv 5 Apr 2021.

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

- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [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)
- [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)
- [Sliced Gromov-Wasserstein](https://mlsanity.com/paper/1905.10124/) (2019)
- [Minibatch optimal transport distances; analysis and applications](https://mlsanity.com/paper/2101.01792/) (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)
- [Generalized Spectral Clustering via Gromov-Wasserstein Learning](https://mlsanity.com/paper/2006.04163/) (2020)
- [Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces](https://mlsanity.com/paper/2002.01615/) (2020)
- [Fluid Communities: A Competitive, Scalable and Diverse Community Detection Algorithm](https://mlsanity.com/paper/1703.09307/) (2017)
- [MREC: a fast and versatile framework for aligning and matching point clouds with applications to single cell molecular data](https://mlsanity.com/paper/2001.01666/) (2020)
- [Gromov-Wasserstein Averaging in a Riemannian Framework](https://mlsanity.com/paper/1910.04308/) (2019)
- [Solving graph compression via optimal transport](https://mlsanity.com/paper/1905.12158/) (2019)
- [Sketching and Clustering Metric Measure Spaces](https://mlsanity.com/paper/1801.00551/) (2018)

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

- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Template based Graph Neural Network with Optimal Transport Distances](https://mlsanity.com/paper/2205.15733/) (2022)
- [The Z-Gromov-Wasserstein Distance](https://mlsanity.com/paper/2408.08233/) (2024)
- [Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsification](https://mlsanity.com/paper/2205.13573/) (2022)
- [Reversible Gromov-Monge Sampler for Simulation-Based Inference](https://mlsanity.com/paper/2109.14090/) (2021)
- [Unbalanced Low-rank Optimal Transport Solvers](https://mlsanity.com/paper/2305.19727/) (2023)
- [Subspace Detours Meet Gromov-Wasserstein](https://mlsanity.com/paper/2110.10932/) (2021)
- [Gromov-Wasserstein-like Distances in the Gaussian Mixture Models Space](https://mlsanity.com/paper/2310.11256/) (2023)
- [Scalable unsupervised alignment of general metric and non-metric structures](https://mlsanity.com/paper/2406.13507/) (2024)
- [An in depth look at the Procrustes-Wasserstein distance: properties and barycenters](https://mlsanity.com/paper/2507.00894/) (2025)
- [Revisiting invariances and introducing priors in Gromov-Wasserstein distances](https://mlsanity.com/paper/2307.10093/) (2023)
- [Gromov-Wasserstein and optimal transport: from assignment problems to probabilistic numeric](https://mlsanity.com/paper/2509.04089/) (2025)
- [Min Generalized Sliced Gromov Wasserstein: A Scalable Path to Gromov Wasserstein](https://mlsanity.com/paper/2605.13753/) (2026)
- [Bridging Maximum Likelihood and Optimal Transport for Efficient Inference and Model Selection in Stochastic Block Models](https://mlsanity.com/paper/2605.28488/) (2026)
- [Gromov-Wasserstein Quantization and Clustering: Structure, Rates, and Algorithms](https://mlsanity.com/paper/2608.11016/) (2026)
- [Gromov-Monge Flow Matching for Equivariant Graph Generation](https://mlsanity.com/paper/2608.26961/) (2026)
- [Unlocking Geodesic Gromov-Wasserstein Distances for 3D Modeling](https://mlsanity.com/paper/2609.32824/) (2026)
- [FlashSinkhorn 2: Block-Sparse Entropic Optimal Transport](https://mlsanity.com/paper/2610.02395/) (2026)

## Abstract (arXiv)

The Gromov-Wasserstein (GW) framework adapts ideas from optimal transport to allow for the comparison of probability distributions defined on different metric spaces. Scalable computation of GW distances and associated matchings on graphs and point clouds have recently been made possible by state-of-the-art algorithms such as S-GWL and MREC. Each of these algorithmic breakthroughs relies on decomposing the underlying spaces into parts and performing matchings on these parts, adding recursion as needed. While very successful in practice, theoretical guarantees on such methods are limited. Inspired by recent advances in the theory of quantization for metric measure spaces, we define Quantized Gromov Wasserstein (qGW): a metric that treats parts as fundamental objects and fits into a hierarchy of theoretical upper bounds for the GW problem. This formulation motivates a new algorithm for approximating optimal GW matchings which yields algorithmic speedups and reductions in memory complexity. Consequently, we are able to go beyond outperforming state-of-the-art and apply GW matching at scales that are an order of magnitude larger than in the existing literature, including datasets containing over 1M points.