Pith. sign in

REVIEW 4 major objections 4 minor 61 references

HOPPER: Learnable Hop Extraction for Linearized Graph Sequence Models

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

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

Pith's one-line read HOPPER makes the hop-sequence extractor of linearized graph sequence models learnable, recovers fixed propagators as special cases, and reports best results on two long-range ECHO-SYNTH tasks.

desk verdict A genuinely new learnable hop-extraction method with clean, checkable theory, but the central explanation for its empirical gains is not established for the architecture that was actually evaluated. read the letter →

arxiv 2608.09031 v1 pith:ZV3KSQBK submitted 2026-08-10 cs.LG

Isuru Herath , Arin Gopakumar , Sharan Sahu This is my paper · ORCID
classification cs.LG
keywords learnablehopextractionlinearizedgraphsequencemodelslong-rangelearningover-squashingChebyshevpolynomialpropagationstate-spacepermutationequivariancefilters
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

Linearized Graph Sequence Models (LGSMs) decouple how far information travels on a graph from how many nonlinear layers process it, but they rely on fixed propagation rules such as adjacency powers or non-backtracking walks. HOPPER's central claim is that making the hop-sequence extractor learnable—conditioned on the graph, the node features, and the hop index—improves long-range propagation without losing permutation equivariance. The paper shows that the learnable extractor contains standard LGSM extractors as exact special cases, and that inside the class of uniformly stable degree-$r$ polynomial propagators the Chebyshev polynomial maximizes first-arrival sensitivity by a factor of $2^{r-1}$, mitigating over-squashing. Empirically, HOPPER reports the best results on eccentricity and single-source shortest-path prediction in ECHO-SYNTH while remaining competitive on diameter, and the memory-window size matters on the LRIM-16 benchmark.

What carries the argument

The carrier of the argument is the linear structural-state recurrence $$$U^{{(k)}}$ = \sum_{j=1}^{M}\left(\$alpha_A^{{(k)}}$[j]A + \$alpha_D^{{(k)}}$[j]D + \$alpha_I^{{(k)}}$[j]I\right)$U^{{(k-j)}}$,$$ with $U^{(0)} = H$ and $U^{(i)} = 0$ for $i < 0$. The coefficients are produced by a hypernetwork from a permutation-invariant graph summary and a hop embedding, so the propagation rule varies across graphs, node features, and hop depth; the memory window $M$ controls how many previous structural states contribute. This recurrence does three jobs: it keeps the extracted states linear in $H$ (Theorem 4.2.1), it contains adjacency-power, non-backtracking, and Chebyshev propagation as exact special cases (Theorem 4.3.1), and it sets up the degree-$r$ polynomial class $\mathcal{P}_r$ in which Chebyshev's extremal leading coefficient yields the first-arrival sensitivity bound (Theorem 4.4.1). A shared state-space sequence model then processes each node's hop trajectory independently, which preserves permutation equivariance and keeps propagation depth separate from nonlinear processing depth.

What would settle it

Run the exact unnormalized recurrence and the normalized experimental recurrence side by side on a small graph using the coefficient settings from Theorem 4.3.1, and compare the resulting sequences with $B^{(k)}H$ and $T_k(A_{\mathrm{sym}})H$; any mismatch at hop $k$ means the deployed model is not covered by the containment and optimality proofs. A second check: clamp HOPPER's coefficients to the Chebyshev values and compare with free training on ECHO-SYNTH; if free training is not at least as good, the reported gains are not evidence of attaining the theorem's optimum.

Watch

Extended reading notes

Core claim

On its own terms, the paper claims that the hop sequences fed to a linearized graph sequence model should not be fixed in advance. HOPPER replaces the fixed extractor with a hypernetwork-conditioned linear structural-state recurrence: an MLP reads a permutation-invariant summary of the graph together with a hop embedding and emits coefficients for a finite-memory combination of adjacency, degree, and identity operators, with a feature-attention term applied only to the output states. Conditional on those coefficients, each state is a finite-hop polynomial in $A$ and $D$, so locality is preserved. The paper proves the family recovers adjacency-power and non-backtracking propagation exactly and that, among uniformly stable degree-$r$ polynomial propagators, the Chebyshev polynomial attains the maximum first-arrival sensitivity $2^{r-1}|[G^r]_{uv}|$, compared with $|[G^r]_{uv}|$ for power propagation. It concludes that HOPPER can transmit long-range information exponentially more strongly than fixed adjacency powers while staying non-expansive, preserve nonstationary spectral content across the sequence, and still report best ECC and SSSP numbers with a competitive diameter number on ECHO-SYNTH.

Load-bearing premise

