The NP-hardness of the Gromov-Wasserstein distance

Natalia Kravtsova
8/12/2024
stat.MLcs.LG

No confident code implementation found for this paper.

Abstract

This note addresses the property frequently mentioned in the literature that the Gromov-Wasserstein (GW) distance is NP-hard. We provide the details on the non-convex nature of the GW optimization problem that imply NP-hardness of the GW distance between finite spaces for any instance of an input data. We further illustrate the non-convexity of the problem with several explicit examples.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Metric properties of partial and robust Gromov-Wasserstein distances

84% match2024

Fast Gradient Computation for Gromov-Wasserstein Distance

82% match2024

Globally solving the Gromov-Wasserstein problem for point clouds in low dimensional Euclidean spaces

82% match2023

The Z-Gromov-Wasserstein Distance

80% match2024

Gromov-Wasserstein-like Distances in the Gaussian Mixture Models Space

79% match1 repo32023

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

78% match2 repos2.8k2023

Cite this paper

@article{kravtsova2024nphardness,
  title  = {The NP-hardness of the Gromov-Wasserstein distance},
  author = {Natalia Kravtsova},
  year   = {2024},
  eprint = {2408.06525},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2408.06525v3}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2408.06525.svg)](https://codeofpaper.com/paper/2408.06525)

Discussion