Representing Higher-Order Networks with Spectral Moments

Hao Tian; Reza Zafarani; Shengmin Jin

REVIEW 4 major objections 4 minor 22 references

Representing Higher-Order Networks with Spectral Moments

T0 review · 4 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The first few spectral moments of higher-order random walks encode hypergraph structure and win classification.

desk verdict Promising higher-order graph representation with strong empirical results, but the theoretical bounds rest on a false weighted-graph identity. read the letter →

arxiv 2505.23691 v1 pith:7FYJQ7KK submitted 2025-05-29 cs.SI

Hao Tian , Shengmin Jin , Reza Zafarani This is my paper

classification cs.SI MSC 05C5005C6568R10

keywords higher-ordernetworkshypergraphsspectralmomentsrandomwalkss-walksgraphclassificationrepresentationlearningLaplacianspectrum

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

What'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.

The 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.

The 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.

Who 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.

Referee Report

4 major / 4 minor

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.

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 (4)

[§4.3, Theorem 1 (Eq. 2)] 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.
[§4.3, Theorems 2 and 3 (Eqs. 4 and 9)] 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.
[§4.3, Theorem 3] 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.
[§4.3, Eq. (5)] 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.

minor comments (4)

[Throughout] 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.
[§1, Introduction] 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.
[§4.2, Figure 1] 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.
[Notation] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the spectral moments are computed directly from the graph's own transition matrices, the structural bounds are derived (not fitted) relationships, and the self-citations are lemmas rather than reductions of the central claim to its own input.

full rationale

The central representation is built by computing spectral moments from the s-walk transition matrices via Eq. (1), then concatenating them across edge orders and overlap sizes. These features are not fitted to labels, to the target degree/clustering quantities, or to a subset of the evaluation data; the graph classification experiments therefore test the representation against held-out classes rather than re-announcing a fitted quantity. Theorems 2 and 3 are mathematical identities/inequalities linking moments to degree and triangle counts of the same hypergraph; while the correctness of Theorem 1's extension to weighted graphs is questionable (the 'weight-k edge as k unit edges' argument may double-count parallel dyadic edges), that is a mathematical-error concern, not circularity: the right-hand sides are not inputs tuned to reproduce the left-hand sides. The paper does cite prior work by one of its authors [10] for the dyadic identities behind Theorems 1 and 3, and it states that the m3 identity is 'easy to prove' while skipping details. This is a self-citation and a proof gap, but it is not a case of a prediction being equivalent to its input by construction, nor does the empirical contribution depend on those identities. Overall, the derivation chain is not circular; any serious concerns about Theorem 1 belong to correctness, not self-reference.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

The representation introduces no new physical entities. The main assumptions are the s-walk construction from prior work and the validity of dyadic spectral moment identities when extended to weighted graphs; the latter is invalid for weights > 1.

free parameters (2)

Number of spectral moments per (r,s) pair = 3 (m2, m3, m4); varied up to 14
The paper chooses the first few moments as features and then studies sensitivity; this is a hand-chosen hyperparameter, not fitted to labels.
Maximum edge order r_max = 5
Set to 5 because the smallest maximum order among datasets is 5 (Section 5.1); higher-order layers above 5 are ignored.

assumptions (6)

domain assumption Undirected hypergraphs
Section 3 states 'We only consider undirected hypergraphs'.
domain assumption s-walk definition and S-Laplacian from Lu and Peng [13]
The construction of the dyadic graph G^(s) relies on this prior definition of s-walks; cited but not re-derived.
domain assumption Random walk transition matrix is well-defined (no isolated nodes)
The spectral moment formulas (Theorem 1) presume a transition matrix without zero rows; the paper does not address isolated ordered s-tuples in V^s.
domain assumption Theorems restricted to 1 ≤ s ≤ r/2
Section 4.3 states 'we only prove cases under 1≤s≤r/2' because s>r/2 introduces repeated vertices.
standard math Dyadic spectral moment formulas from [10]
The paper cites [10] for m2 = E(d_i)E(1/(d_i d_j)) and the m3 analog; this is treated as a known result for unweighted graphs.
ad hoc to paper Weighted edge can be split into unit edges without changing spectral moments
Theorem 1's proof treats a weight-k edge as k unit edges, but this changes the return-probability accounting and is the source of the factor error.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Representing Higher-Order Networks with Spectral Moments." pith.science (2026). https://pith.science/paper/7FYJQ7KK

