mlsanityData to 14 Oct 2026

Note on computational complexity of the Gromov-Wasserstein distance

arXiv 2408.06525 ↗First posted 12 Aug 2024stat.ML cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

This note addresses computational difficulty of the Gromov-Wasserstein distance frequently mentioned in the literature. We provide details on the structure of the Gromov-Wasserstein distance optimization problem that show its non-convex quadratic nature for any instance of an input data. We further illustrate the non-convexity of the problem with several explicit examples.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 10 of its 33 references that are in the map. First posted on arXiv 12 Aug 2024.

Builds on

10 of 33 references.

References · 10

  1. 2019Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matchingcited by 103
  2. 2020Graph Optimal Transport for Cross-Domain Alignmentcited by 103
  3. 2022Optimal Transport Tools (OTT): A JAX Toolbox for all things Wassersteincited by 101
  4. 2018Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical propertiescited by 93
  5. 2021Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costscited by 61
  6. 2019Learning Generative Models across Incomparable Spacescited by 53
  7. 2021Cross-Domain Imitation Learning via Optimal Transportcited by 49
  8. 2020Generalized Spectral Clustering via Gromov-Wasserstein Learningcited by 38
  9. 2023Semidefinite Relaxations of the Gromov-Wasserstein Distancecited by 10
  10. 2023The Gromov-Wasserstein distance between spherescited by 6

Built on by

Not cited yet.