Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Tasks
Authors: Ali Hariri
Alvaro Arroyo
Alessio Gravina
Moshe Eliasof
Carola-Bibiane Schönlieb
Davide Bacciu
Xiaowen Dong
Kamyar Azizzadenesheli
Pierre Vandergheynst
Venue: NeurIPS 2025 spotlight ()
Keywords: Spectral Graph Neural Networks
Primary area: deep_learning

Abstract: ChebNet, one of the earliest spectral GNNs, has largely been overshadowed by Message Passing Neural Networks (MPNNs), which gained popularity for their simplicity and effectiveness in capturing local graph structure. Despite their success, MPNNs are limited in their ability to capture long-range dependencies between nodes. This has led researchers to adapt MPNNs through *rewiring* or make use of *Graph Transformers*, which compromise the computational efficiency that characterized early spatial message passing architectures, and typically disregard the graph structure. Almost a decade after its original introduction, we revisit ChebNet to shed light on its ability to model distant node interactions. We find that out-of-box, ChebNet already shows competitive advantages relative to classical MPNNs and GTs on long-range benchmarks, while maintaining good scalability properties for high-order polynomials. However, we uncover that this polynomial expansion leads ChebNet to an unstable regime during training. To address this limitation, we cast ChebNet as a stable and non-dissipative dynamical system, which we coin Stable-ChebNet. Our Stable-ChebNet model allows for stable information propagation, and has controllable dynamics which do not require the use of eigendecompositions, positional encodings, or graph rewiring. Across several benchmarks, Stable-ChebNet achieves near  state-of-the-art performance.

Return of ChebNet: Understanding and Improving an Overlooked GNN on Long-Range Tasks
Ali Hariri!*
Álvaro Arroyo2
Alessio Gravina**
Moshe Eliasof
Carola-Bibiane Schönlieb"
Davide Bacciu"
Kamyar Azizzadenesheli
Xiaowen Dong*
Pierre Vandergheynst
Abstract
ChebNet, one of the earliest spectral GNNs, has largely been overshadowed by Message Passing Neural Networks (MPNNs), which gained popularity for their simplicity and effectiveness in capturing local graph structure. Despite their success, MPNNs are limited in their ability to capture long-range dependencies between nodes. This has led researchers to adapt MPNNs through rewiring make Graph Transformers, which compromises the computational efficiency that characterized early spatial cassage-passsigg architectures, and typically disregards the graph structure. Almost a decade after its original introduction, we revisit ChebNet shed light its ability model distant node interactions. We find that out-of-box, ChebNet already shows competitive advantages relative to classical MPNNs and GTs on long-range benchmarks, while maintaining good scalability properties for high-order polynomials. However, we uncover that this polynomial expansion leads ChebNet an unstable regime during training. To address this limitation, we cast ChebNet as a stable and non-dissipative dynamical system, which we coin Stable- -hheNNet. Our Stable- Stable-ChebNet model allows for stable information propagation, and has controllable dynamics which do not require the use of eigendecompositions, positional encodings, or graph rewiring. Across several benchmarks, Stable-Cheblie' achieves near state-of-the performance.
Introduction
Graph Neural Networks (GNNs) [81, 43, 74, 67, 14, 25, 44] have emerged as prevalent framework for handling data defined on graphs. Graph convolutional networks have their roots in spectral approaches that extend convolutional filters non-Euclidean domains. The first practical instantiation of GNN proposed by [14], which leveraged the eigenbasis of the graph Laplacian to perform spectral filtering, as an attempt to generalize image convolutions to non-euclidean structures. However, each layer. Defferrard et al. [25] addressed this inefficiency by approximating spectral filters with truncated Chebyshev polynomials, giving rise to ChebNet, the first tractable and localized spectral GNN. By parameterizing filters K Korreer polynomials of the Laplacian, ChebNet could aggregate information from K K-hop neighborhoods without repeated eigendecompossiiions thereby enabling scalable spectral convolution large graphs.
this formulation required costly degemmdccoposstions
École Polytechnique Fédérale de Lausanne (EPFL)
2 University of Oxford
University of Pisa
Uniieersity of Cambridge
'NVIDIA Research
'Equal contribution
Coorrsponddncce to: Ali Hariri adli.hariridepf]
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In 2017, Kipf and Welling distilled ChebNet into simpler, first-order approximation now known as the Graph Convolutional Network (GCN) by (i) restricting the polynomial order to one and (ii) tying filter coefficients across hops [57]. This yielded an architecture that was both lightweight and effective: a GCN with few layers would achieve strong node-classification performance on standard homophilic benchmarks, and its O [E) complexity made it practical for large-scale graphs. GCN's efficiency and strong locality bias quickly made it the default baseline, and subsequent message-passingg neural networks (MPNNs) adopted similar paradigm of iterative neighborhood aggregation [41].
Despite their popularity, MPNNs exhibit pronounced shortcom- ings when made deeper and when capturing long-range de- pendencies [33]. Repeated neigh- borhood aggregations tend to cause representational collapse, where node features become in- distinguishable (often referred to as "oversmoothing") [15, 69], and information from distant nodes is "squashed" through nar- row bottlenecks. limiting the ability to model global con- text [1]- In recent years, re- searchers have proposed various strategies overcome these lim- itations. To mitigate oversmooth- ing, several models have drawn
ChebaNet Step 0
Steep
Step K
Tomperstuuee
Stable-ChobNet
Step O
Step
Step K
Juter hat
Figure Top: Vanilla ChebNet. Bottom: Net. While the original ChebNet's high-order Chebyshev filters induce unstable dynamics resulting in dissipative behavior, our Stable- ChebNet yields bounded propagation through layers.
on principles from physics [28, 12] to preserve feature diversity across layers. At the same time, efforts to capture long-range dependencies have led to graph-rewiring techniques [82, 49, 7] that add or reweight edges to shorten information pathways, as well as the emergence of graph transformers [30], which replace purely local aggregation with global self-attention mechanisms. Although these advances can alleviate depth-related pathologies, they often trade off numerous benefits that made MPNNs appealing: scalability. parameter efficiency, and to only process information along the graph's 's edges. In this context, ChebNet and other spectral GNNs are usually relegated to a footnote mentioned only as a predecessor to GCN, which is typically not revisited as competitive baseline.
In this work, we revisit ChebNet from first principles. We demonstrate that the original Cheb- Net (without any rewiring or attention mechanisms) already delivers ofate-of-the-arr performance or is close on long-range graph tasks while scaling gracefully to large graphs. By deriving and analyzing ChebNet's linearized dynamics, we prove that enlarging its receptive field introduces signal-propagation instabilities. To overcome this, we propose Stable-ChebNet. a minimal set of architectural modifications that restore stable propagation for arbitrarily large receptive fields, supported by both theoretical guarantees and empirical validation. To build intuition for our Stable- ChebNet framework, Figure illustrates how classical ChebNet filters (top) can exhibit unbounded dynamics, whereas our antisymmetric, forward-Eule discretization yields smooth, stable propagation (bottom). An intuitive heat-transfer analogy helps explain the difference: if we inject 'heat' at seed nodes, the high-order filters of vanilla ChebNet diffuse and dissipate this heat so that distant nodes cool rapidly. In contrast, the non-dissipative dynamics induced by the antisymmetric, Korward-Euler step in
preserve energy, keeping temperatures higher nodes many hops away.
Across suite of challenging long-range node- and graph-level benchmarks, pesssage-passing neural networks and graph transformers,
-hhebNet
matches or outperforms state-of-the-ee while retaining the ChebNet backbone. We hope this work will reignite interest in spectral GNNs as a scalable, theoretically grounded alternative for long-range graph modeling.
Contributions and Outline
In Section 3.1, we empirically demonstrate that vanilla ChebNet can achieve very strong perfor- mance on long-range benchmarks without incurring prohibitive computational cost.
In Section 3.2, we analyze ChebNet's 's pronallpoppgation dynamics, providing exact sensitivity analysis, and theoretically and empirically prove the emergence of instability for large filter order.
2

---

In Section 3.3, we introduce Taable-Chebeet which enforces layer-wist wise stability.
In Section 4, we empirically validate that Stable-Chebler consistently outperforms MPNNs, rewiring methods, and graph transformers across a number of tasks.
2 Background
2.1 Background on Spectral Graph Neural Networks
Spectral GNNs extend the notion of convolution to graphs by leveraging the eigen-decompositionn of the graph Laplacian. Given an undirected graph G = E) with normalized Laplacian
L I D 1D-1/4 1/12//D A/22/11/2 1/2, any graph signal X E I" can be filtered in the spectral domain via Y Ugo (A)U*X X, where L = UAU diagonalizes the Laplacian, A diag(A1..... A,) its eigenvalues, and ge is a learnable spectral response. Early methods directly parameterize (A)A). . but require expensive cigendecompositiin of the Laplacian, which can be computationally and memory intensive [14]. ChebNet alleviates the cost of an explicit eigendeconposition by approximating do using the recurrence relation for K-th order Chebyshev polynomial in L [25]. The latter defines go as go (A) = Σk O₂ Th (A), where (A) the k-th polynomial of Á with A Amar I, The spectral convolution can then be written without any eigendecomposition the truncated expansion:
Σ O x
(1)
where L
2L Aman
In enabling efficient, localized filtering in O(K time.
2.2 MPNNs and their Limitations
Message-Passe Passsng Neural Networks (MPNNs) define a general framework in which node features iteratively updated by exchanging "messages" along edges. At each layer every node aggregates information from its neighbors u E (w) and combines it with its own representation. This formulation unifies many graph models, including graph convolutional networks (GCNs) [57] and graph attention networks (GATs) [83]. While this local neighborhood aggregation captures structural information effectively, it has limited capacity to model long-range interactions within the graph. This is due to the phenomenon of over-squashing an information bottleneck that impedes effective information flow among distant nodes [1, 82, 27]. Numerous techniques have emerged to address this limitation such as graph rewiring [49, 7], Graph Transformers [71, 80, 79] in addition to some enhanced spatial methods that tackle over-squashing through combined local and global information [75, 40], or through non-dissipativity achieved by antisymmetric weight parameterization
[45, 46) or Hort-Hamilonnian systems [54].
Fjeech Time (pen) Eqnch Time: (woc.)
However, some of the aforementioned methods suffer from substantial overhead due denser graph shift operators or the use of all all-pairs interactions. Specifically, [79] and other graph transformers increase computational complexity through dense attention-maps; [40] relies on costly full eigendecomposition operations; and graph rewiring techniques heavily pre-process the graph topology, incurring O(z
Chetitie XLiR
Chebitie X...
10
Cheikiis Xedd, Med
time in the case of [49].For detailed discussion on the relevant literature, we point the reader to the Appendix A.
50-
Clatdic X-1li 36-2
Clatdics X-- 34-1
Cheiiiee X... M.d
Dilo
2.3 The Connection between ChebNet and GCN Although often interpreted disparate models, GCN [57] can be derived as a special case of ChebNet [25] by truncating the Cheby- shev expansion K and making additional simplifications such as approximating L improve numerical stability. These choices introduced a strong lo- cality bias, which aligned with widely used homophilic benchmarks and significantly reduced computational costs. Due to some of these strengths, GCN has become the de facto backbone for many modern GNNs, and has led to ChebNet being somewhat forgotten, under the assumption that it does not perform well and will not scale well in mid- to large-size graphs due to its spectral nature. For instance, until recently, ChebNet was almost never included in popular GNN benchmarks, such as [31], or those designed to evaluate long mange dependencies, such as those in the Long Range Graph Benchmark
M-K =
Fpuch Time (wxc.)
100
Cheiiice X-tth Mall
175
Clabbics 3-20 34-2
Cletdics 3--10 36-d
D AD 1/2 and adding self-loops to
Dileer
Figure 2: Epoch times for DRew and ChebNet for dif- ferent receptive fields on the peptides-func task. M is the number of layers, and K is the number of filters.
3

---

(LRGB) [33] and the numerous studies that leveraged this dataset to assess the effectiveness of graph rewiring, positional encodings, or Transformer- based architectures. ChebNet was similarly disregarded from large-scale graph evaluations such as the OGB benchmarks [55], presumably due to prevailing assumptions about its scalability.
3
Analyzing and Improving ChebNet from First Principles
3.1 The Effectiveness and Scalability of Vanilla ChebNet
In this subsection, we perform two high-level empirical tests to challenge the commonplace as- sumption that spectral GNNs inherently suffer from poor performance and limited scalability. We do so by firstly testing ChebNet [25] on a long-range test on the Ring Transfer dataset from [27], which has become de facto benchmark for ofte-of-theear methods seeking to model oong-distance dependencies on graphs. Furthermore, to test scalability, we compare epoch training times on the peptides-fume dataset from [33] with respect to state-of-the-an rewired MPNNs [49] based GCN backbone. We compare ChebNet with different numbers of filters K and layers Mcheb with an MMPNN-layer MPNN. To ensure fair comparison, ensure that Mches K MMPNN so that the two methods would have the same receptive field. The results are shown in Figures 2 and 3.
As seen from Figure 3. ChebNet is capable of performing long-range retrieval the ring trans- fer dataset for rings of up to 50 nodes, which is a substantial improvement over a regular GCN. While this finding aligns with intuition, we will formalize in the following sections, it may nonetheless surprise practitioners, since ChebNet is not typically included as a benchmark in long-range studies such that in [30]. On the other hand, as seen in Figure 2, ChebNet scales gracefully on standard tasks such as the peptides-fure dataset. When compared to DRew, state- of-the-art method that leverages both dynamic rewiring and delay to propagate information through GCN (or other MPNN) backbone, we observe that DRew's ' epoch times are almost up to two orders of magnitude larger than ChebNet's. We note further that this inefficiency is not unique to this particular baseline: Graph Transformers incur quadratic scaling in the number of nodes and, by effectively discarding the underlying graph structure, trade-off inductive bias for increased compute, while many rewiring approaches depend on cubic-time algorithms (e.g., Floyd- Warshall or eigendecompositions)) Together, these examples underscore how numerous contemporary techniques intended to overcome traditional message- passingg limitations actually erode computational benefits, whereas ChebNet, more natural spectral baseline that generalizes GCN, delivers both training speed and strong performance out-of-the-box.
Accurccy
GUN
0.
CbcciNos
0.4
0.2 Nodes
Figure 3: Test accuracy on RingTraan Transfer.
3.2 Signal Propagation Analysis of ChebNet
In this subsection, we conduct sensitivity analysis of ChebNet via the spectral norm of the Jacobian of node features, providing an exact characterization of ChebNet's information flow through different layers and between pairs of nodes, in the spirit of [3]. Specifically, we begin by analyzing the layer-wise Jacobian for Spectral GNNs that use polynomial filters. In this setting, we demonstrate that the layer-wise Jacobian becomes unstable as the polynomial order K increases. Lastly, we investigate the sensitivity of node pairs when using ChebNet. We provide the proofs for the statements in Appendix B.
Lemma 3.1 (Layer- Wise Jacobian for Spectral GNN). Consider a linear spectral GNN whose layer-wise update is performed through the following polynomial filter f(X) = Ex_ (x(L) X θ₂ where E Rxnd is the node feature matrix, TLL E Bax* is the k-th polynomial of the Laplacian L E Rax", and θ E IRdxd are learnable weight matrices. Then, the vectorized Jacobian J = ô (e)
K
ool oe & TL))
Given the laser-wise Jacobian from Lemma 3.1, we proceed to analyze the dynamics a Spectral GNN in Theorem below. Specifically, we focus on the case where the polynomial filter can be approximated by powers of the Laplacian, i.e., (L. L

---

K ==1
K =
K = 3
K 5
K 10
Imoginary
Real
Real
Real
Real
Real
Figure 4: Singular-value spectra of the graph-wise Jacobian the complex plane for vanilla ChebNet with increasing polynomial order K.
Theorem 1 (Layer--Wis Wise Jacobian singular-value distribution). Assume the setting of Lemma 3, with (L( LA and the symmetric normalized Laplacian, and let all O₂ E R be initialized with i..d. (O, o²) entries. Denote the eigenvalues of L as [Ai,..., )n). the squared singular values of O2 O {Hi...... Hd,k), }, and the squared singular values of the Jacobian by "V.y. Then, for sufficiently large d the empirical eigenvalue distribution of O, converges to the Marchenko- Pastur distribution Vk. Then, the mean and variance of each "Hs are
[h,s] 0²
Σ k=1
2k
Var Var[%.]
2k
(4)
Theorem shows that the singular values spectrum of the layer-wise Jacobian depends on the sum over the powers of the normalized Laplacian's 's eigenvalues. This indicates that larger polynomial orders K push the singular value-spe -pulterup towards unstable dynamics, empirically demonstrated in Figure 4. Stacking several layers of large filter orders will therefore severely hinder the trainability of a Spectral GNN of this form.
Beyond analyzing the information propagation dynamics between different layers, we are interested quantifying the communication ability between distant nodes in the graph. Recent literature has proposed to measure information flow in the graph by evaluating the sensitivity of a node embedding after layers (i.e., hops of propagation) with respect the input of another node using the node-wise Jacobian [82, 27, 3]. i.e., Ox /0x!! Following this approach, we measure how sensitive node arbitrary layer with respect the initial features of another node, to better illustrate the long-range propagation capabilities of spectral GNNs.
emhedding of ChebNet
Theorem (ChehNet Sensitivity). Consider a Chehyshev-based Graph Neural Network (ChebNet) defined os:
((+1) => W(O
(5)
where E X2 is the graph Laplacian, (L) the k-th Chebyshev polynomial of the Laplacian, and U)) are learnable weight matrices. Assume activation function a identity and X the input features.
Then, the sensitivity of node respect to node u after layers is given by:
{ IIEnan En(L)w()) ))
(11
0x.
II
(6)
Ox!0)
This result indicates that the sensitivity of ChebNet closely tied to the polynomial order K. We note that, in the case of K = 1, the sensitivity aligns with that of standard MPNNs (such as GCN), exhibiting reduced long-rang ong-range communication. However, for K 1, the higher polynomial orders significantly enhance the ChebNet's 's sensitivity, enabling more effective long-range propagation and improving overall capacity to capture distant dependencies the graph. Therefore, we conclude that a large filter order K is needed to enable long-range communication between nodes in the graph, but this will result unstable training dynamics. This serves explain the decay in performance in Figure 3. In the next subsection, will propose remedy to this issuc.
'The sensitivity upper bound of standard MPNNs further discussed in Appendix B.5.
5