@misc{pith2026250523691,
  author       = {Pith},
  title        = {Pith review of: Representing Higher-Order Networks with Spectral Moments},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7FYJQ7KK}},
  note         = {Machine review of arXiv:2505.23691}
}

read the original abstract

The spectral properties of traditional (dyadic) graphs, where an edge connects exactly two vertices, are widely studied in different applications. These spectral properties are closely connected to the structural properties of dyadic graphs. We generalize such connections and characterize higher-order networks by their spectral information. We first split the higher-order graphs by their ``edge orders" into several uniform hypergraphs. For each uniform hypergraph, we extract the corresponding spectral information from the transition matrices of carefully designed random walks. From each spectrum, we compute the first few spectral moments and use all such spectral moments across different ``edge orders" as the higher-order graph representation. We show that these moments not only clearly indicate the return probabilities of random walks but are also closely related to various higher-order network properties such as degree distribution and clustering coefficient. Extensive experiments show the utility of this new representation in various settings. For instance, graph classification on higher-order graphs shows that this representation significantly outperforms other techniques.

Figures

Figures reproduced from arXiv: 2505.23691 by the authors.

**Figure 1.** Two cases of s-walks when calculating Laplacians. (a) Case 1 ≤ s ≤ r/2, edges are only adjacent to one previous and one following edge; (b) Case r/2 < s ≤ r − 1, there exists more overlaps among edges. along with a sequence of edges e1, e2, ..., ek such that ei = {v(r−s)(i−1)+1, v(r−s)(i−1)+2, ..., v(r−s)(i−1)+r}. Simply speaking, an s-walk of r-uniform hypergraph is a sequence of r-edges where each two consecutive … view at source ↗

**Figure 2.** m2 and m3 via certain bouned values calculated from hypergraph properties, such as degrees and number of triangles. Figure 2a shows inequality of Equation 5, Figure 2b shows inequality of Equation 10. For clearness only 30 out of 500 small graphs from coauth-DBLP are shown. To perform classification on many (but relatively smaller) higher-order graphs, we perform random walk sampling [22] on each graph. Starting fr… view at source ↗

