mlsanityData to 7 Oct 2026

Fast and Provably Convergent Algorithms for Gromov-Wasserstein in Graph Data

arXiv 2205.08115 ↗First posted 17 May 2022cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

In this paper, we study the design and analysis of a class of efficient algorithms for computing the Gromov-Wasserstein (GW) distance tailored to large-scale graph learning tasks. Armed with the Luo-Tseng error bound condition~citepluo1992error, two proposed algorithms, called Bregman Alternating Projected Gradient (BAPG) and hybrid Bregman Proximal Gradient (hBPG) enjoy the convergence guarantees. Upon task-specific properties, our analysis further provides novel theoretical insights to guide how to select the best-fit method. As a result, we are able to provide comprehensive experiments to validate the effectiveness of our methods on a host of tasks, including graph alignment, graph partition, and shape matching. In terms of both wall-clock time and modeling performance, the proposed methods achieve state-of-the-art results.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 21 of its 57 references that are in the map. First posted on arXiv 17 May 2022.

Builds on

21 of 57 references.

References · 21

  1. 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,277
  2. 2018Optimal Transport for structured data with application on graphscited by 170
  3. 2019Gromov-Wasserstein Learning for Graph Matching and Node Embeddingcited by 125
  4. 2019Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matchingcited by 102
  5. 2018Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical propertiescited by 93
  6. 2019Sliced Gromov-Wassersteincited by 66
  7. 2021Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costscited by 61
  8. 2016Convergence Rate of Frank-Wolfe for Non-Convex Objectivescited by 59
  9. 2020The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxationcited by 55
  10. 2019Learning Generative Models across Incomparable Spacescited by 53
  11. 2020Generalized Spectral Clustering via Gromov-Wasserstein Learningcited by 37
  12. 2021Online Graph Dictionary Learningcited by 37
9 more
  1. 2020Learning Graphons via Structured Gromov-Wasserstein Barycenterscited by 36
  2. 2016Calculus of the exponent of Kurdyka-Lojasiewicz inequality and its applications to linear convergence of first-order methodscited by 35
  3. 2015A Unified Approach to Error Bounds for Structured Convex Optimization Problemscited by 21
  4. 2021Semi-relaxed Gromov-Wasserstein divergence with applications on graphscited by 21
  5. 2018Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimizationcited by 20
  6. 2020A global dual error bound and its application to the analysis of linearly constrained nonconvex optimizationcited by 13
  7. 2021A Fast and Accurate Splitting Method for Optimal Transport: Analysis and Implementationcited by 8
  8. 2019Geometry of Graph Partitions via Optimal Transportcited by 6
  9. 2017On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytopecited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Shape-of-You: Fused Gromov-Wasserstein Optimal Transport for Semantic Correspondence in-the-Wildcited by 0