---

3.3 Stable-ChebNet: Stability with Antisymmetric Parameterization
As discussed in Section 3.2, although ChebNet demonstrates strong long-range propagation capabili- ties, increasing the polynomial order introduce significant instability into the model dynamics. To address this challenge, we propose Stable-ChebNet, a simple yet effective modification of classical ChebNet aimed at improving its stability. Recent literature has demonstrated that the effectiveness of neural architectures can be significantly improved by framing them as stable, non-dissipative dynami- cal systems [50, 18, 45, 46, 54]. The core idea behind these approaches is carefully regulate the spectrum of the Jacobian matrix to ensure the network operates within a stable regime. Specifically, this behavior can be achieved by constraining the eigenvalues of the Jacobian to be purely imaginary. Under this constraint, the input graph information is effectively propagated through the successive transformations into the final nodes' representation. Motivated by this line of work, begin by reformulating ChebNet as a continuous-time differential equation. Specifically, we consider the following ordinary differential equation (ODE):
K Σ (L)))(()) k=
dx(() dt
(7)
for time & [0, and subject the initial condition (i.e., the input features) X(0) (0), In other words, the dynamics of the system (i.e., the continuous flow of information over the graph) now described the ChebNet update rule. To ensure the Jacobian of this system has purely imaginary eigenvalues, straightforward approach is to use antisymmetric weight matrices? and the symmetrically normalized Laplacian. This choice, as formalized in the following theorem, directly enforces the desired spectral property, leading to inherently stable dynamics.
Theorem 3 (Purely Imaginary Eigenvalues). Let be the symmetric normalized Laplacian and WW w = O...., K, then the graph-wise Jacobian of the ODE in Equation (7) has purely imaginary eigenvalues, te.,
Re(Ac(J)) = 0, Vi.
Even in this section, provide the proofs for the statements in Appendix B. Theorem shows that by enforcing antisymmetry in the weight matrices and leveraging the symmetric structure of the Laplacian, guarantee that the Jacobian has purely imaginary eigenvalues, ensuring that node representations remain sensitive to input features of far away nodes without suffering from the instability of standard ChebNet.
wetpratiallequuattononnnpeeeeeee neural architectures, a numerical discretization method is needed to solve Equation (7). We solve the equation with simple finite difference scheme, i.c., forward Euler's 's method, yielding the following node update equation
As for standard
K X xx(1 +E Σ T WT -11
where I is the identity matrix, E R. is a hlper-paramette that maintains the stability of the forward Fuler method, and E R, the discretization step.
We refer to the ODE in Equation (9) as Stable-ChebNet, and in the following, we show that this naive Fuler new formulation achieves second-order stability. This is critical improvement, eigenvalues) discretization of the original ChebNet (without imposing constraints on the Jacobian would result in only first-order stability, which is considerably more prone numerical instability, Specifically, without these constraints, the model can exhibit exponential growth or decay in the gradients, significantly limiting its ability to capture long-ram rangr dependencies [3]. In contrast, second-order stable systems, like Stable-Chete ChebNet,, maintain controlled gradient dynamics over longer timescales, allowing for effective long-range information propagation.
A matrix A E [gdxd is antisymmetric (i.e., skew symmetric) if - AT

---

Table Mean test set 1o (MSE) and standard deviation averaged over 4 random weight initializa- tions for each configuration on the Graph Property Prediction dataset. The lower the better.
Model
Diameter
SSSP
Eccentricity
GCN
0.7424 + 0.0466
0.9499 + 0.0001
0.8468 + 0.0028
GAT
0.8221 + 0.0752
0.6951 + 0.1499
0.7909 + 0.0222
GraphSAGE
0.8645 + 0.0401
0.2863 + 0.1843
0.7863 + 0.0207
GIN
0.6131 + 0.0990
-0.5408 0.4193
0.9504 = 0.0007
GCNII
0,5287 + 0.0570
-1.1329 = 0.0135
0.7640 = 0.0355
DGC
0.6028 + 0.0050
-0.1483 0.0231
0.8261 = 0.0032
GRAND
0.6715 + 0.0490
-0.0942 + 0.3897
0.6602 + 0.1393
A-DGN w/ GCN backhome
0.2271 + 0.0804
-1.2288
0.0607
0.7177 = 0.0345
ChebNet
-0.1517 0.0343
-1.8519 + 0.0539
-1.2151 0.0852
Stable-ChebNet (ours)
-0.2477 + 0.0526
-2.2111 + 0.0160
-2.1043 + 0.0766
Theorem 4 (Non-exponential Information Growth or Decay with Antisymmetric Weights). Consider the Stable-type Chebyshev Graph Neural Network "Stable-Chebiee defined by:
x (++1) x Te(L)x(W(")
(10)
with small step size 0 and antisymmetric weight matrices:
= -
1k,
(11)
Then the Jacobian J of the layer does not lead to exponential growth or decay across layers. Specifically, we have:
|| 1 O
(12)
Conversely, for general weights without the antisymmetric property, exponential growth or decay of the Jacobian typically occurs.
4 Experiments
We evaluate ChebNet and its stable formulation (Stable-ChebNet) across a variety of settings to thoroughly assess long- wongrrange capabilities. In this section, we report and discuss the performance of both models on these benchmarks. We report additional experiments on heterophilic node classification tasks from [70] in Appendix F. We run our experiments single A 100 GPU and provide the full details on the hyperparameter search for all datasets in Appendix D, and baseline and datasets details in Appendix C.
Graph Property Prediction Dataset. We evaluate our model's 's ability to predict long-range graph properties using synthetic dataset developed by Corso et.al in [24] under the experimental setup of [45]. The dataset consists of undirected graphs drawn from a diverse set of random and structured families (Erdōs Rényi, Barabási-Allert caterpillar, etc), ensuring a broad coverage of topological properties. Each graph contains between 25 and 35 nodes as per the setup of Gravina et.al [45] (in contrast the 15-25 node range originally used by [24]). thus increasing task complexity and raising need for long-range information propagation. Finally, each node is assigned a single scalar feature sampled uniformly at random from the interval [0, 1). We provide detailed comparison in Table 1.
Results. Compared to classical ChebNet, Stable-ChebNet yields consistent and significant gains across all three tasks, On the Diameter task, classical ChebNet achieves (0g1((MBB) of -0.15, whereas Stable-ChebNer improves it -0.25. On the Single Source Shortest Path (SSSP) task, the gain is larger and goes from 1.88 using ChebNet to -2.21 with our Ceebee form. Finally, on Eccentricity, where the difficulty is highest due the necessity to propagate information about the most distant nodes individually, classical ChebNet achieves log (MSE) of 1122 while Hable-ChebNeer reaches 10, reducing the average prediction error by more than an order of magnitude relative to the baseline. Relative to other baselines, Stable-ChebNet dominates most models based on standard message-passing or modified diffusion mechanisms. Methods like GCN and GCNI are badly over-squashed, barely reaching negative (MSSE) values.
7

---

Over-Squashing Analysis on Barbell Graphs. To further investigate the robustness of our model to oversquashing, we use as benchmark the barbell regression tasks introduced in [5]. In this task, model that fails to transfer any information across the single bridge edge will produce an essentially random constant and obtain a mean-squared error (MSE) close to an error in the 0.4-0.6 band indicates that only a partial amount of information has overcome the bottleneck. Errors around 0.25 and below suggest that the oversquashing has been effectively overcome. this work, we compare Mable-ChebNett performance on barbell graphs of varying sizes (N 10, 25, 50, 100) against numerous baselines, mainly an MLP and variants of MPNNs such as GCN [57], GAT [83]. and SAGE [51]. Further description of the task is found in Appendix C.2.
Results. We observe Figure that both clas- sical ChebNet and Stable-ChebNer successfully learn the small N 10 case with negligible error. However, for moderate graph sizes with N 50, a classical ChebNet with fixed K already sits in the "partial collapse" regime as its MSE increases to around 0.90 and slides towards the random-guess area as N keeps growing (Ta- ble 2). For the same range of hops K, replac- ing the standard update with our stable Euler- based formulation keeps the error almost two orders of magnitude smaller with an MSE below 0.20, confirming that the non-dissipative time- stepping effectively prevents the over-squashing phenomenon.
1.00
0.75
0.50
0.25
10
0.00
10
25
50
Number of nodes
MLP GCN
SAGE
ChebsNet
GAT
Chellee
Figure 5: Mean Squared Error (MSE) compari- son of various MPNN baselines at different node counts N of Barbell graphs.
Table 2: Mean squared error (MSE) of ChebNet and Stable-ChebNer on the over-squashing experi- ment for barbell graphs. Left: sizes N 50, 70 for K and 10. Right: size N 100 for K 20.
Method
K
50
70
Method
K
100
K
0.32 + 0.39
1.08 + 0.05
ChebNet
K 10
0.05 + 0.00
1.08 + 0.01
ChebNet
K = 20
0.87 = 0.05
Stable-
Stable-
K- 9
0.17 + 0.11
0.47 + 0.49
ChebNet (ours)
K = 20
0.21 + 0.27
ChebNet
K 10
0.05 0.00
0.06 0.03
Oren-Graph Benchmark. To evaluate real-world applicability on large-scale graphs, we run experiments for node-level tasks on two large-scale graph datasets from the Open-Graph Benchmark (OGB) [55]. ogbn-arxiv is a citation network in which each node corresponds an academic paper, and the task is node classification by predicting the subject area of unseen papers. The other dataset we use, ogbn-proteins, is a protein protein interaction network aimed inferring protein functions. To ensure a fair comparison and emphasize efficiency, we limit the number of parameters in our models be within the same range as those used in existing and most recent OGB benchmarks.
Results. Table 3 reports the performance on the ogbn-arxiv citation network, where ChebNet achieves around 73% test accuracy, while Stable-ChebNet boosts the performance further 75.7%, outperforming all other methods, including a variety of MPNNs and Graph Transformers such as GraphGPS [71] and Exphormer [80]. Similarly. on the bobn--rottens interaction network. ChebNet attains about 77.6% accuracy compared to Stable-ChebNet ' 79.5% (Table 4). Competing approaches achieve nearly 72% for MPNN-based methods, while Transformer-based models' perfor- mances range from 77.4% for NodeFormer [88] to 79.5% for SGFormer [89]. Hence, Stable-Chebll remarkably competes and often outperforms state-of-tte of-te--f-the-arr models on this benchmark, demonstrating that the Euler formulation consistently narrows the gap with and in some cases overtakes Transformer baselines such as SGFormer [89] and Spexphormer [79]. Together, these results demonstrate that augmenting ChebNet with an Euler step not only addresses the classical ChebNet's shortcomings on long-range information propagation but also performs effectively well on graphs with hundreds of thousands of nodes, in contrast to regular-sized graphs seen in previous experiments.
8

---

Table 3: Accuracy on ogbn-arxiv.
Table 4: Accuracy on ogbn-proteing,
Model
ogbn-arxiv
Model
ogbn-proteins
GCN
71.74 + 0.29
MLP
72.04 0.48
ChebNet
73.27 + 0.23
GCN
72.51 = 0.35
ChebNetll
72.32 + 0.23
ChebNet
77.55 0.43
GraphSAGE
71.49 + 0.27
SGC
70.31 = 0.23
GAT
72.01 + 0.20
GCN-NSAMPLER
73.51 1.31
NodeFormer
59.90 + 0.42
GAT-NSAMPLER
74.63 = 1.24
GraphGPS
70.92 0.04
SIGN
71.24 0.46
GOAT
72.41 + 0.40
NodeFormer
77.45 = 1.15
EXPHORMER+GCN
72.44 + 0.28
SGFormer
79.53 0.38
SPEXPHORMER
70.82 + 0.24
SPEXPHORMER
80.65 0.07
Stable-ChebNet (ours)
75.73 + 0.51
Stable-ChebNet (ours)
79.55 0.34
Long- Graph Benchmark (LRGB). LRGB [33] is collection of GNN benchmarks that evaluate models on tasks involving long-range interactions. We use two of its molecular-propert datasets: Peptides-fune for graph classification and Peptides-struct for graph regression.
Results. A detailed leaderboard is shown Table 5. It can be seen that Stable-ChebNet improves upon its vanilla counterpart. Together with S2GCN, it reaches average precision (AP) above 70 on Peptide-funa and Mean Absolute Error (MAE) below 0.26 on the regression task, bearing in mind that S2GCN requires more expensive full Laplacian eigendecomposition. Overall, model achieves competitive performance on peptide structures with results competing with and often outperforming some well-known graph-based models including graph transformers such as Exphormer [80] and Graph VTT [53], state space models including Graph Mamba and GMN [84], and rewiring methods like DRew [49]. It is worth noting that the gain in AP for DRew comes the cost of computing positional encodings (Laplacian eigenvectors) for every graph before training, while Chhle-ChebNNt does not use any positional encodings.
Heterophilic benchmarks We further assess Stable-ChehNet on node-classification tasks explicitly designed to stress performance under heterophily, following the standardized protocol of Platonov et al. ("Roman-empire,, "Amazon-ratings"" "Minesweeper" and "Tolokers") [70]. We keep the exact data processing, splits, and metrics recommended therein. Concretely, report accuracy Roman-empire and Amazon-ratings, and ROC-AUC on Minesweeper and Tolokers averaging over four random initializations as in the protocol.
Link to oversmoothing, heterophily, and long-rangeness. Our heterophilic results (Table 9) should not be over- ver-interppeted as "evidence of long-range propagation" or as direct antidote to oversmooth- ing. The recent position paper by modii-Rodrig & Errica [2] argues that several widespread assumptions in the literature are often conflated: (i) that heterophily is inherently detrimental while homophily is beneficial, (ii) that long-range propagation best evaluated on heterophilic graphs, and (ii) that performance degradation mainly arises from oversmoothing. They show that heterophily, long-range interactions, and oversmoothing are orthogonal factors: a graph may be heterophilic yet dominated by local dependencies, or homophilic yet require long-range reasoning. Hence, evaluations should focus on the nature of the learning task, not merely on global homophily ratios. this light, Stable- CheehhtheNet scores Roman eemire, Minesweeper, and Tolokers demonstrate that stable spectral propagator has competitive performance on standardized heterophily benchmarks, but they do not by themselves certify rangennge..ss. Those conclusions are better supported by dedicated long-range tests and stability analysis.
Conclusion
In this work, we have re-examined ChebNet, one of the earliest spectral GNNs, from first principles, uncovering its innate ability to capture long-range dependencies via higher-order polynomial filters, also susceptibility unstable propagation dynamics polynomial order grows. By casting ChebNet as continuous-time ODE and imposing antisymmetric weight constraints, we introduced

---

Table 5: Long-range benchmark results. AP the target metric peptides-func (higher is better).
and MAE is the target metric on peptides-struct (lower is better).
Model Type
Model
peptides-func (AP
peptides-struct (MAE !)
SAN+LapPE
63.84 + 1.21
0.2683 0.0043
TIGT
66.79 + 0.74
0.2485 = 0.001.5
Specformer
66.86 + 0.64
0.2550 = 0.0014
Transformer
Exphormer
65.27 = 0,43
0.2481 = 0,0007
G.MLPMixer
69.21 = 0.54
0.2475 = 0.0015
Graph VIT
69.42 = 0.75
0.2449 = 0.0016
GRIT
69.88 + 0.82
0,2460 = 0.0012
LASER
64.40 +
0.3043 = 0.0019
Rewiring
DRew-GCN
69.96 1 0.76
0.2781 = 0.0028
+PB
71.50 = 0.44
0,2536 = 0.0015
Graph Mamba
67.39 1 0.87
0.2478 + 0.0016
State Space
GMN
70.71 + 0.83
0.2473 + 0.0025
MP-SSM
69.93 = 0.52
0.2458 = 0.0017
A-DGN
59.75 + 0.44
0.2874 = 0.0021
ChebNet
69.61 = 0.33
0.2627 = 0.0033
ChebNeil
68.19 = 0.27
0,2618 = 0.0058
GCN
68.60 = 0.50
0.2460 = 0.0007
GRAMA
70.93 = 0.78
0.2436 = 0,0022
GRAND
57.89 = 0.62
0.3418 = 0.0015
GNN
GraphCON
60.22 = 0.68
0.2778 = 0.0018
PH-DGN
70.12 = 0.45
0,2465 = 0.0020
SWAN
67.51 1 0.39
0,2485 - 0.0009
PathNN
68.16 1 0.26
0.2545 - 0.0032
CIN+
65.69 1 1.17
0.2523 0.0013
S2GCN
72.75 = 0.66
0.2467 = 0.0019
+PE
73.11 = 0.66
0.2447 = 0.0032
Cable-CheeNeete (ours)
70.32 = 0.26
0.2542 = 0.0030
Stable-ChebNet, whose forward Fuler discretization yields non-dissipative, second-order-stable information flow without resorting to costly eigendecomposstionn, positional encodings, or graph rewiring. We provide theoretical analysis of Stable-ChebNe showing purely imaginary Jacobian spectra and bounded layerwise sensitivity. We support the analysis with extensive experiments on variety of synthetic and other long-range graph benchmarks. Stable-ChebNet consistently matches or outperforms state-of-the-art message-passingg rewiring, state-space, and transformer- based models, while retaining the fundamental properties Chebyshev filters. Future work can focus on generalizing this ODE-based framework to broader spectral GNN families, whereby the stability analysis can be extended other polynomial types and orthogonal bases.
Impact Statement. This work aims to advance the field of machine learning on graph-structured data which abundant in the real world. There many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Code Availability All code and datasets will be made publicly available at https://gituub.com/aaarttt 3atp://aaaaaaiiii//aaaaaaahCaaha 3/Stable-ChebNet to support reproducibility and future work.
Acknowledgments and Disclosure of Funding
AG and DB acknowledge funding from EU-EIC EMERGE (Grant No. 101070918). XD acknowl- edges support from the Oxford-Man Institute Quantitative Finance and EPSRC No. EP/T023333/1.
10

---

References
[1] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
[2] Adrian Jinaiz-Rodriguce and Federico Errica. Oversmoothing," oversquashing". heterophily, long-range, and more: Demystifying common belief's in graph machine learning. arXiv preprint wrXi::2505.15547 2025.
[3] Á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. arXiv preprint wrXv:22502.10816 2025.
[4] Hugo Attali, Davide Buscaldi, and Nathalie Pernelle. Rewiring techniques to mitigate over- squashing and oversmoothing in gnns: A survey. arXiv preprint arXiv:2411.17422 2024.
[5] Jacob Bamberger, Federico Barbero, Xiaowen Dong, and Michael Bronstein. Bundle neural networks for message diffusion on graphs. arXiv preprint arXiv:2405.15544 2024.
[6] Jacob Bamberger, Benjamin Gutteridge, Scott le Roux, Michael M Bronstein, and Xiaowen Dong. On measuring long-range interactions in graph neural networks. arXiv preprint arXiv:2506.0597), 2025.
[7] Federico Barbero, Ameya Velingker, Amin Saberi, Michael M. Bronstein, and Francesco Di Giovanni. Locality-aware graph rewiring in GNNs. In The Twelfth International Conference on Learning Representations, 2024.
[8] Ali Behrouz and Farnoosh Hashemi. Graph mamba: Towards learning on graphs with state space models. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 119-130, 2024.
[9] Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang. Understanding oversquashing in gnns through the lens of effective resistance. In International Conference on Machine Learning, pages 3528-2544 PMLR, 2023.
[10] Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao. Specformer: Spectral graph neural networks meet transformers. arXiv preprint arXiv:2303.01028 2023.
[11] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low- fwwfureuenccy information in graph convolutional networks. Proceedings of the AAAI Conference on Artificial Intelligence, 35(5):3950-33 3957, May 2021.
[12] Cristian Bodnar, Francesco Di Giovanni, Benjamin P. Chamberlain, Pictro Liò, and Michael M. Bronstein. Neural sheaf diffusion: A topological perspective heterophily and oversmoothing in GNNs, 2022.
[13] Xavier Bresson and Thomas Laurent. Residual Gated Graph ConvNets. arXiv preprint 171.053 2018
[14] Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint 1rXiv:1312.6203 2013.
[15] Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006. 13318, 2020.
[16] Andrea Ceni, Alessio Gravina, Claudio Gallicchio, Davide Bacciu, and Moshe Eliasof. Deessage-Pussing State-Space Models: Improving Graph Learning with Modern Sequence Modeling. arXiv preprint arXiv:2505.18728, 2025.
Schonlieb,
[17] Benjamin Paul Chamberlain, James Rowbottom, Maria Gorinova, Stefan Webb, Emanuele Rossi, and Michael M Bronstein. GRAND: Graph neural diffusion. International Conference on Machine Learning (ICML), pages 1407-1418. PMLR, 2021.
11

---

[18] Bo Chang, Minmin Chen, Eldad Haber, and Ed H. Chi. AntisymmetricNNN: A dynamical system view on recurrent neural networks. In International Conference on Learning Represen- lations, 2019.
[19] Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. Nagphormer: A tokenized graph trans- former for node classification in large graphs. In Proceedings of the International Conference on Learning Representations, 2023.
[20] Ming Chen, Zhewei Wei, Zengfeng Huang. Bolin Ding, and Yaliang Li. Simple and Deep Graph Convolutional Networks. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pages 1735-1735. PMLR, 13-18 Jul 2020.
[21] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations. 2021.
[22] Yun Young Choi, Sun Woo Park, Minho Lee, and Youngho Woo. Topology-informed graph transformer. arXiv preprint arXiv:2402.000005 2025.
[23] Krzysztof Choromanski, Marcin Kuczynski, Jacek Cieszkowski, Paul L., Beletsky, Konrad M. Smith, Wojciech Gajewski, Gabriel De Masson, Tomasz Z. Broniatowski, Antonina B. Gorny, Leszek M. Kaczmarek, and Stanislaw K. Andrzejewski. Performers: A new approach scaling transformers. P Proceedings of the 37th International Conference on Machine Learning (ICML), pages 2020-2031, 2020.
[24] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 13260-13271, 2020.
[25] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
[26] Chenhui Deng, Zichao Yue, and Zhiru Zhang. Polynormer: Polynomial-expressiee graph transformer in linear time. In The Twelfth International Conference Learning Representations, 2024.
[27] Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael M Bronstein. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In International conference on machine learning, pages 7865-7885. PMLR, 2023.
[28] Francesco Di Giovanni, James Rowbottom, Benjamin P Chamberlain, Thomas Markovich, and Michael M Bronstein. Graph neural networks as gradient flows: understanding graph convolutions via energy. arXiv preprint arXiv:2206. 10991, 2022.
[29] Lun Du, Xiaozhou Shi, Qiang Fu, Xiaojun Ma, Hengyu Liu, Shi Han, and Dongmei Zhang. Gbk-gnn: Gated berkel graph neural networks for modeling both homophily and heterophily. In Proceedings of the ACM Web Conference 2022, WWW 222 page 1550-1558, New York, NY, USA, 2022. Association for Computing Machinery.
[30] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699, 2020.
[31] Vijay Prakash Dwivedi, Chaitanya K. Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. J. Mach. Learn. Res,, 24(1), January 2023.
[32] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. International Conference Learning Representations, 2022.
12

---

[33] Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. Advances in Neural Information Processing Systems, 15:22326-22344 2022.
[34] Moshe Eliasof, Alessio Gravina, Andrea Ceni, Claudio Gallicchio, Davide Bacciu, and Carola- Bibiane Schönlieb. Graph Adaptive Autoregressive Moving Average Models. In Forty-second International Conference on Machine Learning, 2025.
[35] Federico Errica, Henrik Christiansen, Viktor Zaverkin, Takashi Maruyama, Mathias Niepert, and Francesco Alesiani. Adaptive message passing: A general framework to mitigate oversmoothing, oversquashing, and underreaching. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 15490- 15515. PMLR, 13-19 Jul 2025.
[36] Lukas Fesser and Melanie Weber. Mitigating over-smoo and over-squashing using aug- mentations of forman-ricei curvature. In Soledad Villar and Benjamin Chamberlain, editors, Proceedings of the Second Learning on Graphs Conference, volume 231 of Proceedings of Machine Learning Research, pages 19:1-19:28. PMLR, 27-30 Nov 2024.
[37] Ben Finkelshtein, Xingyue Huang, Michael M. Bronstein, and Ismail Ilkan Ceylan. Cooperative Graph Neural Networks. In Forty-first International Conference on Machine Learning, 2024.
[38] Fabrizio Frasca, Emanuele Rossi, Davide Fynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004.11198, 2020.
[39] Johannes Gasteiger, Stefan Weiß enberger, and Stephan Günnemann. Diffusion Improves Graph Learning. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[40] Simon Markus Geisler, Arthur Kosmala, Daniel Herbst, and Stephan Günnemann. Spatio- spectral graph neural networks. Advances in Neural Information Processing Systems, 37:49022- 49080, 2024.
[41] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263-1272. PMLR, 2017.
[42] Lorenzo Giusti, Teodora Reu, Francesco Ceccarelli, Cristian Bodnar, and Pietro Liò. Cin++: Enhancing topological message passing, arXiv preprint arXiv:2306.03561, 2023.
[43] M Gori, G Monfardini, and F Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference Neural Networks, 2005., volume 2, pages 729-734, IEEE, 2005.
[44] Alessio Gravina and Davide Bacciu. Deep Learning for Dynamic Graphs: Models and Bench- marks. IEEE Transactions on Neural Networks and Learning Systems, 1188):11788-1180) 2024.
[45] Alessio Gravina, Davide Bacciu, and Claudio Gallicchio. Anti-Symmetric DGN: stable architecture for Deep Graph Networks. In The Eleventh International Conference on Learning Representations, 2023.
[46] Alessio Gravina, Moshe Eliasof, Claudio Gallicchio, Davide Bacciu, and Carola-Bibiane Schönlieb. On oversquashing in graph neural networks through the lens of dynamical systems. In The 39th Anmual AAAI Conference on Artificial Intelligence, 2025.
[47] Alessio Gravina, Claudio Gallicchio, and Davide Bacciu. Non-dissipative Propagation by Randomized Anti-symmetric Deep Graph Networks. In Machine Learning and Principles and Practice of Knowledge Discovery Databases, pages 25-36, Cham, 2025. Springer Nature Switzerland.
13

---

[48] Alessio Gravina, Giulio Lovisotto, Claudio Gallicchio, Davide Bacciu, and Claas Grohnfeldt. Long Range Propagation on Continuous- Time Dynamic Graphs. In Proceedings of the 41st In- ternational Conference on Machine Learning. volume 235 of Proceedings of Machine Learning Research, pages 16206-16225. PMIRR 21-27 Jul 2024.
[49] Benjamin Gutteridge. Xiaowen Dong, Michael M Bronstein, and Francesco Di Giovanni. Drew: Dynamically rewired message passing with delay. In International Conference Machine Learning, pages 12252-12267. PMLR, 2023.
[50] E. Haber and L. Ruthotto. Stable architectures for deep neural networks. Inverse Problems, 34(1), 2017.
[51] William Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, 2017.
[52] Mingguo He, Zhewei Wei, and Ji-Rong Wen. Convolutional neural networks graphs with chebyshev approximation, revisited. Advances in Neural Information Processing Systems, 35:7264-7276. 2022.
[53] Xiaoxin He, Bryan Hooi, Thomas Laurent, Adam Perold, Yann LeCun, and Xavier Bresson. generalization of vit/mlp-mixer to graphs. In International conference on machine learning. pages 12724-12745. PMLR, 2023.
[54] Simon Heilig, Alessio Gravina, Alessandro Trenta, Claudio Gallicchio, and Davide Bacciu. Port- Hant-tamitonian Architectural Bias for Long-Range Propagation in Deep Graph Networks. In The Thirteenth International Conference on Learning Representations, 2025.
[55] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: datasets for machine learning on graphs. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20. Curran Associates Inc., 2020.
[56] Kedar Karhadkar, Pradeep Kr. Banerjee, and Guido Montúfar. Fosr: First-order spectral rewiring for addressing oversquashing in gnns. In The Eleventh International Conference on Learning Representations, ICLR, 2023.
[57] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations (ICLR), 2017.
[58] Kezhi Kong, Jiuhai Chen, John Kirchenbauer, Renkun Ni, C. Bayan Bruss, and Tom Goldstein. GOAT: A global transformer on large-scale graphs. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 17375-17390. PMLR, 23-29 Jul 2023.
[59] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Pro- cessing Systems, 34:21618-21629 2021.
[60] Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. Finding global homophily in graph neural networks when meeting heterophily. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 1222-13256. PMLR, 17-23 Jul 2022.
[61] Huidong Liang, Haitz. Sáez de Ocáriz Borde, Baskaran Sripathmanathan, Michael Bronstein, and Xiaowen Dong. Towards quantifying long-range interactions in graph machine learning: a large graph dataset and a measurement. arXiv preprint 25X0:2500300900. 2025.
[62] Sitao Luan, Chenqing Hua, Qincheng Lu, Liheng Ma, Lirong Wu, Xinyu Wang, Minkai Xu, Xiao-Wen Chang. Doina Precup. Rex Ying, Stan Z. Li, Jian Tang, Guy Wolf, and Stefanie Jegelka. The heterophilic graph learning handbook: Benchmarks, models, theoretical analysis, applications and challenges, 2024.
14

---

[63] Liheng Ma, Chen Lin, Derek Lim, Adriana Romero-Soriano Puneet K. Dokamia, Mark Coates, Philip Torr, and Ser-Nam Lim. Graph inductive biases in transformers without message passing. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 23321-23337. PMLR, 23-29 Jul 2023.
[64] Sohir Maskey, Raffaele Paolino, Aras Bacho, and Gitta Kutyniok. A fractional graph laplacian approach oversmoothing. Advances in Neural Information Processing Systems, 36, 2024.
[65] Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata. Simplifying approach to node classifica- tion in graph neural networks. Journal of Computational Science, 62: 2022.
[66] Gaspard Michel, Giannis Nikolentzos, Johannes Lutzeyer, and Michalis Vazirgiannis. Path neural networks: expressive and accurate graph neural networks. In Proceedings of the 40th International Conference on Machine Learning. ICML'23, JMLR.org, 2023.
[67] Alessio Micheli. Neural Network for Graphs: A Contextual Constructive Approach. IEEE Transactions Neural Networks, 20(3):498 511, 2009.
[68] Khang Nguyen, Hieu Nong. Vinh Nguyen, Nhat Ho, Stanley Osher, and Tan Nguyen. Revisiting over-smoothing and over-squashing using ollivier-ricci curvature. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMLR.org. 2023.
[69] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
[70] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of GNNs under heterophily: Are we re- ally making progress? In The Eleventh International Conference on Learning Representations,
2023.
[71] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 45014151144 2022.
[72] T. Konstantin Rusch, Michael M. Bronstein, and Siddhartha Mishra. A Survey on Oversmooth- ing Graph Neural Networks. arXiv preprint arXiv:2303. 2023.
[73] Konstantin Rusch, Ben Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael Bronstein. Graph-coupled oscillator networks. In International Conference on Machine Learning, pages 18888-18909. PMLR, 2022.
[74] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008
[75] Florian Sestak, Lisa Schneckenreiter, Johannes Brandstetter, Sepp Hochreiter, Andreas Mayr, and Günter Klambauer. Vn-egnn: E (3)-equivariant graph neural networks with virtual nodes enhance protein binding site identification. arXiv preprint arXiv:2404.07/99 2024.
[76] Ahsan Shehzad, Feng Xia, Shagufta Abid, Ciyuan Peng, Shuo Yu, Dongyu Zhang, and Karin Verspoor. Graph transformers: A survey, 2024.
[77] Dai Shi, Andi Han, Lequan Lin, Yi Guo, and Junbin Gao. Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challenges, 2023.
[78] Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjing Wang, and Yu Sun. Masked label prediction: Unified message passing model for sumi-supervised classification. In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelli- gence, IJCAI-21, pages 1558-1554. International Joint Conferences on Artificial Intelligence Organization, 2021. Main Track.
[79] Hamed Shirzad, Honghao L Lin, Balaji Venkatachalam, Ameya Velingker, David P Woodruff, and Danica J Sutherland. Even sparser graph transformers. Advances in Neural Information Processing Systems, 37:71277-71300 2024.
15

---

[80] Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In International Conference on Machine Learning, pages 31613-31632. PMIR, 2023.
[81] Alessandro Sperduti. Encoding labeled graphs by labeling raam. Advances in Neural Informa- tion Processing Systems, 6, 1993.
[82] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations. 2022.
[83] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In Proceedings of the International Conference on Learning Representations (ICLR), 2018.
[84] 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.00779) 2024.
[85] Xiyuan Wang and Muban Zhang. How powerful are spectral graph neural networks. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari. Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 23341-23361 PMLR, 17-23 Jul 2022.
[86] Yifei Wang, Yisen Wang, Jiansheng Yang. and Zhouchen Lin. Dissecting the Diffusion Process in Linear Graph Convolutional Networks. In Advances in Neural Information Processing Systems, volume 34, pages 5758-5769. Curran Associates, Inc., 2021.
[87] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying Graph Convolutional Networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Muchine Learning Research, pages 6861-6871. PMLR, 09-15 Jun 2019.
[88] Qitian Wu, Wentao Zhao, Zenan Li, David P Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems, 35:27387-274011 2022.
[89] Qitian Wu, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nie, Haitian Jiang, Yatao Bian, and Junchi Yan. Sgformer: Simplifying and empowering transformers for large-graph representations. Advances in Neural Information Processing Systems, 36:64753-64777 2023.
[90] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019.
[91] Chengxuan Ying, Tianle Cai,, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Yin Liu. Do transformers really perform bad for graph representation? In Procedingss of the 35th International Conference on Neural Information Processing Systems, NIPS '21. Curran Associates Inc., 2021.
[92] Manzil Zaheer, Guru prasad G. H., Lihong Wang, S. V. K. N. L. Wang. Yujia Li, Jakub Konečny, Shalmali Joshi, Danqi Chen, Jennifer R. R., Zhenyu Zhang, Shalini Devaraj, and Srinivas Narayanan. Bigbird: Transformers for longer sequences. Proceedings of the 37th International Conference Machine Learning (ICML), pages 2168-12178 2020.
[93] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. arXiv preprint arXiv:1907.0499) 04931, 2019.
[94] Jiong Zhu, Ryan A. Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K. Ahmed, and Danai Koutra. Graph neural networks with heterophily. Proceedings of the AAAI Conference on Artificial Intelligence,
May 2021.
[95] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 7793-7804. Curran Associates, Inc., 2020.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All the claims found in the abstract and introduction are supported by the results and theorems discussed in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We mention the scope of this work that is limited to ChebNet and leave the expansion to other Spectral GNN methods for future work.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
17

---

Answer: [Yes]
Justification: The paper provides set of theorems that justify and motivate the choice of the developed model. The corresponding proofs are also presented and can be found in the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofss provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The datasets we use are publicly available and we share the code in the supplementary materials folder. The set of sweeped hyperparameters reproduce the results is also shared.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results.
18

---

reproducible, they 5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification: The provided repository includes all the datasets used as well as the necessary code to reproduce the experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nip) cc/
wtt.sSumiisiioooiiooo.ooo....ice for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /nips. sc/public/gus wwtcc//gugee//eeeeeeeee SoodeeubmissiooPPP
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We specify that we follow the same training procedure for the datasets as their papers of reference. We also show our hyperparameter sweep in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: We provide all our results in terms of graph performance in the format "mean + standard error of the mean".
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
19

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide detailed information about the used resources in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https https://nettt httpp/s///////p////eee wwtpccccpppccceeeeeeeeeeeeeeeeee httpa///Ehhhschlelnnnn.nn
Answer: [Yes]
Justification: We preserve anonymity in our submission and our submission abides by the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss potential positive and negative societal impacts after the conclusion section.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
20

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The release of our data and models does not pose direct risk of misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification; We provide citations for all sources of code and/or data used. both in the paper and in the accompanying repository. For the datasets, we reference the original open-source work they are based on, full accordance with their licensing terms.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
21

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswithcom thcode. com/coo/////ooooo conddataeet has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release new datasets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No crowdsourcing or human subjects were involved the experiments con- ducted for this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No crowdsourcing or human subjects were involved the experiments con- ducted for this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
22

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs are not a core component of this paper in terms of methods.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /ttpp/////euripae ct/ ccCConneeeecece//22222 for what should or should not be described.
23

---

A Supplementary Related Work
Effective propagation and preservation of information graphs remains central challenge in deep learning on graphs, especially when long-range communication between nodes becomes fundamental for the downstream task [77]. GNNs usually rely local neighborhood aggregation, which limits their capacity to capture interactions between distant nodes [1, 27] due to challenges such as over- smoothing [15, 69, 72] and over-squashing [1, 82, 27], which linked the problem of vanishing gradients [3]. Several techniques have been proposed to address this issue.
Graph rewiring techniques [39, 1, 4] modify the original topology, usually pre-proe pre-processing step, with the aim directly connect distant nodes and facilitate information flow. Rewiring methods can be broadly classified based the type of information they leverage, including curvature metrics [1, 68, 36], effective resistance [9], random walks [7], spectral gap [56], and node features [49].
Similarly, Graph Transformers [76, 59, 91, 71] enable direct message passing between any pair of nodes via attention mechanisms, employing an attention mechanism on the entire graph. These models often incorporate positional encodings, such Laplacian eigenvectors [30] or random-walk structural encodings (RWSE) [32], to encode graph structure. reduce the quadratic complexity of the full attention mechanism, recent methods introduce methods such as sparse attention mechanisms [92, 23), Exphormer [80], and linear graph transformers [26].
Despite the success of graph rewiring methods and Graph Transformers, these approaches often introduce additional computational complexity due to the use of denser graph shift operators. An alternative strategy to enhance long-range propagation focuses on constraining the dynamics of the GNN to remain stable and non-dissipative, while maintaining the computational complexity of classical MPNNs. In this paradigm, the GNN is interpreted as discretization of differential equation, leveraging dynamical systems theory to maintain a constant rate of information flow between nodes. This behavior has been achieved either through antisymmetric weight parameterization [45, 46, 47, 48] or by exploiting port-Hamiltonian dynamics [54].
Recent works further explore long-range interactions in GNNs. In [6]. Bamberger et al. formalize and measure interaction ranges in graph operators, while in [61] Liang et al. introduce a large-scale dataset and metric to quantífy long-range dependencies. These studies complement existing approaches by providing tools to better evaluate and understand information propagation across distant nodes.
Other approaches include filtering messages in the information flow [37, 35), using a graph adaptive method based learnable ARMA framework [34], state space models [8, 16], fractional power of the graph shift operator [64].
B Sensitivity Results
In this section, we provide the proofs for the statements in Section 3.2.
B.1 Proof of Lemma 3.1
Proof. Applying vectorization to f(X) and recalling that vec(AXB) (B obtain
X A) vec(X),
vec(f((X) = Σ 1 @
Lec
km
Taking derivatives:
0
K T 69 TL))).
J = 3 vcc
X
B.2 Proof of Theorem 1
Proof. Define the k-hop Jacobian block JR O & L and the full Jacobian J Σk JR. Because θ₁ & L has singular values (0a)) |A, the squared singular values of J, are given by (k) x Mj
Ti.j
24

---

For square Gaussian matrix, the empirical spectrum of O converges to the Marchenko-Pastee (MP) law. Scaling by x² yields
m. (k) 0² 2
(13)
m² (k)
2
(14)
Independence, together with the rotational symmetry of each θ₁ implies the blocks J are asymp- totically free. Freeness gives additive R-transforms, hence additive free cumulants Ki, (Ex Jx)
Es (J&). For 1, 2 the classical moments coincide with the free cumulants, so the ordinary moments of Yi also add:
K
m,
m (k)
T {1,2}.
(15)
k=1
Insert Equation (13) into Equation (15):
mi
2k
(16)
K
m2 = 20
4k
(17)
1=1
Finally,
Var[yaj]
172 mm/
x2x)² 2
20 Σ
1k 0
Σ
2 2
B.3 Proof of Theorem 2
Proof. Recall that the forward pass for one ChebNet layer (omitting the activation function) is:
K
x ((+1)
(0 w!
(18)
k=0
Applying vectorization, we obtain:
vec (1+1)
Σ ((w()) TT((L) vec(x(
(19)
By unrolling Equation (19) and taking the derivative with respect to vec(X(()), we obtain the sensitivity after layers:
Ovec
II
Σ (W
(IW))TT()))
(20)
(v))
1=0
Focusing on a single feature channel (or summing across channels), we obtain the sensitivity:
(1)
1-1
K
= II
Σ
(21)
0x
())
L=
k=0
Then, the sensitivity node e with respect to node u after / layers is given by:
Ox!!! (1)
1-1
K
(((L) ))
II
Σ
(22)
xx
1=0
25

---

B.4 Proof of Theorem 3
Proof. Given that the graph wash-wisee/ue Jacobian of Equation (7) is Equation (2), we note that each term in the Jacobian, of the form W @ (L), is an antisymmetric matrix. This follows from the fact that We antisymmetric by construction, (L) preserves the symmetry the normalized Laplacian, and the Kronecker product of an antisymmetric matrix with symmetric matrix is itself antisymmetric. Finally, since the sum of antisymmetric matrices remains antisymmetric, it follows that the graph-wise Jacobian of Equation (7) has purely imaginary eigenvalues.
B.5 Sensitivity upperbound of standard MPNNs
In the following theorem we report the sensitivity upperbound computed for standard MPNNS in [27].
Theorem (Sensitivity uppperbound standard MPNNs, taken from [27]). Consider a standard
MPNN with I layers, where is the Lipschitz constant of the activation 0, w is the maximal entry-value over all weight matrices, and d is the embedding dimension. For u, U E V we have
Ohe
(oowdd' (O') )O')
(23)
0h (0)
model topology
with O = c.I+ E RAXX is the message passing matrix adopted by the MPNN, with er and co. the contributions of the self-connection and aggregation term.
B.6 Proof of Theorem 4
Proof. First, recall the Jacobian explicitly:
I+
(w)
s Ta(L)).
(24)
k=
Define:
10
(w()) s Ti(())
(25)
k=0
Antisymmetric Case:
When (W ) w the matrix A is antisymmetric, because is Kronecker product of antisymmetric and symmetric matrices. Its eigenvalues purely imaginary (or symmetric about zero), meaning their real parts vanish. Thus, for the spectral radius, we have:
J = p (J()
(26)
p I + (((())) + +(41))) A.).
(27)
Due to antisymmetry:
(A + A =0
(28)
Hence:
| = [I (11))) Aw)
(29)
The matrix (A (())) is symmetric and positive semi-definite, having nonnegative real eigenvalues. Expanding around the identity gives:
| ||2 / +1++ e² Amax ((AW)TT4)) = -
(30)
Thus, no exponential growth or decay occurs.
General Case of Stable-ChebNet (Without Antisymmetry); For arbitrary matrices, the linear term (A()) + (A()T)) typically does not vanish, introducing nonzero real eigenvalues. This causes exponential growth decay in the Jacobian norm across layers:
| 2 R 1 + Cee,
(31)
26