The experiments use a numerically stabilized version of the propagation recurrence, while the theorems that pin down the method's beneficial Chebyshev behavior are proved for the exact version; if the stabilized version cannot realize the same propagation, the paper's theoretical explanation of the empirical gains does not apply.

Editorial extensions

If this is right

  • Users of an LGSM can keep the separation of propagation depth from processing depth while letting propagation adapt to the graph and task; the standard adjacency-power and non-backtracking sequences remain available as fixed coefficient choices.
  • On graphs with spectrum in $[-1,1]$, the Chebyshev-extractible sequence delivers first-arrival sensitivity up to $2^{r-1}$ times that of power propagation at distance $r$ without increasing the spectral norm, so over-squashing is mitigated without rewiring or added nonlinear depth.
  • The sequence-level spectral-preservation result means the downstream sequence model receives a stable amount of nonstationary spectral information at every depth, instead of watching it decay geometrically through repeated adjacency powers.
  • The reported ECHO-SYNTH and LRIM-16 results imply that learnable extraction is at least competitive with hand-designed extractors, and that the memory window $M$ is a meaningful tuning knob for tasks with different long-range demands.

Reading between the lines

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

  • If the normalized recurrence used in the experiments inherits the containment and optimality theorems, the learnable family can smoothly interpolate between power, non-backtracking, and Chebyshev behavior per hop, giving a direct testable knob for over-squashing.
  • The theory suggests a non-learnable Chebyshev extractor might capture much of HOPPER's gain on long-range structural tasks; comparing free HOPPER with coefficients clamped to the Chebyshev setting would isolate what learnability itself adds.
  • The permutation-invariant graph summary and hop-conditioned coefficients could extend to directed or heterophilic graphs, where symmetric normalized propagation is a poor fit; the paper does not test this.
  • A practical diagnostic is to inspect the learned coefficients on sparse long-range benchmarks: if they do not approach Chebyshev-like values, the empirical gains likely come from the feature-attention correction or the state-space processor rather than from the proved sensitivity bound.
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.

Referee Report

4 major / 4 minor

Summary. HOPPER proposes a learnable hop-sequence extractor for Linearized Graph Sequence Models (LGSMs). Instead of a fixed propagation rule, a hypernetwork conditions hop-dependent coefficients on a permutation-invariant graph summary, and a finite-memory linear recurrence produces structural states that are processed by a Mamba2-based SSM. The paper claims permutation equivariance, polynomial locality, containment of adjacency-power and non-backtracking LGSM extractors, an optimal Chebyshev first-arrival sensitivity result, and preservation of nonstationary spectral information. Experiments on ECHO-SYNTH report best or competitive results on eccentricity, SSSP, and diameter, and a memory-window sweep on LRIM-16 is reported.

Significance. If the central claims held as stated, this would be a useful contribution: it generalizes fixed LGSM extractors to an adaptive family while preserving equivariance and locality, and the Chebyshev sensitivity analysis provides a clean theoretical mechanism for mitigating over-squashing. The appendix proofs are a genuine strength: the permutation-equivariance argument, polynomial-locality proof, containment construction, Chebyshev extremal lemma, and spectral-average calculation are carefully presented and check out. The empirical results, however, are only moderately supportive: the ECC win has high variance, the LRIM window comparison is statistically inconclusive, and no LRIM baseline is provided. Most importantly, the theoretical optimality statements are proved for the exact recurrence with unnormalized operators or a symmetric shift, while all experiments use the normalized recurrence; the connection between the theory and the reported gains is not established for the implemented model.

