REVIEW 3 major objections 4 minor 14 references
On cospectral graphons
T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read This paper defines cospectral graphons and proves that three natural definitions—equal cycle densities, equal spectra, and a unitary intertwining operator—are equivalent.
desk verdict The paper's main equivalence theorem is false: cycle densities can't see the zero eigenspace, so cospectral graphons need not be unitarily equivalent. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the graphon viewed as an integral operator $T_W$ on $L^2([0,1])$, a symmetric Hilbert-Schmidt operator with discrete real spectrum whose eigenvalues are square-summable. Two facts carry the argument: Parseval's identity $\|W\|_2^2 = \sum_{\lambda \in \operatorname{Spec}(W)} \lambda^2$ and the formula $t(C_k,W)=\sum_{\lambda \in \operatorname{Spec}(W)} \lambda^k$ for $k\ge 3$. The proof of Theorem 3.2 decomposes the eigenvalue sum into a top part at the farthest eigenvalue modulus $\nu$ with a multiplicity mismatch, a middle part with $h$ terms bounded by $\alpha^k$ for $\alpha<\nu$, and a tail whose $\ell^2$-sum is small, then uses the parity of the multiplicity imbalance to show the $\nu^k$ term does not cancel for one parity.
What would settle it
Find a specific pair of bounded symmetric functions $U,W$ on $[0,1]^2$ with $t(C_k,U)=t(C_k,W)$ for all $k\ge 3$ (or for infinitely many odd and infinitely many even $k$) but with different operator spectra, or exhibit any pair that violates one of the three equivalent criteria; such an example would disprove Theorem 3.2.
Extended reading notes
Core claim
The central claim, Theorem 3.2, is that for any two graphons $U$ and $W$ the following are equivalent: (i) $t(C_k,U)=t(C_k,W)$ for every $k\ge 3$; (ii) the same equality holds for infinitely many odd and infinitely many even $k$; (iii) $\operatorname{Spec}(U)=\operatorname{Spec}(W)$, meaning the eigenvalues with multiplicities coincide; and (iv) there exists a unitary operator $T:L^2([0,1])\to L^2([0,1])$ with $T\circ T_W=T_U\circ T$. The proof of (ii)$\Rightarrow$(iii) chooses $\nu$, the largest eigenvalue modulus at which multiplicities differ, splits each eigenvalue sum at $\nu$ and at a small cutoff $\beta$, and uses square-summability of the spectrum to control the tail by $(h+2)\alpha^k$ with $\alpha<\nu$; the coefficient of $\nu^k$ then has a nonzero value for one of the two parities, forcing infinitely many differences. The equivalence is a direct translation of the finite-graph fact that cycle homomorphism counts are traces of powers of the adjacency matrix.
Load-bearing premise
The equivalence relies on graphon operators being compact, self-adjoint Hilbert-Schmidt operators with square-summable eigenvalues; if a graphon-like kernel lacked this spectral structure, equal cycle densities would no longer pin down the spectrum.
Editorial extensions
If this is right
- Cospectrality of graphon limits is robust: any two graphons with the same cycle densities are automatically intertwined by a unitary operator, so spectral equality in the limit is a purely measure-theoretic statement.
- The threshold is low: matching cycle densities on infinitely many odd and infinitely many even lengths already forces cospectrality, so verifying the full family is unnecessary.
- The example in Theorem 4.2, $U\equiv \frac12$ and $W$ the indicator of $[0,\frac12]^2$, shows cospectral graphon limits can arise from sequences of graphs that are never cospectral, and the same holds for any two graphons with different $L^1$-norms.
- The open Problem 4.4 asks whether equal-$L^1$ cospectral graphons can fail to be cospectrally approximable; if the answer is no, the obstruction in Theorem 4.2 is essentially the only one.
Reading between the lines
- A likely next step is a graphon analogue of quantum isomorphism, since the same framework—families of test graphs, a unitary or projection operator, and an approximation theorem—applies; the paper notes no such extension exists.
- The non-approximability result suggests that spectral fingerprints of large networks are not continuous under the cut distance even when limits are cospectral, which would caution against inferring cospectrality of large graphs from convergence to the same limit.
- One could test the open problem computationally by randomizing the half-square graphon while preserving its $L^1$-norm and checking numerically whether cycle densities remain equal; such experiments could guide a construction.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper defines two graphons U and W to be cospectral when t(C_k, U) = t(C_k, W) for all k ≥ 3. Theorem 3.2 claims this is equivalent to equality of the full spectra of the associated Hilbert-Schmidt operators and to the existence of a unitary operator T on L^2([0,1]) with T ∘ T_W = T_U ∘ T. The paper also proves (Theorem 4.2) that the graphon analogue of a previous approximability result for fractional isomorphism fails: the constant graphon 1/2 and the block graphon on [0,1/2]^2 are cospectral but cannot be limits of sequences of cospectral graphs. The proof uses an L1-norm obstruction.
Significance. Were Theorem 3.2 correct, it would provide a clean graphon counterpart to cospectrality of finite graphs, with cycle densities playing the role of the usual homomorphism counts. The proof strategy for the nonzero part of the spectrum is sensible, and the inapproximability result is elegant and appears correct. However, the main equivalence is false because cycle densities are blind to the zero eigenvalue, and the counterexample is simple and within the paper's own setup. The paper therefore needs substantial revision rather than minor polishing.
major comments (3)
- [Section 3, Theorem 3.2] The equivalence (i)⇔(iii) and (i)⇔(iv) is false. Since t(C_k, W) = Σ_{λ∈Spec(W)} λ^k for k ≥ 3, these values depend only on the nonzero eigenvalues of T_W; the zero eigenvalue, with any multiplicity, contributes nothing. The proof of (ii)⇒(iii) selects a largest positive ν at which the spectra differ, but such a ν need not exist when the only spectral difference is in the zero eigenspace. Concretely, take λ_1 = 1/4 and λ_n = 2^{-n-3} for n ≥ 2, let (φ_n) be an orthonormal basis of L^2([0,1]) with φ_1 = 1 and |φ_n| ≤ √2, and set U(x,y) = λ_1 + Σ_{n≥2} λ_n φ_n(x)φ_n(y). Let W be the indicator of ∪_n (I_n × I_n), where the I_n are disjoint intervals with |I_n| = λ_n. Both are graphons with the same nonzero spectrum {λ_n : n ≥ 1}, so t(C_k, U) = t(C_k, W) for all k ≥ 3. But ker T_U = {0} while ker T_W is infinite-dimensional. No unitary T can satisfy T ∘ T_W = T_U ∘ T, because a nonzero f ∈ ker T_W would be mapped to an element of ker T_U = {0}, contradicting injectivity of T. Thus (i) does not imply (iv), and (i) does not imply (iii) when spectra are counted with multiplicities.
- [Section 3, proof of (iii)⇒(iv)] The construction of T relies on the spectra agreeing on all eigenspaces, including the zero eigenspace, because the direct sum decompositions include K_0 and L_0 and the isometries b_λ are chosen for every λ ∈ Spec(U) = Spec(W). If Spec is interpreted as the multiset of nonzero eigenvalues (a convention some graphon papers adopt), then (iii)⇒(iv) is false by the same counterexample above. If Spec includes zero with multiplicity, then (i)⇒(iii) is false. Thus under no interpretation of Spec are all four statements in Theorem 3.2 equivalent; the theorem needs to be restated, for example by separating the zero eigenspace and requiring a unitary or isometry between the orthogonal complements of the kernels.
- [Section 4, Proposition 4.3] The final inference "By Parseval's Theorem (2.2) we conclude that U' and W' are not cospectral" is not a direct consequence of Parseval alone. Parseval relates the L2 norm to the sum of squares of all eigenvalues, but cospectrality as defined in Definition 3.1 concerns cycle densities, which are sums of k-th powers for k ≥ 3. The needed implication is that different sums of squares of nonzero eigenvalues force different cycle densities for some k; this is true and can be proved by the argument in (ii)⇒(iii) restricted to the nonzero spectrum, but it should be stated explicitly rather than left as an immediate corollary of Parseval.
minor comments (4)
- [Section 3, proof of (ii)⇒(iii)] The existence of the largest ν with different multiplicities is not explicitly justified. It follows because the nonzero eigenvalues of a compact self-adjoint operator have no accumulation point away from 0, but the proof should say this.
- [Section 3, equation (3.1)] If α = 0, i.e., ν is the smallest positive eigenvalue modulus, then the strict inequalities in (3.1) cannot hold. The argument should treat this case separately, observing that the relevant sums in (T3) are empty for β < ν.
- [References] References [9] and [10] are the same book (Lovász, Large networks and graph limits); one should be removed.
- [Section 4, Theorem 4.1] In the quoted statement of Theorem 4.1, "Hn is Gn are fractionally isomorphic" should read "H_n and G_n are fractionally isomorphic."
Circularity Check
No circularity: the equivalence proof is built on external spectral facts, not on its own conclusion.
full rationale
The paper's derivation chain is self-contained and non-circular. Definition 3.1 stipulates cospectrality via equality of cycle densities, and Theorem 3.2 then proves equivalence to spectrum equality and to existence of a unitary intertwiner. The proof uses standard, externally cited results: compact self-adjoint operator spectral theory, Parseval's identity (2.2), and the trace formula t(C_k,W)=sum lambda^k (2.3). The implication (ii) implies (iii) is a genuine spectral-separation argument; it does not assume the target equivalence, and no fitted parameter is later renamed as a prediction. The one self-citation, [6] by Hladky and Hng, appears only as motivational contrast in Theorem 4.1 and is not used as evidence for the paper's own claims, so it is not load-bearing. Section 4's inapproximability proof relies on elementary L1/L2 comparisons, cut-distance bounds, and Parseval, again without assuming the conclusion. A possible mathematical weakness is that cycle densities are blind to the zero eigenspace, so the proof of (iii) implies (iv) may not cover kernels of different dimensions; however, that would be a correctness issue, not circularity, because the argument is not equivalent to its input by construction.
Assumptions & free parameters
assumptions (3)
- standard math Graphon operators are compact, self-adjoint Hilbert-Schmidt operators on L2([0,1]), so they have real discrete spectra and eigenvalues are square-summable.
- standard math Spectral theorem for compact self-adjoint operators: the space L2([0,1]) decomposes into orthogonal eigenspaces and the operator is a sum of λ times projections.
- standard math Parseval's identity for graphons: ‖W‖₂² = Σ_{λ∈Spec(W)} λ².
Cite this review
Pith. "Pith review of On cospectral graphons." pith.science (2026). https://pith.science/paper/23WKGSLY
@misc{pith2026241113229,
author = {Pith},
title = {Pith review of: On cospectral graphons},
year = {2026},
howpublished = {\url{https://pith.science/paper/23WKGSLY}},
note = {Machine review of arXiv:2411.13229}
}
read the original abstract
In this short note, we introduce cospectral graphons, paralleling the notion of cospectral graphs. As in the graph case, we give three equivalent definitions: by equality of spectra, by equality of cycle densities, and by a unitary transformation. We also give an example of two cospectral graphons that cannot be approximated by two sequences of cospectral graphs in the cut distance.
Reference graph
Works this paper leans on
-
[1]
A. Atserias, L. Mančinska, D. E. Roberson, R. Šámal, S. Se verini, and A. Varvitsiotis, Quantum and non- signalling graph isomorphisms , Journal of Combinatorial Theory, Series B 136 (2019), 289–328
work page 2019
- [2]
- [3]
-
[4]
Dvořák, On recognizing graphs by numbers of homomorphisms , J
Z. Dvořák, On recognizing graphs by numbers of homomorphisms , J. Graph Theory 64 (2010), 330–342
work page 2010
-
[5]
J. Grebík and I. Rocha, Fractional isomorphism of graphons , Combinatorica 42 (2022), 365–404
work page 2022
-
[6]
J. Hladký and E. K. Hng, Approximating fractionally isomorphic graphons , European J. Combin. 113 (2023), Paper No. 103751, 19
work page 2023
-
[7]
J. Hladký and I. Rocha, Independent sets, cliques, and colorings in graphons , European J. Combin. 88 (2020), 103108, 18
work page 2020
-
[8]
Lovász, Operations with structures , Acta Math
L. Lovász, Operations with structures , Acta Math. Acad. Sci. Hungar. 18 (1967), 321–328
work page 1967
Show all 14 references
-
[9]
60, American Mathematical Society, Providence, RI, 2012
, Large networks and graph limits , American Mathematical Society Colloquium Publications, vol. 60, American Mathematical Society, Providence, RI, 2012
2012
-
[10]
Lovász, Large networks and graph limits , American Mathematical Society colloquium publications, Amer- ican Mathematical Society, 2012
L. Lovász, Large networks and graph limits , American Mathematical Society colloquium publications, Amer- ican Mathematical Society, 2012
2012
-
[11]
Lovász and B
L. Lovász and B. Szegedy, Limits of dense graph sequences , Journal of Combinatorial Theory, Series B 96 (2006), 933–957
2006
-
[12]
Mančinska and D
L. Mančinska and D. E. Roberson, Quantum isomorphism is equivalent to equality of homomorph ism counts from planar graphs , 2019
2019
-
[13]
M. V. Ramana, E. R. Scheinerman, and D. Ullman, Fractional isomorphism of graphs , Discrete Math. 132 (1994), 247–265
1994
-
[14]
Tinhofer, Graph isomorphism and theorems of Birkhoff type , Computing 36 (1986), 285–300
G. Tinhofer, Graph isomorphism and theorems of Birkhoff type , Computing 36 (1986), 285–300
1986
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.