REVIEW 2 major objections 5 minor 18 references
The Generalized Skew Spectrum of Graphs
T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read This paper generalizes the Skew Spectrum graph embedding to multi-orbit, higher-correlation spectra that are isomorphism-invariant, compute at the original cost, and achieve zero collisions on all 7-node graphs.
desk verdict Solid extension of the Skew Spectrum with a clean invariance proof; the same-cost expressivity claim rests on a reduction proved only for scalar binary f. 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 load-bearing object is the Multi-Orbit $k$-Spectrum: for $f:S_n/S_{n-2}\to\mathbb{C}^d$, its entries are Fourier transforms of $k$-correlations $S_f^{(k)}(G_{k-1})=\frac{1}{|S_n|}\sum_{\tilde{g}\in S_n} f(\tilde{g})\bigotimes_{l=1}^{k-1} f(\tilde{g} g_l)$, and translation invariance of these correlations is what Theorem 4.3 uses to prove isomorphism invariance. Efficiency comes from Fourier sparsity on $S_n/S_{n-2}$: only four irreps of $S_n$, indexed by the partitions $(n)$, $(n-1,1)$, $(n-2,2)$, $(n-2,1,1)$, survive, each with sparse columns, and the $k$-Spectrum is determined by $G_{k-2}$ living in coset spaces rather than the full group. The double-reduction heuristic restricts $G_{k-2}$ to combinations without repetition or order of the 7 double-coset representatives, cutting the entry count from $O(n^{2(k-2)})$ to $\binom{7}{k-2}$ and capping $k$ at 9, while Algorithm 2's dynamic programming precomputes the needed partial sums in $O(d^{k-2}n^3+d^{k-1}n^2)$ steps.
What would settle it
Take the 15A/15B and 6A/6B synthetic families, add a third feature orbit or re-weight the labels, and compute both the doubly-reduced and the full multi-orbit $k$-Spectra for $k=3,\dots,9$; any pair of non-isomorphic graphs that the full spectra separate but the doubly-reduced spectra do not would falsify the claim that the double-reduction heuristic preserves expressivity for multi-orbit inputs. A second check is to repeat the 7-node Atlas collision count on attributed versions of the graphs, comparing concatenated doubly-reduced spectra against the unreduced spectra.
Extended reading notes
Core claim
On the paper's own terms, the central claim is a two-parameter family of graph invariants. A graph is encoded as a function $f: S_n/S_{n-2}\to\mathbb{C}^d$ whose $d$ components are separate data orbits, and the $k$-Spectrum is the Fourier transform over $S_n$ of the $k$-fold correlation of $f$; because the orbit indices mix inside the tensor product, terms of the form $\hat{r}^{(i_1,i_2)}(g_1,\rho)^\dagger \hat{f}_{i_3}(\rho)$ appear, and these interference terms are what let multi-orbit spectra separate graphs whose single-orbit spectra coincide. Theorem 4.3 proves the invariants are unchanged by graph isomorphism: a left translation of $f$ averages out in the correlation sum. Theorem 6.2 then shows the doubly-reduced $k$-Spectrum, evaluated only on the 7 double-coset representatives $S_{n-2}\backslash S_n/S_{n-2}$ and the 4 relevant irreps, costs $O(d^{k-1}n^3 + d^k n^2)$ and has at most $\binom{7}{k-2}\cdot 7\cdot d^k$ non-zero entries, recovering the original reduced Skew Spectrum at $d=1,k=3$. Experimentally, the concatenated spectra erase all collisions in the 7-node graph Atlas where Laplacian eigenvalues and 1-WL tests leave many, while on 8-node chordal graphs 1-WL has fewer collisions.
Load-bearing premise
The load-bearing premise, introduced in Section 4 under Double reduction and used by Algorithm 1, is that omitting repeated and reordered group elements from the spectrum costs no distinguishing power even when the graph function is vector-valued and carries several weighted feature orbits; the paper's own theorems justify this omission only for scalar functions whose values are 0 or 1.
Editorial extensions
If this is right
- For the Atlas of all 7-node graphs, the concatenated doubly-reduced $k$-Spectra for $k\in[3,9]$ have zero collisions, beating both Laplacian eigenvalues and 1-WL tests on that benchmark.
- Multi-orbit spectra resolve graphs that concatenated single-orbit spectra cannot: on the 15A/15B/6A/6B families, Random Forest accuracy jumps from 50% to 100% when the 2-Orbit spectrum is used.
- The doubly-reduced $k$-Spectrum costs $O(d^{k-1}n^3+d^k n^2)$ and has at most $\binom{7}{k-2}\cdot 7\cdot d^k$ non-zero entries, recovering the original reduced Skew Spectrum's cost when $d=1$ and $k=3$.
- Raising $k$ increases what the invariant counts—edges, shared-vertex edge pairs, triangles, and larger substructures—so the family provides a tunable expressivity-versus-cost dial, capped at $k=9$ by the double reduction.
- On 8-node chordal graphs, 1-WL has fewer collisions than the concatenated spectra, indicating $k$-spectra and WL tests measure complementary rather than ordered notions of structure.
Reading between the lines
- If the paper's conjecture of a finite $k_{\max}\in O(n^2)$ is correct, the full $k$-correlation hierarchy would be a complete invariant on $S_n/S_{n-2}$, giving a parameter-free graph isomorphism test whose cost is polynomial in $n$ for each fixed $k$; the doubly-reduced spectrum would then be the practical low-cost slice of that hierarchy.
- The cross-orbit interference mechanism is more general than the paper's examples: any representation that packs several graph attributes into a tensored invariant gains discrimination from mixed indices, so the same construction should transfer to hypergraphs with $q$-ary adjacency tensors, a direction the paper notes but does not implement.
- Because Theorems 4.5 and 4.6 justify the double reduction only for scalar binary functions, the zero-collision Atlas result may not survive on weighted or attributed graphs; a stress test comparing doubly-reduced against full spectra would settle whether the heuristic discards cross-orbit information.
- Using the doubly-reduced spectrum as a pooling or positional-encoding layer inside a GNN, as the paper suggests, would add spectral expressivity at the same message-passing complexity; the PROTEINS experiments already hint that concatenating spectral features helps.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper generalizes the Skew Spectrum of graphs (Kondor & Borgwardt, 2008) in three directions: (i) a Multi-Orbit Skew Spectrum that takes vector-valued functions on S_n/S_{n-2} to handle attributed, multilayer, and hypergraphs; (ii) a family of k-correlation spectra (k-Spectra) enabling a complexity/expressivity trade-off; and (iii) a 'doubly-reduced' k-Spectrum heuristic that restricts to unordered, repetition-free combinations of the 7 double-coset representatives to compute the invariant in O(d^{k-1}n^3 + d^k n^2) operations. The paper proves the translation invariance of the k-Spectra (Theorem 4.3), establishes the reduction to the four irreps and to S_n/S_{n-2} (Theorem 4.4), and gives complexity and non-zero-entry counts (Theorem 6.2). Experiments on synthetic labeled graphs, QM7, QM9, ZINC, the Atlas of 7-node graphs, chordal graphs, and PROTEINS are reported to support the claimed expressivity and GNN integration benefits.
Significance. The proposed framework is a principled group-theoretic extension of a classic invariant. The invariance proof (Theorem 4.3) is clean, and the complexity analysis (Section 6) is detailed and appears correct. The multi-orbit construction is a natural way to capture cross-feature correlations that concatenated single-orbit invariants miss, and Algorithm 2's dynamic-programming precomputation is a nontrivial algorithmic contribution. The paper ships a proof-of-concept implementation, and the deterministic collision experiments on the Atlas of 7-node graphs provide a clear empirical illustration. The central caveat is that the doubly-reduced heuristic, which is the method used in the experiments and recommended for practice, is justified only for scalar binary functions, while it is applied to vector-valued multi-orbit inputs. If that gap can be closed or the claims suitably qualified, the paper would be a solid contribution to the theory and practice of permutation-invariant graph embeddings.
major comments (2)
- [Section 4, 'Double reduction' and Algorithm 1] The no-repetition reduction (Theorem 4.5) is proved only for f : S_n → {0,1}, using idempotence f(g)^2 = f(g). Algorithm 1, however, applies the same reduction to f : S_n/S_{n-2} → C^d with d ≥ 1, as required for the attributed/multilayer/hypergraph settings advertised in the abstract. For d > 1 or non-binary weights, repeated elements are not generally redundant: for example, a term f_i(\tilde g g)^2 carries different information from f_i(\tilde g g), and cross-orbit products f_i(\tilde g g) f_j(\tilde g g) depend on the repetition. Consequently, the claim that the doubly-reduced k-Spectrum 'improves the Skew Spectrum's expressivity at the same computational cost' is not established for multi-orbit inputs. The experiments of §7.2 use unweighted, single-orbit graphs, so they do not exercise the gap. Please either extend Theorem 4.5 (and its proof) to the vector-valued setting, or explicitly restrict the claim and add experiments on attributed or weighted graphs.
- [Section 4, Theorems 4.5 and 4.6] Theorems 4.5 and 4.6 are the sole justification for the double reduction, but both proofs are sketched. Theorem 4.5's proof says 'one can verify S^{(k)}_f(G_{k-1}) = S^{(k-1)}_f(G_{k-2})' without showing the calculation. Theorem 4.6 is stated for scalar f and its proof asserts that 'the terms f(gg_l) commute,' which is immediate for scalars but is not argued for the direct-sum structure in Definition 4.2. Even if the statements are true for scalar f, the missing calculations and the lack of a vector-valued argument mean that the reader cannot verify the most load-bearing step of the paper. Please move the detailed derivations into the main text or an appendix, and state precisely which parts of the double reduction extend to the multi-orbit setting.
minor comments (5)
- [Figure 1] The figure caption contains an orphan passage 'The Multi-Orbits Skew Spectrum: Boosting Permutation-Invariant Data Representations Learning on Graphs Conference 2022' followed by 'An unsupervised permutation-invariant embedding' and related text; this appears to belong to a different figure and should be removed or properly cited.
- [Section 7, Tables 1 and 3] Regression results on QM7, QM9, and ZINC are reported as point estimates without error bars or significance tests; given the small differences between some representations, please add standard deviations over multiple splits or seeds and clarify whether the same train/test split is used for all methods.
- [Section 6.1] The non-zero entry count (7 = 1·3 + 4) is not obviously consistent with Lemma 2.1, which reports two non-zero columns for (n−1,1) and one for (n−2,2); please clarify the counting or correct the lemma.
- [Appendix A and Introduction] There are several typographical errors: 'wether' should be 'whether' (Introduction), 'Ferres diagrams' should be 'Ferrers diagrams' (Appendix A), and 'permuation' should be 'permutation' (Appendix A).
- [Section 4.1] The informal motivation that repeated elements do not increase expressivity 'when representing unweighted graphs' is imprecise: Theorem 4.5 requires binary f, which is a stronger condition than unweightedness (it also excludes weighted unweighted? actually unweighted graphs have 0/1 adjacency, so the statement is true but should be made conditional on the theorem). Please align the informal text with the formal statement of Theorem 4.5.
Circularity Check
No circularity: the derivation relies on standard harmonic analysis and external benchmarks; the multi-orbit double-reduction gap is a correctness issue, not a circular step.
full rationale
The derivation chain is self-contained rather than circular. Theorem 4.3 proves invariance by the change of variables g' = sigma-g in the k-correlation sum, with no fitted parameters and no assumption equivalent to the conclusion. Lemma 2.1's sparsity pattern is proved in Appendix B from the Young-orthogonal decomposition of the projection tau_{S_{n-2}}(rho), and the cited background material (Kondor 2007; Bellante 2024) is standard representation theory, not load-bearing for the paper's invariants. Theorems 4.5 and 4.6 justify the double reduction only for scalar and binary functions, and the paper labels the reduction a heuristic; Algorithm 1's application of that heuristic to vector-valued and weighted inputs is a possible expressivity gap for d>1, but a gap is not circularity because no equation is assumed equal to its conclusion and no fitted value is renamed a prediction. The computational claims (Theorem 6.2) and the zero-collision results on the 7-node Atlas are measured against external data and algorithm counts, not extracted from the definitions. The only self-citation is Bellante 2024 for representation-theory background, which does not carry the central claim. The uncited caption fragment in Figure 1 is a provenance issue, not a circular reduction. Accordingly, no significant circularity is present.
Assumptions & free parameters
assumptions (4)
- standard math Fourier sparsity of functions on Sn/Sn-2: under the Young orthogonal representation, the Fourier transform is supported on partitions (n), (n-1,1), (n-2,2), (n-2,1,1) with the stated zero-column counts.
- domain assumption A graph with multiple data channels (adjacency, labels, layers, features) can be encoded as a right-invariant vector-valued function f: Sn/Sn-2 -> C^d, so isomorphism is exactly left translation.
- standard math The seven listed elements form a complete double-coset transversal of Sn-2\Sn/Sn-2.
- ad hoc to paper The doubly-reduced k-Spectrum, restricted to combinations of the 7 double-coset representatives without repetitions or order, preserves enough expressivity to beat the reduced Skew Spectrum at the same asymptotic cost.
Cite this review
Pith. "Pith review of The Generalized Skew Spectrum of Graphs." pith.science (2026). https://pith.science/paper/FDWCNRIV
@misc{pith2026250523609,
author = {Pith},
title = {Pith review of: The Generalized Skew Spectrum of Graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/FDWCNRIV}},
note = {Machine review of arXiv:2505.23609}
}
read the original abstract
This paper proposes a family of permutation-invariant graph embeddings, generalizing the Skew Spectrum of graphs of Kondor & Borgwardt (2008). Grounded in group theory and harmonic analysis, our method introduces a new class of graph invariants that are isomorphism-invariant and capable of embedding richer graph structures - including attributed graphs, multilayer graphs, and hypergraphs - which the Skew Spectrum could not handle. Our generalization further defines a family of functions that enables a trade-off between computational complexity and expressivity. By applying generalization-preserving heuristics to this family, we improve the Skew Spectrum's expressivity at the same computational cost. We formally prove the invariance of our generalization, demonstrate its improved expressiveness through experiments, and discuss its efficient computation.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
ρ(e) = I, where e is the identity permutation and I the identity matrix
-
[2]
ρ(σ1σ2) = ρ(σ1)ρ(σ2) for all σ1, σ2 ∈ Sn
-
[3]
ρ(σ−1) = ρ(σ)†. Since the direct sum of two representations is also a representation, we say that a representation is irreducible (irrep) if it cannot be decomposed into a direct sum of smaller representations. That is, if ρ(σ) = ρ1(σ) ⊕ ρ2(σ) for all σ ∈ Sn, then either dim(ρ1) = 0 or dim(ρ2) = 0. Irreducible representations of Sn are classified by parti...
work page 2008
-
[4]
Pi(g4, σ, j) = fi(σ · (n, j))
-
[5]
Pi(g1, σ, j) = fi(σ)
-
[6]
Pi(g2, σ, j) = fi(σ · (n − 1, n))
-
[7]
Pi(g3, σ, j) = fi(σ · (n − 1, j))
-
[9]
Pi(g5, σ, j) = fi(σ · (j, n− 1, n))
Show all 18 references
-
[10]
Pi(g6, σ, j) = fi(σ · (j, n, n− 1))
-
[11]
Here, σ · g represents the group operation combining two elements, while σ(j) denotes the image of j under σ
Pi(g7, σ, j) = Fi(σ(j)) − P l∈{3,6} Pi(gl, σ, j) n − 3 with Fi(j) = P l∈[n] l̸=j fi((n − 1, j, n, l)). Here, σ · g represents the group operation combining two elements, while σ(j) denotes the image of j under σ. By utilizing dynamic programming, we can compute these P −functi...
-
[12]
(33) Hence, 1 |Sn−2| X h∈Sn−2 f ′ i (σhg(n − 1), σhg(n)) = f ′ i (σ(n − 1), σ(n)) = fi(σ) (34) So the term breaks in 1 n−2 Pn−2 j=1 Pi(g1, σ, j)
g1 = () σhg(n) = σh(n) = σ(n) (32) σhg(n − 1) = σh(n − 1) = σ(n − 1). (33) Hence, 1 |Sn−2| X h∈Sn−2 f ′ i (σhg(n − 1), σhg(n)) = f ′ i (σ(n − 1), σ(n)) = fi(σ) (34) So the term breaks in 1 n−2 Pn−2 j=1 Pi(g1, σ, j). The choice of how j divides Sn−2 is arbitrary here, so we can...
-
[13]
(37) So the term breaks in 1 n−2 Pn−2 j=1 Pi(g2, σ, j)
g2 = (n − 1, n) σhg(n) = σh(n − 1) = σ(n − 1) (35) σhg(n − 1) = σh(n) = σ(n) (36) Therefore, 1 |Sn−2| X h∈Sn−2 f ′ i (σhg(n − 1), σhg(n)) = f ′(σ(n), σ(n − 1)) = f (σ · (n − 1, n)). (37) So the term breaks in 1 n−2 Pn−2 j=1 Pi(g2, σ, j). Similarly to the previous case, the cho...
-
[14]
Grouping these terms, we can write 1 |Sn−2| X h∈Sn−2 f ′ i (σhg(n − 1), σhg(n)) = 1 (n − 2)! n−2X j=1 (n − 3)!f ′(σ(j), σ(n)) = 1 n − 2 n−2X j=1 f (σ · (n − 1, j))
g3 = (n − 2, n− 1) σhg(n) = σh(n) = σ(n) (38) σhg(n − 1) = σh(n − 2) = σ(j) for j ∈ [n − 2] (39) There are (n − 3)! elements h ∈ Sn−2 that can produce a certain j, and there are n − 2 possible j. Grouping these terms, we can write 1 |Sn−2| X h∈Sn−2 f ′ i (σhg(n − 1), σhg(n)) =...
-
[15]
(43) 17 So the term breaks in 1 n−2 Pn−2 j=1 Pi(g4, σ, j)
g4 = (n − 2, n) σhg(n) = σh(n − 2) = σ(j) for j ∈ [n − 2] (41) σhg(n − 1) = σh(n − 1) = σ(n − 1) (42) Similarly to the case above, 1 |Sn−2| X h∈Sn−2 f ′ i (σhg(n − 1), σhg(n)) = 1 (n − 2)! n−2X j=1 (n − 3)!f ′(σ(n − 1), σ(j)) = 1 n − 2 n−2X j=1 f (σ · (n, j)). (43) 17 So the t...
-
[16]
(46) So the term breaks in 1 n−2 Pn−2 j=1 Pi(g5, σ, j)
g5 = (n − 2, n− 1, n) σhg(n) = σh(n − 2) = σ(j) for j ∈ [n − 2] (44) σhg(n − 1) = σh(n) = σ(n) (45) Hence, 1 |Sn−2| X h∈Sn−2 f ′ i (σhg(n − 1), σhg(n)) = 1 (n − 2)! n−2X j=1 (n − 3)!f ′(σ(n), σ(j)) = 1 n − 2 n−2X j=1 f (σ · (j, n− 1, n)). (46) So the term breaks in 1 n−2 Pn−2 ...
-
[17]
(50) So the term breaks in 1 n−2 Pn−2 j=1 Pi(g6, σ, j)
g6 = (n − 2, n, n− 1) σhg(n) = σh(n − 1) = σ(n − 1) (47) σhg(n − 1) = σh(n − 2) = σ(j) for j ∈ [n − 2] (48) Therefore, 1 |Sn−2| X h∈Sn−2 f ′ i (σhg(n − 1), σhg(n)) = 1 (n − 2)! n−2X j=1 (n − 3)!f ′(σ(j), σ(n − 1)) (49) = 1 n − 2 n−2X j=1 f (σ · (j, n, n− 1)). (50) So the term ...
-
[18]
post-concatenation
g = (n − 3, n− 1)(n − 2, n) σhg(n) = σh(n − 2) = σ(j) for j ∈ [n − 2] (51) σhg(n − 1) = σh(n − 3) = σ(l) for l ∈ [n − 2], l̸= j (52) Then, we obtain 1 |Sn−2| X h∈Sn−2 f ′ i (σhg(n − 1), σhg(n)) = 1 (n − 2)! n−2X j=1 n−2X l=1 l̸=j (n − 4)!f ′(σ(j), σ(l)) (53) = 1 n − 2 n−2X j=1...
2011
-
[203]
Scarselli, F., Gori, M., Tsoi, A
Springer Science & Business Media, 2013. Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G. The graph neural network model. IEEE transactions on neural networks, 20(1):61–80, 2008. Stone, M. H. The generalized weierstrass approximation theorem. Mathemat...
2007 arXiv
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.