# Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsification

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 77 references that are in the map.
- First posted on arXiv 26 May 2022.

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

- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [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)
- [Max-Sliced Wasserstein Distance and its use for GANs](https://mlsanity.com/paper/1904.05877/) (2019)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [Missing Data Imputation using Optimal Transport](https://mlsanity.com/paper/2002.03860/) (2020)
- [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)
- [On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm](https://mlsanity.com/paper/2002.03293/) (2020)
- [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)
- [Learning Generative Models across Incomparable Spaces](https://mlsanity.com/paper/1905.05461/) (2019)
- [Stochastic Frank-Wolfe Methods for Nonconvex Optimization](https://mlsanity.com/paper/1607.08254/) (2016)
- [A Statistical Perspective on Algorithmic Leveraging](https://mlsanity.com/paper/1306.5362/) (2013)
- [Generalized Spectral Clustering via Gromov-Wasserstein Learning](https://mlsanity.com/paper/2006.04163/) (2020)
- [Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenters](https://mlsanity.com/paper/2202.03813/) (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)
- [Unsupervised Hyperalignment for Multilingual Word Embeddings](https://mlsanity.com/paper/1811.01124/) (2018)
- [Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces](https://mlsanity.com/paper/2002.01615/) (2020)
- [Linear Time Sinkhorn Divergences using Positive Features](https://mlsanity.com/paper/2006.07057/) (2020)
- [Large-scale optimal transport map estimation using projection pursuit](https://mlsanity.com/paper/2106.05838/) (2021)
- [Recognizing Cuneiform Signs Using Graph Based Methods](https://mlsanity.com/paper/1802.05908/) (2018)
- [Optimal Distributed Subsampling for Maximum Quasi-Likelihood Estimators with Massive Data](https://mlsanity.com/paper/2005.10435/) (2020)
- [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)
- [Fast Sinkhorn I: An O(N) algorithm for the Wasserstein-1 metric](https://mlsanity.com/paper/2202.10042/) (2022)
- [Near-Optimal Entrywise Sampling of Numerically Sparse Matrices](https://mlsanity.com/paper/2011.01777/) (2020)

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

- [Temporally Consistent Unbalanced Optimal Transport for Unsupervised Action Segmentation](https://mlsanity.com/paper/2404.01518/) (2024)
- [The Z-Gromov-Wasserstein Distance](https://mlsanity.com/paper/2408.08233/) (2024)
- [Hilbert Curve Projection Distance for Distribution Comparison](https://mlsanity.com/paper/2205.15059/) (2022)
- [Importance Sparsification for Sinkhorn Algorithm](https://mlsanity.com/paper/2306.06581/) (2023)
- [Fast Gradient Computation for Gromov-Wasserstein Distance](https://mlsanity.com/paper/2404.08970/) (2024)
- [Decentralized Entropic Optimal Transport for Distributed Distribution Comparison](https://mlsanity.com/paper/2301.12065/) (2023)
- [Biomechanical-phase based Temporal Segmentation in Sports Videos: a Demonstration on Javelin-Throw](https://mlsanity.com/paper/2509.24606/) (2025)
- [Gromov-Wasserstein and optimal transport: from assignment problems to probabilistic numeric](https://mlsanity.com/paper/2509.04089/) (2025)
- [Core-elements Subsampling for Alternating Least Squares](https://mlsanity.com/paper/2509.18024/) (2025)
- [Towards Effective and Efficient Graph Alignment without Supervision](https://mlsanity.com/paper/2603.08526/) (2026)
- [SRRM: Improving Recursive Transport Surrogates in the Small-Discrepancy Regime](https://mlsanity.com/paper/2603.18781/) (2026)

## Abstract (arXiv)

As a valid metric of metric-measure spaces, Gromov-Wasserstein (GW) distance has shown the potential for matching problems of structured data like point clouds and graphs. However, its application in practice is limited due to the high computational complexity. To overcome this challenge, we propose a novel importance sparsification method, called textscSpar-GW, to approximate GW distance efficiently. In particular, instead of considering a dense coupling matrix, our method leverages a simple but effective sampling strategy to construct a sparse coupling matrix and update it with few computations. The proposed textscSpar-GW method is applicable to the GW distance with arbitrary ground cost, and it reduces the complexity from O(n4) to O(n2+δ) for an arbitrary small δ>0. Theoretically, the convergence and consistency of the proposed estimation for GW distance are established under mild regularity conditions. In addition, this method can be extended to approximate the variants of GW distance, including the entropic GW distance, the fused GW distance, and the unbalanced GW distance. Experiments show the superiority of our textscSpar-GW to state-of-the-art methods in both synthetic and real-world tasks.