Pith. Sign in

REVIEW

Graph Distortion Distances, Gromov-Hausdorff and the Hardness of Gromov-Wasserstein

PaperPDF from arXiv

data files

ReviewThe objections and verdict, as JSON Paper breakdownThe authors' claims, conditions and measurements, as JSON Signed receiptProof this review has not been altered
X Bluesky LinkedIn Reddit Hacker News
Jens Breitung, Timo Gervens, Julius Pörzgen

Discrete Mathematics · Submitted 12 Oct 2026 · 102 references

Pith's verdict: The paper packs a lot—real contributions on maximum distortion and path embedding, but the flagship GW-hardness proof relies on a Lemma 46 whose lower bound I don't fully trust on a first pass; that part needs careful refereeing.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on October 14, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

  1. T0 AI review An AI read the paper and answered a fixed list of questions.
  2. T1 Audit Automatic checks that the references and files the paper relies on exist and match.
  3. T2 Compute The paper's code or calculations re-run with the same results.
  4. T3 Formal statement The claims written out in a formal math language a computer can read.
  5. T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 2 major objections · 6 minor · Ask about this paper · The compiled record · Read the full review →
Challenge this review Comment (0) Read on arXiv ↗
Cite ▾
arXiv ID2610.16926 (version 1)
Pith ID7OPPNKGX, Pith's permanent record of this paper and its review
CitationJens Breitung, Julius P\"orzgen, Timo Gervens. "Graph Distortion Distances, Gromov-Hausdorff and the Hardness of Gromov-Wasserstein." arXiv:2610.16926 (2026). https://pith.science/paper/7OPPNKGX
Cite this reviewBibTeX for Pith's review of this paper
Claim paper

Why Pith says this

Highlight any text to comment on it.

Referee report

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

The authors provide the first formal proof that the Gromov-Wasserstein distance is NP-hard and establish inapproximability for maximum, local, and global graph distortion distances.

The reading

Graphs can be compared by how much their shortest-path distances change when you match their vertices. This paper defines a family of graph similarity measures called graph distortion distances, which capture maximum, global, and local discrepancies. The authors prove that for the maximum distortion, even approximating it within a factor of two is NP-hard, even for simple tree structures. They also give a fast algorithm to exactly compute maximum distortion when one graph is a path. For global distortion, they relate it to the Gromov-Wasserstein distance, a popular tool in machine learning and shape matching, and prove that computing it is NP-hard. This fills a gap: many previous works claimed NP-hardness without a correct proof. The paper also provides approximation algorithms for graphs with bounded pathlength, and shows that local distortion distances are hard to approximate. Overall, the paper offers a comprehensive complexity analysis of these distortion-based graph metrics.
Extended reading notes

Core claim

The paper provides the first formal proof that computing the p-Gromov-Wasserstein distance is NP-hard for any 1 ≤ p ≤ ∞, even when both input spaces are simple graphs of the same order with uniform distribution. This result, stated as Theorem 4, is supported by a reduction from Three-Partition and a detailed analysis of fractional vertex alignments (doubly stochastic matrices).

Load-bearing premise

The hardness reductions rely on standard complexity assumptions (P ≠ NP) and the strong NP-completeness of Three-Partition. The reduction for Gromov-Wasserstein (Theorem 19) additionally assumes that the graphs are large enough and that the parameter M is chosen sufficiently large (144mA+1). The validity of the central claim depends on these assumptions, but they are standard and the construction is polynomial.

Original abstract

