Note on computational complexity of the Gromov-Wasserstein distance

2024/08/12 by Natalia Kravtsova, Kravtsova, Natalia · 1 citation
Mathematics · #Commutative Algebra and Its Applications #FOS: Computer and information sciences #Geometric and Algebraic Topology #Homotopy and Cohomology in Algebraic Topology #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · pdf · doi:10.48550/arxiv.2408.06525

openalex publication_date 2024/08/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

Abstract

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.

Cited by

• Rigid-Invariant Sliced Wasserstein via Independent Embeddings

Related

• Semidefinite Relaxations of the Gromov-Wasserstein Distance
• Sliced Gromov-Wasserstein
• Metric properties of partial and robust Gromov-Wasserstein distances
• Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs
• Computing the Gromov--Hausdorff distance using gradient methods