# A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 53 references that are in the map.
- First posted on arXiv 12 Mar 2023.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [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)
- [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)
- [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)
- [Dirichlet Graph Variational Autoencoder](https://mlsanity.com/paper/2010.04408/) (2020)
- [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)
- [A Unified Approach to Error Bounds for Structured Convex Optimization Problems](https://mlsanity.com/paper/1512.03518/) (2015)
- [Semi-relaxed Gromov-Wasserstein divergence with applications on graphs](https://mlsanity.com/paper/2110.02753/) (2021)
- [Graph Neural Networks for Multimodal Single-Cell Data Integration](https://mlsanity.com/paper/2203.01884/) (2022)
- [Robust Attributed Graph Alignment via Joint Structure Learning and Optimal Transport](https://mlsanity.com/paper/2301.12721/) (2023)
- [A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization](https://mlsanity.com/paper/2006.16440/) (2020)
- [Mask-GVAE: Blind Denoising Graphs via Partition](https://mlsanity.com/paper/2102.04228/) (2021)
- [A Fast and Accurate Splitting Method for Optimal Transport: Analysis and Implementation](https://mlsanity.com/paper/2110.11738/) (2021)
- [Geometry of Graph Partitions via Optimal Transport](https://mlsanity.com/paper/1910.09618/) (2019)

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

- [Fused Gromov-Wasserstein Graph Mixup for Graph-level Classifications](https://mlsanity.com/paper/2306.15963/) (2023)
- [Unbalanced Low-rank Optimal Transport Solvers](https://mlsanity.com/paper/2305.19727/) (2023)
- [Spurious Stationarity and Hardness Results for Bregman Proximal-Type Algorithms](https://mlsanity.com/paper/2404.08073/) (2024)
- [Gradual Domain Adaptation for Graph Learning](https://mlsanity.com/paper/2501.17443/) (2025)
- [Covariance alignment: from maximum likelihood estimation to Gromov-Wasserstein](https://mlsanity.com/paper/2311.13595/) (2023)
- [A Fused Gromov-Wasserstein Approach to Subgraph Contrastive Learning](https://mlsanity.com/paper/2502.20885/) (2025)
- [A Provably Convergent and Practical Algorithm for Gromov--Wasserstein Optimal Transport](https://mlsanity.com/paper/2605.04175/) (2026)
- [The Joint Gromov Wasserstein Objective for Multiple Object Matching](https://mlsanity.com/paper/2511.16868/) (2025)
- [Fused Gromov-Wasserstein Distance with Feature Selection](https://mlsanity.com/paper/2605.12161/) (2026)
- [Establishing Boundary KKT Convergence of Mirror Descent through Reparameterization](https://mlsanity.com/paper/2608.07248/) (2026)
- [Adaptive Bregman Alternating Projections for Feasible Gromov-Wasserstein Learning](https://mlsanity.com/paper/2610.04264/) (2026)

## Abstract (arXiv)

In this work, we present the Bregman Alternating Projected Gradient (BAPG) method, a single-loop algorithm that offers an approximate solution to the Gromov-Wasserstein (GW) distance. We introduce a novel relaxation technique that balances accuracy and computational efficiency, albeit with some compromises in the feasibility of the coupling map. Our analysis is based on the observation that the GW problem satisfies the Luo-Tseng error bound condition, which relates to estimating the distance of a point to the critical point set of the GW problem based on the optimality residual. This observation allows us to provide an approximation bound for the distance between the fixed-point set of BAPG and the critical point set of GW. Moreover, under a mild technical assumption, we can show that BAPG converges to its fixed point set. The effectiveness of BAPG has been validated through comprehensive numerical experiments in graph alignment and partition tasks, where it outperforms existing methods in terms of both solution quality and wall-clock time.