{"id":"01b0adeb-26d3-4fbf-9df3-fc62847d5796","arxiv_id":"2505.23691","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"Spectral moments of random walks on s-walk dyadic conversions of hypergraphs are proposed as a whole-graph representation and achieve strong classification accuracy, though key theoretical bounds contain errors.","lead":"Researchers show that random walk spectral moments can represent higher-order networks (hypergraphs) for graph classification. The method splits a network by edge size and computes return-probability moments from specially constructed random walks, achieving high accuracy, but several central theorems contain mathematical errors.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's identity m2 = E(d_i) E(1/(d_i d_j)) is false for weighted graphs; the s-walk dyadic graph has parallel edges, so Theorems 2 and 3 inherit the error.","rationale":"The reader's weakest assumption is exactly the point that breaks the paper's formal contribution. Re-deriving Theorem 1: for a weighted/multigraph edge of weight k between i and j, the 2-step return consists of choosing one of k parallel edges on the way out and one on the way back, contributing k^2/(d_i d_j) to m2, not 1/(d_i d_j) (nor k/(d_i d_j)). The 2-node two-edge example gives m2=1 while the claimed formula yields 1/2. The graph G^(s) is described as weighted, and the proof of Theorem 2 sums degrees with multiplicities via the factor binom(r,s) s! binom(r-s,s) s! |Er|, so the unweighted identity cannot be applied even if an implementation later drops duplicate edges. Thus Theorems 2 and 3, which are the theoretical basis for the abstract's claim that moments capture degree and clustering, are not established. The paper also limits its proofs to 1 <= s <= r/2 and skips details for the m3 formula, further narrowing formal coverage. The empirical classification results may indicate practical utility, but they do not repair the proof; secondary issues such as unfair baseline comparison (baselines see only downgraded dyadic graphs) and missing code strengthen the reject judgment. No change to the reader's verdict is needed.","tokens_in":10067,"tokens_out":10399,"duration_ms":91772,"concrete_test":"Compute the second spectral moment directly for the two-node graph with two parallel edges (edge weight 2). The claimed formula yields E(d_i) E(1/(d_i d_j)) = 2 * (1/4) = 1/2, whereas the transition matrix has P^2 = I, so m2 = 1; if the mismatch appears, the identity is false. Then verify that the s-walk construction yields such multiplicities: for hyperedges {a,b,c} and {a,b,d} with r=3, s=1, the dyadic graph contains a weight-2 edge (a,b). If both checks pass, the proofs of Theorems 2 and 3 must be re-derived with k^2 weights, and their stated bounds are not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's formal contribution is the claim that spectral moments of s-walk transition matrices bound higher-order degree and clustering properties (Theorems 2 and 3). Both proofs invoke Theorem 1, which asserts that the unweighted identity m2 = E(d_i) E(1/(d_i d_j)) extends to weighted graphs. That assertion is false. In a weighted/multigraph with edge weight k between i and j, the 2-step return contribution is (k/d_i)(k/d_j) = k^2/(d_i d_j), not k/(d_i d_j) or 1/(d_i d_j), because both the outgoing and return steps can choose among k parallel unit edges. The proof's 'treat a weight-k edge as k unit edges' only produces a factor k, missing the second factor k. A minimal counterexample is the two-node graph with two parallel edges: Theorem 1 gives m2 = 2 * (1/4) = 1/2, while direct computation gives P^2 = I and m2 = 1. This is not a degenerate case for this paper: the constructed dyadic graph G^(s) is weighted, with parallel edges whenever two hyperedges share the same ordered s-tuple pair, and even a single hyperedge yields multiple permutation-induced dyadic edges. Since Theorem 2's formula substitutes 1/(d_i d_j) with 1/(D[i]D[j]) and Theorem 3 repeats the same substitution for triads, both rely on the invalid identity. The central theoretical claim that moments bound degree and clustering is therefore unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a spectral representation of higher-order networks. It splits the network into uniform hypergraph layers of edge order r, defines s-walk transition matrices on associated weighted dyadic graphs whose nodes are ordered s-tuples, and uses the leading spectral moments m_l = (1/n) tr(P^l) across all (r,s) pairs as a graph-level feature vector. The authors claim (Theorems 1-3) that these moments bound hypergraph degree and clustering properties, and they report graph-classification experiments on 15 datasets showing that the representation outperforms dyadic graph-kernel and graph-CNN baselines.","tokens_in":10406,"tokens_out":5170,"duration_ms":48172,"significance":"If correct, the representation would be attractive because it is permutation-invariant, computable from transition matrices without training, and interpretable through the claimed bounds on degrees and triangles. The empirical study is well-scoped: it uses 15 public higher-order datasets, compares against four baselines, and includes ablations on the number of moments and on sampled graph size. The classification results are a useful empirical finding. However, the paper's formal core is not sound: Theorem 1 is false for weighted multigraphs, and Theorems 2 and 3 inherit this error. The advertised structural guarantees are therefore unsupported, even though the empirical features may still work in practice.","major_comments":[{"comment":"The identity m2 = E(d_i)E(1/(d_i d_j)) is claimed for weighted graphs, but the proof's step of replacing a weight-k edge by k unit edges is incorrect. A weight-k edge contributes k^2/(d_i d_j) to the two-step return probability, not 1/(d_i d_j), because both the outgoing and return steps may select among the k parallel unit edges. A minimal counterexample is the two-node graph with two parallel edges: the theorem gives m2 = 2 * (1/4) = 1/2, while direct computation gives P^2 = I and m2 = 1. The dyadic graphs G^(s) constructed in Section 4.2 are precisely such weighted multigraphs, since different hyperedge pairs and permutations can generate the same ordered-s-tuple dyadic edge.","section":"§4.3, Theorem 1 (Eq. 2)"},{"comment":"Both theorems rely on substituting the invalid Theorem 1 identity into the dyadic graph. Consequently Eq. (4) omits edge-weight factors and is already false in the simplest dyadic case r=2, s=1, where it yields m2 = (m/n)E(1/(D[i]D[j])) instead of the correct (2m/n)E(1/(D[i]D[j])). Eq. (9), which repeats the same substitution for the third spectral moment, is therefore also unestablished. Because these equations are the basis of the claimed bounds on degrees and clustering, the central formal contribution of the paper fails.","section":"§4.3, Theorems 2 and 3 (Eqs. 4 and 9)"},{"comment":"The proof of Theorem 3 is skipped: the text states 'we skip the details for brevity' after asserting m3 = 2E(delta_i)E(1/(d_h d_i d_j)) for weighted graphs, and Eq. (6) is introduced without derivation. Since the clustering bound in Eqs. (10)-(11) is one of the two advertised structural guarantees, this is a load-bearing missing proof rather than a minor omission. The formula for the weighted third moment would also need the same correction as Theorem 1, making the current bound doubly unsupported.","section":"§4.3, Theorem 3"},{"comment":"The statement that Eq. (5), m2 >= (1/(2 binom(r-s,s))) E(1/(D[i]D[j])), follows from Eq. (4) is not justified: Eq. (4) contains the factor binom(r,s)|E_r|/(2 binom(r-s,s)|V_G|), and the inequality requires an additional condition relating |E_r|, |V_G|, and the binomial coefficients. If this condition is intended to be immediate from hypergraph size, it should be stated and proved; otherwise the displayed 'natural bound' is not a corollary of the theorem as written.","section":"§4.3, Eq. (5)"}],"minor_comments":[{"comment":"There are several typos, including 'Nomalized' in §4.1, 'Spectal Moments' in Table 2, 'Preformances' in §5.5, and 'coath' instead of 'coauth' in Figure 4; these should be corrected.","section":"Throughout"},{"comment":"The claim of being 'the first work to represent higher-order networks in their entirety with spectral information' is a strong novelty assertion that is not substantiated by a comprehensive literature comparison; the wording should be softened.","section":"§1, Introduction"},{"comment":"Figure 1 is not referenced in the proofs of Theorems 2 or 3, and its caption does not explain how the ordered-s-tuple nodes and the dyadic edges are formed; a precise caption or a short derivation would help the reader follow the construction.","section":"§4.2, Figure 1"},{"comment":"The letter G is used for both the higher-order network and the dyadic graph (e.g., 'G = (V, E_1, E_2, ...)' vs. 'G^(s)'), and the subscript/superscript notation is inconsistent; a clear distinction between the two objects would improve readability.","section":"Notation"}],"recommendation":"reject","confidential_remarks":"I agree with the reader's assessment. The paper's central theorems are false as stated, and the error cannot be repaired by local corrections: the weighted dyadic construction is essential to the method, and any corrected moment identity would have to carry edge-weight factors through Theorems 2 and 3, changing the claimed bounds. The empirical classification results may still be publishable as a purely experimental contribution if the theoretical claims are removed or substantially revised, but that would be a different paper. I would not recommend revision within the current scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the representation idea is sensible and the classification results are strong, but the theoretical claims rest on a false identity for weighted graphs. As written, Theorems 2 and 3 don't hold, so the paper overstates what it proves.\n\nWhat's actually new: concatenating the first few spectral moments of s-walk transition matrices over edge orders and overlap sizes is, as far as I know, a new feature vector for hypergraphs. The empirical work is broad: 15 datasets, 8 classes, multiple baselines, and the accuracy gains are large and fairly consistent. The writing is clear and the preprocessing steps are described carefully enough to follow.\n\nThe soft spot is load-bearing and it is in the math. Theorem 1 claims that for weighted graphs m2 = E(d_i) E(1/(d_i d_j)). That's not true. For a weight-k edge, the two-step return contribution is k^2/(d_i d_j), not 1/(d_i d_j). The proof's trick of treating a weight-k edge as k unit edges misses the second factor of k: after going i→j along one unit edge, the walk can return along any of the k unit edges, giving k choices in each direction. A two-node graph with two parallel edges gives m2=1, while the claimed formula gives 1/2. This is not a degenerate case: the dyadic graphs constructed from hypergraphs have parallel edges whenever multiple hyperedges induce the same s-tuple pair. Moreover, even for unweighted dyadic graphs, Theorem 2 is off by a factor of 2. For r=2,s=1 it gives m2=(m/n)E(1/(d_i d_j)) instead of (2m/n)E(...). A single edge or a triangle confirms the discrepancy. Theorem 3 inherits the same problem and its proof is mostly skipped. So the central claim that spectral moments bound higher-order degree and clustering properties is unsupported.\n\nThe empirical comparison has a weaker issue: baselines only see downgraded dyadic graphs, so they never get access to the higher-order structure. That's understandable but makes the headline comparison less strong than it looks.\n\nWho should read this: researchers working on hypergraph classification and higher-order network features. The representation might be practically useful even if the proofs are wrong, and the error is identifiable and fixable. I'd send it to review, but with a strict instruction to the referee to check the moment identities. As it stands, the theoretical claims should not be trusted.","headline":"Promising higher-order graph representation with strong empirical results, but the theoretical bounds rest on a false weighted-graph identity.","tokens_in":10922,"tokens_out":10735,"would_cite":false,"duration_ms":86947,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C65","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The first few spectral moments of higher-order random walks encode hypergraph structure and win classification.","keywords":["higher-order networks","hypergraphs","spectral moments","random walks","s-walks","graph classification","graph representation learning","Laplacian spectrum"],"falsifier":"Take a two-node graph with one edge of weight 2. The paper's identity gives $m_2 = E(d_i)E(1/(d_i d_j)) = 2 \\cdot (1/4) = 1/2$, but direct computation of the transition matrix gives $P^2 = I$ with both squared eigenvalues equal to 1, so the true second spectral moment is 1. This mismatch is observable by computing actual two-step return probabilities.","tokens_in":9840,"feed_emoji":"🕸️","tokens_out":7546,"duration_ms":70721,"temperature":0.7,"pith_summary":"Higher-order networks, whose edges connect more than two nodes, lack the simple spectral machinery that works for ordinary graphs. This paper proposes representing such a network by splitting it into uniform hypergraphs by edge size, converting each layer into weighted dyadic graphs whose nodes are ordered tuples of vertices and whose edges encode overlapping $s$-walks, and then concatenating the first few spectral moments of the corresponding random walk transition matrices. It proves that the second and third moments bound degree and triangle statistics of the original hypergraph, and experimentally shows that this compact vector, fed to a standard classifier, outperforms graph kernels and a deep convolutional baseline applied to downgraded dyadic versions of the same data. If right, it gives practitioners a cheap, explainable, order-invariant feature vector for higher-order graphs.","feed_headline":"A few spectral moments beat baselines on hypergraph classification","feed_subtitle":"Splitting hyperedges by size and overlap turns structure into a compact vector that wins classification tasks.","key_machinery":"The load-bearing objects are $s$-walks in an $r$-uniform hypergraph: a sequence of $r$-edges in which consecutive edges share exactly $s$ vertices. Each such walk is mapped to a walk of the same length in a weighted dyadic graph whose nodes are ordered $s$-tuples of vertices, and the normalized Laplacian and transition matrix of that dyadic graph supply the spectrum. Spectral moments $m_l = (1/n)\\sum_i \\lambda_i^l$ are then the expected return probability of an $l$-step $s$-walk. Theorems 1 through 3 carry the argument: Theorem 1 supplies the weighted-graph identity for $m_2$, and Theorems 2 and 3 use the counting of dyadic edges generated by each hyperedge to turn that identity into bounds on hypergraph degrees and triangles.","core_discovery":"On the paper's own terms, the central discovery is that the spectral moments $m_l = E(\\lambda^l)$ of the $s$-walk transition matrix, taken over every edge order $r$ and overlap size $s$, capture the higher-order structure of a network. For $1 \\le s \\le r/2$, each $r$-uniform hypergraph layer is converted to a weighted dyadic graph $G^{(s)}$ on ordered $s$-tuples; Theorem 2 expresses $m_2$ as a constant times $E(1/(D[i] D[j]))$ over hyperedge degrees, yielding an upper bound, and Theorem 3 expresses $m_3$ in terms of the average number of hypergraph triads and degree triples, again yielding bounds. These results show that the first moments are not arbitrary features: they measure return probabilities of random walks and directly encode degree and clustering properties of the original higher-order edges.","pith_inferences":["Going beyond the paper: because spectral moments are return-probability expectations, graphs that differ only in non-backtracking or long-range structure can share the same low-order moments; testing on synthetic hypergraphs with identical first few moments but different community structure would delineate what this representation cannot see.","Going beyond the paper: the same dyadic conversion could feed spectral moments into generative models or anomaly detection, where compact structural summaries of hypergraphs are currently missing.","Going beyond the paper: a natural next test is whether the moment vector is competitive with higher-order graph kernels on node-level classification, not just whole-graph label prediction.","Going beyond the paper: the counting arguments behind Theorems 2 and 3 suggest direct estimators for hypergraph degree and triangle statistics from sampled moments, which could be validated against exact counts on medium-sized datasets."],"forward_implications":["The full higher-order graph can be summarized by a single vector of spectral moments computed per edge order and overlap size, so no pairwise kernel matrix or node embeddings are required.","Because $m_2$ and $m_3$ bound hypergraph degree and triangle statistics, classifiers using the first few moments are using structure that is provably tied to high-order connectivity rather than arbitrary graph statistics.","In the reported experiments the method beats shortest-path, Weisfeiler-Lehman, RetGK, and PSCN baselines on downgraded graphs, for both the eight-class and per-domain classification tasks.","Using more than the first two to four moments does not systematically improve accuracy and can hurt on some tasks, since higher moments converge to stationary probabilities and add noise.","The representation remains competitive as sampled subgraph size grows, unlike shortest-path and PSCN, which hit performance bottlenecks at larger sizes."],"supporting_citations":[{"why":"Defines spectral moments of random-walk transition matrices and proves the unweighted $m_2$ identity that Theorem 1 extends to weighted graphs.","marker":"[10]"},{"why":"Introduces $s$-walks and generalized Laplacians on hypergraphs, the walk definition the representation is built on.","marker":"[13]"},{"why":"Foundational higher-order Laplacian for $r$-uniform hypergraphs, which the S-Laplacian construction generalizes.","marker":"[5]"},{"why":"Supplies the 15 real-world higher-order network datasets used in the classification experiments.","marker":"[1]"},{"why":"RetGK baseline whose return-probability kernel the method is compared against.","marker":"[21]"},{"why":"Weisfeiler-Lehman subtree kernel baseline in the classification comparison.","marker":"[19]"},{"why":"Shortest-path kernel baseline on downgraded dyadic graphs.","marker":"[3]"},{"why":"Random-walk hypergraph sampling procedure used to generate training subgraphs.","marker":"[22]"},{"why":"PSCN deep convolutional baseline on downgraded graphs.","marker":"[16]"}],"fun_headline_variants":["Spectral moments pack hypergraph structure into a vector that beats baselines","Moments of s-walk spectra capture hypergraph degree and clustering","Higher-order network fingerprints from spectral moments","Spectral moments make hypergraphs classifiable with a few numbers","From edges to hyperedges: spectral moments as compact descriptors"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The main theoretical bridge rests on treating a weighted edge of strength $k$ as $k$ separate ordinary edges, but in a weighted random walk a stronger edge is traversed more often in both directions, so the claimed $k$-fold contribution is not what the walk actually makes.","fun_headline_variants_meta":{"raw":{"variants":["Spectral moments pack hypergraph structure into a vector that beats baselines","Moments of s-walk spectra capture hypergraph degree and clustering","Higher-order network fingerprints from spectral moments","Spectral moments make hypergraphs classifiable with a few numbers","From edges to hyperedges: spectral moments as compact descriptors"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000859,"raw_usage":{"total_tokens":3702,"prompt_tokens":893,"completion_tokens":2809,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":509,"completion_tokens_details":{"reasoning_tokens":2726}},"tokens_in":509,"tokens_out":2809,"duration_ms":19485,"temperature":1.0,"reasoning_tokens":2726,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:42:09.405426+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a two-node graph with one edge of weight 2. The paper's identity gives $m_2 = E(d_i)E(1/(d_i d_j)) = 2 \\cdot (1/4) = 1/2$, but direct computation of the transition matrix gives $P^2 = I$ with both squared eigenvalues equal to 1, so the true second spectral moment is 1. This mismatch is observable by computing actual two-step return probabilities.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines spectral moments of random-walk transition matrices and proves the unweighted $m_2$ identity that Theorem 1 extends to weighted graphs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces $s$-walks and generalized Laplacians on hypergraphs, the walk definition the representation is built on."},{"cited_title":"Expanding graphs pp","cited_arxiv_id":null,"evidence_quote":"Foundational higher-order Laplacian for $r$-uniform hypergraphs, which the S-Laplacian construction generalizes."},{"cited_title":"Simplicial Closure and higher-order link prediction","cited_arxiv_id":"1802.06916","evidence_quote":"Supplies the 15 real-world higher-order network datasets used in the classification experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"RetGK baseline whose return-probability kernel the method is compared against."},{"cited_title":"Journal of Machine Learning Research 12(77), 2539–2561 (2011)","cited_arxiv_id":null,"evidence_quote":"Weisfeiler-Lehman subtree kernel baseline in the classification comparison."},{"cited_title":"In: Fifth IEEE Inter- national Conference on Data Mining (ICDM’05)","cited_arxiv_id":null,"evidence_quote":"Shortest-path kernel baseline on downgraded dyadic graphs."},{"cited_title":"In: Sch¨ olkopf, B., Platt, J., Hoffman, T","cited_arxiv_id":null,"evidence_quote":"Random-walk hypergraph sampling procedure used to generate training subgraphs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"PSCN deep convolutional baseline on downgraded graphs."}],"review_version":1}