# Semi-relaxed Gromov-Wasserstein divergence with applications on graphs

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 77 references that are in the map.
- First posted on arXiv 6 Oct 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019)
- [Wasserstein Weisfeiler-Lehman Graph Kernels](https://mlsanity.com/paper/1906.01277/) (2019)
- [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)
- [GOT: An Optimal Transport framework for Graph comparison](https://mlsanity.com/paper/1906.02085/) (2019)
- [Convergence Rate of Frank-Wolfe for Non-Convex Objectives](https://mlsanity.com/paper/1607.00345/) (2016)
- [The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation](https://mlsanity.com/paper/2009.04266/) (2020)
- [Distance Metric Learning using Graph Convolutional Networks: Application to Functional Brain Networks](https://mlsanity.com/paper/1703.02161/) (2017)
- [Generalized Spectral Clustering via Gromov-Wasserstein Learning](https://mlsanity.com/paper/2006.04163/) (2020)
- [Learning Graphons via Structured Gromov-Wasserstein Barycenters](https://mlsanity.com/paper/2012.05644/) (2020)
- [Online Graph Dictionary Learning](https://mlsanity.com/paper/2102.06555/) (2021)
- [Wasserstein Dictionary Learning: Optimal Transport-based unsupervised non-linear dictionary learning](https://mlsanity.com/paper/1708.01955/) (2017)
- [Bayesian Semi-supervised Learning with Graph Gaussian Processes](https://mlsanity.com/paper/1809.04379/) (2018)
- [Adjusting for Chance Clustering Comparison Measures](https://mlsanity.com/paper/1512.01286/) (2015)
- [Gromov-Wasserstein Factorization Models for Graph Clustering](https://mlsanity.com/paper/1911.08530/) (2019)
- [DS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems](https://mlsanity.com/paper/1711.10733/) (2017)
- [GAP: Generalizable Approximate Graph Partitioning Framework](https://mlsanity.com/paper/1903.00614/) (2019)
- [Mean-field theory of graph neural networks in graph partitioning](https://mlsanity.com/paper/1810.11908/) (2018)
- [Optimal spectral transportation with application to music transcription](https://mlsanity.com/paper/1609.09799/) (2016)

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

- [Unbalanced Optimal Transport, from Theory to Numerics](https://mlsanity.com/paper/2211.08775/) (2022)
- [A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening](https://mlsanity.com/paper/2306.08854/) (2023)
- [Fused Gromov-Wasserstein Graph Mixup for Graph-level Classifications](https://mlsanity.com/paper/2306.15963/) (2023)
- [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)
- [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)
- [On Probabilistic Embeddings in Optimal Dimension Reduction](https://mlsanity.com/paper/2408.02433/) (2024)
- [Estimating Long-term Heterogeneous Dose-response Curve: Generalization Bound Leveraging Optimal Transport Weights](https://mlsanity.com/paper/2406.19195/) (2024)
- [Metric properties of partial and robust Gromov-Wasserstein distances](https://mlsanity.com/paper/2411.02198/) (2024)
- [Gradual Domain Adaptation for Graph Learning](https://mlsanity.com/paper/2501.17443/) (2025)
- [Fast and Provably Convergent Algorithms for Gromov-Wasserstein in Graph Data](https://mlsanity.com/paper/2205.08115/) (2022)
- [On the Convergence of Semi-Relaxed Sinkhorn with Marginal Constraint and OT Distance Gaps](https://mlsanity.com/paper/2205.13846/) (2022)
- [Hybrid Gromov-Wasserstein Embedding for Capsule Learning](https://mlsanity.com/paper/2209.00232/) (2022)
- [Sliced Inner Product Gromov-Wasserstein Distances](https://mlsanity.com/paper/2605.08546/) (2026)
- [Interpolating between Clustering and Dimensionality Reduction with Gromov-Wasserstein](https://mlsanity.com/paper/2310.03398/) (2023)
- [Towards Pre-trained Graph Condensation via Optimal Transport](https://mlsanity.com/paper/2509.14722/) (2025)
- [Supervised Distributional Reduction via Optimal Transport and Dependence Maximization](https://mlsanity.com/paper/2605.27619/) (2026)
- [Bridging Maximum Likelihood and Optimal Transport for Efficient Inference and Model Selection in Stochastic Block Models](https://mlsanity.com/paper/2605.28488/) (2026)
- [Network Learning with Semi-relaxed Gromov-Wasserstein](https://mlsanity.com/paper/2606.02223/) (2026)
- [Unlocking Geodesic Gromov-Wasserstein Distances for 3D Modeling](https://mlsanity.com/paper/2609.32824/) (2026)

## Abstract (arXiv)

Comparing structured objects such as graphs is a fundamental operation involved in many learning tasks. To this end, the Gromov-Wasserstein (GW) distance, based on Optimal Transport (OT), has proven to be successful in handling the specific nature of the associated objects. More specifically, through the nodes connectivity relations, GW operates on graphs, seen as probability measures over specific spaces. At the core of OT is the idea of conservation of mass, which imposes a coupling between all the nodes from the two considered graphs. We argue in this paper that this property can be detrimental for tasks such as graph dictionary or partition learning, and we relax it by proposing a new semi-relaxed Gromov-Wasserstein divergence. Aside from immediate computational benefits, we discuss its properties, and show that it can lead to an efficient graph dictionary learning algorithm. We empirically demonstrate its relevance for complex tasks on graphs such as partitioning, clustering and completion.