We study the computational complexity of graph distortion distances, a family of graph metrics measuring how vertex distances differ between two graphs. Formally, these distances are defined in terms of standard matrix norms on the difference of distance matrices under an optimal vertex alignment. The resulting metrics have natural interpretations, corresponding to three ways of measuring the distortion of shortest-path distances: the maximum distortion among all vertex pairs (entrywise maximum norm), global aggregation (entrywise $p$-norms), and local aggregation (operator $p$-norms) of distortions. For maximum distortion, we show that approximation below a factor of two is NP-hard even for highly restricted trees. Due to the close connection to the Gromov-Hausdorff distance, we obtain a similar hardness result for the latter. In both cases, we show essentially optimal additive inapproximability. On the algorithmic side, we give a subcubic-time algorithm for optimal embeddings of connected graphs into paths, based on a structural decomposition along a diametral path. Additionally, we give a simple approximation algorithm when one input graph has a "relatively path-like" metric structure, i.e. has bounded pathlength. For local and global distortion, we derive various hardness results even for restricted inputs. Making use of a close connection between the global distortion distances and Gromov-Wasserstein distances, we give the first formal proof of NP-hardness of the latter, which has been claimed in the literature many times but has, to the best of our knowledge, never been correctly proven.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-10-14: 1 request, 7,637 input tokens.

What the abstract itself states, as probabilities: claims first 0.78 · states limitation 0.26 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.96 · compares with prior results 0.72 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; .

We study the computational complexity of graph distortion distances, a family of graph metrics measuring how vertex distances differ between two graphs. Formally, these distances are defined in terms of standard matrix norms on the difference of distance matrices under an optimal vertex alignment. The resulting metrics have natural interpretations, corresponding to three ways of measuring the distortion of shortest-path distances: the maximum distortion among all vertex pairs (entrywise maximum norm), global aggregation (entrywise $p$-norms), and local aggregation (operator $p$-norms) of distortions. For maximum distortion, we show that approximation below a factor of two is NP-hard even for highly restricted trees. Due to the close connection to the Gromov-Hausdorff distance, we obtain a similar hardness result for the latter. In both cases, we show essentially optimal additive inapproximability. On the algorithmic side, we give a subcubic-time algorithm for optimal embeddings of connected graphs into paths, based on a structural decomposition along a diametral path. Additionally, we give a simple approximation algorithm when one input graph has a "relatively path-like" metric structure, i.e. has bounded pathlength. For local and global distortion, we derive various hardness results even for restricted inputs. Making use of a close connection between the global distortion distances and Gromov-Wasserstein distances, we give the first formal proof of NP-hardness of the latter, which has been claimed in the literature many times but has, to the best of our knowledge, never been correctly proven.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#sentencerolethe authors' own workstates the main conclusionstrength
s0 We study the computational complexity of graph distortion distances, a family of graph metrics measuring how vertex distances differ between two graphs. contribution 0.72 0.74 0.06 asserted 0.99
s1 Formally, these distances are defined in terms of standard matrix norms on the difference of distance matrices under an optimal vertex alignment. background 0.61 0.24 0.02 asserted 1.00
s2 The resulting metrics have natural interpretations, corresponding to three ways of measuring the distortion of shortest-path distances: the maximum distortion among all vertex pairs (entrywise maximum norm), global aggregation (entrywise $p$-norms), and local aggregation (operator $p$-norms) of distortions. interpretation 0.42 0.38 0.03 asserted 1.00
s3 For maximum distortion, we show that approximation below a factor of two is NP-hard even for highly restricted trees. result 0.99 0.96 0.27 asserted 1.00
s4 Due to the close connection to the Gromov-Hausdorff distance, we obtain a similar hardness result for the latter. result 0.89 0.89 0.12 asserted 0.99
s5 In both cases, we show essentially optimal additive inapproximability. result 0.99 0.94 0.13 asserted 1.00
s6 On the algorithmic side, we give a subcubic-time algorithm for optimal embeddings of connected graphs into paths, based on a structural decomposition along a diametral path. contribution 0.75 0.96 0.06 asserted 1.00
s7 Additionally, we give a simple approximation algorithm when one input graph has a "relatively path-like" metric structure, i.e. has bounded pathlength. contribution 0.85 0.96 0.03 asserted 1.00
s8 For local and global distortion, we derive various hardness results even for restricted inputs. result 0.93 0.94 0.08 asserted 1.00
s9 Making use of a close connection between the global distortion distances and Gromov-Wasserstein distances, we give the first formal proof of NP-hardness of the latter, which has been claimed in the literature many times but has, to the best of our knowledge, never been correctly proven. contribution 0.51 0.94 0.44 asserted 1.00