major comments (4)
  1. [Appendix B and §4.3] The theoretical containment results are proved for the exact recurrence in Eq. (15) with unnormalized A and D, or for the generalized recurrence with a symmetric shift S, but Appendix B states that all experiments use the normalized recurrence Eq. (22) with A_rw = D^{-1}A and I-D^{-1}. The similarity argument after Theorem 4.3.1 conjugates only the adjacency channel: D^{1/2} A_rw D^{-1/2} = A_sym. The degree channel transforms as D^{1/2}(I-D^{-1})D^{-1/2} = I-D^{-1}, which is a non-scalar diagonal operator. Consequently, the non-backtracking coefficient assignment of Theorem 4.3.1(ii) does not produce B^(k) in the evaluated recurrence, and Chebyshev propagation is realized only if the learned coefficients satisfy alpha_D[j]=0 for every hop. The paper provides no evidence about the learned alpha_D values, so the claimed containment and the optimal-sensitivity explanation are not established for the model behind Tables 1-2. This does not invalidate the empirical results, but it removes the theoretical support for why the learnable extractor helps, which is central to the paper's framing.
  2. [§4.4 and Definition 1] Theorem 4.4.1 and Corollary 4.4.1 are stated for a symmetric graph operator with spectrum in [-1,1]. The experimental recurrence uses the non-symmetric random-walk operator A_rw. Similarity to A_sym is not by itself sufficient: the extremal class P_r is defined on [-1,1] for polynomials of a symmetric operator, and the proof uses the spectral theorem for that symmetric operator. Even in the special case alpha_D=alpha_I=0, the paper does not prove that the normalized recurrence exactly realizes T_r(A_sym) or that the stated sensitivity bound holds for the non-symmetric T_r(A_rw) under the same stability constraint. An analogous extremal statement for the normalized family, or an explicit weakening of the theoretical claims, is needed before Theorem 4.4.1 can be cited as the mechanism behind the empirical gains.
  3. [Table 1 and §5] The headline empirical claim that HOPPER 'achieves the best performance on eccentricity' rests on an ECC MSE of 6.571 with standard deviation 2.656 over only three seeds, compared with LGSM's 13.549±0.539. With this variance, the ECC improvement is not statistically robust, and the DIAM result (3.200±0.528 vs. LGSM 3.089±0.389) is within noise. The SSSP result (0.021±0.008 vs. 0.040±0.008) is more convincing, but the overall state-of-the-art claim is overstated. Additional seeds, confidence intervals, or a paired comparison would be needed to support the strength of the current wording.
  4. [Table 2 and Appendix B] The LRIM experiment does not establish that learnable extraction is beneficial. Table 2 reports log10(MSE) values for M=2,4,8,16, but Appendix B states 'We evaluate M in {2,4,8}', so the table and text are contradictory. Moreover, M=8 (-3.505±0.063) and M=16 (-3.502±0.081) differ by less than one standard deviation, and each value is the mean of only two seeds. There is no comparison against LGSM or any fixed-extractor baseline on LRIM, so the claim that varying the structural memory window 'can optimize accuracy' is not supported as an advantage of HOPPER over existing extractors.
minor comments (4)
  1. [§3.2 and Appendix B] The number K of learnable seed queries is introduced as a free parameter in Eq. (12) but its value is never reported in Appendix B or in the experimental setup. Please state the value used and whether it was swept.
  2. [§4.4] The discussion following Theorem 4.4.2 says the Cesàro average of Dirichlet energy converges to 1/2 E(H), but the theorem's conclusion is 1/2 ||H_perp||_F^2, which equals 1/2 E(H) only when the stationary component vanishes. Please correct this statement.
  3. [Throughout] The term 'Dirchlet energy' is misspelled and should be 'Dirichlet energy' in the two places it appears.
  4. [Appendix B] The sentence 'No clipping occurs in any of our reported experiments, so the characterization of Theorem C.2.1 applies throughout' is misleading, because Theorem C.2.1 characterizes the exact recurrence while the reported experiments use the normalized recurrence of Eq. (22). The claim should be restricted to the polynomial-structure and locality parts that hold for both recurrences.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the theoretical claims are proved from the recurrence definition and standard polynomial/spectral facts, and the empirical claims rest on external benchmarks.

full rationale

Walking the claimed derivation chain: (i) the containment claims (Theorem 4.3.1 / C.2.2) are algebraic special-case statements obtained by substituting specific hypernetwork coefficient values into the recurrence; they do not feed any fitted output back into the claim and are not predictions. (ii) The optimal first-arrival sensitivity result (Theorem 4.4.1 / C.3.1) follows from the classical Chebyshev leading-coefficient extremum (Lemma C.3.1) combined with graph-distance locality, so it is an independent mathematical fact rather than a consequence of HOPPER's learned values. (iii) The spectral-preservation result (Theorem 4.4.2 / C.4.1) follows from eigendecomposition and the Cesàro average of cos^2(kθ), again independent of the learned coefficients. (iv) The ECHO-SYNTH and LRIM-16 numbers are external benchmark measurements; the M-sweep in Table 2 is an honest hyperparameter report, not a quantity predicted from the model's own fitted parameters. There is no load-bearing self-citation: the cited LGSM and benchmark works have author lists disjoint from the present paper. The only related concern is a theory-experiment gap, namely that all Section 5 experiments use the normalized recurrence in Eq. (22) while the containment and optimality theorems are stated for the exact recurrence in Eq. (15) or a generalized recurrence with an additional shift S; closing that gap would need an argument that the normalized path realizes the same propagators, but this is a correctness question, not circularity, because no prediction is equivalent by construction to its inputs.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

No new physical or mathematical entities are postulated. The structural memory window is a hyperparameter, the hop embedding and seed queries are ordinary learned parameters, and the theoretical claims rely on standard spectral and approximation-theoretic background. The main assumptions are the restricted eigenvalue condition in Theorem 4.4.2 and comparability of external baselines, both flagged above.