**Figure 3.** Accuracy changes with more spectral moments used as features. From top left to bottom right: 8-classes, coauth, contact, email, tags and twitter. 5-50 51-100 101-200 201-400 401-800 0.5 0.6 0.7 0.8 0.9 Graph Size ACCs Spectral Moments RetGK W-L Subtree Shortest Path PSCN [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

[1]

Simplicial Closure and higher-order link prediction

Benson, A.R., Abebe, R., Schaub, M.T., Jadbabaie, A., Kleinberg, J.M.: Simplicial closure and higher-order link prediction. CoRRabs/1802.06916(2018)

work page Pith review arXiv 2018
[2]

Higher-order organization of complex networks

Benson, A.R., Gleich, D.F., Leskovec, J.: Higher-order organization of complex networks. CoRRabs/1612.08447(2016)

work page Pith review arXiv 2016
[3]

In: Fifth IEEE Inter- national Conference on Data Mining (ICDM’05)

Borgwardt, K., Kriegel, H.: Shortest-path kernels on graphs. In: Fifth IEEE Inter- national Conference on Data Mining (ICDM’05). pp. 8 pp.– (2005)

work page 2005
[4]

Chen, T., Guestrin, C.: XGBoost: A scalable tree boosting system. In: KDD. pp. 785–794. KDD ’16, ACM, New York, NY, USA (2016)

work page 2016
[5]

Expanding graphs pp

Chung, F.: The laplacian of a hypergraph. Expanding graphs pp. 21–36 (1993)

work page 1993
[6]

Do, M.T., Yoon, S.e., Hooi, B., Shin, K.: Structural patterns and generative mod- els of real-world hypergraphs. p. 176–186. KDD ’20, Association for Computing Machinery, New York, NY, USA (2020)

work page 2020
[7]

Jin, S.: Interpretable network representations (2022)

work page 2022
[8]

In: 2022 IEEE International Conference on Knowledge Graph (ICKG)

Jin, S., Ma, R., Li, J., Eftekharnejad, S., Zafarani, R.: A spectral measure for net- work robustness: Assessment, design, and evolution. In: 2022 IEEE International Conference on Knowledge Graph (ICKG). pp. 97–104. IEEE (2022)

work page 2022

Show all 22 references

[9]

Jin, S., Tian, H., Li, J., Zafarani, R.: A spectral representation of networks: The path of subgraphs. p. 698–708. KDD ’22 (2022)

2022
[10]

Jin, S., Zafarani, R.: The spectral zoo of networks: Embedding and visualizing networks with spectral moments. pp. 1426–1434. KDD ’20 (2020)

2020
[11]

CoRR (2019)

Kriege, N.M., Johansson, F.D., Morris, C.: A survey on graph kernels. CoRR (2019)

2019
[12]

Leskovec, J., Huttenlocher, D., Kleinberg, J.: Signed networks in social media (2010)

2010
[13]

Lu, L., Peng, X.: High-ordered random walks and generalized laplacians on hyper- graphs (2011)

2011
[14]

Science298(5594) (2002)

Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.: Network motifs: Simple building blocks of complex networks. Science298(5594) (2002)

2002
[15]

CoRR (2017)

Narayanan, A., Chandramohan, M., Venkatesan, R., Chen, L., Liu, Y., Jaiswal, S.: graph2vec: Learning distributed representations of graphs. CoRR (2017)

2017
[16]

Niepert, M., Ahmed, M., Kutzkov, K.: Learning convolutional neural networks for graphs. vol. 48, pp. 2014–2023. PMLR, New York, New York, USA (2016)

2016
[17]

CoRR (2019)

Pineau, E.: Using laplacian spectrum as graph feature representation. CoRR (2019)

2019
[18]

Rossi, R.A., Ahmed, N.K., Koh, E.: Higher-order network representation learning. p. 3–4. WWW ’18 (2018)

2018
[19]

Journal of Machine Learning Research 12(77), 2539–2561 (2011)

Shervashidze, N., Schweitzer, P., van Leeuwen, E.J., Mehlhorn, K., Borgwardt, K.M.: Weisfeiler-lehman graph kernels. Journal of Machine Learning Research 12(77), 2539–2561 (2011)

2011
[20]

SIGKDD Explor

Tian, H., Zafarani, R.: Higher-order networks representation and learning: A sur- vey. SIGKDD Explor. Newsl.26(1), 1–18 (Jul 2024)

2024
[21]

Zhang, Z., Wang, M., Xiang, Y., Huang, Y., Nehorai, A.: Retgk: Graph kernels based on return probabilities of random walks (2018)

2018
[22]

In: Sch¨ olkopf, B., Platt, J., Hoffman, T

Zhou, D., Huang, J., Sch¨ olkopf, B.: Learning with hypergraphs: Clustering, classi- fication, and embedding. In: Sch¨ olkopf, B., Platt, J., Hoffman, T. (eds.) Advances in Neural Information Processing Systems. vol. 19. MIT Press (2006)

2006

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Simplicial Closure and higher-order link prediction

Benson, A.R., Abebe, R., Schaub, M.T., Jadbabaie, A., Kleinberg, J.M.: Simplicial closure and higher-order link prediction. CoRRabs/1802.06916(2018)

work page Pith review arXiv 2018

[2] [2]

Higher-order organization of complex networks

Benson, A.R., Gleich, D.F., Leskovec, J.: Higher-order organization of complex networks. CoRRabs/1612.08447(2016)

work page Pith review arXiv 2016

[3] [3]

In: Fifth IEEE Inter- national Conference on Data Mining (ICDM’05)

Borgwardt, K., Kriegel, H.: Shortest-path kernels on graphs. In: Fifth IEEE Inter- national Conference on Data Mining (ICDM’05). pp. 8 pp.– (2005)

work page 2005

[4] [4]

Chen, T., Guestrin, C.: XGBoost: A scalable tree boosting system. In: KDD. pp. 785–794. KDD ’16, ACM, New York, NY, USA (2016)

work page 2016

[5] [5]

Expanding graphs pp

Chung, F.: The laplacian of a hypergraph. Expanding graphs pp. 21–36 (1993)

work page 1993

[6] [6]

Do, M.T., Yoon, S.e., Hooi, B., Shin, K.: Structural patterns and generative mod- els of real-world hypergraphs. p. 176–186. KDD ’20, Association for Computing Machinery, New York, NY, USA (2020)

work page 2020

[7] [7]

Jin, S.: Interpretable network representations (2022)

work page 2022

[8] [8]

In: 2022 IEEE International Conference on Knowledge Graph (ICKG)

Jin, S., Ma, R., Li, J., Eftekharnejad, S., Zafarani, R.: A spectral measure for net- work robustness: Assessment, design, and evolution. In: 2022 IEEE International Conference on Knowledge Graph (ICKG). pp. 97–104. IEEE (2022)

work page 2022