Pith. Sign in

REVIEW

Some Thoughts on Graph Similarity

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
Martin Grohe

Discrete Mathematics · Submitted 15 Nov 2024 · 57 references

Pith's verdict: Useful survey of graph similarity measures, but the proof of Theorem 3.4 contains a false inequality and needs repair before the paper can stand as a self-contained account.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 12, 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 →

· 3 major objections · 5 minor · Ask about this paper · The compiled record · Read the full review →
Challenge this review Comment (0) Read on arXiv ↗
Cite ▾
arXiv ID2411.10182 (version 2)
Pith IDA3VIYGMW, Pith's permanent record of this paper and its review
CitationMartin Grohe. "Some Thoughts on Graph Similarity." arXiv:2411.10182 (2024). https://pith.science/paper/A3VIYGMW
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 paper argues that operational graph similarity—how cheaply one graph can be edited into another—and declarative graph similarity—how closely graphs agree on counts of small patterns—are dual views that coincide after a blow-up…

The reading

The paper sets out to make “are these two graphs similar?” a mathematical question with a defensible answer. It organizes the many existing distance measures into two camps: operational distances, which count edits or small perturbations needed to turn one graph into the other, and declarative distances, which compare counts of small patterns or logical properties. Its central claim is that these two camps are dual views of the same geometry, not rival definitions. Concretely, it states that after a blow-up construction that equalizes graph sizes, the edit distance equals an optimal-transport distance (Theorem 3.10), and that the cut distance and the homomorphism-density metric define the same topology (Theorem 4.7). A sympathetic reader comes away with the guiding principle that, for dense graphs (many edges relative to vertices), “easy to transform into” and “shares many small features with” converge to the same notion of closeness.

What carries the argument

The load-bearing object is the blow-up operation $G^{\odot k}$, which replaces each vertex by $k$ indistinguishable twins and each edge by a complete bipartite graph; it makes graphs of different orders comparable and defines the limiting distances $\delta^{\odot}_{(1)}$, $\delta^{\odot}_\square$. The proof engine is a set of scaling identities for matrix norms—$||B^{\odot ℓ}||_{(1)} = ℓ^2 ||B||_{(1)}$, $||B^{\odot ℓ}||_\square = ℓ^2 ||B||_\square$, $||B^{\odot ℓ}||_1 = ℓ ||B||_1$—together with Lemma 3.5, which turns these identities into the inequalities needed to show the blow-up limits exist. On the declarative side, the companion objects are homomorphism densities $hd(F,G)$, the probability that a random map from $F$ to $G$ preserves edges, and the Weisfeiler-Leman colouring, whose vectors define a graph kernel and a metric $\delta_{WL}$. The bridge between the two sides is built from doubly stochastic matrices: optimal-transport couplings $Q$ with rational entries (Lemma 3.11) realize blow-up alignments, and a decomposition of integer doubly stochastic matrices into permutations (Lemma 3.13) yields the approximation of edit distance by optimal transport. The paper's strongest unifying statements, Theorem 4.7, are taken from earlier work and used to conclude that the operational and declarative metrics induce identical topologies.

Extended reading notes

Core claim