free parameters (5)
  • M (memory window size) = 8, chosen as best on LRIM validation; margin over M=16 is within one standard deviation
    M controls the order of the structural recurrence in Eq. 15. The paper reports M=8 as best on LRIM-16 but the difference from M=16 is within reported error bars.
  • L (sequence length) = 40 for ECHO-SYNTH, 32 for LRIM
    Chosen by hand. Appendix B says all experiments use L=32 and then states L=40 for ECHO-SYNTH, an internal inconsistency.
  • N_blk (number of SSM blocks) = 8
    Architecture hyperparameter fixed for LRIM; not swept and not reported for ECHO.
  • d (hidden dimension) = 64
    Architecture hyperparameter fixed for LRIM; not reported for ECHO.
  • K (number of seed queries) = unspecified
    Q_s is defined in R^{K x d} with K learnable seed queries, but the paper never gives a value for K; required to reproduce the graph summary.
assumptions (5)
  • standard math Chebyshev polynomial identities: T_k(cos theta) = cos(k theta), leading coefficient 2^(k-1), sup norm at most 1 on [-1,1].
    Used in Theorems 4.4.1 and 4.4.2 to establish optimal first-arrival sensitivity and spectral averages. Proved in Lemma D.0.1 for completeness.
  • standard math Spectral theorem for symmetric matrices.
    Used throughout Section 4 to decompose A_sym, bound operator norms, and compute spectral averages over information depth.
  • domain assumption The normalized adjacency matrix A_sym = D^{-1/2} A D^{-1/2} has spectrum in [-1,1].
    Used in Theorems 4.3.1(iii) and 4.4.1; standard for normalized adjacency without isolated vertices.
  • domain assumption All non-unit eigenvalues of A_sym satisfy |lambda| < 1 in Theorem 4.4.2.
    This excludes graphs with eigenvalue -1 (e.g., bipartite components), so the no-over-smoothing claim does not cover all graphs. The assumption is stated but its restrictiveness is not discussed.
  • domain assumption The published ECHO-SYNTH and LRIM baseline numbers are comparable under the same evaluation protocol.
    The paper adopts published baseline results rather than re-running them, and only reports its own model's seeds for some configurations.

how reviews work

0 comments
Cite this review

Pith. "Pith review of HOPPER: Learnable Hop Extraction for Linearized Graph Sequence Models." pith.science (2026). https://pith.science/paper/ZV3KSQBK

@misc{pith2026260809031,
  author       = {Pith},
  title        = {Pith review of: HOPPER: Learnable Hop Extraction for Linearized Graph Sequence Models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZV3KSQBK}},
  note         = {Machine review of arXiv:2608.09031}
}
read the original abstract

Graph neural networks typically propagate information through repeated message-passing layers, coupling the distance over which information travels with the number of nonlinear transformations applied. This coupling can make deep architectures difficult to optimize and can lead to over-smoothing, over-squashing, and the loss of long-range information. Linearized Graph Sequence Models (LGSMs) address this issue by separating information depth from processing depth and treating the successive propagation states of each node as a sequence. However, existing LGSMs construct these sequences using fixed graph operators, limiting their ability to adapt propagation to the input graph, node features, and downstream task. We introduce HOPPER, an end-to-end learnable extension of LGSM that learns how hop sequences should be extracted before they are processed by a modern state-space model. Our framework supports feature-conditioned, structure-aware, graph- and hop-adaptive propagation mechanisms while preserving permutation equivariance. Standard adjacency-based and non-backtracking LGSM sequences arise as special cases of our proposed extractor family. We show that HOPPER is state-of-the-art or competitive across the ECHO-Synth benchmark, and that varying the maximum neighborhood size of message backtracking cancellation (i.e. structural memory window) can optimize accuracy on the LRIM physics-based long-range dependency benchmark. These results demonstrate that learnable sequence extraction provides a flexible and effective approach to long-range graph representation learning.

Figures

Figures reproduced from arXiv: 2608.09031 by the authors.

Figure 1
Figure 1. Standard LGSMs extract hop sequences using a fixed propagation rule shared across graphs and depths. HOPPER instead learns a graph and hop-adaptive sequence extractor through a permutation-invariant graph summary, hop-conditioned coefficients, a finite-memory linear structural recurrence, and an output-only feature-attention correction. 3.2 Hypernetwork-Conditioned Structural-State Recurrence The key contributions o… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