---

for some constant C' = m C(,) > 0. Iterating over layers results in exponential instability:
[](]((1)) J 112 (1 + Cc)',
(32)
which grows or decays exponentially as the depth increases.
Thus, antisymmetric weights provide explicit protection against exponential growth or decay, while general weights typically do not.
Standard ChebNet Case: Iterating over layers, this results in exponential instability:
| J 2|2 (+O)),
(33)
which grows or decays exponentially as the depth increases.
C Dataset and Baseline Description
C.1 Graph Property Prediction task description
For the graph property prediction dataset, we make use of three separate tasks:
Diameter (Graph-Level.. The diameter is defined the length of the longest shortest path between any two nodes in the graph. It requires aggregating information from distant regions of the graph.
SSSP (Node-Level). Single-Source Shortest Path requires predicting each node's distance to designated source node. Solving this task with GNNs places a strong emphasis on propagating information from nodes that may lie many hops away from the source.
Eccentricity (Node-Level). For each node u, the eccentricity is the length of the maximum shortest path between u and any other node, As with diameter and SSSP, accurate eccentricity estimation relies heavily on capturing long-distance relationships.
In total, the task contains 5,120 graphs for training, 640 for validation, and 1,280 for testing. The ttain/valiaation/esst splits follow the same seed and setup in [45]. We train models by optimizing mean squared error (MSE) for each task, performing grid search over hyperparameters (e.g.. learning rate, weight decay, number of layers). Each experiment is repeated across four random initializations, and we report the average performance.
Because shortest-path path-related tasks inherently rely on propagating signals over large portions of graph, they serve as a natural stress test for the capacity of GNNs to perform long-range propagation.
C.2 Barbell graph task description
A Barbell graph Ba, is formed by connecting two complete graphs Kn, (the "bells") with a simple path of length & (the "bridge"). Therefore, every node inside bell has high intra-cluster connectivity (n - 1 neighbors), whereas the bridge nodes have degree 2 and constitute the only communication route between the two bells. In this task, the target for nodes to output the average input feature over nodes of the opposite bell and vice-versa, as illustrated in Figure 6. Mean squared error (MSE) used for node-level regression as a proxy for how severely the GNN either oversquashing (failing to pass information across the narrow "bridge") or oversmoothing (collapsing all node embeddings to be nearly identical). Numerical MSE outcomes are associated with each pathology.
The model is so bottlenecked by the bridge that it effectively ignores or fails incorporate information from the other "bell." In other words, each side of the barbell can predict its own node labels, but the information from the opposite side characteristic level of error (+= in their chosen label distribution).
An MSE of around 1 corresponds to oversquashing:
never gets through, leading
An MSE of around 30 corresponds to oversmoothing: The model passes messages so many times (or in such way) that it "collapses" all node embeddings toward the same prediction, ignoring local distinctions within each side. Because the barbell's node labels are diverse (randomly assigned), forcing every node toward the same value yields much larger overall MSE (xx 30 in their setup).
the other hand, an MSE of around 0.5 as shown in the results simply means that the model doing better than the severe oversquashing case (it is not completely failing to pass information across
27

---

the barbell), In other words, some amount of meaningful communication is happening between the two "bells," and the node representations are not entirely collapsed.
t/ 3NN
x V3-V3N.0 03
Input
Output
x
Figure 6: Illustration of input and output node features in a barbell graph setup. Adapted from Bamberger et.al [5].
C.3 Employed baselines
In our experiments, the performance of our method is compared with various statc-of-the-art GNN baselines from the literature. Specifically, consider:
Classical GNN methods, i.e., GCN [57], GraphSAGE [51], GAT [83], GIN [90], and GC-
NII [20], ChebNet [25], ChebNetll [52], CIN++ [42], PathNN [66], S2GCN [40], SGC [87],
SIGN [38], GRAMA [34], GatedGCN [13]. CoGNN [37], H2GCN [95], CPGNN [94],
FAGCN [11], GPR-GNN [21], FSGNN [65], GloGNN [60]. GBK-GNN [29], JacobiCony [85]:
Differential-cquation inspired GNNs (DE-GNNs), i.e., DGC [86], GRAND [17], Graph- CON [73], A-DGN [45], and SWAN [46] PH-DGN [54];
Graph Transformers, i.c., SAN [59], GraphGPS [71], GOAT [58]. Exphormer [80], GRIT[63), Gra [53], G.MLPMixer [53] SPEXPHORMER [79], TIGT [22], SG- Former [89], NodeFormer [88], Specformer [10], GCN-nsampler and GAT-nsampler [93],
GT [78], NAGphormer [19], Polynormer [26]:
dowiring-based methods, i.e., LASER [7], and DRew [49];
SSM-based GNN, i.e., Grabh-Mamba [84], GMN [8], MP-SSM [16]
D Hyper-parameter grids
Tables 6 to 8 summarize our hyperparameter exploration: Table 6 listing the sweep ranges for Htable-CheNNet on Peptides-func, graph-property benchmarks (Diameter, SSSP, Eccentricity), and ogbn-arxiv along with ogbn-proteins experiments, respectively.
28

---

Table 6: Hyper- hyper-parameter grid for Stable-ChebNer ablation on Peptides- func.
Hyper-parameter
Reference
Sweep values used in ablation
Hidden dim d
140
100, 120, 140, 145, 160
Polynomial order K
10
6,8,10
Num of layers
4
3,4,5
MLP layers
2
1,2,3
Step size
0.5
[0.1, 1.0]
Dissipative force
0.05
0.001, 0.01, 0.05, 0.1
Batch size
64
32, 64, 128
Learning rate
0.001
0.0001, 0.001, 0.01
Optimizer
Adam W
AdamW None, Laplacian, RW 8, 16, 32
Pos-enc type
None
Pos-enc dim
16
Table 7: Hyper- srper-parameter grid and best settings for Cabbe-Cheebeet on three synthetic benchmarks.
Hyper-parannn paremppareeter
Values in grid
Diam
SSSP
Eсc
Hidden dimension d
20, 30, 50
50
30
30
Number of layers
1, 3, 10, 20
20
Polynomial order K
3, 5,
Step size
0.01, 0.10, 0.20, 0.30
0.40
0,30
0,30
Dissipative force
0, 0.01, 0.50, tanh, relu 0.001,0.003
0.01
0,00
0.00
Activation function
relu
relu
relu
Learming rate
0.003
0.003
0.003
Weight decay
x 10
1 1 10
x 10
x 10
Table Hyper-parameter sweep ranges for Stahle-ChebNet on ogbn-arxiv and ogbn-proteins.
Hyper-parameter
Sweep (arxiv)
Sweep (proteins)
Hidden dim
128, 256, 512
256. 512, 1024
Polynomial order K
4. 5, 6, 10
5, 10, 15
Num of layers
2, 3, 4,
5,
MLP layers
2,
1,
Step size
[0.1, 1.0]
[0.1, 1.0] 0.01, 0.05, 0.1 512, 1024, 2048 0.0005, 0.001, 0.005
Dissipative force 7
0.01, 0.05, 0.1 256, 512, 1024
Batch size
Learning rate
0.001, 0.01, 0.05 Adam None, Laplacian, RW 8, 16, 32
Optimizer
Adam None, Laplacian, RW 16, 32, 64
Pos-enc type
Pos-enc dim
E Eigenvalues distribution comparison
Figures 7a and 7b provide an empirical comparison of the Jacobian eigenvalue spectra for a classical ChebNet versus our Stable-ChebNet layer at K 5. The top two panels illustrate ChebNet's spectrum: the left histogram shows that both the real and imaginary parts of its cigenvalues span broadly from roughly -2 to +2, with pronounced peaks near the extremes signaling large spectral radius and susceptibility to unstable, oscillatory dynamics. The accompanying scatter plot maps these eigenvalues in the complex plane, revealing many points lying well outside the unit circle, which corroborates the theoretical prediction that high-order Chebyshev filters can push the system toward chaotic regimes.
In contrast, the bottom row portrays the spectrum Stable-ChehNet. Its histogram (bottom left) tightly concentrated within approximately -0.4 0.4 to +0.4 on both axes, indicating that cigenvalues

---

remain far inside the unit circle. The complex plane scatter (bottom right) further demonstrates that all eigenvalues lie symmetrically about the imaginary axis and are bounded magnitude, consistent with the antisymmetric weight parameterization, guaranteeing purely imaginary Jacobian eigenvalues and therefore more stable dynamics.
120
2
Braghorn
100
Frequency
80
Imaginary
60
40
20
Eigenvalues
Real
(a)
1.0
800
Inagnary
Frequency
600
Imaginary
0.0
400
-0.5
200
-1.0
0.0
-0.5
0.5
1.0
Eigenvalues
Real
(b)
Figure 7: Comparison of eigenvalue distributions: (a) ChebNet and (b) StableChebNet.
F
Additional Experiments on Heterophilic Benchmarks
To further evaluate the performance of our Stable-ChebNet, we assess its the effectiveness in capturing complex relational information in heterophilic settings, where nodes belonging same class are often connected through longer and sparser paths, we consider the five node classification tasks introduced in [70]. Specifically, we consider the "Roman-ent "Roman-empire", "Amazon-ratings" and "Minesweeper", "Tolokers" datasets. We adhere to the same data and experimental setting presented in [70].
30

---

Table Mean test set score and std averaged over random weight initializations on heterophilic datasets. The higher, the better.
Roman-empire
Amazon-ratings Acc
Minesweeper AUC
Model
Acc f
AUC f
[62]
MLP-2
66.044a..71
49.55 +9.55-t0.81
50.92+
74.58=0.75
SOC-1
44.60.0.52
82.04.10.77
13.80_1.5
MLP-1
64.12g...0
38.60
50.59
71.89=0.82
MPNNS
GAT
80.87
49.09
92.01 1:0.
83,70 0..47
(LapPE)
84.80+0.44
44.90+0.78
93.50+0.644
84.99=0.05
GAT (RWSE)
86.62+0..6
48.58 48.58++0.41
92.53++0.65
85.02=0.er
0..4
43.00
8..54
17.31=1.34
GCN
73.69
48.70
89.75+0.62
83.64-0.07
GCN (LapPE)
83.37 20.07
20.35.00.36
94.26::0.49
84.95
GCN (RWSE)
84.84
46.40..
93.84
85.1120.77
CO GNN(E,,
91.57 1..57
51.28
95.09 1:18
83.36_0.89
CO-GNN(j,, p)
91.37+0.85
$4.17+0.99
97.31+0.41
84.45-1.17
SAGE
85.74
53.63-go0339
93.51
82.43=0044
Graph Transformers
Expharmer
89.03
$3.51
90.744.0.55
83.77
NAGphormer
74.34
51,26
84.19+0.ce
78.32
GOAT
71. 71.59+11.2
44.61 +0.50
81.09++1022
83. 11.11=1.00
GPS
82.00.0.66
53.10.20.8 42
90.63-10.67
20.4
GPP (LapPE)
83.96 83.96
48.20
93.8510.41
84.7220.77
GPSocciPateee (RWSE)
84.72+0..65
48.08
92.88++0.60
84.81=0.80
GPSocN (LapPE)
0OM
0OM
91.82+0.41
83.51=0.93
GPS Tousfoeee (RWSE)
OOM
0OM
91.17.40.61
83.53_1100
GT
86.51 86.51
51.17+0.96
91.85+0.76
83.23-0..4
GT-sep
a7.32
$2.18:g0.50
92. 92.29
82.52
Polynormer
g0.50
54.81 49
97.46110.36
85.91
GNNs
CPGNN
63.96..
34.79.10.
52.03
73.36
FAGCN
65 23.222:0.00
44.12
88. 171.0.79
77.75
ESONN
79.92+0.66
$2.74+0.59
00.08+0.70
82.76=0.01
GBK GNN
74.57
45.98
90.85
81.01 81.01100000
09.63+a.669
10.14
11.08+1..28
73.39=11.17
GPR-GNN
64 64.85
44.88+0.54
86 86.24+
72.94-0.07
H2GCN
60.11
36.47.20.23
89.71
73.35
JacohiCom
71.14
43.55
89.66
68.66_00.05
Graph SSMs
GMN
87 87.6910.550
54.07.1.33
91.0110.93
84.52m0-aa
GPS + Mamba
0.
45.13340.57
89.93
83.70= Loo
GRAMAGcN
88.61
$3.48.10
95.27
86.23_.1.1
MP SSM
90.91 g.0.
53.65
95.33
85.26_0.00
Ours
ChebNet
20.85
53.15 a1
85.55ga..a
31


Reviews:
[{"review_id": "hY4TR22xsS", "reviewer": "Reviewer_E5Qi", "summary": "The paper reevaluates the spectral GNN ChebNet on long-range graph tasks showing that it still performs competitively compared to baseline methods. It also introduces Stable-ChebNet, a slight modification of ChebNet to enforce layer-wise stability that achieves near state-of-the-art performance across a variety of experiments.", "questions": "1. Could you please elaborate why Figure 1 illustrates how classical ChebNet filters can exhibit unbounded dynamics? What do you mean by temperature here? Why does a temperature close to zero for most of the nodes at step T illustrate unbounded dynamics? \n2. Overall Stable-ChebNet indeed achieves superior results on the synthetic long-range interaction datasets, but how can these findings translate to actual real-world datasets? The results from the long-range benchmark peptides dataset show that it can match the performance there, but the advantage over e.g. simple GCN is small. Do these results not suggest that we should just use more powerful methods like S2GCN, combining the two paradigms and be done with it?\n3. Why did you evaluate ChebNet only on these three real-world datasets and did not include comparisons on standard homophilic node classification, the heterophilic datasets from Platanov et al. [3] and for the ones from OGB also on ogbn-products and some graph property prediction tasks? This would significantly simplify the inclusion of ChebNet as a standard baseline in future work.\n4. The Barbell graph describes an extremely artificial scenario, which limits the transferability of these findings to real-world graphs. Could you elaborate further on how such a graph could arise in real-world scenarios?\n5. Did you consider the findings and discussions from [1]? There has recently been a lot of discussion about fair and comparable evaluation of GNNs. They show that in many papers the baselines are not properly tuned. Do you think there is a similar issue with ChebNet, and did you use a similar approach? Or if not, could you use the ideas from [1] to improve the results of ChebNet even further (e.g. adding layer/batch norm)?\n\n[1] Luo et al., Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification, NeurIPS 2024 Track on Datasets and Benchmarks\n\n[2] Bamberger et al., Bundle Neural Network for message diffusion on graphs, ICLR 2025\n\n[3] Platonov et al. A critical look at the evaluation of GNNs under heterophily: Are we really making progress?, ICLR 2023", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n- Paper is well-written, well-structured and most visualizations are helpful and clear.\n- There are both theoretical and empirical validation for the claims made.\n- The authors have successfully identified and filled a niche in the GNN literature/benchmarking. ChebNet is indeed often omitted as a baseline in the literature.\n- It is clearly communicated why ChebNet should be included as a baseline in the future, especially on longe-range interaction graphs.\n\n**Weaknesses**\n1. Experiments are somewhat limited. The full results on LRGB and OGB could be provided.\n2. Generally, the choice of methods to compare against is inconsistent. For example, in Table 3 and 4, completely different baselines are considered. Additionally, on long-range interaction tasks, one should also compare against methods like S2GCN or BuNN [2] that were created exactly for this task. Also, more recent experimental settings on standard GNNs like GAT from [1] are omitted, even though these would perform best on ogbn-proteins in the table provided.\n3. The discussion on how to proceed based on these findings could be more pronounced. Yes, SpectralGNNs are strong baselines, but still if you look at the leaderboards of the benchmarks, e.g. on the OGB datasets, you don’t find any pure GNN approach anymore. How could this trend be changed?\n4. Figure 5 and Table 2 seem to show the exact same information. Why were there no other baselines included that were constructed to work well for long-range interactions?", "was_revised": true, "final_justification": "Overall, the authors have addressed the concerns raised well, and the announced changes will further enhance the quality of the paper.\n\nThe main weakness of the paper lay in its empirical evaluation, which was initially insufficient for a practitioner to gain a clear understanding of the model’s overall performance. In the rebuttal, the authors provided additional results on both real and synthetic datasets, which substantially strengthened this aspect. In particular, for long-range datasets, I fully agree with the authors’ claim that (Stable-)ChebNet demonstrates a consistent advantage across a broad spectrum of tasks, underscoring its general practical relevance. Moreover, the results on other benchmark datasets provide clear indications that (Stable-)ChebNet can perform competitively in a wider range of scenarios.\n\nAlthough certain points of discussion remain between the reviewer and the authors, particularly regarding benchmarking and the identification and assessment of long-range interactions, the overall benefits for the community are clear. Taking into account the discussion and the announced improvements, I therefore recommend accepting the paper.", "rebuttal": "We sincerely thank the reviewer for their encouraging feedback. We appreciate the recognition of the clarity and utility of our visualizations. We are also grateful for the acknowledgement of our theoretical and empirical contributions, as well as our effort to address a gap in GNNs.  Below, we address the reviewer’s comments in detail.\n\n**Clarifying the model’s figure:**  We apologize for the confusion around Figure 1;  To clarify, in this figure we plot at each layer the temperature of each node—by which we mean the ‘heat’ or magnitude of its signal—propagated through the filter. In the classical ChebNet (top row), high‑order Chebyshev filters act like a dissipative diffusion: by step T, most nodes have “cooled” almost to zero (very low temperature), indicating that information has effectively leaked away and that small perturbations can blow up or vanish uncontrollably—i.e. unbounded dynamics. In contrast, our Stable ChebNet (bottom row) enforces an antisymmetric, non‑dissipative update so that heat (information) is retained even at large T, yielding bounded, well‑conditioned propagation across layers. The main aim of this figure was to shed light on the importance of developing an information-preserving system by drawing an analogy to heat dissipation. We agree that “temperature” was not defined clearly in the original caption, and we’ll incorporate exactly this explanation in the corrected version.\n\n**Comparison with S2GCN and real world setting:** Although DRew and S2GCN achieve high AP on Peptides‑func, they both depend on expensive graph preprocessing steps: DRew must perform costly graph rewiring (e.g. all‑pairs shortest paths plus positional encoding construction) before training, while S2GCN requires a full Laplacian eigendecomposition for its spectral filter basis. These operations impose prohibitive runtime and memory overhead on large or evolving graphs. \nBy contrast, Stable‑ChebNet delivers competitive long‑range accuracy entirely within the standard Chebyshev‑polynomials which approximate the Laplacian eigendecomposition: each layer executes sparse, polynomial‑filter updates in O(K·|E|) time, without any rewiring, eigencomputations, or additional encodings. This keeps training times and memory costs on par with a vanilla ChebNet, preserves end‑to‑end differentiability, and requires no extra implementation complexity, making Stable‑ChebNet both practically scalable and straightforward to deploy. The cost of using ChebNet compared to DRew is highlighted in Figure 2, which further motivates the need for a performant ChebNet on long-range tasks given its simplicity. \n\nWhile the community still lacks gold‑standard long‑range GNN benchmarks, we evaluated Stable‑ChebNet in complementary scenarios covering both graph and node-level tasks to demonstrate its applicability on real‑world and synthetic data. On the Peptides‑func benchmark, which highlights distant residue interactions, Stable‑ChebNet is on par with sota methods. On the OGB‑Proteins dataset where graphs can exceed 100k nodes, it achieves accuracy on par and often better than Graph Transformers, proving that stable information can compete with Transformers and other models of high complexity.\n\n**Testing on a newly released benchmark:** We note that very recently, Liang et al. [4] publicly released City‑Networks, a large‑scale transductive benchmark designed explicitly to probe long‑range dependencies in GNNs, derived from real-world city road networks.  \n\n Aligned with our findings, the benchmarking results of that paper show (though without detailed analysis) that ChebNet performs well on long-range tasks; it is often the best baseline and has a consistently high influence score, even on Ogbn-arxiv which we also report in our paper. To further validate our model on real-world road networks, we ran our Stable-ChebNet on the Paris City-Networks data and compared it to vanilla ChebNet in the Table below. \n\n| # of Layers (L) | K (Hops) | ChebNet (%)      | Stable-ChebNet (%)  |\n|-----------------|----------|------------------|---------------------|\n| 2               | 10       | 39.96 ± 0.04     | 49.52 ± 0.12        |\n| 3               | 10       | 47.16 ± 0.08     | 51.22 ± 0.07        |\n| 3               | 12       | 47.39 ± 0.12     | 51.28 ± 0.28        |\n\nThese results underscore Stable‑ChebNet’s ability to capture long‑range dependencies in both synthetic and large‑scale real‑world settings using parameter‑efficient operations.\n\n**Additional benchmarks:** In line with the reviewer’s suggestion, we will additionally include results for the Bundle Neural Network (BuNN) from Bamberger et al. [2] across the common benchmarks, allowing for a more comprehensive comparison. In addition, we would like to clarify that our submission already includes a set of Graph Property Prediction tasks, namely Diameter, SSSP, and Eccentricity, designed to test long‑range information propagation (see Section 4 and Table 1). We believe these tasks are important to evaluate the long‑range capabilities of GNNs. \n\n**On the inclusion of heterophilic datasets:** We agree that examining the relationship between label heterophily and long‑range dependency is valuable. \nIn this work, we do not benchmark on common heterophilic datasets as we believe there is not yet a clear connection between a graph being heterophilic and the presence of long-range dependencies — the latter being the main challenge this paper aims to address. One recent position paper sheds light on this issue [5], emphasizing that heterophily and long-range dependencies are not inherently linked as a graph can be heterophilic and require only local reasoning, or homophilic and require long-range reasoning.\n\nTo further investigate this phenomenon, we have followed your recommendation and trained ChebNet and Stable‑ChebNet on the Roman‑Empire and Amazon‑Ratings datasets using the hyperparameters from Platonov et al. [3]. We find that both vanilla ChebNet and Stable-ChebNet can indeed match the highest performances reported in the Table with updated MPNN performances. Interestingly, we find that on both Amazon-Ratings and Roman-Empire, we converge towards higher performances at relatively lower hop neighborhoods, indicating a more local aspect to these heterophilic graphs. \n\n**Dataset: Amazon-Ratings**\n| K | L | Stable-ChebNet |\n|---|---|---------------|\n| 4 | 4 | 53.80 ± 0.32  |\n| 3 | 4 | 54.17 ± 0.11  | \n| 3 | 5 | 54.24 ± 0.23  |\n\n\n**Dataset: Roman-Empire**\n|  K  |  L  |     ChebNet      |       Stable-ChebNet       |\n|:---:|:---:|:----------------:|:------------------:|\n|  3  |  7  |  91.26 ± 0.36    |  90.65 ± 1.08      |\n|  5  |  7  |  90.79 ± 1.19    |  89.77 ± 1.06      |\n|  6  |  7  |  84.75 ± 0.35    |  89.03 ± 2.19      |\n\n**Emphasizing the importance of the Barbell dataset:**  While Barbell‐like structures might seem like a purely synthetic scenario, it actually captures a very common challenge in real‑world networks that are not well represented in the GNN community’s long-range benchmarks; One suitable example is two densely interconnected communities joined by just one or a handful of bridging connections. For instance, in infrastructure graphs we might have two urban centers whose local roads are very dense yet connected to each other by just one main highway. In protein‐interaction networks, functional modules such as signaling pathways can be highly interconnected internally, yet communicate with other modules through very few cross‐module interactions. \nThese cases all mirror the barbell topology: high intra‐module cohesion plus a narrow inter‐module bottleneck. This creates exactly the same narrow bottleneck that standard GNNs struggle to traverse without squashing information. Hence, despite its simplicity, the barbell graph provides a useful stress test for how well GNN architectures can propagate information across real‐world “bridge” edges without oversquashing or loss of signal fidelity by just adjusting clique size.\n\n**The Role of Hyperparameter Tuning:** Thank you for your thoughtful suggestion and for pointing us to [1]. We have carefully considered the findings and discussions presented in that work. In fact, we had already examined [1] and noted the improvements in performance achieved through more rigorous hyperparameter tuning and architectural modifications such as the inclusion of additional layers or normalization techniques.\nAt the time of our experiments, we adhered to the benchmark settings commonly used in prior work to ensure a fair and consistent comparison. While we did observe that deeper GNN architectures can lead to performance gains, we consciously operated within a parameter budget to highlight the efficiency of our model. We followed a similar protocol for Peptides func where we were bound to 500k params, above which we could reach near 72 AP on Peptides-func.\n\nIndeed, the improvements reported in [1], especially for GCN and GAT on the OGB-Proteins dataset—come with significantly increased parameter counts (on the order of ~1M and ~3M, respectively). In contrast, our ChebNet-based model uses only ~80K parameters, yet still manages to outperform even the 1M-parameter GCN variant on the same dataset. This demonstrates the effectiveness of our approach under a constrained parameter budget. That said, we acknowledge that incorporating ideas from [1] could further improve our model’s performance and plan to explore these enhancements in future work.\n\nWe sincerely hope that our revisions have effectively addressed your concerns and encouraged a reconsideration of your evaluation and score. \n\n[4] Liang et al. (2025). Towards Quantifying Long-Range Interactions in Graph ML. arXiv preprint https://arxiv.org/abs/2503.09008 \n\n[5] Adrián Arnaiz‑Rodríguez and Federico Errica (2025). Oversmoothing, “Oversquashing”, Heterophily, Long‑Range, and more: Demystifying Common Beliefs in Graph Machine Learning. Position paper published on https://arxiv.org/abs/2505.15547"}, {"review_id": "vYRsANr9GU", "reviewer": "Reviewer_zDKz", "summary": "The paper shows the limitations of the ChebNet framework in propagating information in long range graphs. Specifically, the authors show that as the order of the chebyshev polynomial grows the response function becomes unstable (eigenvalues of the Jacobian exponentially increases). In order to circumvent this issue, the authors propose to restrict the weight matrices to be antisymmetric so as to have imaginary eigenvalues for the Jacobian. This bounds the norm of the Jacobian. In the modified method (Stable-Chebnet) the authors cast the Chebnet as a continuous ordinary differential equation and the layerwise update is obtained using the forward euler method. The method performs comparably to some SoTA methods on synthetic and long range benchmarks.", "questions": "1)\tHow would the method perform on omethods using different basis functions ([1,2]). Would the proposed limitations still exist?\n2)\tSince the paper argues that the limitations of Chebnet arises due to exploding response function with filter order: What if the norms would be constrained after every layer In Chebnet using layernorm, instancenorm etc. How would the method behave in this case? A study might help understand the importance of current method.\n3) Please see weakness section above\n\n[1] Xiyuan Wang, & Muhan Zhang. (2022). How Powerful are Spectral Graph Neural Networks.\n\n[2] Mingguo He, Zhewei Wei, Zengfeng Huang, & Hongteng Xu. (2022). BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n1)\tThe paper provides a novel analysis on ChebNet’s limitations and proposes a solution\n2)\tThe method obtains competitive results over chebnet and current SoTA methods\n3)\tThe paper is well written\n\n**Weaknesses**\n\n1)\tWhile the overall method achieves good results, some studies should be provided on the benefit of the individual components. For example, the authors should provide ablations of their method using only antisymmetric weight, only the forward Euler method etc.\n2)\tThe paper should also provide a study showing ability of the modified chebnet to approximate an arbitrary filter function. It would be interesting to see if it is able to better approximate the filters overcoming limitations of Chebnet here or whether some new limitations are introduced.", "was_revised": true, "final_justification": "The author rebuttal has clarified most of the queries I had. Considering the response and other reviews, I keep my score of accepting the paper.", "rebuttal": "We sincerely appreciate the reviewer’s insightful feedback on our work. Thank you for highlighting our novel analysis of ChebNet’s limitations and our proposed solution, as well as recognizing that our method delivers performance on par with other state‑of‑the‑art approaches. We’re also grateful for your kind words about the clarity and quality of our writing. Your comments and score motivate us to further strengthen and refine this research. Below, we address the reviewer’s comments in detail.\t\n\n**Extension to different basis functions:** Thank you for the insightful question. In this work, we focused on ChebNet due to its historical significance as the most well-known and widely used spectral GNN model. That said, a formal extension of our theoretical analysis to alternative bases (such as the ones discussed in [1,2]) would require revisiting the spectral norm and Jacobian dynamics in those settings. While we expect similar dynamics to emerge, a comprehensive treatment is outside the scope of this paper and is an exciting direction for future work. In theory, the non-dissipative aspect should generalize to other basis though we leave the analysis for separate work. Only then it would be interesting to address heterophily and compare different basis' ability to tackle a long-range, heterophilic graph given their ability to both propagate information in a stable manner and tackle different frequency levels depending on their filter properties which would prompt an interesting comparison across spectral basis (e.g Bernstein vs ChebNet).\n\n**Model behavior under normalization:** We appreciate the reviewer’s suggestion and agree that applying normalization techniques such as LayerNorm or InstanceNorm could help alleviate some of the instabilities observed in high-order ChebNet by implicitly bounding feature magnitudes. However, we would like to emphasize that the internal mechanisms of such normalization layers are complex, often dataset-dependent, and their stabilizing effect on model dynamics is not fully understood from a theoretical standpoint. In contrast, our proposed approach, based on Euler discretization and antisymmetric parameterization, is a principled and interpretable framework for enforcing stability, with formal guarantees on the Jacobian spectrum and resulting signal propagation properties of the model. That said, we agree that further comparison would be valuable. We will include a brief discussion of this point in the revised version of the paper, and we plan to investigate the empirical effect of normalization-based strategies as part of our camera-ready submission or future work.\n\n**Isolation antisymmetric effect:** Thank you for the insightful suggestion regarding component ablations. Following your recommendation, we conducted an additional experiment on the OGB‑Proteins benchmark to isolate the effect of antisymmetric weights in our model. Specifically, we evaluated a variant that enforces antisymmetry but omits the forward‑Euler discretization. This “antisymmetry‑only” model resulted in a significantly lower performance (72.2% test accuracy) compared to the full Stable‑ChebNet (79.5%), highlighting the importance of combining both antisymmetry and the discretization scheme for effective learning.\n\n| Model Variant           | Test Accuracy on OGB-Proteins |\n|-------------------------|-------------------------------|\n| Full Stable-ChebNet     | 79.5%                         |\n| ChebNet-Antisymmetry Only       | 72.2%                         |\n\n**On Stable-ChebNet’s ability function approximation ability:** We appreciate the reviewer addressing this concern. However, this point is not directly applicable to our method, as Stable-ChebNet does not alter the basis functions or the parameterization of the spectral filters used by ChebNet. The modification we propose applies solely to the propagation dynamics (i.e., how information flows through layers), by introducing a stable ODE-inspired formulation. As such, the filter expressivity and approximation capacity remain unchanged. We will make this clarification more explicit in the revised manuscript to avoid confusion on this point.\n\nWe sincerely hope that our responses and revisions have addressed your concerns. We once again thank the reviewer for their valuable time and consideration."}, {"review_id": "DSBWgBRtEd", "reviewer": "Reviewer_EiU1", "summary": "The authors note that the early ChebNet spectral GNN has surprisingly good capabilities for modeling long-range interactions on graphs. They revisit ChebNet and uncover that it suffers from an unstable behaviour during training. The authors are therefore proposing stable variants of ChebNet, that obtain competitive and state-of-the-art results on their empirical evaluation.", "questions": "- Please see the \"Weaknesses\" sections above.\n\n- Did the authors also consider performing experiments with positional encodings (such as LapPE or RWSE)? The computation overhead is minimal, and I wonder if they could obtain further performance gains with this. This could also be an interesting and \"low-hanging\" addition to Table 5, since peptides-func normally benefits from positional encodings.", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n\n1. The paper is well-written and easy to follow.\n2. The paper continues a recent line of research where spectral models are reassessed for their effectiveness in modeling long-range interactions, with a notable related example being the Spatio-Spectral GNN [[1]]. I believe that this line of work (and the broader analysis of the behaviour of signals and weights of GNNs) is an important and promising direction going forward.\n3. To my knowledge, this is the first paper that re-evaluates the performance of an overlooked model like ChebNet and demonstrates its competitiveness on tasks that are difficult for message-passing GNNs.\n4. The design choices behind Stable-ChebNet are principled and well-justified. The authors also connect their approach to neural networks inspired by differential equations and provide theoretical support.\n5. Stable-ChebNet performs well compared to MPNNs, Graph Transformers, and rewiring-based methods, particularly given that it does not rely on positional encodings.\n\n**Weaknesses**:\n\n1. The greatest weakness is that the empirical evaluation section is somewhat lacking. The paper would have been stronger if datasets that are not considered \"long-range\" were included, or even other datasets from the LRGB (such as PCQM-contact). Moreover, some datasets that are common when discussing long-range capabilities and over-squashing are also omitted (such as NeighborsMatch from [[2]]). The node-level datasets are also lacking, with only ogbn-proteins and ogbn-arxiv being used in the empirical evaluation. Since Stable-ChebNet improves signal propagation, I am wondering if it could also obtain better performance on heterophilic datasets, such as the ones introduced in [[3]].\n2. Figure 1 is confusing and not very informative, especially in the context of the introduction. I suggest the authors clarify the figure's purpose and consider moving it to a later section.\n3. The related work discussion is not fully fleshed out. Although Section 2 (\"Background\") mentions prior work, the coverage of spectral methods, rewiring strategies, and Graph Transformers is limited. The paper also shares conceptual connections with recent sequential and state-space models, such as [[4]], which explore similar ideas from a signal processing perspective. I recommend expanding the related work section in the appendix and, if space allows, in the main text.\n\n**Conclusion:**\n\nOverall, I believe that this is a good paper and should be accepted. However, my initial score is 4 (borderline accept). I will update my score to a 5 (accept) if the authors expand their empirical evaluation and address some of the other weaknesses I raised. Please note that I will not lower my score if the additional experiments turn out to be weak, since negative results would also be very informative, and the paper currently contains a good amount of strong results. I believe that the paper, the core idea, and the direction of research are strong, even if some results do not reach state-of-the-art performance. That said, the current empirical results are not sufficient for a practitioner or researcher to form a clear understanding of the model's overall performance.\n\nI may further update my score depending on the comments and opinions of the other reviewers, particularly if they raise points that I strongly agree with or that significantly influence my assessment.\n\n\n[1]: https://arxiv.org/abs/2405.19121\n[2]:https://arxiv.org/abs/2006.05205\n[3]:https://arxiv.org/abs/2302.11640\n[4]:https://arxiv.org/pdf/2303.06349", "was_revised": true, "final_justification": "The authors have significantly improved their experimental evaluation section by adding new real-world and synthetic datasets. Moreover, the authors were very active during the rebuttal and have responded well to the concerns raised by all reviewers.", "rebuttal": "Thank you for the thoughtful and encouraging feedback. We appreciate the recognition of our clear writing, the importance of revisiting spectral methods for long-range interactions, and our novel re-evaluation of ChebNet. We're grateful for the acknowledgment of our principled design of Stable-ChebNet—its theoretical grounding, simplicity, and strong empirical performance without positional encodings. Your insights have been valuable in refining the paper. Below, we address your comments and outline our revisions. \n\nWe thank the reviewer for their thoughtful feedback and valuable suggestions regarding the empirical evaluation section.\n\n**On node-level tasks:** We would like to clarify that, although it may not have been sufficiently emphasized in the original submission, our evaluation already includes several node-level prediction tasks. Specifically, the synthetic tasks—SSSP, Eccentricity, and the Barbell task—are formulated as node-level tasks, where the goal is to predict scalar values at each node. The only graph-level benchmarks in our evaluation are LRGB and the Diameter dataset in the GraphProp tasks, which we included to complement the node-level analyses.\n\n**Tree-NeighborsMatch dataset:** In response to the reviewer’s helpful suggestion, we have now included results on the Tree-NeighborsMatch, a dataset commonly used to assess long-range information propagation and over-squashing [2]. Up until a depth of 4, we can reach an accuracy of 100% with both Stable ChebNet and vanilla ChebNet. At depth 5, we reach 65% with vanilla ChebNet alone, which is already better than most baselines. Given the timeline of the rebuttal and the intense runtime at depths higher than 4, we were not able to run until depth 8 of this dataset, but we are happy to include them in the revised version. We expect that around depth 5 or 6, ChebNet will collapse while Stable ChebNet will persist as in the case of the Barbell task. \n\n**On the inclusion of heterophilic datasets:** We appreciate the suggestion to explore how label heterophily connects with long‑range dependency. In this work, however, we did not include standard heterophilic benchmarks, since there is currently no established correspondence between a graph’s heterophily and the need for long‑range information propagation—the latter being our primary focus. In fact, a recent position paper [5] argues that heterophily and long‑range reasoning are not inherently linked: the authors give examples of graphs that may exhibit strong heterophily yet only demand local feature aggregation, or conversely be highly homophilic but require messages to traverse many hops. \n\nTo address your point empirically, we have now retrained both ChebNet and our Stable‑ChebNet model on the Roman‑Empire and Amazon‑Ratings datasets, using the hyperparameter settings from Platonov et al. [3]. Encouragingly, both models reach performance on par with the best updated MPNN results reported in the paper, while noting that the hyperparameter tuning was not extensive and it is possible that we could reach even higher results. An interesting observation from the tables below is the fact that even at a higher receptive field K, the degradation of Stable-ChebNet’s signal is less than that of ChebNet, as can be seen at K=6 for the Roman Empire dataset. \n\n**Dataset: Amazon-Ratings**\n| K | L | Stable-ChebNet |\n|---|---|---------------|\n| 4 | 4 | 53.80 ± 0.32  |\n| 3 | 4 | 54.17 ± 0.11  | \n| 3 | 5 | 54.24 ± 0.23  |\n\n**Dataset: Roman-Empire**\n|  K  |  L  |     ChebNet      |       Stable-ChebNet       |\n|:---:|:---:|:----------------:|:------------------:|\n|  3  |  7  |  91.26 ± 0.36    |  90.65 ± 1.08      |\n|  5  |  7  |  90.79 ± 1.19    |  89.77 ± 1.06      |\n|  6  |  7  |  84.75 ± 0.35    |  89.03 ± 2.19      |\n\n**Further validation on a newly released benchmark:** We extend our evaluation to the recently published City‑Networks benchmark by Liang et al. [4], which comprises large-scale, transductive tasks based on real-world urban road networks and is specifically designed to test GNNs’ ability to capture long-range dependencies. \nThe benchmarking results of that paper align with our findings and show (though without detailed analysis) that ChebNet performs well on long-range interactions given that it is often the best baseline and has a consistently high influence score, even on Ogbn-arxiv which we report in our paper. To further validate our model on real-world road networks, we ran our Stable-ChebNet on the Paris City-Networks data and compared it to vanilla ChebNet in the Table below. \n\n| # of Layers (L) | K (Hops) | ChebNet (%)      | Stable-ChebNet (%)  |\n|-----------------|----------|------------------|---------------------|\n| 2               | 10       | 39.96 ± 0.04     | 49.52 ± 0.12        |\n| 3               | 10       | 47.16 ± 0.08     | 51.22 ± 0.07        |\n| 3               | 12       | 47.39 ± 0.12     | 51.28 ± 0.28        |\n\nThese results highlight Stable‑ChebNet’s effectiveness in capturing long-range dependencies across both synthetic and large-scale real-world scenarios, all while maintaining parameter efficiency.\n\n**Clarifying Figure 1:** We apologize for the confusion surrounding Figure 1. This figure shows, at each layer, the \"temperature\" of each node—that is, the magnitude (or \"heat\") of its signal after being processed by the filter. In the classical ChebNet (top row), high-order Chebyshev filters behave like a dissipative diffusion process: by step T, most nodes have nearly \"cooled\" to zero, meaning that their signals have diminished significantly. This indicates that information dissipates over layers, leading to unbounded dynamics where small perturbations may grow uncontrollably or vanish. In contrast, our Stable ChebNet (bottom row) uses an antisymmetric, non-dissipative update rule that preserves signal magnitude even at large T. As a result, information remains stable and well-conditioned throughout the layers. We acknowledge that \"temperature\" was not clearly defined in the original caption and will include this explanation in the revised version.\n\n**Expanding the Related Work Discussion:** We appreciate the reviewer’s suggestion and will substantially enrich our discussion of rewiring strategies and Graph Transformers in the revision. In the main text’s Background section, we will introduce a broader spectrum of rewiring techniques and transformer-based graph architectures, highlighting how each approach addresses long-range dependency challenges. In particular, we will emphasize methods such as DRew for which we already include comparative runs alongside the benchmarked baselines in our tables. Several relevant transformer-based models are also represented in our main tables, including SPEXFormer, Exphormer, TIGT, and SAN+LapPE. These models reflect a range of strategies for overcoming long-range dependency and over-squashing issues in graph learning, and we will more clearly articulate how our approach relates to them. A more comprehensive comparison will be provided in the appendix, with key insights integrated into Section 2 where space allows.\n\n**Effect of Positional Encoding (and Virtual Node):** We did in fact extend our peptide‑function experiments with both Laplacian positional encodings (LapPE) and random‑walk structural encodings (RWSE), but found that neither led to gains—instead, accuracy dipped by roughly 1–2 points and per‑epoch training time increased by 20–30 percent. We suspect two main factors: first, ChebNet’s polynomial filters already capture much of the same spectral information that LapPE explicitly provides, so appending handcrafted eigenvector features can introduce redundancy or even noise, leading to slight overfitting on small peptide graphs. Second, computing LapPE via partial eigendecomposition (and RWSE via truncated walk statistics) incurs nontrivial overhead—especially on batches of variable‑size peptide graphs—so the resulting slowdown outweighs any marginal benefit. Given these findings, we opted not to include positional encodings in our main table, but we will add a brief note in Table 5’s caption summarizing that neither LapPE nor RWSE improved peptide‑function performance and that both incurred noticeable computational cost.\n\nFurthermore, in our preliminary experiments on the Peptides-func graph-level task, incorporating a Virtual Node did not lead to improved model performance, nor did the addition of positional encodings. We attribute this to the fact that both Stable-ChebNet and its vanilla version already capture the graph structure effectively and possess a sufficiently large receptive field, rendering the global Virtual Node largely redundant. The results, presented in the table below, show that the Virtual Node offers more benefit to GCN than to Stable-ChebNet.\n\n| Model                  | Accuracy on Peptide-Func      |\n|------------------------|-------------------------------|\n| GCN                    | 68.60 ± 0.50                  |\n| GCN + VN               | 69.21 ± 0.25                  |\n|  Stable-ChebNet                | 70.32 ± 0.26                  |\n| Stable-ChebNet + VN    | 69.73 ± 0.33                  |\n\nWe sincerely hope that our clarifications and revisions have addressed your concerns and prompted a reconsideration of your evaluation and score. We thank again the reviewer for their time and consideration.\n\n[4] Liang et al. (2025). Towards Quantifying Long-Range Interactions in Graph ML. arXiv preprint https://arxiv.org/abs/2503.09008 \n\n[5] Adrián Arnaiz‑Rodríguez and Federico Errica (2025). Oversmoothing, “Oversquashing”, Heterophily, Long‑Range, and more: Demystifying Common Beliefs in Graph Machine Learning. Position paper published on https://arxiv.org/abs/2505.15547"}, {"review_id": "45lNCDPc8Q", "reviewer": "Reviewer_XzyD", "summary": "This paper revisits ChebNet, a classical spectral Graph Neural Network (GNN), and proposes a stabilized variant, Stable-ChebNet, for long-range graph tasks. The authors analyze the instability of high-order Chebyshev polynomial filters using a continuous-time ODE interpretation and propose antisymmetric weight parameterizations with dissipative terms to mitigate gradient explosion. Empirical evaluations on long-range benchmarks such as LRGB and OGB show that Stable-ChebNet achieves strong performance, competitive with or exceeding attention-based graph Transformers and rewiring techniques. While the approach is grounded in classical spectral theory, it is presented with modern theoretical and empirical rigor.", "questions": "- How does Stable-ChebNet compare in performance and scalability to recent models using hierarchical self-attention [1], multiresolution message passing [2, 3] or virtual node [4]?\n\n- Would integrating learnable hierarchies or dynamic clustering (as in adaptive attention or pooling-based GNNs) [2] further enhance ChebNet’s capacity for long-range dependency modeling?\n\n- Could the antisymmetric formulation be extended to more expressive spectral bases such as graph wavelets or multiresolution spectral domains [5, 6]?\n\nReferences:\n\n[1] Thuan Nguyen Anh Trang, Khang Nhat Ngo, Hugo Sonnery, Thieu Vo, Siamak Ravanbakhsh, Truong-Son Hy, Scalable Hierarchical Self-Attention with Learnable Hierarchy for Long-Range Interactions, Transactions on Machine Learning Research (TMLR). URL: https://openreview.net/pdf?id=qH4YFMyhce\n\n[2] Truong-Son Hy and Risi Kondor, Multiresolution Equivariant Graph Variational Autoencoder, Machine Learning: Science and Technology, Volume 4, Number 1, DOI 10.1088/2632-2153/acc0d8. URL: https://iopscience.iop.org/article/10.1088/2632-2153/acc0d8\n\n[3] Nhat Khang Ngo, Truong-Son Hy, and Risi Kondor, Multiresolution Graph Transformers and Wavelet Positional Encoding for Learning Long-Range and Hierarchical Structures, Journal of Chemical Physics, Volume 159, Issue 3, DOI 10.1063/5.0152833. URL: https://pubs.aip.org/aip/jcp/article/159/3/034109/2903066/Multiresolution-graph-transformers-and-wavelet\n\n[4] Chen Cai, Truong-Son Hy, Rose Yu, and Yusu Wang, On the Connection Between MPNN and Graph Transformer, ICML 2023, Proceedings of Machine Learning Research 202:3408-3430. URL: https://proceedings.mlr.press/v202/cai23b/cai23b.pdf\n\n[5] Truong-Son Hy and Risi Kondor, Multiresolution Matrix Factorization and Wavelet Networks on Graphs, ICML 2022 (Workshop on Topology, Algebra, and Geometry in Machine Learning), Proceedings of Machine Learning Research 196:172-182. URL: https://proceedings.mlr.press/v196/hy22a/hy22a.pdf\n\n[6] Truong-Son Hy, Viet Bach Nguyen, Long Tran-Thanh and Risi Kondor, Temporal Multiresolution Graph Neural Networks For Epidemic Prediction, ICML 2022 (Workshop on Healthcare AI and COVID-19), Proceedings of Machine Learning Research 184:21-32. URL: https://proceedings.mlr.press/v184/hy22a/hy22a.pdf", "limitations": "- The proposed approach focuses narrowly on stabilizing ChebNet rather than expanding its expressiveness. By contrast, several recent works have introduced architectural innovations for long-range modeling (please see the references above).\n\n- Stable-ChebNet assumes a fixed graph structure and does not address dynamic graphs or graphs with evolving topologies.\n\n- The long-range benchmarks used still rely on synthetic or curated datasets; performance in realistic, noisy, or application-specific domains (e.g., biological networks or scientific simulations) is untested.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Rigorous theoretical motivation, interpreting ChebNet as a dynamical system and identifying stability issues.\n\n- Efficient implementation that avoids heavy architectural modifications or positional encodings.\n\n- Solid benchmark results on long-range tasks.\n\n- Reintroduces a classical method with modern improvements, offering a computationally lighter alternative to Transformers.\n\nWeaknesses:\n- The work does not sufficiently engage with recent advances in long-range modeling using adaptive attention and multiscale architectures such as hierarchical self-attention [1], multiresolution message passing [2], multiresolution graph transformers [3], and virtual node [4].\n\n- The analysis assumes linear activations and simplified training dynamics, which may not reflect real-world performance under nonlinearity and optimization noise.\n\n- There is no in-depth ablation to isolate the benefits of antisymmetric weights and the dissipative term.\n\nReferences:\n\n[1] Thuan Nguyen Anh Trang, Khang Nhat Ngo, Hugo Sonnery, Thieu Vo, Siamak Ravanbakhsh, Truong-Son Hy, Scalable Hierarchical Self-Attention with Learnable Hierarchy for Long-Range Interactions, Transactions on Machine Learning Research (TMLR). URL: https://openreview.net/pdf?id=qH4YFMyhce\n\n[2] Truong-Son Hy and Risi Kondor, Multiresolution Equivariant Graph Variational Autoencoder, Machine Learning: Science and Technology, Volume 4, Number 1, DOI 10.1088/2632-2153/acc0d8. URL: https://iopscience.iop.org/article/10.1088/2632-2153/acc0d8\n\n[3] Nhat Khang Ngo, Truong-Son Hy, and Risi Kondor, Multiresolution Graph Transformers and Wavelet Positional Encoding for Learning Long-Range and Hierarchical Structures, Journal of Chemical Physics, Volume 159, Issue 3, DOI 10.1063/5.0152833. URL: https://pubs.aip.org/aip/jcp/article/159/3/034109/2903066/Multiresolution-graph-transformers-and-wavelet\n\n[4] Chen Cai, Truong-Son Hy, Rose Yu, and Yusu Wang, On the Connection Between MPNN and Graph Transformer, ICML 2023, Proceedings of Machine Learning Research 202:3408-3430. URL: https://proceedings.mlr.press/v202/cai23b/cai23b.pdf", "was_revised": true, "final_justification": "I have read the authors' rebuttal as well as other reviewers' comments. I appreciate that the authors have conducted more experimental results based on my suggestions. I decided to keep my original rating as borderline accept.", "rebuttal": "We thank the reviewer for raising these insightful and technically relevant questions. We appreciate the opportunity to clarify the positioning of Stable-ChebNet with respect to recent advancements in hierarchical and attention-based GNN architectures. Below, we provide a detailed discussion on the comparative aspects regarding performance, scalability, and potential extensions of our model through integration with learnable hierarchies or dynamic clustering mechanisms. \n\n**Performance comparison:**  The common dataset we share with the mentioned references is the Peptides dataset of Long Range Graph Benchmark (LRGB). Below we provide a comparative analysis that we would be happy to add in a revised version, especially given that Multi-Resolution Graph Transformers and Wavelet Positional Encodings make interesting benchmarks for our case. \n\nIn terms of performance, StableChebNet has an overall comparative performance to the Multi-Resolution Graph Transformer [3], as the latter shows a better performance in the regression task of Peptides-struc, while our model’s advantage is in the classification task of Peptides-func. \n\n| Model             | Peptides-func (AP ↑) | Peptides-struct (MAE ↓) |\n|------------------|----------------------|--------------------------|\n| Sequoia + RWPE   | 0.6755 ± 0.0074       | **0.2453 ± 0.0006**      |\n| Sequoia + LapPE  | 0.6323 ± 0.0042       | 0.2526 ± 0.0019          |\n| MGT + LapPE      | 0.6728 ± 0.0152       | 0.2488 ± 0.0014          |\n| MGT + RWPE       | 0.6709 ± 0.0083       | 0.2496 ± 0.0009          |\n| MGT + WavePE     | 0.6817 ± 0.0064       | **0.2453 ± 0.0025**      |\n| Stable-ChebNet   | **0.7032 ± 0.0026**   | 0.2542 ± 0.0030          |\n\nMoreover, in our earlier experiments with the Peptides-func graph-level task, introducing a Virtual Node did not enhance our model’s performance, nor did the inclusion of positional encodings. We believe a potential reason for that is the fact that Stable-ChebNet and its vanilla counterpart already account well enough for the graph’s structure and cover a wide-enough receptive field that makes a global Virtual Node more redundant. We report the findings in the Table below, where we notice that a VN is more valuable for a GCN than for Stable ChebNet. \n\n| Model                  | Accuracy on Peptide-Func      |\n|------------------------|-------------------------------|\n| GCN                    | 68.60 ± 0.50                  |\n| GCN + VN               | 69.21 ± 0.25                  |\n|  Stable-ChebNet                | 70.32 ± 0.26                  |\n| Stable-ChebNet + VN    | 69.73 ± 0.33                  |\n\n**Dynamic clustering and scalability:** While making an interesting direction to explore, it is worth noting that Dynamic Clustering methods come with a certain computational cost, whether using adaptive attention or pooling-based GNNs that use Gumbel-Softmax trick for sampling, which might make the choice less plausible.  That being said, in terms of scalability, Stable‑ChebNet offers some advantages over the aforementioned approaches. \nHierarchical attention models could incur O(nlog⁡n) complexity to compute global or multi‑scale attention maps, while Stable‑ChebNet performs only Chebyshev recurrences, yielding strictly O(K∣E∣) work per layer (with K the polynomial order). Similarly, the Multi-Resolution Graph Transformer performs costly precomputations: wavelet bases or Laplacian eigendecompositions that can scale as O(n^3) or require significant storage across scales, whereas our method needs only Chebyshev recurrence approximation the Laplacian eigendecomposition with repeated sparse multiplications. \nWe make a similar point in our response to Reviewer E5Qi, highlighting that, unlike benchmarks such as DRew or S2GCN, our approach avoids expensive pre-processing steps for finding geodesic distances or performing full Laplacian eigendecomposition. Instead, we demonstrate the efficiency of using the Chebyshev approximation as a computationally lightweight alternative, with Stable-ChebNet offering stronger experimental results due to its non-dissipative properties.\n\n**Integrating learnable hierarchies:**  We believe Dynamic Clustering integrations can boost StableChebNet’s performance in task-specific scenarios. One example is graph-level tasks requiring both local AND global context where a notable amount of graph information is “lost” in pooling layers. The integration of hierarchical learning and Dynamic clustering  can be especially beneficial for very large graphs. In that scenario, a suitable approach consists of partitioning a very large graph (as in OGB benchmarks) and performing an **intra then inter-cluster stable propagation**. This strategy benefits from both advantages StableChebNet and dynamic clustering have to offer. For smaller graphs GCN could serve as a better backbone prior to dynamically clustering and learning in hierarchy, to allow for a fair combination of local and global information. This can be seen in the Table above whereby for the smaller Peptide graphs, Virtual Nodes, being one layer of hierarchical learning, had more benefit on top of GCN as compared to Stable-ChebNet which has already accounted for the global picture.\n\nOn the other hand, many node-level tasks require very long-range propagation but do not necessarily benefit from a full global context vector. In that case, dynamic clustering might be counterproductive given the limited improvement and the higher cost of training associated with it. That being said, we believe that the benefit of hierarchical learning and the inclusion of global context vectors prior to classification highly depends on the task under disposal whereas the amount of local and global information needed should be tested. However, we believe this is indeed an interesting direction that should be explored in future extensions. \n\n**On studying temporal graphs :** We thank the reviewer for the insightful suggestion. Indeed handling dynamic and evolving networks is an important challenge in graph learning, especially considering its significance in numerous applications. While Stable-ChebNet focuses on the dynamics within the spatial domain, we agree that integrating it to the temporal setting would be a fascinating direction. Given the broad literature on temporal and dynamic GNNs, and the separate considerations for long-range dependencies in the temporal setting (See [7]) , we believe this would be more suitable for future work. \n\n**Further validation on a newly released benchmark:** We broaden our evaluation to include the recently released City-Networks benchmark by Liang et al. [8], which features large-scale, transductive tasks grounded in real-world urban road networks. This benchmark is specifically designed to assess GNNs' capacity to model long-range dependencies.\n\nThe benchmarking results of that paper align with our findings and show (though without detailed analysis) that ChebNet performs well on long-range interactions given that it is often the best baseline and has a consistently high influence score, even on Ogbn-arxiv which we report in our paper. To further validate our model on real-world road networks, we ran our Stable-ChebNet on the Paris City-Networks data and compared it to vanilla ChebNet in the Table below. \n\n| # of Layers (L) | K (Hops) | ChebNet (%)      | Stable-ChebNet (%)  |\n|-----------------|----------|------------------|---------------------|\n| 2               | 10       | 39.96 ± 0.04     | 49.52 ± 0.12        |\n| 3               | 10       | 47.16 ± 0.08     | 51.22 ± 0.07        |\n| 3               | 12       | 47.39 ± 0.12     | 51.28 ± 0.28        |\n\nThese results highlight Stable‑ChebNet’s effectiveness in capturing long-range dependencies across both synthetic and large-scale real-world scenarios, all while maintaining parameter efficiency.\n\n**On separating anti-symmetry:**  Following the reviewer’s suggestion, we carried out an additional experiment on the OGB‑Proteins benchmark to examine the isolated impact of antisymmetric weights in our model. We tested a variant that enforces antisymmetry but excludes the forward‑Euler discretization. This “antisymmetry‑only” model achieved a notably lower test accuracy (72.2%) compared to the full Stable‑ChebNet (79.5%), emphasizing the crucial role of combining antisymmetry with the discretization scheme for effective learning.\n\n| Model Variant           | Test Accuracy on OGB-Proteins |\n|-------------------------|-------------------------------|\n| Full Stable-ChebNet     | 79.5%                         |\n| ChebNet-Antisymmetry Only       | 72.2%                         |\n\n**Extension to other spectral bases:** Thank you for the thoughtful question. In this study, we chose to focus on ChebNet given its historical importance and its status as one of the most prominent and widely adopted spectral GNN models. While we anticipate that similar dynamics would arise with alternative bases such as graph wavelets and multiresolution spectral domains, formally extending our theoretical analysis to those settings would require a fresh examination of the spectral norm and Jacobian behavior. Providing such a comprehensive analysis is beyond the current scope but represents a promising avenue for future research.\n\nWe genuinely hope that our responses and revisions have resolved your concerns and led you to reconsider your evaluation and score. We once again thank the reviewer for their valuable time and thoughtful assessment.\n\n[7] Marisca et al. (2025). Oversquashing in Spatiotemporal Graph Neural Networks . arXiv preprint https://arxiv.org/abs/2506.15507\n\n[8] Liang et al. (2025). Towards Quantifying Long-Range Interactions in Graph ML. arXiv preprint https://arxiv.org/abs/2503.09008"}]

Author rebuttal:

Meta-review: All reviewers argue to accept this paper, which revisits a spectral approach to graph neural network modelling which was widely considered to be superseded by message passing neural networks and graph transformers. The paper includes novel analysis which motivates a more stable variant of the ChebNet, allowing scaling to greater depth.

There was very extensive discussion during the rebuttal phase, which led to greatly expanded experimental validation on a broader set of benchmarks, establishing the utility of the approach. Multiple reviewers raised their scores. I think this paper will be quite interesting to the community and may lead to broader interest and future work on spectral approaches to GNNs.
Decision: Accept (spotlight)