What kind of paper the classifier reports this is: theoretical result 0.99 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read
  • arXiv listing abstract v1
not examined
  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers
levels run
  • P abstract
not run
  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures
Figure 1. The trees of pathwidth two constructed in the reduction of Theorem 1. White boxes correspond to paths of ℓ vertices (P, R) and paths of 2ℓ vertices (Q). If I is a YES-instance, there is a bijection that preserves the coloured regions and maps each leaf set of G into a single leaf set of H. If I is a NO-instance, for every bijection, a leaf set corresponding to some ai in G is split up and, by choice of c := 3mℓ + 2, its vertices end up in at least two distinct leaf sets of H
Figure 2. Two alignments between the same two multisets. Each multiset is arranged horizontally with its bags (black dots and boxes) placed at consecutive integer positions, i.e. the top multiset has support [3n + 1], the bottom one [2n + 1]. Black dots denote a single point (bags of size one) while a box labelled k denotes a bag of k points, all at the same position. Both multisets have 7n − 1 elements. Alignments are visualised by grey edges; an edge connects two bags B, B′ if there is an x ∈ B with π(x) ∈ B ′ . Red edges indicate pairs of maximum distortion under the respective alignment.…
Figure 3. The trees of maximum degree three constructed in the reduction. White boxes correspond to paths of ℓ vertices (P, R) and paths of 2ℓ vertices (Q). The first and last m leaves of the upper binary tree are connected to the paths Q 1 , . . . , Qm and R 1 , . . . , Rm, respectively. The leaves in between (circled in red) are ‘kept dangling’. Note that the vertex counts do not match those of a valid construction for an instance I but are for illustration purposes only. (π(v), π(v ′ )) in H, it is clear that at most three such binary trees are (partially) traversed in any shortest path.…
Figure 4. The trees G and H for the proof of Theorem 7. White boxes correspond to paths. σ by the condition σ −1 (j) = {κ(j, 1), κ(j, 2), κ(j, 3)} for all j ∈ [m]. We will use κ to define a correspondence between G and H. For j ∈ [m] and k ∈ [3] let η(j, k, ·): [aκ(j,k) ] → [A] be the injection defined by η(j, k, h) = h+ Pk−1 c=1 aκ(j,c) and note that the images of η(j, 1, ·), η(j, 2, ·) and η(j, 3, ·) partition [A] according to the sizes aκ(j,1), aκ(j,2), aκ(j,3) into sets of consecutive integers. Consider the correspondence R ∈ Corr(V, W) defined by (1) (rG, rH) ∈ R, (2) p r κ(j,k) , q…
Figure 5. Visualisation of the relevant relations between a(x), a(q), a(q ′ ), a(x ′ ). Each integer point (i, j) corresponds to the set Bi,j , hence u is at coordinate (0, d) and v is at coordinate (d, 0) with the diametral path (visualised in black) being the diagonal of points (i, j) satisfying i + j = d. Each vertex of the graph G lies in the upper triangle of the plot. The blue diagonal lines correspond to the sets Ca
Figure 6. The six cases of where s may lie in our case distinction. We use the same conceptual drawing as in
Figure 7. Two alignments between the same two multisets given over {0, . . . , 8}. Each multiset is visualised horizontally, with the multiplicities of each integer denoted by black dots and boxes: Dots correspond to multiplicity of one, a box labelled k denotes a multiplicity of k. Both multisets have 38 elements. Alignments are visualised by grey edges; an edge connects two bags B, B′ if there is an x ∈ B with π(x) ∈ B ′ . Red edges indicate pairs of maximum distortion under the respective alignment. ▶ Example 36. Consider the multisets depicted in
Figure 8. The trees in the construction of the proof of Theorem 15
Figure 9. Transforming an example graph F as described in the construction for Theorem 16. Here n = 6 and ℓ := 20k 2 . Cliques are indicated by large circles and boxes. Edges between cliques indicate that all pairs of vertices are connected by edges

Figures reproduced from arXiv:2610.16926 by the authors.

References

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.