61 extracted references · 51 canonical work pages

  1. [1]

    MixHop: Higher-order graph convolutional architectures via sparsified neighborhood mixing

    Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. MixHop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. InProceedings of the 36th International Conference on Machine Learning, volume 97 ofProceedings of Machine Learning Research, p...

    work page 2019

  2. [2]

    On the bottleneck of graph neural networks and its practical implications

    Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. InInternational Conference on Learning Representations, 2021. URL https: //openreview.net/forum?id=i80OPhOCVH2. 1, 14

    work page 2021

  3. [3]

    On vanishing gradients, over- smoothing, and over-squashing in gnns: Bridging recurrent and graph learning.Advances in Neural Information Processing Systems, 38:74356–74393, 2026

    Álvaro Arroyo, Alessio Gravina, Benjamin Gutteridge, Federico Barbero, Claudio Gallicchio, Xiaowen Dong, Michael Bronstein, and Pierre Vandergheynst. On vanishing gradients, over- smoothing, and over-squashing in gnns: Bridging recurrent and graph learning.Advances in Neural Information Processing Systems, 38:74356–74393, 2026. 8

    work page 2026

  4. [4]

    Graph mamba: Towards learning on graphs with state space models.arXiv preprint arXiv:2402.08678, 2024

    Ali Behrouz and Farnoosh Hashemi. Graph mamba: Towards learning on graphs with state space models.arXiv preprint arXiv:2402.08678, 2024. URL https://arxiv.org/abs/ 2402.08678. 1, 2, 14

    arXiv 2024

  5. [5]

    Best of both worlds: Advantages of hybrid graph sequence models

    Ali Behrouz, Ali Parviz, Mahdi Karami, Clayton Sanford, Bryan Perozzi, and Vahab Mirrokni. Best of both worlds: Advantages of hybrid graph sequence models. InProceedings of the 42nd International Conference on Machine Learning, volume 267 ofProceedings of Machine Learning Research, pp. 3533–3561. PMLR, 2025. URLhttps://proceedings.mlr.press/ v267/behrouz2...

    work page 2025

  6. [6]

    Non-backtracking spectrum of random graphs: Community detection and non-regular ramanujan graphs

    Charles Bordenave, Marc Lelarge, and Laurent Massoulié. Non-backtracking spectrum of random graphs: Community detection and non-regular ramanujan graphs. In2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 1347–1357. IEEE, 2015. doi: 10.1109/FOCS.2015.86. 14

    work page doi:10.1109/focs.2015.86 2015

  7. [7]

    GNN-FiLM: Graph neural networks with feature-wise linear modulation

    Marc Brockschmidt. GNN-FiLM: Graph neural networks with feature-wise linear modulation. InProceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 1144–1152. PMLR, 2020. URL https: //proceedings.mlr.press/v119/brockschmidt20a.html. 14

    work page 2020

  8. [8]

    Message-passing state-space models: Improving graph learning with modern sequence modeling.arXiv preprint arXiv:2505.18728, 2025

    Andrea Ceni, Alessio Gravina, Claudio Gallicchio, Davide Bacciu, Carola-Bibiane Schönlieb, and Moshe Eliasof. Message-passing state-space models: Improving graph learning with modern sequence modeling.arXiv preprint arXiv:2505.18728, 2025. URL https://arxiv. org/abs/2505.18728. 14

    arXiv 2025

