{"id":"84d1c833-87c7-48ca-9425-8885b7923289","arxiv_id":"2505.23609","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The generalized Skew Spectrum embeds attributed, multilayer, and hypergraph data into permutation-invariant vectors, and its doubly-reduced k-spectra distinguish all 7-node graphs at the same asymptotic cost as the original Skew Spectrum.","lead":"This paper builds a family of graph codes that stay the same no matter how the nodes are numbered, extending an older method called the Skew Spectrum. The new codes handle labeled, multilayer, and hypergraph data, and a cheaper version distinguishes more graphs at the same computational cost.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The no-order/no-repetition double reduction is justified by Theorems 4.5–4.6 only for scalar (binary) f; Algorithm 1 applies it to vector-valued multi-orbit inputs, where tensor factors don't commute and repeated elements carry correlation, so the claimed expressivity gain at Skew Spectrum cost…","rationale":"The paper's central promise is that the doubly-reduced k-Spectrum preserves the generalization to richer graph structures while matching the Skew Spectrum's asymptotic cost. That promise rests on two theorems: 4.5 (repetitions add nothing) and 4.6 (order doesn't matter). Both proofs are restricted: 4.5 requires f: Sn -> {0,1} and uses idempotence f(g)^2=f(g); 4.6 is stated for scalar f and its proof uses commutativity of the factors f(gg_l), which fails for vector-valued f because tensor factors in (8) do not commute in general. Algorithm 1 nevertheless applies the unordered, repetition-free reduction to C^d-valued inputs, so for attributed or weighted graphs the reduced object may discard exactly the cross-orbit correlation terms that were the motivation for the multi-orbit construction (Section 3). Thus the 'generalization-preserving' claim and the 'same computational cost' claim are not established in the multi-orbit regime. This is the same weakest assumption identified by the reader; I agree with that identification. I did not make the Figure 1 caption fragment the lead concern because, while it is a legitimate provenance/novelty flag that must be clarified, it does not bear directly on the correctness of the algorithmic claims; nevertheless it should be resolved (authors should either cite the 2022 work or remove the stray text). The proposed test - comparing ordered vs unordered reduced spectra on small multi-orbit graphs - will settle whether the concern lands. If the test shows order/repetition matters for d>1, the paper should either restrict the double-reduction claim to scalar unweighted graphs or prove extended versions of Theorems 4.5/4.6. Verdict remains CONDITIONAL.","tokens_in":23166,"tokens_out":6971,"duration_ms":62122,"concrete_test":"Implement the ordered and unordered versions of the reduced k-Spectrum for a small vector-valued f (e.g., n=5, d=2, two orbits like adjacency plus node labels) and compare them on a pair of graphs with the same unordered orbit spectra but different cross-orbit correlations. If the unordered (doubly-reduced) version cannot separate graphs that the ordered version separates, or if permuting the three double-coset representatives in G_{k-2} changes the spectrum for d=2, then Theorem 4.6 does not extend to multi-orbit inputs and the generality claim in the abstract fails. Similarly, re-run the collision experiment of §7.2 on the 7-node Atlas with node labels (two orbits) and compare collisions for doubly-reduced vs. ordered spectra.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4's 'Double reduction' (Theorems 4.5 and 4.6) is the sole justification for computing the k-Spectrum only on C(7,k-2) unordered, repetition-free combinations of double-coset representatives. Theorem 4.5 is proved only for f: Sn -> {0,1}, using f(g)^2=f(g); for weighted or vector-valued f, repeated elements do not generally add zero information. Theorem 4.6 is stated and proved only for scalar f: the proof asserts 'the terms f(gg_l) commute', which is false for vector-valued f, where the tensor product f(g)⊗f(gg1)⊗...⊗f(gg_{k-2}) is order-sensitive. Algorithm 1, however, applies the same double reduction to f: Sn/Sn-2 -> C^d (d≥1) and to weighted inputs, as required for attributed, multilayer, and hypergraph structures claimed in the abstract. Consequently, for d>1 or non-binary weights, the doubly-reduced spectrum may be strictly weaker than the full k-Spectrum, and the central claim that the heuristics 'improve the Skew Spectrum's expressivity at the same computational cost' is not established for the multi-orbit generalization. The experiments in §7.2 use unweighted, single-orbit graphs, so they do not exercise this gap. (Secondary: the orphan caption fragment 'The Multi-Orbits Skew Spectrum ... Conference 2022' in Figure 1 is uncited and should be clarified; this is a provenance/novelty issue, not a correctness issue.)","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":23446,"tokens_out":11391,"duration_ms":96168,"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":[{"comment":"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":"Section 4, 'Double reduction' and Algorithm 1"},{"comment":"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.","section":"Section 4, Theorems 4.5 and 4.6"}],"minor_comments":[{"comment":"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":"Figure 1"},{"comment":"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":"Section 7, Tables 1 and 3"},{"comment":"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.","section":"Section 6.1"},{"comment":"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":"Appendix A and Introduction"},{"comment":"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.","section":"Section 4.1"}],"recommendation":"major_revision","confidential_remarks":"The main obstacle is the gap between the scalar/binary theorems justifying the double reduction and the vector-valued multi-orbit usage in Algorithm 1. This is fixable, either by proving a suitable generalization or by qualifying the claims. I would also encourage the authors to clarify the relation to the first author's thesis (Bellante 2024), which is cited for background but may contain earlier versions of some of these results; this is not a blocking issue. The experimental section is useful as a proof of concept, but the regression comparisons should be more rigorous before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a genuine extension of Kondor and Borgwardt's Skew Spectrum. The invariance theorem is correct, the complexity bounds are careful, and the new pieces—multi-orbit spectra, the k-Spectrum family, and the dynamic-programming algorithm—are real contributions. On unweighted single-orbit graphs the experiments back the claim: concatenated k-Spectra give zero collisions on the 7-node Atlas, beating 1-WL and Laplacian eigenvalues in that setting. The paper deserves a serious referee.\n\nThe main soft spot is the double reduction. Theorems 4.5 and 4.6 justify ignoring repeated elements and ordering only for scalar functions; 4.5 uses f(g)^2 = f(g), so binary f, and 4.6 relies on the terms f(gg_l) commuting, which fails for vector-valued f because the tensor product is order-sensitive. Algorithm 1 applies the same reduction to f: Sn/Sn-2 -> C^d and to weighted inputs, so the central claim—improving expressivity at the same computational cost—is rigorously established only in the binary scalar case. The authors are honest that this is a heuristic, but the claim is stated more broadly than the proofs support. The experiments in Section 7.2 happen to be on unweighted single-orbit graphs, so they do not exercise the gap. This needs either a proof extension or a restriction of the claim to the proven setting.\n\nOther concerns are minor. Figure 1 carries an orphan caption fragment referencing a 2022 conference paper; that needs a clarification, but it does not look like substantive overlap. No code or data are shipped, and the QM7 and PROTEINS comparisons lack error bars and modern baselines. Those are experimental weaknesses, not theory problems. The WL discussion is appropriately framed as empirical and complementary.\n\nThe math is in good shape. The invariance proof is elementary and correct, the sparsity analysis is detailed, and the complexity bound O(d^{k-1} n^3 + d^k n^2) with C(7,k-2) * 7 * d^k non-zero entries is consistent with the algorithm. The citations to Adler-Konheim, Chazan-Weiss, and Kakarala are appropriate and not inflated.\n\nWho this is for: anyone working on group-theoretic graph invariants or spectral embeddings. I would bring it to a reading group. For peer review: accept. The double-reduction gap is fixable and the core results are solid. If the authors extend the reduction theorems to vector-valued f or explicitly restrict the expressivity claim to binary scalar f, I would be happy to see it published.","headline":"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.","tokens_in":24046,"tokens_out":4071,"would_cite":true,"duration_ms":34358,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C60","05C50","20C30","68R10","43A75"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["generalized skew spectrum","multi-orbit graph embeddings","k-correlation spectra","Fourier transform on the symmetric group","graph isomorphism invariants","doubly-reduced k-spectrum","Weisfeiler-Lehman expressivity","attributed and multilayer graphs"],"falsifier":"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.","tokens_in":22860,"feed_emoji":"🕸️","tokens_out":15281,"duration_ms":133063,"temperature":0.7,"pith_summary":"The paper tries to establish that the Skew Spectrum—a permutation-invariant graph embedding built from Fourier analysis on the symmetric group—can be generalized in two directions at once: vector-valued multi-orbit functions that pack adjacency, node features, edge features, or layers into one object, and higher-order $k$-correlation spectra that trade computation for expressivity. The central claim is that both generalizations remain invariant under graph isomorphism, so isomorphic graphs always receive the same embedding, and that a doubly-reduced variant computes at the same asymptotic cost as the original Skew Spectrum while distinguishing more graphs. This matters because most practical graph representations either fail on attributed, multilayer, or hypergraph structures or lack expressivity guarantees beyond the Weisfeiler-Lehman test. On the Atlas of all 7-node graphs, the concatenated doubly-reduced $k$-spectra for $k=3,\\dots,9$ give zero collisions, outperforming Laplacian eigenvalues and 1-WL; on 8-node chordal graphs the situation reverses, showing the two families measure different structure. If right, the paper offers a principled expressivity dial for graph learning rather than a single fixed invariant.","feed_headline":"Zero collisions: new graph spectra separate all 7-node graphs","feed_subtitle":"Group-theoretic embeddings tell every non-isomorphic 7-node graph apart at the original skew spectrum's computational cost.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"It defines the original Skew Spectrum and the reduced invariant whose invariance, sparsity, and cost this paper generalizes.","marker":"(Kondor & Borgwardt, 2008)"},{"why":"It supplies the fast Fourier transform on the symmetric group that makes the $O(n^3)$ transforms on $S_n/S_{n-2}$ possible.","marker":"(Maslen, 1998)"},{"why":"It provides efficient Fourier transforms for $S_{n-k}$-invariant functions, which the paper cites for extending the construction to hypergraphs.","marker":"(Clausen & Hühne, 2017)"},{"why":"It establishes that correlation functions form complete translation invariants on abelian groups, motivating the hierarchy of k-correlations.","marker":"(Adler & Konheim, 1962)"},{"why":"It identifies settings in which triple correlations already give complete invariants, supporting the paper's conjecture of a finite complete k.","marker":"(Kakarala, 1992)"},{"why":"It anchors the 1-WL expressivity bound for message-passing GNNs that the experiments compare against.","marker":"(Xu et al., 2019)"},{"why":"It connects higher-order GNNs to the WL hierarchy, the expressivity reference used to position k-spectra.","marker":"(Morris et al., 2019)"},{"why":"It supplies the QM7 Coulomb-matrix dataset and atomization energy task used in the multi-orbit regression experiments.","marker":"(Rupp et al., 2012)"},{"why":"It provides the connected chordal graph data used for the 8-node collision comparison.","marker":"(McKay)"}],"fun_headline_variants":["Generalized skew spectrum: no collisions on 7-node graphs","New graph invariants tell all 7-node graphs apart","Generalized skew spectrum: richer embeddings, same cost","Fourier-based graph invariants distinguish all 7-node graphs","Permutation-invariant spectra: zero 7-node collisions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Generalized skew spectrum: no collisions on 7-node graphs","New graph invariants tell all 7-node graphs apart","Generalized skew spectrum: richer embeddings, same cost","Fourier-based graph invariants distinguish all 7-node graphs","Permutation-invariant spectra: zero 7-node collisions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000328,"raw_usage":{"total_tokens":1854,"prompt_tokens":992,"completion_tokens":862,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":608,"completion_tokens_details":{"reasoning_tokens":779}},"tokens_in":608,"tokens_out":862,"duration_ms":9052,"temperature":1.0,"reasoning_tokens":779,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:43:40.845510+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}