The paper's central mathematical content is a chain of identifications between operational and declarative graph metrics. On the operational side, graph edit distance $\delta_{(1)}$, local edit distance $\delta_1$, and cut distance $\delta_\square$ are defined on equal-size graphs, then extended to arbitrary sizes by the blow-up operation $G^{\odot k}$, which replaces each vertex by $k$ twins and each edge by a complete bipartite graph. On the declarative side, homomorphism densities $hd(F,G)$ are collected into the metric $\delta_G$. The paper proves that blow-up edit distance equals the optimal-transport distance $\delta^{OT}_{(1)}(G,H) = \min_Q \sum |A_G(u,v)-A_H(w,w')|\,Q(u,w)Q(v,w')$, and states the analogous equality $\delta^{\odot}_\square = \delta^{OT}_\square$. It then presents the topological equivalences (Theorem 4.7): $\delta^{\odot}_\square$ and $\delta_G$ define the same topology, as do the fractional cut distance $\delta^*_\square$ and the tree-homomorphism metric $\delta_T$; Theorem 4.11 adds that $\delta_G$ and the sampling distance $\delta_{samp}$ define the same topology. These results say that comparing graphs by editing cost, by transport plans, by subgraph sampling, and by homomorphism counts all pick out the same notion of closeness in the dense regime. The paper also records complexity facts: edit distance is NP-hard even for trees, exact homomorphism indistinguishability ranges from polynomial to undecidable, and the convex relaxations are efficiently computable.

Load-bearing premise

The central unifying theorems about topologies are not proved in this paper but imported from earlier work, so the whole duality picture rests on those external proofs being correct; additionally, the normalization by $n^2$ presumes dense graphs with quadratically many edges, so the equivalences are only meaningful in that regime.

Editorial extensions

If this is right

  • For dense graphs, algorithms and intuitions can move freely between editing cost, transport plans, and pattern counts: if two graphs are close in one sense, they are close in the others.
  • The equality $\delta^{\odot}_{(1)} = \delta^{OT}_{(1)}$ gives the hard combinatorial edit distance a continuous transport formulation, so optimal-transport machinery becomes a candidate tool for approximating graph edit distance.
  • Because $\delta_{samp}$ and $\delta_G$ define the same topology, comparing graphs by sampling small induced subgraphs is not a heuristic shortcut but an equivalent way of measuring closeness, with quantitative bounds by $k$.
  • The zero-distance classes are pinned down: for all graphs, isomorphism; for trees, fractional isomorphism and Weisfeiler-Leman equivalence.
  • Complexity is sharply split: operational distances are mostly NP-hard to compute, while the convex relaxations are efficiently computable and several declarative distances can be sampled or computed in polynomial time.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Implied but not pursued in the paper: the same transport/coupling format used for edit and cut distance could be applied to the distortion distance, yielding an optimal-transport variant that inherits blow-up limit behavior and connects directly to metric-space matching.
  • A reader can infer that because $\delta_G$ and $\delta_{samp}$ are topologically equivalent, a learned graph representation built from Weisfeiler-Leman features should asymptotically see the same closeness relation as one built from homomorphism densities; this is a testable design consequence, not shown in the paper.
  • The dense-regime normalization is a stated limitation. A natural extension, left implicit, is that transferring the equivalences to sparse graphs would require a different normalization, and the paper's clean duality would likely break.
  • The author conjectures that optimal-transport and blow-up distances are hard to compute. If that is correct, the efficiently computable convex relaxations are not merely relaxations but the only practical algorithmic route, making the quantitative gap between $\delta^*$ and $\delta^{\odot}$ a pressing quantity to estimate.
Original abstract

We give an overview of different approaches to measuring the similarity of, or the distance between, two graphs, highlighting connections between these approaches. We also discuss the complexity of computing the distances.

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-09-23: 1 request, 2,188 input tokens.

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

The abstract, sentence by sentence

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

We give an overview of different approaches to measuring the similarity of, or the distance between, two graphs, highlighting connections between these approaches. We also discuss the complexity of computing the distances.

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 give an overview of different approaches to measuring the similarity of, or the distance between, two graphs, highlighting connections between these approaches. contribution 0.97 0.46 0.14 asserted 0.93
s1 We also discuss the complexity of computing the distances. contribution 0.97 0.24 0.05 asserted 0.71

What kind of paper the classifier reports this is: review 1.00 · evidence from literature 0.95.

What was examined, and what was not

sources read
  • arXiv listing abstract v2
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. 1: Which of these three molecular graphs are most similar? algorithms for hard algorithmic problems. We may use symmetries to prune search trees in backtracking algorithms (e.g. in SAT solving [47]) or to reduce the size of instances of hard algorithmic problems (e.g. in optimisation [6, 30] or model checking [16]). It is not clear what makes two graphs similar. Consider the three molecular graphs in
Figure 3. 1: A graph G and its blow-up G⊙6 When thinking of graph edit distance, the most obvious way to compare graphs of distinct orders would be to add another edit operation: delete or add an isolated vertex. Let us call the version of edit distance where we allow this operation by δ ⊕ ed. We define the following padding operation on graphs. For a graph G and a nonnegative integer k ∈ N, by G⊕k we denote the graph obtained from G by adding k isolated vertices.3 Then it is easy to see that for all graphs G, H we have δ ⊕ ed(G, H) = ( k + δed(G⊕k , H) if |H| − |G| = k ≥ 0, k + δed(G, H⊕k )…
Figure 4. 1: Weisfeiler-Leman colours viewed as trees. function K : X × X → R is a kernel function if and only if there is a vector embedding η : X → I of X into some inner product space I, which we can even take to be a Hilbert space, such that K is the mapping induced by h·, ·iI , that is, K(x, y) = hη(x), η(y)i I for all x, y ∈ X (see [50, Lemma 16.2] for a proof). For background on kernels and specifically graph kernels, see [37, 48]. To give a meaningful and practically relevant example of a graph kernel, that is, a kernel function on the class of graphs, this is a good place to introduce…

Showing 3 of the paper's 4 figures. See all figures in the PDF ↗ Figures reproduced from arXiv:2411.10182 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.