Show all 61 references
  1. [9]

    Simple and deep graph convolutional networks

    Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. InProceedings of the 37th International Conference on Machine Learning, volume 119 ofProceedings of Machine Learning Research, pp. 1725–1735. PMLR,

  2. [10]

    Adaptive universal generalized PageRank graph neural network

    Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized PageRank graph neural network. InInternational Conference on Learning Representations,

  3. [11]

    Chung.Spectral Graph Theory

    F.R.K. Chung.Spectral Graph Theory. Conference Board of Mathematical Sciences. American Mathematical Society, 1997. ISBN 9780821803158. URL https://books.google.com/ books?id=4IK8DgAAQBAJ. 8

    1997

  4. [12]

    Transformers are SSMs: Generalized models and efficient algorithms through structured state space duality

    Tri Dao and Albert Gu. Transformers are SSMs: Generalized models and efficient algorithms through structured state space duality. InProceedings of the 41st International Conference on Machine Learning, volume 235 ofProceedings of Machine Learning Research, pp. 10041– 10071. PM...

    2024

  5. [13]

    Convolutional neural networks on graphs with fast localized spectral filtering

    Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. InAdvances in Neural Information Processing Systems, volume 29, 2016. URL https://proceedings.neurips.cc/paper/2016/hash/ 04df4d434d481...

    2016

  6. [14]

    Konstantin Rusch, Michael M

    Francesco Di Giovanni, T. Konstantin Rusch, Michael M. Bronstein, Andreea Deac, Marc Lackenby, Siddhartha Mishra, and Petar Veliˇckovi´c. How does over-squashing affect the power of GNNs?Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL https://openreview.ne...

    2024

  7. [15]

    Long range graph benchmark

    Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. InAd- vances in Neural Information Processing Systems, volume 35, pp. 22326–22340,

  8. [16]

    Bronstein, and Federico Monti

    Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Benjamin Paul Chamberlain, Michael M. Bronstein, and Federico Monti. SIGN: Scalable inception graph neural networks. InICML 2020 Workshop on Graph Representation Learning and Beyond, 2020. URL https://arxiv. org/abs/2004.11198. 14

    2020 arXiv

  9. [17]

    Predict then propagate: Graph neural networks meet personalized PageRank

    Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized PageRank. InInternational Conference on Learning Representations, 2019. URLhttps://openreview.net/forum?id=H1gL-2A9Ym. 14

    2019

  10. [18]

    Schoenholz, Patrick F

    Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. InProceedings of the 34th International Conference on Machine Learning, volume 70 ofProceedings of Machine Learning Research, pp. 1263–1272. ...

    2017

  11. [19]

    Mamba: Linear-time sequence modeling with selective state spaces

    Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. InFirst Conference on Language Modeling, 2024. URL https://openreview.net/forum? id=tEYskw1VY2. 1, 14

    2024

  12. [20]

    Efficiently modeling long sequences with structured state spaces.arXiv preprint arXiv:2111.00396, 2021

    Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces.arXiv preprint arXiv:2111.00396, 2021. URL https://arxiv.org/abs/2111. 00396. 14

    2021 arXiv

  13. [21]

    Bronstein, and Francesco Di Giovanni

    Benjamin Gutteridge, Xiaowen Dong, Michael M. Bronstein, and Francesco Di Giovanni. DRew: Dynamically rewired message passing with delay. InProceedings of the 40th Inter- national Conference on Machine Learning, volume 202 ofProceedings of Machine Learning Research, pp. 12252–...

    2023

  14. [22]

    Dai, and Quoc V

    David Ha, Andrew M. Dai, and Quoc V . Le. Hypernetworks. InInternational Conference on Learning Representations, 2017. URL https://openreview.net/forum?id=rkpACe1lx. 2, 14

    2017

  15. [23]

    Hamilton, Rex Ying, and Jure Leskovec

    William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. InAdvances in Neural Information Processing Sys- tems, volume 30, 2017. URL https://proceedings.neurips.cc/paper/2017/hash/ 5dd9db5e033da9c6fb5ba83c7a7ebea9-Abstract.html. 14

    2017

  16. [24]

    Zeta functions of finite graphs and representations of p-adic groups

    Ki-ichiro Hashimoto. Zeta functions of finite graphs and representations of p-adic groups. In Automorphic Forms and Geometry of Arithmetic Varieties, volume 15 ofAdvanced Studies in Pure Mathematics, pp. 211–280. Kinokuniya and Academic Press, 1989. 14

    1989

  17. [25]

    BernNet: Learning arbitrary graph spectral filters via bernstein approximation

    Mingguo He, Zhewei Wei, Zengfeng Huang, and Hongteng Xu. BernNet: Learning arbitrary graph spectral filters via bernstein approximation. InAdvances in Neural Information Processing Systems, volume 34, 2021. URL https://proceedings.neurips.cc/paper/2021/hash/ 76f1cfd7754a6e4fc3...

    2021

  18. [26]

    What can we learn from state space models for machine learning on graphs?arXiv preprint arXiv:2406.05815, 2024

    Yinan Huang, Siqi Miao, and Pan Li. What can we learn from state space models for machine learning on graphs?arXiv preprint arXiv:2406.05815, 2024. URL https://arxiv.org/ abs/2406.05815. 14

    2024 arXiv

  19. [27]

    Banerjee, and Guido Montúfar

    Kedar Karhadkar, Pradeep Kr. Banerjee, and Guido Montúfar. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. InInternational Conference on Learning Representations, 2023. URLhttps://openreview.net/forum?id=3YjQfCLdrzz. 2, 14

    2023

  20. [28]

    Revisiting random walks for learning on graphs.arXiv preprint arXiv:2407.01214, 2024

    Jinwoo Kim, Olga Zaghen, Ayhan Suleymanzade, Youngmin Ryou, and Seunghoon Hong. Revisiting random walks for learning on graphs.arXiv preprint arXiv:2407.01214, 2024. URL https://arxiv.org/abs/2407.01214. 2, 14 11 HOPPER: Learnable Hop Extraction for Linearized Graph Sequence Models

    2024 arXiv

  21. [29]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. InInternational Conference on Learning Representations, 2017. URL https: //openreview.net/forum?id=SJU4ayYgl. 1, 2, 14

    2017

  22. [30]

    Diffusion im- proves graph learning

    Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion im- proves graph learning. InAdvances in Neural Information Processing Systems, volume 32, 2019. URL https://proceedings.neurips.cc/paper/2019/hash/ 23c894276a2c5a16470e6a31f4618d73-Abstract.html. 2, 14

    2019

  23. [31]

    Hamilton, Vincent Létourneau, and Prudencio Tossou

    Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. InAdvances in Neural Infor- mation Processing Systems, volume 34, 2021. URL https://proceedings.neurips.cc/ paper/2021/hash/4b...

    2021

  24. [32]

    Spectral redemption in clustering sparse networks.Proceedings of the National Academy of Sciences, 110(52):20935–20940, 2013

    Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zde- borová, and Pan Zhang. Spectral redemption in clustering sparse networks.Proceedings of the National Academy of Sciences, 110(52):20935–20940, 2013. doi: 10.1073/pnas.1312486110. 14

    2013 doi

  25. [33]

    Kosiorek, Seungjin Choi, and Yee Whye Teh

    Juho Lee, Yoonho Lee, Jungtaek Kim, Adam R. Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention-based permutation-invariant neural networks. InProceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Ma...

    2019

  26. [34]

    Deeper insights into graph convolutional networks for semi-supervised learning

    Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. InProceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018. URL https://ojs.aaai.org/index.php/AAAI/article/view/11604. 14

    2018

  27. [35]

    Towards deeper graph neural networks

    Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 338–348, 2020. doi: 10.1145/3394486.3403076. 14

    2020

  28. [36]

    LRIM: a physics-based benchmark for provably evaluating long-range capabilities in graph learning

    Joël Mathys, Henrik Christiansen, Federico Errica, Takashi Maruyama, and Francesco Alesiani. LRIM: a physics-based benchmark for provably evaluating long-range capabilities in graph learning. InThe Fourteenth International Conference on Learning Representations, 2026. URL http...

    2026

  29. [37]

    From message-passing to linearized graph sequence models.arXiv preprint arXiv:2605.12358, 2026

    Joël Mathys, Basil Rohner, Saku Peltonen, and Roger Wattenhofer. From message-passing to linearized graph sequence models.arXiv preprint arXiv:2605.12358, 2026. URL https: //arxiv.org/abs/2605.12358. 1, 3, 9, 14

    2026 arXiv

  30. [38]

    Can you hear me now? a benchmark for long-range graph propagation

    Luca Miglior, Matteo Tolloso, Alessio Gravina, and Davide Bacciu. Can you hear me now? a benchmark for long-range graph propagation. InInternational Conference on Learning Representations, 2026. URLhttps://openreview.net/forum?id=DgkWFPZMPp. 8, 15

    2026

  31. [39]

    Graph neural networks exponentially lose expressive power for node classification

    Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. InInternational Conference on Learning Representations, 2020. URL https://openreview.net/forum?id=S1ldO2EFPr. 14

    2020

  32. [40]

    Smith, Albert Gu, Anushan Fernando, Ça˘glar Gülçehre, Razvan Pascanu, and Soham De

    Antonio Orvieto, Samuel L. Smith, Albert Gu, Anushan Fernando, Ça˘glar Gülçehre, Razvan Pascanu, and Soham De. Resurrecting recurrent neural networks for long sequences. InProceed- ings of the 40th International Conference on Machine Learning, volume 202 ofProceedings of Machi...

    2023

  33. [41]

    Recipe for a general, powerful, scalable graph trans- former

    Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph trans- former. InAdvances in Neural Information Processing Systems, volume 35, pp. 14501– 14515, 2022. URL https://proceedings...

    2022

  34. [42]

    DropEdge: Towards deep graph convolutional networks on node classification

    Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. DropEdge: Towards deep graph convolutional networks on node classification. InInternational Conference on Learning Representations, 2020. URLhttps://openreview.net/forum?id=Hkx1qkrKPr. 2, 14

    2020

  35. [43]

    A survey on oversmoothing in graph neural networks.arXiv preprint arXiv:2303.10993, 2023

    T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks.arXiv preprint arXiv:2303.10993, 2023. 8 12 HOPPER: Learnable Hop Extraction for Linearized Graph Sequence Models

    2023 arXiv

  36. [44]

    Sutherland, and Ali Kemal Sinop

    Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. InProceedings of the 40th Interna- tional Conference on Machine Learning, volume 202 ofProceedings of Machine Learning Research, pp. 3161...

    2023

  37. [45]

    Walking out of the weisfeiler leman hierarchy: Graph learning beyond message passing.Transactions on Machine Learning Research, 2023

    Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Walking out of the weisfeiler leman hierarchy: Graph learning beyond message passing.Transactions on Machine Learning Research, 2023. URLhttps://openreview.net/forum?id=vgXnEyeWVY. 2, 14

    2023

  38. [46]

    Bronstein

    Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. InInternational Conference on Learning Representations, 2022. URL https://openreview. net/forum?id=7Umj...

    2022

  39. [47]

    Gomez, Łukasz Kaiser, and Illia Polosukhin

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. InAdvances in Neural Information Processing Systems, volume 30, pp. 5998–6008, 2017. URL https: //proceedings.neurips.cc/pap...

    2017

  40. [48]

    Graph attention networks

    Petar Veliˇckovi´c, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. InInternational Conference on Learning Representations,

  41. [49]

    Graph-mamba: Towards long-range graph sequence modeling with selective state spaces.arXiv preprint arXiv:2402.00789, 2024

    Chloe Wang, Oleksii Tsepa, Jun Ma, and Bo Wang. Graph-mamba: Towards long-range graph sequence modeling with selective state spaces.arXiv preprint arXiv:2402.00789, 2024. URL https://arxiv.org/abs/2402.00789. 1, 2, 14

    2024 arXiv

  42. [50]

    Representation learning on graphs with jumping knowledge networks

    Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. InProceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine ...

    2018

  43. [51]

    How powerful are graph neural networks? InInternational Conference on Learning Representations, 2019

    Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? InInternational Conference on Learning Representations, 2019. URL https: //openreview.net/forum?id=ryGs6iA5Km. 14

    2019

  44. [52]

    Do transformers really perform badly for graph repre- sentation? InAdvances in Neural Information Processing Systems, volume 34, pp

    Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yan- ming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph repre- sentation? InAdvances in Neural Information Processing Systems, volume 34, pp. 28877–28888, 2021. URL https://procee...

    2021

  45. [53]

    Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabás Póczos, Ruslan Salakhutdi- nov, and Alexander J. Smola. Deep sets. InAdvances in Neural Information Processing Systems, volume 30, 2017. URL https://proceedings.neurips.cc/paper/2017/hash/ f22e4747da1aa27e363d86d40ff44...

    2017

  46. [54]

    Adaptive diffusion in graph neural networks

    Jialin Zhao, Yuxiao Dong, Ming Ding, Evgeny Kharlamov, and Jie Tang. Adaptive diffusion in graph neural networks. InAdvances in Neural Information Processing Systems, volume 34, pp. 23321–23333, 2021. URL https://proceedings.neurips.cc/paper/2021/hash/ c42af2fa7356818e03895937...

    2021

  47. [55]

    PairNorm: Tackling oversmoothing in GNNs

    Lingxiao Zhao and Leman Akoglu. PairNorm: Tackling oversmoothing in GNNs. InInter- national Conference on Learning Representations, 2020. URL https://openreview.net/ forum?id=rkecl1rtwB. 2, 14 13 HOPPER: Learnable Hop Extraction for Linearized Graph Sequence Models A Related W...

    2020

  48. [60]

    In particular,∥∂[T r(S)H]u/∂Hv∥2 = 2r−1|[Sr]uv|, whereas standard power propagation satisfies ∥∂[SrH]u/∂Hv∥2 =|[S r]uv|

    Then sup p∈Pr ∂[p(S)H]u ∂Hv 2 = 2r−1 |[Sr]uv|, and the supremum is attained by the Chebyshev propagatorp=T r. In particular,∥∂[T r(S)H]u/∂Hv∥2 = 2r−1|[Sr]uv|, whereas standard power propagation satisfies ∥∂[SrH]u/∂Hv∥2 =|[S r]uv|. Hence, whenever [Sr]uv ̸= 0, Chebyshev propaga...

  49. [61]

    This proves the result

    Averaging overkand applying Lemma C.4.1 to eachλ i ∈(−1,1)yields lim L→∞ 1 L L−1X k=0 ∥(I−Π)U (k)∥2 F = X λi̸=1 lim L→∞ 1 L L−1X k=0 Tk(λi)2 ! ∥ci∥2 2 = 1 2 X λi̸=1 ∥ci∥2 2 = 1 2 ∥H⊥∥2 F . This proves the result. 23 HOPPER: Learnable Hop Extraction for Linearized Graph Sequenc...

  50. [2018]

    URLhttps://openreview.net/forum?id=rJXMpikCZ. 2, 14

  51. [2020]

    URLhttps://proceedings.mlr.press/v119/chen20v.html. 14

  52. [2021]

    URLhttps://openreview.net/forum?id=n6jl7fLxrP. 2, 14

  53. [2022]

    URL https://proceedings.neurips.cc/paper_files/paper/2022/hash/ 8c3c666820ea055a77726d66fc7d447f-Abstract-Datasets_and_Benchmarks.html . 1, 14

    2022

Pith tools

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