On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning
Authors: Alvaro Arroyo
Alessio Gravina
Benjamin Gutteridge
Federico Barbero
Claudio Gallicchio
Xiaowen Dong
Michael M. Bronstein
Pierre Vandergheynst
Venue: NeurIPS 2025 poster ()
Keywords: graph neural networks
vanishing gradients
long-range propagation
oversmoothing
oversquashing
Primary area: deep_learning
TL;DR: We show the effects of vanishing gradients on GNNs.

Abstract: Graph Neural Networks (GNNs) are models that leverage the graph structure to transmit information between nodes, typically through the message-passing operation. While widely successful, this approach is well-known to suffer from representational collapse as the number of layers increases and insensitivity to the information contained at distant and poorly connected nodes. In this paper, we present a unified view of on the appearance of these issues through the lens of vanishing gradients, using ideas from linear control theory for our analysis. We propose an interpretation of GNNs as recurrent models and empirically demonstrate that a simple state-space formulation of an GNN effectively alleviates these issues at no extra trainable parameter cost. Further, we show theoretically and empirically that (i) Traditional GNNs are by design prone to extreme gradient vanishing even after few layers; (ii) Feature collapse is directly related to the mechanism causing vanishing gradients; (iii) Long-range modeling is most easily achieved by a combination of graph rewiring and vanishing gradient mitigation. We believe our work will help bridge the gap between the recurrent and graph neural network literature and will unlock the design of new deep and performant GNNs.

On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning
Álvaro Arroyo
Alessio Gravina Benjamin Gutteridge'
Federico Barbero Pierre Vandergheynst"
Claudio Gallicchio Xiaowen Dong'
Michael Bronstein 1.3
University of Oxford
University of Pisa
BATTHYRA
4EPFL
Abstract
Graph Neural Networks (GNNs) are models that leverage the graph structure transmit information between nodes, typically through the peessage-passinggg operation. While widely successful, this approach is well-known to suffer from representational collapse as the number of layers increases and insensitivity to the information contained at distant and poorly connected nodes. In this paper, we present a unified view the appearance of these issues through the lens of vanishing gradients, using ideas from linear control theory for our analysis. We propose an interpretation of GNNs as recurrent models and empirically demonstrate that simple state-space formulation of GNN effectively alleviates these issues no extra trainable parameter cost. Further, we show thcoretically and empirically that (i) Traditional GNNs are by design prone to extreme gradient vanishing even after a few layers; (ii) Feature collapse is directly related to the mechanism causing vanishing gradients; (iii) Long-range modeling most easily achieved by a combination of graph rewiring and vanishing gradient mitigation. We believe our work will help bridge the gap between the recurrent and graph learning literature and unlock the design of new effective models that benefit from both worlds.
1 Introduction
have become a widely used architecture for processing information graph domains. Most GNNs operate via message passing, where infor- mation exchanged between neighboring nodes, giving rise to DeessagePaassigg Neural Networks (MPNNs). Some of the most popular instances of this type of architecture include GCN [67], GAT [01]. GIN [106), and GraphSAGE (56).
Graph Neural Networks (GNNs) 98 45 94
76
17 29
Despite its widespread use, this paradigm also suffers from some fundamental limitations. Most importantly, we highlight the issue of feature collapse (sometimes termed over-smoothing) 779 where feature representations become exponentially similar the number of layers increases, and over-squashing I 100 30, which describes the difficulty of propagating information across faraway nodes, as the exponential growth in node's receptive field results in many messages being compressed into fixed-size vectors. Although these two issues have been studied extensively, and there exists evidence that they are trade-offs of each other [4], there is no unified theoretical framework that explains why architectures that solve these problems work and whether there exists common underlying cause that governs these problems.
In this work, we analyze these issues arising from GNN depth through the lens of vanishing gradients. In particular, we ask several questions regarding the appearance and consequences of this
* Equal contribution. Correspondance to
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

phenomenon in GNNs: (i) How prone are GNNs to gradient vanishing? (ii) What is the effect of gradient vanishing on node feature evolution? (iii) Can preventing vanishing gradients effectively mitigate over-squashing and enable long-range modelling? (iv) Can methods used in the non-linear 61 82 9 and more recently, linear [52 [T recurrent neural network (RNN) literature be effective at dealing with feature collapse and long-range modeling? We answer these questions by providing a novel perspective that bridges the gap between recurrent and graph learning.
Contributions and outline. In summary, the contribu- tions of this work are the following:
In Section B explore the connection between GNNs and recurrent models and demonstrate how classical GNNs are susceptible
phenomenon term extreme gradient vanishing. We propose GNN-SSM, a GNN model that written as a state-space model, allowing for better control of the spectrum of the Jacobian.
In Section we show how vanishing gradients con- tribute to node feature evolution, providing more pre- cise explanation for why GNNs struggle with depth and how node feature collapse emerges via spectral analysis of the layer-wise Jacobians. We show that GNN-SSMs are able to exactly control the rate of collapse of deep representations.
Figure 1: Latent evolution of 2- dimensional node features when pass- ing through layers of GNN-SSM with cig(A) ~ 1. Node states evolve in norm-preserving manner, without col- lapsing or contracting. The blue lines indicate how each node feature evolves acToss layers, i.e., more layers are added. Each circle corresponds to a node's 2D feature. Circles connected by a blue line represent the same node across successive layers. The color of each circle encodes the norm of the node feature, and the vector field indicates di- rection.
In Section[3] we show how vanishing gradients are re- lated to over-squashing. We argue that over squussqush should therefore be tackled by approaches that both per- form graph rewiring and mitigate vanishing gradients.
Overall, we believe that our work provides a new and interesting perspective on well-known problems that occur in GNNs, from the point of view of sequence models. We believe this to be an important observation connecting two very wide yet surprisingly disjoint- - bodies of literature.
2 Background and Related Work
We start by providing the required background on graph and sequence models. We further discuss the existing literature on over-smoothing and over-squashing in GNNs and vanishing gradients in recurrent sequence models.
2.1 Message Passing Neural Networks
Let a graph G be a tuple (V, E) where V is the set of nodes and E is the set of edges. We denote edge from node e V node v E V with (u, v) E E. The connectivity structure of the graph is encoded through an adjacency matrix defined as A E [axx where n is the number of nodes in the graph. We assume that G an undirected graph and that there is set of feature vectors { E Rd with each feature vector being associated with a node in the graph. Graph Neural Networks (GNNs) are functions fe (G. (ha)) ~ y, with parameters trained via gradient descent and y being node-level or graph level prediction label. These models typically take the form of Message Passing Neural Networks (MPNNs), which compute latent representation by composing layers of the following node-wise operation:
(A)) (1(k-))
: (u, E)),
for k = (1, .., K}. where (b)) is permutation intirtatatiioninnianntt aggregation function and (k)) combines the incoming messages from one's neighbors with the previous embedding of oneself to produce an updated representation. The most commonly used aggregation function takes the form
((b(tt)))) (k-1) (u, v) E E}) = Σ b (k-1)
(2)
a

---

where A = D AD and D E Raxn is diagonal matrix where D = Aij. One can also
consider a matrix representation of the features H(*), Ruxxd, Throughout the paper, we will use terms GNN and MPNN interchangeably, and will generally consider the most widely used instance of GNNs, which are Graph Convolutional Networks (GCNs) [67] whose matrix update equation given by:
H
(AH(-"W((-")))
where À (D+I) (A + T) (D 11 is the adjacency matrix with added self connections through the identity matrix I, and o-) is nonlinearity, Our analysis also applies to Graph Attention Networks (GATs) [1OI), where the fixed normalized adjacency is replaced by learned adjacency matrix which dynamically modulates connectivity while preserving the key spectral properties used in our analysis.
2.2 Recurrent Neural Networks
A Recurrent Neural Network (RNN) is function go y, where (x(1)x(())
(()
and y (y(", ,
(K)), where x**) e R is the input vector at time step it and y R ...... .-... is the output vector at time step k, and 9 are learnable parameters. RNNs are designed to handle
sequential data by maintaining a hidden state h(*) E Rd that captures information from previous time steps. This hidden state" allows the network model sequential dependencies in the data. The
update equations for the hidden state of the RNN are as follows:
h (b) a (W,h(k-)) (k-1) W (x))
This type of approach has deep connections with ideas from dynamical systems [9] and chaotic systems [39]. These ideas have become more relevant in recent work [54] [8]. where the nonlinearity in (4) is removed in the interest of parallelization and the ability to directly control the dynamics of the system through the eigenvalues of the state transition matrix W.. We note that these types of approaches are also popular in the reservoir computing litcrature [63]. where the state transition matrix is left untrained and more emphasis is placed on the dynamics of the model.
2.3 The Vanishing and Exploding Gradient Problem
Both RNNs and GNNs are trained using the chain rule. One can backpropagate gradients w.r.. the weights at th layer of K- K-layer GNN RNN
7L 2016
OL
I kmi+1
K
(H(
(5)
(H(K)
HH
2010
where matrix (k) an RNN will contain single state vector. As identified by 822. a major issue training this type of models arises from the product Jacobian, given by:
--
K
(6) =
K
J=
11
-
11 J
(6)
k=++1
In general, we have that if J s X for all layers, then ||J||2 & K This means that require s for gradients to neither explode nor vanish, a condition also known as edge of chaos.
2.4 Over-smoothing, Over-squashing, and Vanishing Gradients in GNNs
Node Feature Collapse and Over-smoothing. GNNs are known not perform well large depths [69]. This issue has been heavily linked with the issue of over-smoothing [18) 80), which describes the tendency of GNNs produce smoother representations as more and more layers are added. In Section 4 we study this issue from the lens of vanishing gradients and show that the performance degradation of GNNs has a much simpler explanation: it occurs due to the norm-contracting nature of GNN updates, which is also intimately related to some notions of smoothing presented in the literature 90
NNote that purposefully maintain the notation for the hidden state as the one in the previous subsection for node features.
WWe elaborate on the definition we use in the paper around over-smoothing as it related to the broader literature in Appendix
3

---

Over-squ.
Over-squashing [00 30, Z was originally introduced as a bottleneck resulting from 'squashing' into node representations amounts of information that are growing potentially exponentially quickly due to the topology of the graph. It is often characterized by the quantity ( /2h (0) being low, implying that the final representation of node u is not very sensitive
the initial representation at some other node v. While the relationship between over-squashing [ we explore this relationship in detail by showing that techniques aimed to mitigate vanishing gradients in sequence models help to mitigate over-squahhing in GNNs.
and vanishing gradients was hinted at by [00, in Section
Vanishing gradients. Vanishing gradients have been extensively studied in RNNs while this problem has been surprisingly mostly overlooked in the GNN community. For detailed discussion on the relevant literature. we point the reader the Appendix FJ We simply highlight that there are works that have seen success in taking ideas from sequence modelling [9]
47 102
10 66
or signal propagation 40 95 and bridging them GNNs, but they rarely have a detailed discussion we show that vanishing gradient mitigation techniques from RNNs seem to be very effective towards the mitigation of feature collapse and over-squashing in GNNs and argue that the two communities have very aligned problems and goals.
on vanishing gradients. In Section 5
3 Connecting Sequence and Graph Learning through State-Space Models
In this section, we study GNNs from a sequence model perspective. We show that the most common classes of GNNs are more prone to vanishing gradients than feedforward or recurrent networks due the spectral contractive nature of the normalized adjacency matrix. We then propose GNN-SSMs, a Saate-spacemmoes model- -insiied construction of a GNN that allows more direct control of the spectrum.
3.1 Similarities and differences between learning on sequences and graphs
The GNN architectures that first popularized deep learning on graphs [1 29 were initially presented as a generalization of Convolutional Neural Networks (CNNs) to irregular domains. GCNs [67] subsequently restricted the architecture (29 to a one-hop neighborhood. While this is still termed "convolutional" (due to weight sharing across nodes), the iterative process of aggregating information from each node's 's neighborhood can also be viewed as recurrent-lic state updates.
If we consider an RNN unrolled over time, it forms a directed path graph feeding into a state node with a self-connection, making it a special case of a GNN. Conversely, node representations in GNNs can be stacked using matrix vectorization, allowing us to interpret GNN layer operations as iterative state updates. This connection suggests that the main difficulty faced by RNNs, namely the vanishing and exploding gradients problem [82], may likewise hinder the learning ability of GNNs. We note, however, that one key difference between RNNs and GNNs is that RNN memory only depends on how much information is dissipated by the model during the hidden state update, whereas GNNs normalize messages by the inverse node degree, which introduces an additional information dissipation step that we will explore in more detail in Section
3.2 Graph convolutional and attentional models are prone to extreme gradient vanishing
Based the previously introduced notion of stacking node representations using the matrix vectoriza- tion operation, we now analyze the gradient dynamics of GNN. In particular, we focus on the gradient propagation capabilities of graph convolutional and attentional models initialization, given their widespread use in the literature. Specifically, we demonstrate that the singular values of the layer-wise Jacobian in these models form highly contractive mapping, which prevents effective information propagation beyond a few layers. We formalize this claim in Lemma 3.1 and Theorem 3.2 and we refer the reader to Appendix for the corresponding proofs.
À ( W be linear GCN layer, where À has eigenvalues (Aa...., An) and w has eigenvalues (pi..... .ag.. Consider the
Lemma 3.1 (Spectrum of layer-wise Jacobian's 's singular values). Lei (())
layer-wise Jacobian à (*)) vec (H(H (H(t-1)) then the squared singular values J given by the
set
x2 pg i I....,m, j L..... ,dz..

---

Theorem 3.2 (Jacobian singular-ve value distribution). Assume the setting of Lemma 3.1 and let W R be initialized with i..d. (0, o²) entries. Denote the squared singular values of the Jacobian by ", Then, for sufficiently large dg the empirical eigenvalue distribution of WW" converges to the Marchenko-Pastie distribution. Then, the mean and variance each "v..s
[[ms]] X2 o²
d2
Var[ X; o² dx-1
(8)
Theorem 3.2
shows that the singular-value spectrum of the Jacobian is modulated by the squared spectrum the normalized adjacency. Since |Λ;] 1 for all eigenvalues of the normal- ized adjacency, the ability of GCNs to propagate gradients is in expectation worse than that of
RNNs MIPs. In particular, iterating these operations causes the majority of the spectrum to shrink to zero more quickly than in classical deep linear [93] or nonlinear (84) networks. Moreover, using sigmoidal activations and orthogonal weights will not push the singular-value spectrum to the edge of chaos as in [84) due to the additional contraction from the adjacency.
The effect of each op- eration on the layer- wise Jacobian is empir- ically demonstrated in Figure 2 which also showcases the contrac- tion effect of the nor- malized adjacency. The figure reveals that even single layer's Jaco- bian exhibits a long tail of squared singular val- ues near zero. This spectral structure leads to ill-conditioned gradient propagation and non-isometric (not norm-preserving) signal dynamics. The same results hold for GATs, the adjacency still exhibits contractive spectral structure despite being learned during training.
GCN-Laner
420
GCN-BeLU
Frequency
Miose
Imnetnary
400
200
00
121
Figure Left: Histogram of eigenvalue modulus of the Jacobian for linear, linear convolutional, and nonlinear convolutional layers. Middle: Vectorized Jacobian for GCN. Right: Vectorized Jacobian for GCN- SSM with cig(A) x 1, (B) 0.1.
Note that to overcome this contraction without altering the architecture, one would have to both set o² in a way that precisely compensates for the normalized adjacency (which can be computationally expensive estimate) and choose the nonlinearity carefully. In the next subsection, we present general, simple, and computationally efficient method to place the Jacobian at the edge of chaos at initialization by writing feature updates in a state-space representation.
3.3 GNN-SSM: Improving the training dynamics of GNNs through state-space models
To allow direct control of the signal propagation dynamics of any GNN, we can rewrite its layer-to- layer update state-space model. Concretely, we express the update
(--1T A H (TT + (N)
A OT (H K)
where we refer to as the state transition matrix and B as the input matrix and F (*), k) as time-varying coupling function which connects each node to some neighborhood. We refer to the model defined in Equation (9) as GNN-SSM. From an RNN perspective, A plays the role of the "memory", in charge of recalling all the representations at each layer at the readout layer, while the neighborhood aggregation plays the role of an input injected into the state via B. In traditional GNNs, this recurrent memory mechanism is absent, these models act in memoryless way: features at one layer do not explicitly store or retrieve past information in the way a stateful model would.
In the state-space view, the eigenvalues of A determine the memory dynamics: large eigenvalues can preserve signals (or, if above unity, cause exploding modes), whereas small eigenvalues quickly
'Here, we deviate from the traditional state-space formalism, which uses A as the state transition matrix, since we use this notation for the adjacency. Further, we employ transposes to increase the resemblance to the traditional SSM updates.
5

---

attenuate them. Meanwhile, B controls which aspects of the node features get injected into the hidden state each step. Because this framework agnostic to the exact coupling function, any MPNN layer can serve as Fo. We showcase the effect of these matrices on the layer-wise Jacobian in Proposition 3.3.
Proposition 3.3 (Effect of state-space matrices). Consider the setting in and I vec(F ( ///a voc(H Let denote the Kronecker product. Then, the norm of the vectorized Jacobian is bounded as:
J E Id2
② 2 2- + Lae X | + B 2
2 12
(10)
The result above shows that the spectrum of the Jacobian is controlled through the eigenvalues of A. If we have that the spectrum of r is around zero, it suffices to have rig(A) = to bring the vectorized Jacobian to the edge of chaos. We empirically validate this in Figure 2
For simplicity and clarity of conclusions, we consider and B to shared across layers and fixed (i.e., not trained by gradient descent) to guarantee the desired properties. To construct A, we first generate a random unitary matrix, which has all eigenvalues on the unit circle, and then scale it to control the spectral radius allowing to design with precise control over the system dynamics. Only the coupling function Fg is optimized. Empirically, we observe that this simpler scheme actually improves downstream performance in some settings. We highlight, however, that this is the most simple instance of a more general framework that aims to incorporate ideas from recurrent processing into GNNs without losing semmutation-qquiiarinnne equivariance. One could easily extend this state-space idea to include more complex gating [61] or other constraints on the state transition matrix (60)
4 How does Extreme Gradient Vanishing affect Over-smoothing?
In this section, we study the practical implications of the mechanism causing vanishing gradients in GNNs in relation to node feature evolution. We show empirically and theoretically how GNN layers acting as contractions make node features collapse to a fixed point. We experimentally validate our points by analyzing Dirichlet energy, node feature norms, and node classification performance for increasing numbers layers. Overall, we believe this section provides a more practical and general understanding of the consequences of extreme vanishing in GNNs by analyzing them from the point of view of their layer-wise Jacobians.
4.1 A contractive GNN leads to node feature collapse
We consider in our analysis GNN layers as in Equation 3 We view a GNN layer as a map fa Rnn T and construct a deep GNN f via composition of layers, i.e. f f= fx Let J, E Rudxnd denote the layer-wise Jacobian of a GNN f. The supremum of the Jacobian (if well-defined) of f over a convex set U' corresponds to the Lipschitz constant II (58), i.e.
fi-
I1 = SUPHeu (H) where by submultiplicatiiity of Lipschitz constants we have that Il Illl < I l.fx We point to the Appendix A.2 for a more detailed explanation of the objects in question. A Lipschitz function f is contractive if Il < 1. We now assume that [| ipp < 1 for all k, meaning that each layer is contraction mapping]
Lemma 4.1 (Banach Fixed Point Theorem (5)). Let be an operator with Lipschitz constant 1. Then for any starting point Xg. the fixed-point iteration Xa+1 = f(xx) converges to the unique fixed point of J at linear rate (1/ (1))))p))
< lll
From Lemma 4.1 above and the extreme gradient vanishing results presented in Section 3.2
can distinguish two cases for contractive GNN layers: (I) With shared layers (as in (31)), repeated applications of the GNN will result in convergence to a unique fixed point; (2) with repeated application of non-shared but highly contracting layers, the overall GNN function will converge to, or very close to, unique fixed point in single forward pass due to the low Lipschitz constant of
$ "An alternative strategy consists computing the matrix eigendecomposition. manually place the eigenvalues where desired, and reconstruct the matrix.
'In our analysis, it is important that the input the GNN is vector in red rather than matrix in good as Jacobians and norms are different for the two cases. For this reason, is important take care in the definitions of these objects.
Note that the analysis holds for any submultiplicative matrix norm.

---

10-1
Acceuroyy (90
SSM, 4g/1
Dinehke
10-4
25
GUN-SSN 8SM
GON
GCN- CONN-Baarr
10-11
505
20-
16
48
Tager
Loneer
Figure 3: Experimental evaluation on Cora for an increasing number of layers. Left: Dirichlet Energy
evolution for different ||A||2- Middle: 2-Dimensional random feature projection evolution with fixed point at zero. Right: Node classification performance.
the overall GNN. Both cases result in convergence towards fixed point as all nodes evolve using common transformations. practice, we observe that node representations tend to collapse to zero norm node state, see Figure 3 To study this further, we consider a GNN update, under the following assumption, which is consistent with the setup in 33:
Lemma 4.2. Consider a GNN layer [K as Equation 3 with non-linearity a such that o()) (e.g. ReL.U or lanh). Then, f(()) O, i.e. 0 is fixed point of f.
Then, we have that node representations will evolve as in Proposition 4.3 presented next.
Proposition 4.3 (Convergence to a unique fixed point.). Let [| ffrr some e > 0 for all
k 1...II L. Then, for H e U Rnd we have that:
I (1 E) | H
(11)
In particular, K - 00, f(H) O.
In other words, in the setting have considered, layers fa. are contractive, their repeated application will monotonically converge to the unique fixed point O, by Lemmas and 4.1 which serves to explain the behavior observed empirically. We note that this is similar to the analysis in [8 but we highlight that our analysis is much more broad, as it applied to number of models beyond GCNs, and only required knowledge of behavior of each layer through the Lipschitz constant. Furthermore. we emphasize the important connection between the Lipschitz constant and the vanishing gradients problem, which are linked through the Jacobian.
The collapse of node features to a single point has been typically described as over-smoothinng In particular, over-smoothing describes the tendency of node features become too similar each other as more layers are added in GNNs [8]. A common way of measuring over-smoothing in GNNs, [9T 90), is via the unnormalized Dirichlet energy E(H) 88 Given a feature matrix H Raxd an unweighted graph G, {H)) takes the form:
E(H) H AH)
Σ (u,e)E
lb., 1
(12)
where A is the unnormalized graph Laplacian (28
The Dirichlet energy measures the smoothness of a signal over a graph and will be minimized when the signal is constant over each node at least when using the unnormalized Laplacian. In Proposition 4.4 we show how the layer-wise Jacobians
relate to the unnormalized Dirichlet energy.
Proposition 4.4 (Contractions decrease Dirichlet energy.). ) Let f a GNN, |E| be the number of edges in G, and H e R
We have the following bound:
K 2 |I llep |||
E((HH)
(13)
In particular, if [[ffellapp (H(H)) - O.
e for some for all k 1... K, then K 00 we have that
This result shows that the energy is directly controlled by the norm of the input signal H and by the contracting effect of the layers ft. The repeated application of contractive layers results in the unnormalized Dirichlet energy being artificially lowered as signals are gradually reduced in norm.
'We offer more precise characterization oh how this relates to the normalized Dirichlet energy of node
features in Appendix E

---

GIN
Gated-GCN
Dirichles Eneerg
10
1000
1024
CalolCCN
2000
500
10/0
1000
10
10a
16
10
Layer
111
Figure 4: Left: Evolution of Dirichlet Energy on the Cora dataset for GIN and Gated-GCN. Right:
Histograms of eigenvalue spectra of layer-to-layer Jacobians for GIN and Gated-GCN.
Important consequences of our theoretical results. 1) The most important takeaway of the analysis above is that vanishing gradients are directly connected to over-smoothing through the Lipschitz constant. In particular, the same mechanism that causes gradient vanishing issues, is responsible for the collapse of all features to a unique zero fixed point (i.e. zero feature collapse) where the Dirichlet energy is minimized. The quick collapse of traditional graph convolutional and attentional models can also be understood from the extreme gradient vamishing result introduced
in Section 3 such, while much of the literature, starting with [80 [8] has attributed over- smoothing to iterative aggregation and convergence to a rank-one subspace, our analysis shows that this phenomenon instead an artifact of representations collapsing to zero. As later noted by [3] (without any formal argument), over-smoothing is not necessarily the cause of performance degradation. Here, we provide a theoretical explanation for the poor performance of MPNNS at large depths, linking it to inherent trainability limitations arising from vanishing (and in some cases exploding) gradients.
2) This result also provides a connection between the study of GNNs and the study of signal propagation (or dynamical isometry) in feedforward networks (93, 86 34] and recurrent neural networks [6] 2 [I. In the dynamical isometry literature, the primary interest is to improve the learning times of deep feedforward networks, whereas the recurrent neural network literature focuses on memory and long-range information retrieval. We highlight that connecting ideas from these fields of study will enable the design of new models that benefit from both worlds, even though these techniques were originally developed with different objectives in mind. This also serves as an explanation for why simple modifications, such as residual connections or normalization, worked in practice to mitigate over-smoothing, given their links to dynamical isometry [107 75).
3)
Finally, we highlight that this result provides an objective evaluation metric to gauge whether GNN will over-smooth or not. We hope that the eigenanalysis of the Jacobian will become a widespread empirical test used for this purpose.
4.2 Empirical validation of theoretical results
To validate the theory above, we perform series of empirical tests. In particular, we check the evolution of the Dirichlet energy, latent vector norms, and node classification accuracy on the Cora dataset as the number of layers of different models is increased. The results are presented in Figure Further, we present additional experiments for different graph structures and models in Appendix D.I. and showcase how several models with edge-of-chaos Jacobians result in no over-smoothing, reinforcing the generality of this result beyond classical MPNNs.
From Figure 3 we see that through the spectrum of the Jacobian, which can, in turn, be modified through the spectrum of A in the GNN-SSM model. Furthermore, this shrinks faster the lower the norm of the Jacobian is, which validates Proposition 444] Beyond a Dirichlet energy analysis of the system, notice that node classification performance does not deteriorate when eig( ()) 1. and improves over simply applying an SSM layer with no modulation of the hyperparameters or a residual connection without gating. The dynamics of the GNN in this setting shown in Figure
exactly control the evolution of the Dirichlet energy of the system
Results for Additional MPNNs. In this section, we have focused on GCN and GAT because their layer operators admit clean characterizations, which makes the analysis mathematically tractable. However, the arguments extend to any GNN, where it suffices to examine the eigenvalues of the layer-
NNte that the case of GCN. is sufficient to scale weight norms to prevent the Dirichlet energy from collapsing to zero with additional layers, as the Dirichlet energy only depends on the maximum eigenvalue of the Jacobian. However, obtaining good performance on node-classification tasks required to transport the whole spectrum to be centred around the edge of chaos to obtain good performance. We elaborate this in App. B
8

---

wise Jacobians. To make this concrete, in Figure we plot (i) histograms of the Jacobian eigenvalues for GIN [106], and GCN [[6], and (ii) the evolution of each model's Dirichlet energy as the number of layers increases. We observe that GIN exhibits occasional outliers with |^| > 1 and Gated-GCN displays a sizeable mass above the unit circle, which indicates unstable dynamies. This perspective helps explain several empirical findings reported in []] the divergence of Dirichlet energy in some architectures follows directly from norm expansion driven by unstable Jacobians, whereas the zero feature collapse seen in GCN and GAT reflects their contraction. Consequently, while not all GNNs oversmooth (some instead become unstable and blow up) the generally poor performance of many GNNs at large depths can be understood through their learning dy dynamics: collapse under contraction (as in GCNs and GATs, especially with ReLUs) or divergence under instability.
5
The Impact of Vanishing Gradients on Over-squashing
In this section, we study the connection between vanishing gradients and over-squashing in GNNs, which fills in the gaps and open questions left in the analysis of 30) 10
5.1
Mitigating over-squashing by combining increased connectivity and non-dissipativity
Over-squashing is typically measured via the sensitivity of a node embedding after & layers with respect to the input of another node using the node-wise Jacobian.
Theorem 5.1 (Sensitivity bounds, (0). Consider a standard MPNN with k layers, where Co is the Lipschitz constant of the activation o, w is the maximal entry-value over all weight matrices, and d is the embedding dimension. For u, E V we have
(k) The
< wd) (O* (O*)
(14)
Th (0)
model
topology
where = c.I A E Raxx is the message passing matrix adopted by the MPNN, and where C and ca are the contributions of the self- celf-connection and aggregation term.
Theorem 5.1 shows that the sensitivity of the node embedding is combination of (i) a term based on the graph topology and (ii) a term dependent on the model dynamics, with over-squashing occurring when the right-hand side of Equation (14 becomes too small. We highlight that this differs from the standard product Jacobian, which arises in RNNs. This is because, in MPNNs, messages are scaled by the inverse node degree, incurring an extra information dissipation step. Consequently, while recurrent architectures only need to adjust their dynamics to ensure long memory, MPNNs must simultaneously enhance graph connectivity and modify their dynamics to mitigate vanishing and exploding gradients.
Even though the sensitivity bound in Theorem 5.1 is controlled by two components, the majority of the literature has typically focused addressing only the topological term via graph rewiring [42 1000 655
Table 1: Ablation on LRGB datasets. d f adds latent dims; removes; + adds.
S 41), with some methods also target- ing the model dynamics [47 48 59). In fact, (30 explicitly
Pept-func AP1
Pept-struct MARI (x 1073)
Model
discourages increasing the model term in Theorem 5. and claims that doing so could lead to over wver-fitting and poorer gen- cralization. However, we argue that increasing the model term, directly linked to vanishing gradients as discussed in Section 4 is essential to mitigate over-squashing. Rather than harming performance, boosting this term helps prevent over-smoothing, since even in a well-connected graph where information can be reached in fewer hops, unaddressed vanishing gradients due to the model term will cause the target node's 's features to collapse during message passing. Frameworks combining these strategies include (55), which integrates graph rewiring with a delay term, and 32 which
GCN
60.93 138
33.41 041
KGCN-SSM
69.02 0. 218
28.98
+d 1
72. 72.12
27.01 071
-ii(A)
61.41 22.
25.81 _0.032
SSM
57.7021.971
26. 26.02
-hop
60.93
33.41 10.411
DRew-GCN
68. 68.0441.44
27. 27.6640.15
+d
68. 68.05 e220
27.61
-Delay
49.02
27.08
In this part, we mostly focus on range interactions, which has been many cases treated synonymously with squr-squa in the literature. For a more precise characterization of the relationship between over- squashing and long range. we point the reader to 3]. We highlight that we believe the distinction between computational and topologiaal bottlenecks is not particularly relevant in our setting.

---

merges multi-hop aggregation with ideas from SSMs These approaches have generally led to sate-of-thee-rr results, significantly improving performance over standalone rewiring.
5.2 Empirical validation of claims
We focus our empirical validation on answering the following questions: (i) What is the result of combining an effective rewiring scheme with vanishing gradient mitigation? (ii) Will this result in similar state-of-the-ar results? To investigate this, we construct a minimal model that combines high connectivity with -on-disiipativity. In particular, we make of the GNN-SSM model and employ k-hop aggregation scheme for the coupling function Fo, which we term kGNN SGNN-SSM (more details are provided in Appendix B).
We start by testing the performance fer task introduced in [30], as it is a task where we certifiably know that long-range dependencies exist.
the RingTrans-
100
100
Accurayy (15)
GCN
We modify the eig(A) (A) in the kGNN-SSM to move the Jacobian from the edge of stability to a progressively more dissipative state. The results are shown in Figure 5 From the figure, we see that (i) kGNN SSM achieves statc-of-the art performance only when coupling strong connectivity and an edge of chaos Jacobian (ii) making the model more dissipative directly results in worse long-range modeling capabilities. We believe the latter point demonstrates the importance of the model term in Theorem 5.
63
IXGUNN
AGCNN-SMM
60
A
AGUN--550, mk
Al-3/
40
Nodes
NoNos
Figure 5: Left: Performance the RingTraas- fer task. Right: Effect dissipativity.
Table 2: Mean and std. for test logio averaged
Next, we ablate each component of the model on three graph property prediction tasks in- troduced in 477 alongside the real-world long-range graph benchmark (LRGB) from 36), focusing on the peptides- func and -struct tasks. Additional details regarding the datasets and the experimental setting are reported in Appendix [ Here, we focus on ablating the effect of rewiring, adding an SSM layer, and placing the model at the edge of chaos through A. In the LRBG tasks, we additionally ablate the effect of increasing the hidden memory size, as we consider forty layers in the peptides-fune dataset, which requires more long-range capabilities. Here, we also ablate DRew (55) under the same settings. We also provide more detailed comparison with other models in Appendix D.3 and provide additional comments around the LRGB tasks in Appendix D.4
over 4 random weight initializations the GPP tasks
Model
Dian.
SSSP
Ecc.
GCN
0.74220.047
0,950
40. 15-10-5
0.847_a.00s
-2.821 20.560
2.245 ons
eig(A) = 1
-2.44440.008
.3.593
-2.258
k-bop -3.075
g0.05a
-3.00420.029
-4.265 10.178
DRew-GCN
-2.369 10016
-1.591 20.008
-2. 22.100
dellay
100
-1.602-20.0os
224
The results are shown in Tables and 2 Across the board, we observe that KGNN-SSM not only matches DRew-Delay, but also outperforms by a large amount in all cases, showcasing the strength of our state-space approach. In particular, we generally observe significant decreases in performance when removing both the high connectivity and non-dissipativity components of the model, highlighting their individual importance. Finally, we see that increasing memory size plays big role in the peptides fuc task, which is in line with observations made in the sequence modeling literature [53].
6 Conclusion
In this work, we revisit the well-known problems of representational collapse and over- over-squashing in GNNs from the lens of vanishing gradients, by studying GNNs from the perspective of recurrent and state-space models. In particular, we show that GNNs are prone to a phenomenon we term extreme gradient vanishing, which results in ill-conditioned signal propagation with few layers. As such, we argue that it is important to control the layerwise Jacobian and propose model, termed GNN-SSM, to do so. We then uncover that vanishing gradients result specific form of over-smoothing in which all signals converge exactly to a unique fixed point, and support this claim empirically. Finally, we theoretically argue and empirically show that the mitigation of over- -quashing is best achieved through a combination of strong graph connectivity and non-dissipative dynamics.
sette--pac-iisspree GNN
Further links between the delay term and vanishing gradients are discussed in Appendix D.2 Further, we show that models tend to converge the edge of chaos during training in Appendix D.3
10

---

Acknowledgments and Disclosure of Funding
AA and XD thank the Oxford-Man Institute for financial support. XD also acknowledges support from EPSRC No. EP/T023333/1. AA thanks T. Anderson Keller for engaging comments early versions of the manuscript, Max Welling for valuable pointers the dynamical isometry literature. AG and CG acknowledge funding from EU-EIC EMERGE (Grant No. 101070918). CG acknowledges support from NEURONE, project funded by the European Union Next Generation EU, M4C1 CUP 153D23003600006, under program PRIN 2022 (prj. code 20229JRTZA).
References
[1] Uri Alon and Eran Yahav. On the Bottleneck of Graph Neural Networks and its Practical Implications. International Conference on Learning Representations, 2021.
[2] Martin Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neural networks.
In International conference on machine learning, pages 1120 1120-112. PMLR, 2016.
[3] Adrian Amaiz-Rodrigee and Federico Errica. Oversmoothing." oversquashing", heterophily, long-range, and more: Demystifying common beliefs in graph machine learning. arXiv preprint 2rXiv:2505.15544 2025.
[4] Jacob Bamberger, Benjamin Gutteridge, Scott le Roux, Michael M Bronstein, and Xiaowen Dong. On measuring long-range interactions in graph neural networks. In Forty-second International Conference on Machine Learning, 2025.
[5] Stefan Banach. Sur les opérations dans les ensembles abstraits et leur application équations intégrales. Fundamenta mathematicae, 3(1):133-181, 1922.
[6] Federico Barbero, Alvaro Arroyo, Xiangming Gu, Christos Perivolaropoulos, Michael Bron- stein, Petar Veličković, and Razvan Pascanu. Why do llms attend the first token? arXiv preprini 2ttii:2550000227:33 2025.
[7] Federico Barbero, Andrea Banino, Steven Kapturowski, Dharshan Kumaran, João GM Araújo, Alex Vitvitskyi, Razvan Pascanu, and Petar Veličković. Transformers need glasses! information over-squashing in language tasks. arXiv preprint SxXi::2406.02267, 2024.
[8] Federico Barbero, Ameya Velingker, Amin Saberi, Michael Bronstein, and Francesco Di Gio- vanni. Locality-aware graph-rewiring in gnns. arXiv preprint 10.0v:2310.01668, 2023.
[9] Maximilian Beck, Korbinian Pöppel, Markus Spanring, Andreas Auer, Oleksandra Prud- nikova. Michael Kopp, Günter Klambauer, Johannes Brandstetter, and Sepp Hochreiter. xlstm: Extended long short-term memory. arXiv preprint arXivv2405.04517 2024.
[10] Ali Behrouz and Farnoosh Hashemi. Graph Mamba: Towards Learning on Graphs with State Space Models, 2024.
[1]] Yoshua Bengio. Learning long-term dependencies with gradient descent is difficult. IEEE transactions neural networks, 5(2): 1994.
[12] Richard Bergna, Sergio Calvo-Ordoned Felix L Opolka, Pietro Liò, and Jose Miguel Hermandez-Lobato. Uncertainty modeling in graph neural networks via stochastic differ- 2024.
ential equations. arXiv preprint
[13] Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang. Understanding oversquashing in gnns through the lens of effective resistance. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMLR.org, 2023.
[14] Cristian Bodnar, Francesco Di Giovanni, Benjamin P. Chamberlain, Pietro Liò, and Michael M. Bronstein. Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in GNNs, 2022.
[15] Haitz. Sáez de Ocáriz Borde, Álvaro Arroyo, and Ingmar Posner. Projections of model spaces for latent graph inference. arXiv preprint arXiv:2303.117:: 2023.

---

[16] Xavier Bresson and Thomas Laurent. Residual gated graph convnets. drXiv:1711.07553,22 2017.
arXiv preprint
[17] Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs, 2014.
[18] Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006. 13318, 2020.
[19] Sergio Calvo-Ordonez, Jiahao Huang, Lipei Zhang, Guang Yang, Carola-Bibiane Schonlieb, and Angelica I Aviles-Rivero. Beyond u: Making diffusion models faster & lighter. arXiv preprint arxii:23100.0009: 2023.
[20] Sergio Calvo- CalloeOrdonez, Matthieu Meunier, Francesco Piatti, and Yuantao Shi. Partially stochas- tic infinitely deep bayesian neural networks. arXiv preprint arXiv:2402.03495 2024.
[21] Sergio Calvo-Ordoñez, Jonathan Plenk, Richard Bergna, Alvaro Cartea, Jose Miguel Hernandez-Lobato, Konstantina Palla, and Kamil Ciosek. Observation noise and initialization in wide neural networks. arXiv preprint arXiv:2502.01556 2025.
[22] Benjamin Chamberlain, James Rowbottom, Davide Eynard, Francesco Di Giovanni, Xiaowen Dong, and Michael Bronstein. Beltrami flow and neural diffusion graphs. Advances in Neural Information Processing Systems, 34:1594-1609 2021.
[23] Benjamin Paul Chamberlain, James Rowbottom, Maria Gorinova, Stefan Webb, Emanuele Rossi, and Michael M Bronstein. GRAND: Graph neural diffusion. In International Conference on Machine Learning (ICML), pages 1407-1418. PMLR, 2021.
[24] Ines Chami, Rex Ying, Christopher Ré, and Jure Leskovee. Hyperbolic graph convolutional neural networks, 2019.
[25] Peter G Chang, Gerardo Martin, Alexander Y Shestopaloff, Matt Jones, and Kevin Murphy. Low-rank extended kalman filtering for online learning of neural networks from streaming data. arXiv preprint arXiv:23005. 2.0i::2300//933355 19535, 2023.
[26] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and Deep Graph Convolutional Networks. In Hal Daumé IIII and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1725-1735. PMLR, 13-18 Jul 2020.
[27] Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differential equations. Advances in neural information processing systems, 31, 2018.
[28] Fan RK Chung. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
[29] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering, 2017.
[30] 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 Machine Learning, pages 7865-7885. PMLR, 2023.
[31] 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.
[32] Yuhui Ding, Antonio Orvieto, Bobby He, and Thomas Hofmann. Recurrent distance filtering for graph representation learning. In Forty-first International Conference Machine Learning, 2024.
[33] Gerardo Duran-Martin, Matias Altamirano, Alexander Y Shestopaloff, Leandro Sánchez-- Betancourt, Jeremias Knoblauch, Matt Jones, Fravgois-Xavier Briol, and Kevin Murphy, Outlier-robust kalman filtering through generalised bayes. arXiv preprint arXiv:2405. 055666 2024.
12

---

[34] Gerardo Muran-Martin, Leandro Sänchez-Betancourt Alexander Y Shestopaloff, and Kevin Murphy, Bone: unifying framework for bayesian online learning in non-stationary environ- ments. arXiv preprint arXiv:241 1. 10153, 2024.
[35] Vijay Prakash Dwivedi and Xavier Bresson. A Generalization of Transformer Networks to Graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
[36] Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. In S. Koyejo. S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 22326-22344 Curran Associates, Inc., 2022.
[37] 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.
[38] Moshe Eliasof, Eldad Haber, and Eran Treister. Pde-gen: Novel architectures for graph neural networks motivated by partial differential equations. Advances in neural information processing systems, 34:3836-3849, 2021.
[39] Rainer Engelken and Fred Wolf. Lyapunov spectra of chaotic recurrent neural networks. Physical Review Research, 5(4):043044, 2023.
[40] Bastian Epping, Alexandre René, Moritz Helias, and Michael T Schaub. Graph neural networks do not always oversmooth. arXiv preprint arXiv:2406.0222 2024.
[41] Ben Finkelshtein, Xingyue Huang, Michael M Bronstein, and Ismail Ilkan Ceylan. Cooperative graph neural networks. In Forty-first International Conference on Machine Learning, 2024.
[42] Johannes Gasteiger, Stefan Weißenherger, and Stephan Günnemann. Diffusion improves graph learning. Advances in neural information processing systems, 32, 2019.
[43] Simon Geisler, Arthur Kosmala, Daniel Herbst, and Stephan Günnemann. Spatio-spectral graph neural networks. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 49022-49080. Curran Associates, Inc., 2024.
[44] Jhony H Giraldo, Konstantinos Skianis, Thierry Bouwmans, and Fragkiskos D Malliaros. On the trade-off between over smoothing and over-squashing in deep graph neural networks. In Proceedings the 32nd ACM international conference information and knowledge management, pages 1666576,770 2023.
[45] M Gori, G Monfardini, and F Scarselli, A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume pages 729-734. IEEE, 2005.
[46] Alessio Gravina and Davide Bacciu. Deep Learning for Dynamic Graphs: Models and Benchmarks. IEEE Transactions on Neural Networks and Learning Systems, 35(9):11788- 11801, 2024.
[47] Alessio Gravina, Davide Bacciu, and Claudio Gallicchio. Ayti-Symmetric DGN: a stable architecture for Deep Graph Networks. In The Eleventh International Conference on Learning Representations, 2023.
[48] 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. Proceedings of the AAAI Conference on Artificial Intelligence, 39(16):1606611614 Apr. 2025.
[49] Alessio Gravina, Claudio Gallicchio, and Davide Baceiu. 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

---

[50] Alessio Gravina, Giulio Lovisotto, Claudio Gallicchio, Davide Bacciu, and Claas Grohnfeldt. Long Range Propagation on Continuous- Time Dynamic Graphs. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 16206-16225. PMIR, 21-27 Jul 2024.
[51] Alessio Gravina, Daniele 7ambon, Davide Bacciu, and Cesare Alippi. Temporal graph odes for irreularly-samplled time series. In Kate Larson, editor, Proceedings of the Thirty- Third International Joint Conference on Artificial Intelligence, IJCAI-24, pages International Joint Conferences on Artificial Intelligence Organization, 8 2024.
[52] Albert Gu and Tri Dao. Mamba: I Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00752, 2023.
[53] Albert Gu, Karan Goel, and Christopher Re. Efficiently modeling long sequences with structured state spaces. In International Conference on Learning Representations, 2021.
[54] Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Ré. Learning mixed-curvature repre- sentations in product spaces. In ICLR, 2019.
[55] Benjamin Gutteridge, Xiaowen Dong, Michael M Bronstein, and Francesco Di Giovanni. DRew: dynamically rewired message passing with delay. International Conference on Machine Learning, pages 12252-12267. PMLR, 2023.
[56] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[57] Ali Hariri, Álvaro Arroyo, Alessio Gravina, Moshe Eliasof, Bacciu, Kamyar Azizzadenesheli, Xiaowen Dong, and Pierre Vandergheynst. Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Tasks. arXiv, abs/2506.07624, 2025.
Schönlieb, Davide
[58] K Khalil Hassan et al. Nonlinear systems. Departement of Electrical and computer Engineer- ing, Michigan State University, 2002.
[59] Simon Heilig, Alessio Gravina, Alessandro Trenta, Claudio Gallicchio, and Davide Bacciu. Port Hamiltonian Architectural Bias for LongeRange Propagation in Deep Graph Networks. In The Thirleenth International Conference on Learning Representutions, 2025.
[60] Mikael Henaff, Arthur Szlam, and Yann LeCun. Recurrent orthogonal networks and long- memory tasks. In International Conference on Machine Learning, pages 2034-2042. PMLR, 2016.
[61] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9()) 1735 1997.
[62] 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.
[63] Herbert Jaeger. The "echo state" approach to analysing and training recurrent neural networks- with an erratum note. Bonn, Germany: German National Research Center for Information Technology GMD Technical Report, 148(34):13, 2001.
[64] Matt Jordan and Alexandros Dimakis. Exactly computing the local lipschitz constant of relu networks. Advances in Neural Information Processing Systems, 33:7344-7353, 2020.
[65] Kedar Karhadkar, Pradeep Banerjee, and Guido Montúfar. Fosr: First-order spectral rewiring for addressing oversquashing in gnns. arXiv preprint 2rXiv:2210.11790, 2022.
[66] Bobak T Kiani, Lukas Fesser, and Melanie Weber. Unitary convolutions for learning on graphs and groups. arXiv preprint
2024.
14

---

[67] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks, 2017.
[68] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34:21618 -16629,, 2021.
[69] Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In Proceedings of the IEEE/CVF international conference on computer vision, pages 9267-9276, 2019.
[70] 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: large graph dataset and measurement. arXiv preprint arXiv:2503.00000 2025.
[71] Juncheng Liu, Kenji Kawaguchi, Bryan Hooi, Yiwei Wang, and Xiaokui Xiao. Eignn: Efficient infinite-depth graph neural networks. Advances in Neural Information Processing Systems, 34:18762-18773, 2021.
[72] Vladimir Alexandrovich Marchenko and Leonid Andreevich Pastur. Distribution of eigenvalues for some sets of random matrices. Matematicheski Shornik, 114(4):507-536, 1967.
[73] Thomas Markovich. Qdc: Quantum diffusion convolution kernels on graphs, 2023.
[74] Sohir Maskey, Raffaele Paolino, Aras Bacho, and Gitta Kutyniok. A fractional graph laplacian approach to oversmoothing. Advances Neural Information Processing Systems, 36, 2024.
[75] Alexandru Meterez, Amir Joudaki, Francesco Orabona, Alexander Immer, Gunnar Ratsch, and Hadi Daneshmand. Towards training without depth limits: Batch normalization without gradient explosion. In The Twelfth International Conference on Learning Representations, 2024.
[76] Alessio Micheli.
Neural Network for Graphs: Contextual Constructive Approach. IEEE
Transactions on Neural Networks, 20(3)449--51,, 2009.
[77] Fernando Moreno-Ping Pinno Álvaro Arroyo, Harrison Waldon, Xiaowen Dong, and Álvaro Cartea. Rough transformers: Lightweight and continuous time series modelling through signature patching. Advances in Neural Information Processing Systems, 37: 37:106264-1162294 2024.
[78] Alexander Norcliffe, Cristian Bodnar, Ben Day, Nikola Simidjievski, and Pietro Liò. On
second order behaviour in augmented neural odes. Advances in neural information processing systems, 33:591 1-5921, 2020.
[79] Hoang Nt and Takanori Maehara. Revisiting graph neural networks: All have is low-pass filters. arXiv preprint 1.XXv:9905.095500 2019.
[80] Kenta Oono and Taiji Suzuki. Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. In International Conference on Learning Representations, 2020.
[81] Antonio Orvieto, Samuel Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, and Soham De. Resurrecting recurrent neural networks for long sequences. In International Conference on Machine Learning, pages 26670-26698. PMLR, 2023.
[82] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In Proceedings of the 30th International Conference International Conference on Machine Learning, volume 28, pages III-1310, 2013.
[83] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In International Conference on Learning Represen- tations, 2020.
[84] Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli. Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practice. Advances neural information processing systems, 30, 2017.
15

---

[85] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look the evaluation of GNNs under heterophily: Are we re- ally making progress? In The Eleventh International Conference on Learning Representations, 2023.
[86] Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Exponential expressivity in deep neural networks through transient chaos. Advances in neural information processing systems, 29, 2016.
[87] Ladislav Rampášek, Mikhail 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, 35, 2022.
[88] Andreas Roth and Thomas Liebig. Rank collapse causes over-smoothing and over-correlation in graph neural networks. In Learning on Graphs Conference, pages 35-1. PMLR, 2024.
[89] Yulia Rubanova, Ricky TQ Chen, and David K Duvenaud. Latent ordinary differential equations for iregularly-samppl time series. Advances in neural information processing systems, 32, 2019.
[90] T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303. 10993, 2023.
[91] T Konstantin Rusch, Ben Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael Bronstein. Graph-coupled oscillator networks. International Conference on Machine Learning, pages 18888-18909, PMLR, 2022.
[92] Haitz Sáez de Ocáriz Borde, Alvaro Arroyo, Ismael Morales, Ingmar Posner, and Xiaowen Dong. Neural latent geometry search: product manifold inference via -husdoofff- informed bayesian optimization. Advances in Neural Information Processing Systems, 36, 2024.
[93] Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. arXiv preprint arXiv:1312.6122 2013.
[94] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfar- dini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008.
[95] Michael Scholkemper, Xinyi Wu, Ali Jadbabaie, and Michael T Schaub. Residual con- nections and normalization can provably prevent oversmoothing in gnns. arXiv preprint SKKiv:2406.029997 2024.
[96] Dai Shi, Andi Han, Lequan Lin, Yi Guo, and Junbin Gao. Exposition on over-squashing problem on gnns: Current methods, benchmarks and challenges, 2023.
[97] Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjing Wang, and Yu Sun. Masked Label Prediction: Unified Message Passing Model for Semi Semi-Supervised Classification. In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference Artifi- cial Intelligence, IJCAI-21, pages 1548-1554, International Joint Conferences on Artificial Intelligence Organization, 8 2021. Main Track.
[98] Alessandro Sperduti. Encoding labeled graphs by labeling raam. Advances in Neural Informa- tion Processing Systems, 6, 1993.
[99] Steven H Strogatz. Nonlinear dynamics and chaos: with applications to physics, biology, chemistry, and engineering. CRC press, 2018.
[100] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint arXiv:2111.11522, 2021.
[101] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. ArXiv, 2018.
16

---

[102] Chloe Wang, Oleksii Tsepa, Jun Ma, and Bo Wang. Graph-mambs Towards long range graph sequence modeling with selective state spaces. arXiv preprint arXiv:2402.00789, 2024.
[103] 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
Curran Associates, Inc., 2021.
[104] Qitian Wu, Chenxiao Yang, Wentao Zhao, Yixuan He, David Wipf, and Junchi Yan. DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion. In The Eleventh International Conference on Learning Representations, 2023.
[105] Xinyi Wu, Amir Ajorlou, Zihui Wu, and Ali Jadbabaic. Demystifying oversmoothing in attention-basee graph neural networks. Advances in Neural Information Processing Systems, 36:35084 36:35084-35106, 35106, 2023.
[106] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 1 2018.
[107] Greg Yang. Jeffrey Pennington, Vinay Rao, Jascha Sohl-Dickstein, and Samuel Schoenholz. A mean field theory of batch normalization. arXiv preprint 1rXiv:1902.08819, 2019.
[108] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 40-48, New York, New York, USA, 20-22 Jun 2016. PMLR.
[109] Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng. Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34:28877-28888 2021.
17

---

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 the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in 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.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Yes, this is included in the supplementary material.
Guidelines:
The answer NA means that the paper has no 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 their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect 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 is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
18

---

Justification:
Yes, all assumptions are stated and proofs can be found in the supplementary
material.
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 in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or 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 of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Yes, datasets are publicly available and the hyperparameters used the code is in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 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 a specific model and empirical evaluation, it may be necessary either make it 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 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 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) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If 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 to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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 (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
19

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes)
Justification:
We provide the code in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a 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
/ "cipps.c/puullc//guu /ot.e//Suudeeooeomuummmiiiiiii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to 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. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
Yes, we follow the standard procedure for each individual dataset.
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 a 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, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We provide the results in the format "mean + standard error".
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
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.)
20

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation 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 enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the 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 provided information on the GPU used in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the 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 rums 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 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics htttps:/neuurps::: http://wwwwp..cco/a//a//cccccaaa
Answer: [Yes]
Justification:
Our submission abides by the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is 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 no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact 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.
21

---

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 an 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 to 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 as 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 ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a 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 a 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 to 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
Question: 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?
Answer: [Yes]
Justification: We provide citations for all sources of code and/or data used, both in the paper and in the accompanying repository.
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 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.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
22

---

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:
No new datasets are introduced.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the dataset/code/mmodll 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 used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing 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 in 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 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 the main paper.
According to the NeurIPS Code 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 crowdsourcing nor research with human subjects.
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 NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
23

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it 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.
Answer: [NA]
Justification: LLMs are not central component of the paper in terms of methodological advancements.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standart components.
Please refer to our LLM policy (https://nee) //tp:/:////.p....eee.. wwwperripppccoooeeeeeeeeeeee /t//Confereence//2225. for what should or should be described.
24

---

2 and Omax = (1 + 2 If the entries X have variance σ² 1, then the A Theoretical Results
A.1 Proofs of Jacobian Theorems
Definition A.1 (Vectorization and Kronecker product). Let X E Rmxx be a real matrix. The vectorization of X, denoted vec(X), is the (mn) diimensooni column vector obtained by stacking the columns of X:
X
vec(X)
E
IR IR"..
X
One key property of the vectorization operator is its relationship to the Kronecker product. In particular, for compatible matrices A, B, C, we have
vec(ABC) = (C" & vec
Here, @ denotes the Kronecker product.
Definition A.2 (Wishart matrix). Let X E RuxP be matrix with i..d. entries Xij NN(0, The random matrix X X RPxP is called Wishart matrix (up to scaling factor). In particular, such matrix follows the Wishart distribution Wi(nn, o²) in certain parametrizations.
Definition A.3 (Marchenko-Paie Pastur distribution. (72). In the high-dimensional limit (n.p oo at a fixed ratio p/nn - c), the empirical eigenvalue distribution the (properly normalized) Wishart matrix X converges to the ParrhennkoPPasttre distribution. Concretely, if X R=*p has entries N(0, 1). then the cigenvalues X lie within [[1 vc) (1 + vc)²| for large n, p, and their density converges to
(x) = 2TC V (xx amin) ( (mmax z), x [Amiu: 0max].
with amin =1 support is rescaled by o².
Lemma A.4 (Spectrum of the Jacobian's 's singular values). Ler H = Á (k-1)) W be a linear GCN layer, where A has eigenvalues {AI...., :,n] and W W has eigenvalues {pi,... Pay
Consider the layer-wise Jacobian J = Ô vee (ec(( (H))) vee (H ())), Then the squared singular
values of J are given by the set
{ My
I,
dx
Proof. By the property
of vectorization (Definition A.I we have
vec Ä (R-1) w) (W7 @ A) vec (t))
Hence
= WT A.
By properties of the Kronecker product, the eigenvalues of J are the products of the eigenvalues of WWW and A Equivalently,
spec(JJ") spec
spec (A²);
where spec is the vectorized version of the set of eigenvalues of matrix. If W W has eigenvalues (1y de and A has eigenvalues { 1 then the squared singular values of J are precisely X P for E (1, nl.....n).j (1,...,d:).
Theorem A.5 (Jacobian singular-vabi value distribution). Assume the setting of Lemma 3.1 and ler W E Rdd-1xde be initialized with i..dd (000 o²) entries. Denote the squared singular values of the Jacobian by V.g. Then, for sufficiently large d, the empirical eigervalue distribution WWT converges to the Marchenko- Pustur distribution. Then, mean and variance of each "i. are
E E[
(15)
Var[%s X² 0 ds
(16)
d
25

---

Proof. In this setting, WW7 is Wishart if W has i... Gaussian entries. Its eigenvalues H4j thus converge to the Marchenko Pastur distribution for large dg. From standard results on the moments of Wishart eigenvalues,
B(y) = o², Var(u;) = o² ds dx-1
Since Va X2 Mjj we obtain
E[ = Xē = X²
X Var(uy) X X²0² 0² d2 dx-1
Var[ma]
This completes the proof.
Proposition A.6 (Effect of state-space matrices). Consider the setting in 9 and
( ()/ (k) Let @ denote the Kronecker product. Then, the norm of the vectorized Jacobian is bounded as:
| < [d, @ A
la & BB 2
A B 1
(17)
Proof. We start by writing
(Ia A (Ja, 8B)
Using the triangle inequality for the spectral norm,
J 2
[Ta, A (Ja, & B) & [t, @ + II(Ja @ B)
By the submultiplicative property of the spectral norm, I1a,, @ B) & [L, @ B 11
Since Lde & M||2 || for any matrix M, we obtain
Ia, @ Al2
| and [[ X B
|
Hence,
J & A|] + | ||
A.2 Proofs Smoothing Theorems
Definition A.7 (Lipschitz continuity). A function f 12" - Rm is Lipschitz continuous if there exists an such that for all x, y IR,, we have that:
(1(()) - s(y)ll & L|x x - yll,
where we equip R and R with their respective norms. The minimal such called the Lipschitz constant of f.
The notion of Lipschitz continuity effectively a bound on the rate of change of a function. It is therefore not surprising that we state a useful and well-known result (88) that relates the (continuous) Jacobian map J continuous function f R - Th to its Lipschitz constant L 0. In partieular, the Lipschitz constant is is the supremum of the (induced) norm of the Jacobian taken over its domain.
relate the Lipschitz constant to the Jacobian of f. In particular,
Lemma A.8 (158). Let f g
Rm be continuous, with continuous Jacobian Jy. Con- sider convex set U R" If there exists L > 0 such that [x](x)]] & L for all U, then [lf - fly)l L ||x yll. In particular, we have that the Lipschitz constant of L is:
L = sup |
xeU
26

---

The condition of U being convex is a technicality that is easily achieved in practice with the assump- tion that input features bounded and that therefore they live in a convex hull U. In particular, at each layer & one can also find convex hull Uj such that the image of the layer k - is contained within Up. We highlight that for non-linearities such ReL.U, there are technical difficulties when taking this supremum as there a non-differentiable point at O. This can be circumvented by consid- ering instead a supremum of the (Clarke) generalized Jacobian [64]. We ignore this small detail in this work for simplicity for ReLU this is equivalent to considering the supremum over U/0, i.e. simply ignoring the problematic point 0.
Lemma A.9. Consider GNN layer fe as in Equation 3 with non- linearity a such that o 0
(e.g. ReL.U or tanh). Then, f(0) O, i.e. 0 is fixed point of f.
Proof. fe(0) (Aow) = a (0) = O.
Proposition A.10 (Convergence to unique fixed point.). Let I[ & for some e > 0 for all
È s..... L. Then, for H U S Rdd we have that:
||(H]] & (1- H < ||]]-
(18)
particular, as L J. ((H) O.
Proof. By Lipschitz regularity of f over U, we have that llf(x) f(y)ll & I1fllup |x 1-yl. Recall
that by Lemma 4.2 have that f(0) 0. This implies:
[I f(0)l = [f(H))
|I
Llii
H
fe I
H
where in the last step we use the fact that Lipschitz constants are submultiplicative and that for all é have that [e Luip by assumption. The final statement is immediate by the Banach fixed point theorem and by noting that fe all share the same fixed point 0 by Lemma 4.2
edges in G, and H e Rgnd, We have the following bound: Proposition A.11 (Contractions decrease Dirichlet energy.). Let f be GNN, [E] be the number of
L E(((H) < 2
|
(19)
8-1
In particular, if l[fellisp & 1 for some > 0.for all = 1... L, then as L - 0o, E(f(H) - 0.
Proof. We denote by [(H),, Rd. the d-dimensional evaluation of f(H) at node We make use of the incquality [H) [H].
27

---

E((()) Σ [I)(H)): S(H)
Σ [I [ +1
2 Σ
[I)(H))
< 2211 Σ H
= 2 2| liip
|B| H
<
[1
liip
E
H
{=1
is then clear that, if le
< - e for some
0 for all = I...L,
He Ilfellipp & (1- as I 0c.
We note that similar procedure used 80 1 for the specific case GCNs. Our procedure is more general, as we use the Lipschitz constant of the network, which only requires knowledge of the input-output Jacobian of each layer of the network. In the case of GCN, this would encapsulate the dynamics of the adjacency and weight matrix, and also allows us to understand how any GNN (no matter how complex its internal structure) affects the Dirichlet energy. without requiring the use of heavy assumptions or simplifications for mathematical tractability.
IT
B KGNN-SSM: A simple method to combine high connectivity and non-dissipativity.
To test our assumption on more complex downstream tasks, we construct minimal model that combines high connectivity with non-dissipatiiity. To guarantee high connectivity, we employ k-hop aggregation scheme. particular, each node at layer will aggregate information as
(k) 0i.k 4 (11 (K) :j))(())))
(20)
where
Na(1 :- (je V: d)(i,)) k}
Rzo is the length of the minimal walk connecting nodes i and j. This approach avoids a large amount of information being squashed into a single vector, and is more in line with the recurrent paradigm. We note that this scheme is similar [32]. but in this case do not consider different block or parameter sharing, and our recurrent mechanism is based on an untrained SSM layer.
and de V x V
We denote a GNN endowed with this rewiring scheme and wrapped with our SSM layer as kGNN-SSM,
C Experimental Details
In this section, we provide additional experimental details, including dataset and experimental setting description and employed hyperparameters.
Over-smoothing task. In this task, aim to analyze the dynamics of the Dirichlet energy across
three different graph topologies: Cora [108]. Texas [83), and grid graph. The Cora dataset is citation network consisting of 2,708 nodes (papers) and 10.556 edges (citations). The Texas dataset represents a webpage graph with 183 nodes (web pages) and 499 edges (hyperlinks). Lastly, the grid graph a two-dimensional 10 10 regular grid with 4-neighbor connectivity. For all three graphs, node features are randomly initialized from normal distribution with a mean of 0 and variance of These node features are then propagated over 80 layers (or iterations) using untrained GNNs to observe the energy dynamics.
28

---

Table 3: The grid of hyperparameters employed during model selection for the graph property prediction tasks (GraphProp), and peptides- func and peptides-struce
Values
Hyperparameters
GraphProp
peptides- (func, struct)
Optimizer
Adam
A
Learning rate
0.003
0.001
Weight decay
10-6
N. Layers
40.17
embedding dim
20, 30
105
tanh
ReLU
eig(A) A)
0.5, 0.75, 1.0
1.0
Graph Property Prediction. This experiment consists of predicting two node-level (i.e., eccentric- ity and single source shortest path) and one graph-level (i.e., graph diameter) properties on synthetic graphs sampled from different distribution, ie., Erdōs-Rény: Barabasi-Albest grid, caveman, tree, ladder, line, star, caterpillar, and lobster. Each graph contains between 25 and 35 nodes, with nodes assigned with input features sampled from a uniform distribution in the interval [0. 1). The target values correspond to the predicted graph property. The dataset consists of 5,120 graphs for training, 640 for validation and 1,280 for testing.
We employ the same experimental setting and data outlined 447 Each model is designed as three components: the encoder, the graph convolution, and the readout. We perform hyperparameter tuning via grid search, optimizing the Mean Square Error (MSE). The models are trained using the Adam optimizer for maximum of 1500 epochs, with early stopping based on the validation error, applying a 100 epochs patience. For each model configuration, we perform 4 training runs with different weight initializations and report the average results. We report in Table 3 the employed grid of hyperparameters.
Long-Range Graph Benchmark. We consider the peptides-fune and peptides-struct datasets from [36]. Both datasets consist 15,535 graphs, where each graph corresponds to ID amino acid chain (i.e., peptide), where nodes the heavy atoms of the peptide and edges the bonds between them. peptides-fun feiides--unee func is a multi-label graph classification dataset whose objective predict the peptide function, such antibacterial and antiviral function. peptides- -erruct is multi-label graph regression dataset focused on predicting the 3D structural properties of peptides, such the inertia of the molecule and maximum atom-pair distance.
We use the same experimental setting and splits from [36] We perform hyperparameter tuning via grid search, optimizing the Average Precision (AP) in the Peptides-func and Mean Absolute Error (MAE) the Peptide-struct. The models are trained using the Adam optimizer for maximum of 300 epochs. For each model configuration, we perform four training runs with different weight initializations and report the average results. We report in Table the employed grid of hyperparameters.
Tested Hyperparameters. In Table we report the grid of hyperparameters employed in our experiments by our method.
All experiments were run single NVIDIA RTX4090 GPU.
D Additional empirical results
In this section, we propose additional empirical results on over-smoothing and over-squashing, as well as the eigendistribution of the layerwise Jacobians of various standard GNNs.
D.1 Additional Over-Smoothing Results
Here, we include additional results related to over-smoothing experiments. Figure 6 shows the effect of ||Al]] in GCN-SSM on different graph structures (similarly Figure for GAT-SSM), showing that
29

---

lower Jacobian norms leads to rapid decay of the Dirichlet energy, whereas values closer to one result more stable energy evolution. This result is also confirmed by Figure and Figure The former presents the vectorized Jacobian for ADGN 47 SWAN 48], and PHIGG [ on Cora, while the latter the Dirichlet energy evolution of different models on different topologies. Notably, in Figure 2 ADGN, SWAN, and PHDGN exhibit stable Dirichlet energy across layers, and Figure B reveals that these Jacobian norms are close to one. These results confirm that stable dynamics also ensure non-decaying Dirichlet energy, effectively preventing over-smoothing.
Daticlle Eaerg
10
Dasohles Energy
10
Dizichle: Energy
10"
10-4
10-4
Asge 1.25
10
1.25
1.77
Asg 1.75
1.75
10
20
10
105
1.05
40
18
Layer
Layer
32
Layer
16
Figure 6: Dirichlet Energy evolution of GCN-SSM for different ||A||2 on different graph topologies. Left: Cora. Middle: Grid graph. Right: Texas.
Dirichiet Encrge
10-1
Drtichiet Eneegg
10-3
10"
10-1
10-4
10-4
0.
1.S
Z
0.
0.75
10
1
Aug
1000
10
Layer
322
64
10
Layer
16
32
04
10
Layer
16
32
64
Figure 7: Dirichlet Energy evolution of GAT-SSM for different ||A||2 different graph topologies. Left: Cora. Middle: Grid graph. Right: Texas.
13
1.5
1.3
1.0
1.0
1.0
Emaginacy
0.5
-1.0
-1.0
-10
4.5
-100
1.5
-4.5
-1.5
0.0
Medi
Rec.
Ren.
Figure 8: Vectorized Jacobian for ADGN 47). SWAN 48) and PHDGN 159 Middle: SWAN. Right: PHDGN.
on Cora. Left: ADGN.
D.2 Link between delay and vanishing gradients
Here, we show how the delay term [55] is directly related preventing vanishing gradients. We do so by showing that adding the delay term to GCN is effective at preventing over-smoothing, see Figure 10 as well as by checking
histogram of eigenvalues of the Jacobian, see Figure Figure II shows the effect of ||A]|2 in DRew-SSM the performance on the Ring Transfer task, showing that lower Jacobian norms leads a rapid performance decay, i.e., poor long-range propagation.
12
30

---

107
107
10"
10
30-1
10"
DON
GON ADGN SWAR
Strubles
GCN
ADGNN
ADION SWAN PHIGN
10
SWAS
22
10
10
10
Loger
Lager
Logor
Figure 9: Dirichlet Energy evolution of different models on different topologies. Left: Cora. Middle: Grid graph. Right: Texas.
Diekikke Easrge
10
Dickcáles Eacegg
10
Dickclles Energe
10
10
10
10"
10-11
GCN
GCN
OCN
GCN-Dala
GCN-Delky
10
10
10-14
32
64
16
32
Figure 10: Dirichlet Energy evolution of GCN (+delay mechanism) on different topologies. Left:
Cora. Middle: Grid graph. Right: Texas.
(%)
60
Fillaoe SSM
600
SSM, dggA)
40
40
20
20
50
100
0
30
100
Noces
Nodes
Figure 11: Left: Performance the Ring task for DRew on performance.
55
Right: Effect of dissipativity
16-
33'
02-
22
80-
-53
1.5
1.0
8.0
Figure 12: Eigenvalue distribution of DRew- BRew-lG on the ring transfer task.
D.3 Graph Property Prediction
Edge-of-chaos behavior and long-range propagation. To further support our claim that mitigating gradient vanishing is key strong long-range performance, Figure [3 each method's average Jacobian eigenvalue distance to the odge-of-chaos (EoC) region. The figure demonstrates that methods such as ADGN 47 and SWAN [48), which remain closer EoC, effectively propagate information over large graph radii, resulting in superior performance across all three tasks. Figure presents an ablation study on multiple ADGN variants, controlled by the hyperparameter 7, which governs the positioning of the Jacobian eigenvalues (7 0 places them outside the stability region, 0 inside, and 7 0 on the unit circle). Notably, regardless of the initial value of 7, ADGN consistently converges towards the EoC region performance improves.
31

---

DIAM
SSSP
ECC
1.0
1.0
ToC Distimo
0.0
0.0
500
1000
500
1000
500
1000
1.0
0.0
0.5
-2.0
0.0
1000
1000
Epochs
Epochs
Egpchh
ADGN
GCN
GIN
GraphCON
SWAN AWAN
Figure Performance on Graph Property Prediction tasks and average Jacobian eigenvalue distance to the edge of chaos (FoC) region for different GNN models.
DIAM
SSSP
EOC
0.3
FaC. Distoner
0.2
0.2
0.2
0.1
0.0
0.0
0.0
500
1.0
1.0
(SSE))
0.0
-1.0
-2.0
0.4
500
Epochs
Epocls
Epochs
ADGN(1 0.1)
ADGN(S 0)
ADGN 0.1)
ADGN(2 0.5)
ADGN 1)
Figure 14: Performance on Graph Property Prediction tasks and average Jacobian eigenvalue distance to the edge of chaos (EoC) region for different ADGN dynamics, i.e., 7 e [-0.1, 1]. Negative values of y places the eigenvalues of the ADGN Jacobian outside the stability region, otherwise for positive values.
Complete results. Table compares our method on graph property prediction tasks against range of state-of- of-the-ar art approaches, including GCN [6]] GAT [1OI. GraphSAGE (56). GIN [106,, GC- NII (26), DGC [103], GRAND (23, GraphCON 11], ADGN [77), SWAN 48, PH-DGN (9 and
DRew 55 Our method achieves exceptional results across three tasks, consistently surpassing
MPNN baselines, differential equation-inspired GNNs, and multi-hop GNNs. These findings under- score how combining powerful model dynamics with improved connectivity provides substantial benefits in tasks that require long-range information propagation.
32

---

Table Mean test set Logno (MSE)( and std averaged on 4 random weight initializations on Graph Property Prediction tasks. The lower, the better. Baseline results are reported from 47
48 59
Model
Diameter
SSSP
Eccentricity
MPNNS
GCN
0.7424
=0.001
0.8468 00.000
GAT
0.822 10.0752
16.551.01499
0.7909 20.0222
GraphSAGE
0,8645 10445.0.000 4400401
0.2863
0.7863 2000077
GIN
0.6131 1: .99u
-0.5408 _0.4008
0,9504 0000077
GCNII
0.5287 10.0570
1..332900.0138
0.7640=0.00m
Differential Equation inspired GNNs
DGC
40.000
-0.1483=m..2aa
0.8261 00,0
GRAND
0.6715 19711500.0400 10.0490
-0.0942200.3897
0.
GraphCON
0.0964 10.0620
-1.3836..0.00m
0.683310.0077
ADGN
-0.5188 10.1812
-3.2417
100075
0,4296 1003
SWAN
-0.5981 10.1145
-3.5425
-000800
-0.0739 =0. 2190
PH-DGN
00.473++0.1074
-4.2993 00.0721
-0,9348 -0.2007
Graph Transformers
GPS
0.5121+0.0422
-3.5990
=0.077=0
Multi-hop GNNs DRew-GCN + delay
2.36922t0.100
-1.5905=000034
-2.1004=0.0256
22.4018+0.1000
-1.6023
2.0029
Our
CCN-SSM
-2,4312 0329
2.8206=005666
-2.2446
222446600.002 0.0027
+ eig(A) =
-2.4442 10.0984 0984
-3.5928 1026
-2,2583 00.0088
+ k-hop
-3.0748 10.0545
-3.6044 000029
-4.2652 0.7176
D.4 Additional comments on LRGB tasks
In our experiments with the LRGB tasks, we observe that the peptides- task exhibits signifi- cantly longer-range dependencies than the septides-struce task. Notably, the peptides-stee -ttruc task performs best when the model is not initialized at the edge of chaos and requires fewer layers. Conversely, on peptides-fun the model performs best when it is set to at the edge of chaos, and shows monotonic performance increase with additional layers, with optimal results achieved when using forty layers.
Furthermore, we highlight that while our experiments with a small hidden dimension adhere to the parameter budget established in (36), increasing the hidden dimension (d 1) to 256 causes us to exceed the 500k parameter budget limit, even though our model maintains the same number of parameters as a regular GCN. While this budget a useful tool benchmark different models, we highlight that this restriction results in models running with fewer layers and small hidden dimensions. However, large number of layers is crucial for effective long-range learning in graphs that are not highly connected, while increasing the hidden dimension also directly affects the bound in Theorem 5.1 As such, we believe that this parameter budget indirectly benefits models with higher connectivity graphs, inadvertently hindering models that do not perform edge addition.
To further strengthen the comparison on real-world tasks, in Table we report results against GRED 32]. a method inspired by state-space models (SSMs). We note that our model achieves superior performance on peptides-fune, while GRED performs better on peptide-struct. Although GRED shares a few conceptual similarities with our approach, we emphasize several key differences: (i) GRED aggregates information from multiple neighborhoods at each layer, whereas our model aggregates from single-hop neighborhood per layer. (ii) GRED's 's SSM update operates inward, beginning with distant nodes and moving toward the root node, whereas our model each additional layer aggregates from progressively more distant neighbors, moving outward. This propagation pattern more consistent with the standard MPNN framework. (iii) Our model employs a fixed and non-learned state matrix, removing the need for additional constraints to guarantee stable learning dynamics. (iv) Unlike GRED, we do not perform weight sharing when applying k-hop aggregation. Finally, we stress that the primary goal of our model design is not achieve state-of-
33

---

the-art performance (as is the case with GRED) but rather to construct a minimal and controllable framework that allows to isolate and study specific phenomena of interest.
Table 5: Comparison with GRED on the LRGB dataset. 1 adds latent dims.
Pept-struct Pept-func
Model
APt
MAE] (x10
KGCN-SSM
69.02+0.22
28.98
+d
72.12
27.01
GRED
70.85
25.03
D.5 Scalability Results
In terms of runtime, GNN-SSM was deliherately designed to retain the simplicity and efficiency of its backbone (e.g., GCN). Our formulation introduces only two additional (fixed) matrices to store w.r.t. its backbone, and involves one element-wiss addition and two extra matrix multiplications per layer. These additions have a negligible impact on memory and runtime. Consequently, our model retains the complexity of its backbone while substantially improving performance, Tables 6 and below.
Table 6: Epoch Time (sec.) for GCN and GCN-SSM when performing node classification the Cora dataset.
Layers
GCN
GCN-SSM
5
0.009
0.009
0.015
0.017
20
0.025
0.031
30
0.041
0.046
40
0.053
0.051
50
0.066
0.075
60
0.078
0.089
Table 7: Accuracy on ogbn- 62
Model
ogbn-arxiv
MPNNs
GAT
72.01 10.20
GCN
70.84 10.23
GraphSAGE
71.49 10.27
Graph Transformers
NodeFormer
59.90
GraphGPS
70.92
GOAT
72.41 +0.40
EXPHORMER + GCN SPEXPHORMER
72.44 +0028
10.22
Our GCN-SSM
72.49 +0.16
D.6 State-Space Matrices Sensitivity
Empirically, we have that sharing A across layers did not alter performance: using a single fixed A yielded the same accuracy as training each A, with identical dynamics. Fixing ensures the system remains at the edge of chaos during training. Preserving this prior under a trainable A would require additional constraints, line with stabilization techniques used RNN architectures, see Table below.
34

---

Table Performance comparison for different design choices when performing node classification of the Cora dataset.
Layers
GCN-SSM (shared)
GCN-SSM (no sharing)
GCN-SSM (trained A)
5
76.3
78.3
71.3
10
78.5
78.5
71.1
20
81.2
77.8
49.9
30
78.1
79.6
33.8
40
77.5
78.5
31.9
50
76.4
74.6
31.9
60
77.8
77.4
31.9
D.7
Preliminary Results on Heterophilic benchmarks
To further complement the empirical evaluation of our method, we conducted experiments on three heterophilic tasks from [85]: Amazon Ratings, Roman Empire, and Minesweeper. We compared GCN-SSM against the original GCN results reported in [85]. as well as GCN with the same depth as our model (denoted GCN (Optimal L)). The depth for each task was tuned based on validation performance, resulting in optimal layer counts of 4 for Amazon Ratings, 9 for Roman Empire, and 12 for Minesweeper. Results, averaged over three random seeds, are reported Table show that GCN-SSM outperforms the original GCN by approximately accuracy points average, and exceeds GCN (Optimal L) by 31 accuracy points.
Table 9; Performance comparison of our GCN-SSM with respect to the original GCN results reported in 855, well as a GCN with the same depth as our model (denoted GCN (Optimal L)) on the heterophilic datasets from 85
Amazon Ratings
Roman Empire Acct
Minesweeper AUC1
Model
Acot
GCN 185
47.70+0.03 47.57+0.67
73.69
89.75
GCN (Optimal L)
33.83+0.41
60.84+00.8
GCN-SSM (Optimal L)
51.72
88.37
96.02.20.52
E
Additional Details and Comments on Over-Smoothing
E.1 Choice of Feature Distance Measure
Throughout the paper we adopt the unnormalized Dirichlet energy
{(H) = tr LH) =
Σ
h hel?
(u.a)eE
This choice aligns with several well cited papers in the over-smoothing literature 191 90] Moreover, the connection we unravel between vanishing gradients and over-smoothing also explains why expected to mitigate feature collapse in techniques borrowed from recurrent architectures 99
GNNs.
While our theoretical analysis focuses on {HH) for mathematical simplicity, we will now also evaluate an alternative smoothness measure to ensure our insights generalize beyond this choice, In particular, use the smoothness measure employed in other over-smoothing works [05 95
1 1 N
(HH)= H 7H 7h
empirical experiments this measure, which empirically shows that the qualitative trends predicted by our unnormalized-energy theory also manifest under this alternative metric. Although formal equivalence between these energies and our collapse proofs is not explored,
We report in Figure 15
35

---

this empirical alignment provides strong justification for the broader applicability of our analysis to the broader literature on oversmoothing.
10
(X 1K-1rxl
10
10
10-14
Layer
16
32
64
Figure 15: GCN-SSM on Cora with p (H) smoothing measure.
E.2
The effect of the Jacobian spectrum on node classification performance
order to assess how the spectral properties of the layer-wise Jacobian influence node-classification performance, we carried out the following two experiments on the Cora citation network.
First, we systematically varied the spectrum of the diagonal matrix in our GCN-SSM backbone. For each number of layers one of {1, 0.66, 0.33), retrained the model, and recorded the best accuracy. As shown in Table [O, moving the spectrum of A away from unity leads to pronounced degradation in accuracy, indicating that keeping the Jacobian eigenvalues near one crucial for stable and effective information propagation across many layers.
{5, 10, 20, 30, 40, 50, 60). we set the maximal eigenvalue of A to
Second, isolate the contribution of the SSM backbone itself, performed an analogous spectrum- shaping experiment directly on the weight matrix W of a vanilla GCN (i.e. without any SSM components). We scaled W that its spectral radius lay near the edge of stability (spectral norm x 1), but otherwise left the model architecture and training unchanged. Despite matching the Jacobian stability regime, these "spectrally tuned" vanilla GCNs failed to achieve the accuracy improvements seen with the full GCN-SSM backbone (first column of Table IO). This confirms that merely tuning W's spectrum insufficient: the structured state-space dynamics provided by the SSM backbone essential for the observed performance gains.
Table 10: Node-classification accuracy on Cora when varying the spectrum of the backbone Jacobian (A) and comparing vanilla GCN models whose weight matrix W is spectrally tuned near the edge of stability.
Wayyer
eig A)
eig(A)
0.66
eig(A)
0.33
eig(W) (GCN)
5
81.30
78.10
74.00
71.90
10
78.70
61.90
56.00
33,80
20
78.90
48.00
30.20
31.80
30
80.00
39.70
18,00
22.30
40
77.90
34.60
20.30
25.60
50
77.70
29.10
24.90
23,80
60
77.70
20.50
20.40
29.10
E.3
On Residual Connections and Gating
Several prior works have employed residual connections GNNs to counteract over-smoothing, for example, see [69]. In fact, these residual-GNN designs can be viewed special case of our approach, corresponding to the choice A I. Under this constraint, the model outperforms a standard, memoryless GCN (see Fig. 3), but only by accumulating node features in an unstructured way.
In order to guarantee stable propagation dynamics, the spectral properties of the propagation matrix B play an important role: by appropriately "damping" incoming signals, one can stabilize the system's behavior and prevent feature collapse explosion.
36

---

To highlight the role of B, we conducted an ablation study on the Cora dataset in which the propagation matrix was removed from our method. Table reports the results, showing that for deeper networks, the inclusion of B consistently improves performance. This behavior can be understood theoretically from the perspective of the Jacobian. While the eigenvalue structure induced by places the system near the edge of stability (with eigenvalues close to 1 in modulus), it is B that controls how much these dynamics "disperse" around the critical point (1,0) shown in Figure 2 In this setting, too much dispersion can lead to instability.
Table 1:: Node-clasifficttonn accuracy Cora with and without the propagation matrix B across different number of layers.
Wayyrr
Without B
With B
2
80.2
79.6
4
77.8
80.4
8
80.0
79.8
16
74.1
79.8
32
31.9
79.9
64
31.9
79.9
128
14.9
77.9
256
13.0
80.2
F
Supplementary Related Work and Limitations
Long-range propagation and depth GNNs. Learning long-range dependencies on graphs involves effectively propagating and preserving information across distant nodes. Despite recent advancements, ensuring effective long-range communication between nodes remains an open problem [96]. Several techniques have been proposed to address this issue, including graph rewiring methods, such as
42 100 65 & 13,, which modify the graph topology to enhance connectivity and facilitate information flow. Similarly, Graph Transformers enhance the connectivity to capture both local and
68 87 [04]. Other approaches incorporate non-local dynamics by using fractional power of the graph shift operator [74), leverage quantum diffusion kernels [73]. regularize the model's weight space [47
global interactions, as demonstrated by [T99] 35 97
48 49), exploit port-hamiltoniaa
dynamics [59]. or use graph adaptive method based learnable ARMA framework [37). Some methods which have increased the depth GNNs include [69 [T]. Alternative methods combine the spatial and spectral perspective of graph propagation enable long-range communication between nodes, either by using spatially and spectrally parametrized graph filters [43 or spectral filters based Chebyshev polynomials [57]. Recent work has also proposed new datasets test long range dependencies (70). as well as ways to theoretically measure them [4].
Despite the effectiveness of these methods in learning long-range dependencies graphs they primarily introduce solutions to mitigate the problem rather than establishing a unified theoretical framework that defines its underlying cause.
Vanishing gradients in sequence modelling and deep learning. One of the primary challenges in training recurrent neural networks lies in the vanishing (and sometimes exploding) gradient problem, which can hinder the model's ability to learn and retain information over long sequences. In response, researchers have proposed numerous architectures aimed at preserving or enhancing gradients through time. Examples include Unitary RNNs (2), Orthogonal RNNs (0), Linear Recurrent Units [81, and By leveraging properties such orthogonality, carefully designed parameterizations, or alternative update mechanisms, these models seek to alleviate gradient decay and capture range--ragee temporal relationships more effectively. We highlight recent work that also extends these insights to transformer based architectures 6
Structured State Space Models 53 52
Dynamical systems and physics inspired neural networks. Since the introduction of Neural ODEs in [27]. there have been various methods that employ ideas of dynamical systems within neural networks, including continuous-time methods [89 78
19
20
12
77 21 or state-space approaches
25 33 34 37). Within graph neural networks, we highlight PDE-GCN (38, GRAND 23, BLEND
22 and Neural Sheaf Diffusion [1]] in the static graph domain, while CTAN [50] and TG-ODE 51
37

---

in the temporal graph domain [46]. Other approaches which leverage other type of physics-inspired inductive biases such as topologiaal latent space modelling include 22
54 15 92
Broader Impact, Limitations and Future Work. We believe our work opens up a number of interesting directions that aim bridge the gap between graph and sequence modeling. In particular, we hope that this work will encourage researchers to adapt vanishing gradient mitigation methods from the sequence modeling community to GNNs, and conversely explore how graph learning ideas can be brought to recurrent models. In our work, we mostly focused on GCN and GAT type updates, we believe that our analysis can be extended to understand how different choices of updates and non non-lincarities affect training dynamics, which we leave for future work.
38


Reviews:
[{"review_id": "vGyWsRXnNm", "reviewer": "Reviewer_v1TX", "summary": "This paper analyzes depth‐related performance drops in GNNs (e.g., over-smoothing, over-squashing) through the lens of vanishing gradients. By vectorizing node features and treating layer-to-layer propagation as a dynamical system, this paper shows that standard graph convolution and attention layers are susceptible to gradient vanishing, whose Jacobians are strongly contractive because of the normalized adjacency operators. This paper introduces GNN-SSM, a state-space model-inspired architecture that explicitly controls the eigenvalues of the state transition matrix. This preserves gradient norms, prevents feature collapse, and, when combined with k-hop aggregation, achieves strong performance on synthetic long-range benchmarks and the LRGB tasks.", "questions": "Please see Weaknesses", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Pros: \n- This paper provides a unified perspective that links vanishing gradients, over-smoothing, and over-squashing via spectral bounds of Jacobians\n- To validate the theoretical analysis, this paper designs a simple remedy to the gradient-vanishing problem by making the eigenvalues of the state transition matrix close to 1, inspired by state-space models, and further combines k-hop aggregation to address over-squashing. The model's good empirical performance validates the theory\n\nCons:\n\nMy major concern with this paper is that its contribution/novelty compared to existing works is unclear.\n\nTheory side, the theoretical analysis of this paper has a lot of overlaps with previous studies. E.g., [1] analyzed over-smoothing from the dynamical system's point of view and reached similar conclusions about convergence to fixed points. [2] explored the connection between gradient-vanishing and over-squashing, similarly to this paper.\n\nModel design side, this paper proposes to connect SSMs and GNNs. This idea has already been explored in the graph SSM literature. Especially, the GNN-SSM architecture proposed by this paper is very similar to GRED [3]. GRED has already used LRU to bound the eigenvalues of the state transition matrix for stable signal propagation, and combined k hops to address over-squashing (similar to kGNN-SSM). However, the relation to GRED seems to be downplayed in this paper, lacking proper comparison/discussion\n\n[1] Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. ICLR 2020.  \n[2] On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology. ICML 2023.  \n[3] Recurrent Distance Filtering for Graph Representation Learning. ICML 2024", "was_revised": true, "final_justification": "The authors' rebuttal provides a more detailed explanation of the relation to previous works, which addresses my concerns. Given the new additions in the discussion, I'd like to raise my rating and recommend acceptance.", "rebuttal": "We would like to thank you very much for your thorough review. We also thank you for the excellent points you bring up, we would like to address them below.\n\n>**Weakness 1** Theory side, the theoretical analysis of this paper has a lot of overlaps with previous studies. E.g., [1] analyzed over-smoothing from the dynamical system's point of view and reached similar conclusions about convergence to fixed points. [2] explored the connection between gradient-vanishing and over-squashing, similarly to this paper.\n\nThank you for raising these great points. While we agree with the reviewer that there are similarities with prior work in the oversmoothing literature, we emphasize several key differences between our contributions and existing research:\n\n(i) We argue that the primary issue limiting depth in GNNs is not oversmoothing per se, but rather trainability, specifically, the problem of vanishing (and sometimes exploding) gradients. In fact, the well-known feature collapse phenomenon arises as a consequence of vanishing gradients. In our view, GNNs fail at large depths due to extreme trainability issues, not a loss of expressivity. To the best of our knowledge, this connection has not been explicitly discussed in prior work.\n\n(ii) The analysis in [1] is limited to GCNs and GATs. Our theoretical study also begins with these models to illustrate the severity of gradient vanishing in these models via Jacobian analysis. However, our use of layer-wise Jacobians to assess both network trainability and the degree of smoothing is novel, and can be applied to gain insight into any GNN layer that might be difficult to study mathematically. As an example of this, and in light of your suggestion and that of Reviewer ZDHY, we analyzed the Jacobian spectrum of a randomly initialized GIN layer and observed significant instability, with spectral norms reaching approximately 150 (much larger than the region of stability around 1), which would lead to exploding gradients when stacked together. This leads to divergent Dirichlet energy with more layers, which explains behaviors recently discussed in [3]. It is this instability, rather than the appearance of smoothing, that hampers GIN’s trainability. \n\nWe will include this analysis in the paper along with other common GNN architectures (e.g. Gated-GCN) to illustrate that our point is not restricted to GCNs.\n\nRegarding our theoretical treatment of over-squashing, we highlight key distinctions from [2]:\n\n(i) We explicitly connect oversmoothing and over-squashing via vanishing gradients. Building on our earlier results, we argue that even if two nodes are able to communicate perfectly at a given layer  $l$, this communication becomes ineffective if the messages have already collapsed to an uninformative fixed point. We demonstrate the importance of this effect in Figure 4. This connection, to our knowledge, was left open in [2], which states:\n\n> “On a different note, this work has not touched on the important problem of over-smoothing; we believe that the theoretical connections we have derived, based on the relation between over-squashing, commute time, and Cheeger constant, suggest a much deeper interplay between these two phenomena.”\n\n(ii) While [2] primarily focuses on rewiring to improve connectivity, we argue that it is equally important to prevent vanishing gradients through model design. We note that existing architectures that perform well in long-range tasks (e.g., Drew or GRED) implicitly address both aspects, although they do not explicitly state the importance of this combination or the reasons behind it. We test this through the kGCN-SSM framework, which was designed to be as minimal and controllable as possible, while still allowing us to isolate and showcase the role of effective rewiring and stable gradients. Our ablation studies confirm the necessity of these individual components.\n\nThis perspective contrasts with [2], which explicitly cautions against mitigating vanishing gradients via the model term:\n\n> “However, this is not an optimal solution since increasing the contribution of the model (i.e., the term $c_{\\sigma} w p$ may lead to overfitting and poorer generalization (Bartlett et al., 2017). Taking larger values of $c_{\\sigma}, w, p$ affects the model globally and does not target the sensitivity of specific node pairs induced by the topology...”\n\nMoreover, [2] hints toward the need to explore ideas from RNNs in this context:\n\n> “We believe that the relation between over-squashing and vanishing gradients deserves further analysis. In particular, it seems that there is a phase transition that MPNNs undergo—from over-squashing of information between distant nodes, to vanishing of gradients at the level of the loss. In fact, this connection suggests that traditional methods used in RNNs to mitigate vanishing gradients may also be beneficial for over-squashing.”\n\nOur work directly addresses and bridges the above gaps by offering theoretical insights and a minimal framework with which to prevent the effects of gradient vanishing.\n\n>**Weakness 2:** Model design side, this paper proposes to connect SSMs and GNNs. This idea has already been explored in the graph SSM literature. Especially, the GNN-SSM architecture proposed by this paper is very similar to GRED [3]. GRED has already used LRU to bound the eigenvalues of the state transition matrix for stable signal propagation, and combined k hops to address over-squashing (similar to kGNN-SSM). However, the relation to GRED seems to be downplayed in this paper, lacking proper comparison/discussion\n\nWe would like to clarify that the primary goal of our model design is not to achieve state-of-the-art performance (as is the case with GRED) but rather to construct a minimal and controllable framework that allows us to isolate and study specific phenomena we are interested in. In particular, GNN-SSM was designed to investigate the influence of vanishing gradients, while kGNN-SSM extends this to jointly analyze the impact of vanishing gradients and rewiring. For this reason, the majority of our experiments take the form of targeted ablations rather than performance benchmarks.\n\nThe k-hop rewiring scheme was deliberately chosen to be similar to that of DRew [5], with the distinction that in our setting, a node at layer $l$ only aggregates information from nodes exactly $l$-hops away. This choice allowed us to construct a strong baseline that supported an independent evaluation of gradient stability and its effect on over-squashing. As the reviewer notes, this also bears resemblance to GRED; however, we emphasize that such multi-hop aggregation schemes predate GRED or Drew, for instance, ChebNet [4], which is one of the earliest GNN designs, uses a very similar aggregation scheme. \n\nHaving said this, we also note several important differences:\n\n(i) **Aggregation scope**: GRED aggregates information from several neighborhoods at each layer. In contrast, our approach aggregates from a **single-hop neighborhood** per layer.\n\n(ii) **Aggregation direction**: GRED’s SSM update operates inward, beginning with distant nodes and moving toward the root node. In our model, each additional layer aggregates from progressively more distant neighbors, moving outward. This pattern is more consistent with the standard MPNN framework.\n\n(iii) **Parameterization of the state matrix**: In our model, the state matrix is fixed and not learned, eliminating the need for additional constraints to guarantee stable learning dynamics.\n\n(iv) **Weight sharing**. We do not perform weight sharing when performing k-hop aggregation, as in GRED.\n\nWe stress that our intention was not to downplay GRED, but rather to conduct a fair evaluation. We found our model to be more related to DRew (due to their similar rewiring and information processing schemes), which made the comparison much more amenable to ablation. In particular, in DRew, we can directly assess the impact of the model term by removing the delay term, while doing so in GRED was slightly more complex. For example, GRED is wrapped around a “Transformer-type block” structure, which we thought would make it hard to disentangle what was driving performance exactly, and would potentially limit the validity of a controlled ablation.\n\nNonetheless, in response to the reviewer’s comment, we now include the following results on the Peptides dataset:\n\n| Dataset           | Model              | Performance (Mean ± Std) |\n|------------------|--------------------|---------------------------|\n| Peptides-func     | kGCN-SSM (small \\(d\\)) | 69.02 ± 0.218             |\n|                  | kGCN-SSM (large \\(d\\)) | 72.12 ± 0.268             |\n|                  | GRED                | 70.85 ± 0.27              |\n| Peptides-struct   | kGCN-SSM (small \\(d\\)) | 28.98 ± 0.324             |\n|                  | kGCN-SSM (large \\(d\\)) | 27.01 ± 0.071             |\n|                  | GRED                | 25.03 ± 0.19              |\n\nWe will also include a more extensive discussion of these comparisons in the revised version, as well as more detailed ablations on both the Peptides and GPP tasks.\n\nIn light of the clarified contributions above, we kindly ask the reviewer to consider raising their score or let us know whether there is further improvement that will lead to a more favourable evaluation of our work.\n\n[1] Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. ICLR 2020.\n\n[2] On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology. ICML 2023.\n\n[3] Arnaiz-Rodriguez, A., et al.. \"Oversmoothing,\" Oversquashing\", Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning. arXiv preprint arXiv:2505.15547 (2025).\n\n[4] Defferrard, M., et. al. \"Convolutional neural networks on graphs with fast localized spectral filtering.\" NeurIPS 2016.\n\n[5] Gutteridge, B., et al. \"Drew: Dynamically rewired message passing with delay.\" ICML 2023."}, {"review_id": "bSt4MoHawv", "reviewer": "Reviewer_CMgd", "summary": "The paper presents a GNN as convolutional neural network with recurrent state updates. This connection is then exploited to create a state-space formulation of the GNN gradient descent updates. The nature of gradient update across the shared weights is shown as an evolution dynamics in state space. The problems of vanishing gradient and homogenization are explained in terms of this state-space dynamics. The issue of diminishing effect of distant nodes are also shown to exist.\n\nNext, authors propose changes in the learning and update mechanism which arrest these problems. The state-space formulation allows a control theoretic analysis of the strategies and synthesis of effective update rules. The method is elegant.", "questions": "1. Does the proposed method scale to very large scale GNN where the challenges of vanishing gradient and homogenization are even more pronounced.\n\n2. How does the proposed method compare with state of art GNN training techniques which are not based on state space formulations but use sophisticated optimizer and message passing heuristics.\n\n3. Provide a discussion between the functional differences in the proposed method to avoid vanishing gradient in comparison with the known approaches in literature.", "limitations": "The method is elegant. More results on large scale GNNs are required to consider the preent work as a state of art in GNN training.\n\nFurther experimental results comparing with state of art in GNN with respect to the identified challenges should be presented.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The strength of the paper is the elegant state-space formalization of the GNN learning problem. The effects of vanishing gradient and homogenization can be easily observed in this analysis framework. Mitigation of these challenges using control theoretic methods in the state-space is found to be effective. Experimental results demonstrate effectiveness of the proposed technique.\n\nThe theoretical formulation is nice. However, there are some concerns about practical applicability in large scale GNN. The resulting state-space may explode and many of the existing control theoretic methods my break-down in large state-spaces. The typical state-space sizes common in control theoretic problems are much smaller.\n\nComparison with state-of-art GNN training schemes are not presented in the experimental results section. particularly the ones which rely on modifications of the message passing techniques.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive review. We respond to your questions and comments below.\n\n> Does the proposed method scale to very large scale GNN where the challenges of vanishing gradient and homogenization are even more pronounced.\n>How does the proposed method compare with state of art GNN training techniques which are not based on state space formulations but use sophisticated optimizer and message passing heuristics.\n\nThank you for your question regarding scalability and comparison with more sophisticated GNN training strategies.\nIn terms of computational complexity and scalability, GNN-SSM was deliberately designed to retain the simplicity and efficiency of its backbone (e.g., GCN). Our formulation introduces only two additional fixed matrices and involves one elementwise addition and two additional matrix multiplications per layer. This has a negligible effect on memory and runtime, particularly when compared to models with learnable global attention or deep message-passing schemes. As a result, GNN-SSM maintains the scalability of its base architecture, which we demonstrate below.\n\n| # Layers | GCN   | GCN-SSM |\n|----------|--------|-----------|\n| 5        | 0.009  | 0.009     |\n| 10       | 0.015  | 0.017     |\n| 20       | 0.025  | 0.031     |\n| 30       | 0.041  | 0.046     |\n| 40       | 0.053  | 0.051     |\n| 50       | 0.066  | 0.075     |\n| 60       | 0.078  | 0.089     |\n\nTo further assess scalability and performance, we also evaluated GCN-SSM on the large-scale ogbn-arxiv benchmark. \n| Dataset     | GCN             | GCN-SSM         |\n|--------------|------------------|------------------|\n| ogbn-arxiv   | 70.84 ± 0.23     | 72.49 ± 0.16     |\n\n\nTo contextualize this, we compare it with published results from a range of MPNN and Graph Transformer baselines, see [4]\n\n| Model              | ogbn-arxiv     |\n|--------------------|----------------|\n| GraphSAGE          | 71.49 ± 0.27   |\n| GAT                | 72.01 ± 0.20   |\n| NodeFormer         | 59.90 ± 0.42   |\n| GraphGPS           | 70.92 ± 0.04   |\n| GOAT               | 72.41 ± 0.40   |\n| EXPHORMER + GCN    | 72.44 ± 0.28   |\n| SPEXPHORMER        | 70.82 ± 0.24   |\n\nAs the results show, GCN-SSM is competitive with or better than several recent high-performing models that rely on more complex architectures or training schemes, despite using a simpler, more interpretable design.\n\nFurthermore, the paper already includes extensive comparisons on synthetic graph algorithm benchmarks designed to test long-range reasoning capabilities, which includes state-of-the-art methods like DRew [5].  Below, we reproduce the relevant portion of the table for reference:\n\n| Model            | Diameter         | SSSP             | Eccentricity     |\n|------------------|------------------|------------------|------------------|\n| **MPNNs**        |                  |                  |                  |\n| GCN              | 0.7424 ± 0.0466  | 0.9499 ± 0.0001  | 0.8468 ± 0.0028  |\n| GAT              | 0.8221 ± 0.0752  | 0.6951 ± 0.1499  | 0.7909 ± 0.0222  |\n| GraphSAGE        | 0.8645 ± 0.0401  | 0.2863 ± 0.1843  | 0.7863 ± 0.0207  |\n| GIN              | 0.6131 ± 0.0990  | -0.5408 ± 0.4193 | 0.9504 ± 0.0007  |\n| GCNII            | 0.5287 ± 0.0570  | -1.1329 ± 0.0135 | 0.7640 ± 0.0355  |\n| **DiffEq-inspired GNNs** |         |                  |                  |\n| DGC              | 0.6028 ± 0.0050  | -0.1483 ± 0.0231 | 0.8261 ± 0.0032  |\n| GRAND            | 0.6715 ± 0.0490  | -0.0942 ± 0.3897 | 0.6602 ± 0.1393  |\n| GraphCON         | 0.0964 ± 0.0620  | -1.3836 ± 0.0092 | 0.6833 ± 0.0074  |\n| ADGN             | -0.5188 ± 0.1812 | -3.2417 ± 0.0751 | 0.4296 ± 0.1003  |\n| SWAN             | -0.5981 ± 0.1145 | -3.5425 ± 0.0830 | -0.0739 ± 0.2190 |\n| PH-DGN           | -0.5473 ± 0.1074 | -4.2993 ± 0.0721 | -0.9348 ± 0.2097 |\n| **Graph Transformers** |         |                  |                  |\n| GPS              | -0.5121 ± 0.0426 | -3.5990 ± 0.1949 | 0.6077 ± 0.0282  |\n| **Multi-hop GNNs** |               |                  |                  |\n| DRew-GCN         | -2.3692 ± 0.1054 | -1.5905 ± 0.0034 | -2.1004 ± 0.0256 |\n| + delay          | -2.4018 ± 0.1097 | -1.6023 ± 0.0078 | -2.0291 ± 0.0240 |\n| **GCN-SSM (ours)**| -2.4312 ± 0.0329| -2.8206 ± 0.5654 | -2.2446 ± 0.0027 |\n| + eig(Λ) ≈ 1     | -2.4442 ± 0.0984| -3.5928 ± 0.1026 | -2.2583 ± 0.0085 |\n| + k-hop          | -3.0748 ± 0.0545| -3.6044 ± 0.0291 | -4.2652 ± 0.1776 |\n\nThese results highlight that GNN-SSM not only scales well in practice, but also achieves competitive or superior performance across both real-world and synthetic tasks, while maintaining a minimal and interpretable formulation.\n\n> Provide a discussion between the functional differences in the proposed method to avoid vanishing gradient in comparison with the known approaches in literature.\n\nOur approach, unlike other recent methods for mitigating vanishing gradients in GNNs [1–3], gives explicit control over the model's dynamics via the spectrum of the Jacobian. This allows us to directly regulate gradient flow and stability. We will add a brief discussion of this in the revised version, along with a comparison to other more opaque strategies for gradient mitigation, such as those relying on normalization layers or residual scaling, which often lack interpretability.\n\n[1] Alessio Gravina, Davide Bacciu, and Claudio Gallicchio. Anti-Symmetric DGN: A Stable Architecture for Deep Graph Networks. ICLR, 2023.\n\n[2] 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. AAAI, 2025.\n\n[3] T. Konstantin Rusch, Ben Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael Bronstein. Graph-Coupled Oscillator Networks. ICML, 2023.\n\n[4] Luo, Yuankai, et al. \"Enhancing graph transformers with hierarchical distance structural encoding.\" Advances in Neural Information Processing Systems 37 (2024): 57150-57182.\n\n[5] Gutteridge, Benjamin, et al. \"Drew: Dynamically rewired message passing with delay.\" International Conference on Machine Learning. PMLR, 2023."}, {"review_id": "V5EjLPVowc", "reviewer": "Reviewer_ZDHY", "summary": "This paper proposes to study problems associated with graph neural networks such as oversmoothing and oversquashing through the lens of vanishing gradients. Vanishing gradients were originally studied in recurrent neural networks, and this paper argues that vanishing gradients can also be used to study oversmoothing and oversquashing in GNNs. Gradients are already commonly used as a tool for quantifying oversquashing, but this paper uses vanishing gradients to unify the study of oversmoothing and oversquashing. The contributions of this paper are as follows:\n- Theorem 3.2 proves that if the weight matrix is normally distributed with variance < 1, then the Jacobian of a GCN has eigenvalues < 1, so GCNs would experience vanishing gradients in this setting. Figures 2, 5, and 6 analyses the eigenvalues of real GNNs and show that Theorem 3.2 is true in practice.\n- The paper proposes GNN-SSM as a remedy for the vanishing gradient problem posed by Theorem 3.2. GNN-SSM combined elements of classical GNNs with state-space models. \n- Proposition 3.3 shows that the eigenvalues of the Jacobian of GNN-SSM are controlled both by a GNN update (which by Theorem 3.2 has small eigenvalues) and a state transition matrix. Thus, by controlling the eigenvalues of the state transition matrix, the eigenvalues of the entire Jacobian can be controlled. This is validated in Figure 2.\n- The paper use vanishing gradient to prove why may GNNs experience oversmoothing. Proposition 4.4 shows that GNNs that experience vanishing gradients will also experience oversmoothing. It proves this by showing that the feature of GNNs with vanishing gradients will necessarilly converge to the zero vector as their norms shrink with each layer. This also implies that the Dirichlet energy of the node features will decrease after each layer. Figures 7 and 8 demonstrate that a GNN-SSM has constant Dirichlet energy across layers.\n- The paper argue GNN-SSMs can also help alleviate oversquashing. It was previously argued that oversquashing was caused by small gradients between the features of different nodes. The authors argue that GNN-SSMs could increase the gradient between nodes, thereby alleviating oversquashing. One of the most common remedies for oversquashing is rewiring. Figure 4 shows that using rewiring in conjunction with GNN-SSMs improves over using either of them separately.\n- The authors test GNN-SSMs on various real world datasets and show that GNN-SSMs can improve over vanilla GNNs in these settings. Tables 1, 2, and 4 show that GNN-SSMs typically outperform classical GNN baselines on these tasks.", "questions": "# Questions\n- How are the state transition matrices $\\Lambda$ computed, and how do you control their eigenvalues? Are these matrices learnable or fixed?\n- In Figure 3, middle, what is model is this plotting the features for?\n\n# Suggestions\n- Figure 1 is a little hard to understand, even after reading the paper. What are the blue lines? Which circles correspond to features of the same node? What circle are at the same layer, and which are at different layers? I think this figure could be improved if each element was more clearly labelled.\n- The boxes around the theorem statements look awkward as the text inside the box is too close to the edge. I would recommend using larger margins on the border of the box. Borders on the boxes and rounded corners may also improve the look of the boxes. \n\n# Typos\nLine 109: \"over-smoothing [15, 68] describes the tendency\". I am not sure what you intended to say here, but there must have been a typo as this sentence doesn't make sense.\nLine 777: \"were run in\" -> \"were run on\"", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths\n\n- The authors do an excellent job of validating their claims both theoretically and experimentally. Every theorem in the paper has an accompanying experiment showing this holds in practice and an experiment demonstrating how properly designed GNN-SSMs can alleviate the observed bad behavior. Thus, the authors demonstrate conclusively that GNNs face several problems that GNN-SSMs can help fix.\n- The authors empirically show that GNN-SSMs can achieve strong performance on real datasets compared to many baselines.\n- In this weaknesses, I mention that some of the theoretical results only prove sufficient but not necessary conditions for many of the claims in the paper. However, in these instances, the paper does a good job of augmenting the theoretical results with empirical evidence to show that fixing vanishing gradients can help fix the problem in question.\n\n# Weaknesses\n\n- Many of the theoretical results are one-sided. e.g., only proving a sufficient but not necessary condition for the expected behavior. For example, Proposition 3.3 only proves an upper bound on the Jacobian by the norm of the state transition matrix, so increasing the norm of the state transition matrix will not necessarily increase the norm of the Jacobian. Likewise, Proposition 4.4 show that vanishing gradients can lead to decreasing Dirichlet energy. Thus, Proposition 4.4 does not prove that decreasing Dirichlet energy only happens when there are vanishing gradients, and alleviating vanishing gradients is necessary but not necessarily sufficient to fix these oversmoothing.  \nLikewise, Theorem 3.2 only holds for GCNs, while ideally it would hold for more general message-passing networks like GINs or GATs.", "was_revised": true, "final_justification": "After reading the rebuttal to my review, and the reviews and rebuttals of all other reviewers, I maintain my original opinion that this is a strong paper that is clearly worthy of acceptance at NeuRIPS.", "rebuttal": "Thank you for the very positive and encouraging review. We're glad to hear that both the theoretical and empirical aspects of the paper came through clearly. We also appreciate your constructive comments on the scope of our theoretical results, and we hope that the clarifications and additions in our rebuttal help to address any remaining concerns.\n\n> Many of the theoretical results are one-sided. e.g., only proving a sufficient but not necessary condition for the expected behavior. For example, Proposition 3.3 only proves an upper bound on the Jacobian by the norm of the state transition matrix, so increasing the norm of the state transition matrix will not necessarily increase the norm of the Jacobian. Likewise, Proposition 4.4 show that vanishing gradients can lead to decreasing Dirichlet energy. Thus, Proposition 4.4 does not prove that decreasing Dirichlet energy only happens when there are vanishing gradients, and alleviating vanishing gradients is necessary but not necessarily sufficient to fix these oversmoothing. Likewise, Theorem 3.2 only holds for GCNs, while ideally it would hold for more general message-passing networks like GINs or GATs.\n\nThank you for this thoughtful and technically precise feedback. As you rightly point out, many of our theoretical results establish sufficient (but not necessary) conditions. In some cases, such as Proposition 3.3, we only prove upper bounds (e.g., on the Jacobian norm via the state transition matrix). While this does not guarantee that increasing the norm of $\\Lambda$ will necessarily increase the Jacobian norm, we observed empirically that this correspondence does hold in practice. We will make the limitations of these results clearer in the revised version.\n\nYour comment on oversmoothing is particularly insightful. Our core argument is that what is commonly referred to as \"over-smoothing\" largely stems from the contractive nature of typical GNNs, and that vanishing gradients are a primary underlying cause. While vanishing gradients are not the only mechanism that can lead to over-smoothing, we believe that it captures the majority of such failures observed in practice. In our view, the depth limitations in GNNs stem more from trainability issues than expressivity constraints due to convergence to rank-one representations. \n\nWe would also like to clarify that while Theorem 3.2 focuses on GCNs, our analysis also extends to GATs, since attention-weighted adjacency matrices share the same contractive properties. As you correctly note, we do not currently formalize behavior for more general GNNs such as GIN. This is indeed more difficult to analyze rigorously, but one advantage of our Jacobian-spectrum-based analysis is that it can be applied to arbitrary GNN layers. Inspired by your suggestion and that of Reviewer v1TX, we computed the Jacobian spectrum for a randomly initialized GIN layer and found it to be highly unstable (with spectral norms around 150), resulting in divergent Dirichlet energy. This may help explain behaviors recently highlighted in [1], and we will include this analysis in the revised manuscript.\n\n>How are the state transition matrices $\\Lambda$ computed, and how do you control their eigenvalues? Are these matrices learnable or fixed?\n\nThank you for the question. To construct the state transition matrices $\\Lambda$, we begin by generating a random unitary matrix, which has all eigenvalues on the unit circle. We then scale it to control the spectral radius. Alternatively, we can compute its eigendecomposition, manually place the eigenvalues where desired (e.g., near 1 in modulus), and reconstruct the matrix. This allows us to design $\\Lambda$ with precise control over the system dynamics.\n\nIn terms of training, we keep $\\Lambda$ fixed. We made this decision to ensure controllable and stable dynamics, as we found that making $\\Lambda$ learnable led to divergence and instability during training. We had mentioned this briefly in line 99, but based on your feedback, we will now include a more dedicated explanation in the revised manuscript.\n\n> In Figure 3, middle, what is model is this plotting the features for?\n\nThank you for pointing that out. All plots in Figure 3 (including the middle one) are for the Cora dataset. We'll make this clearer in the revised version to avoid any confusion.\n\n> Figure 1 is a little hard to understand, even after reading the paper. What are the blue lines? Which circles correspond to features of the same node? What circle are at the same layer, and which are at different layers? I think this figure could be improved if each element was more clearly labelled\n\nThank you for the feedback. We agree that Figure 1 can be clarified further. To address your questions:\n- The blue lines indicate how each node feature evolves across layers, that is, how the 2D feature vector for each node changes as more layers are added.\n- Each circle corresponds to a node’s 2D feature at a given layer and is placed in the x-y plane according to the feature values.\n- Circles connected by a blue line represent the same node across successive layers.\n- The color of each circle encodes the norm of the node feature.\n\nThe goal of the figure is to illustrate that node features evolve through the network in a norm-preserving manner, without collapsing or contracting, which aligns with the theoretical results discussed in the paper. We will revise the caption to make these points clearer.\n\n> The boxes around the theorem statements look awkward as the text inside the box is too close to the edge. I would recommend using larger margins on the border of the box. Borders on the boxes and rounded corners may also improve the look of the boxes\nLine 109: \"over-smoothing [15, 68] describes the tendency\". I am not sure what you intended to say here, but there must have been a typo as this sentence doesn't make sense. Line 777: \"were run in\" -> \"were run on\"\n\nThank you, we’ll fix these typos! We also appreciate the suggestion regarding the theorem boxes. We’ll increase the internal padding, and we’ll experiment with using borders and rounded corners to improve readability and visual consistency.\n\n\n\n[1] Arnaiz-Rodriguez, Adrian, and Federico Errica. \"Oversmoothing,\" Oversquashing\", Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning. arXiv preprint arXiv:2505.15547 (2025)."}, {"review_id": "aA2U2ZwCzi", "reviewer": "Reviewer_VdM3", "summary": "This paper investigates the problem of vanishing gradients in Message-Passing Neural Networks (MPNNs) through a theoretical analysis grounded in signal processing. The authors highlight that many MPNNs experience what they term \"extreme gradient vanishing\", a phenomenon closely tied to over-smoothing. To address this, they introduce a state-space formulation for GNNs, referred to as kGNN-SSM, and demonstrate that in certain settings, this model avoids vanishing gradients and performs well on some long-range tasks.", "questions": "- Please see the \"Weaknesses\" section above and the conclusions.\n\n- It is unclear to me if any kind of positional encodings were used. Mentioning this in Table 3 would be useful.", "limitations": "The authors should discuss their limited empirical evaluation for the kGNN-SSM model if additional experiments will not be performed.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n\n1. The paper is very well-written.\n2. While prior work has suggested a connection between vanishing gradients and issues like over-squashing and over-smoothing, this paper does an excellent job of formalizing those intuitions. The authors present a rigorous theoretical framework that makes these relationships explicit and clarifies a set of long-standing assumptions in the community.\n3. The paper also effectively links over-smoothing to the limited long-range capabilities of MPNNs, adding further clarity to how these phenomena affect their performance.\n4. The authors offer several insightful observations on why standard approaches for handling long-range dependencies or representation collapse, especially those borrowed from sequence modeling, may not translate effectively to GNNs. For instance, the comment from lines 164–165 offers a particularly clear example.\n5.  I find the empirical analysis of the different GNN models to be insightful (e.g., Figs. 2 - 3, Figs. 5 - 13).\n\n**Weaknesses**:\n\n1. Minor typo: line 108: GNNs are known.\n2. Minor typo: I believe that the authors wanted to refer to peptides-func on Line 823 - \"Conversely, on peptides-func (...)\". \n3. The font for some figures should be increased. Figure 2 is particularly hard to read.\n4. The authors might consider adding a related work discussion regarding the connection between their analysis and recently proposed spectral methods for modelling long-range interactions, such as [[4]] or [[5]].\n5. While the theoretical analysis is strong and the authors connect vanishing gradients to over-smoothing and over-squashing in a compelling way, the proposed GNN-SSM model is very similar to prior work, such as GRED [[1]], with the main difference being the use of a custom SSM formulation instead of an LRU. As noted by the authors in Line 215, one could easily incorporate mechanisms like gating or other constraints on the state transition matrix, but the paper does not explore such variants. This makes the model feel more like a proof of concept rather than a technically novel contribution. The paper misses an opportunity to explore these minimal architectural variations of the GNN-SSM. Even a small set of experiments testing whether design choices like gating improve performance would have helped assess the proposed approach better.\n6. The empirical evaluation of GNN-SSM is limited in both scope and depth. The model is only tested on the Peptides datasets from the LRGB, while other relevant datasets like PCQM-Contact are excluded. Moreover, the analysis focuses mainly on long-range tasks and does not consider standard graph benchmarks such as QM9, ZINC, ogbn-arxiv, or ogbn-proteins. Including these would help determine whether GNN-SSM generalizes beyond specialized cases.\n7. It is unclear to me whether the peptides-func dataset is a truly reliable indicator of long-range modeling capabilities. Prior work has shown that adding positional encodings to standard MPNNs (such as a GCN) can already lead to strong performance [[3]], which calls into question how much the gains on peptides-func are due to actual long-range modelling. A more targeted evaluation, such as the mechanistic in-context learning task from S2GNN [[4]], would better demonstrate the model’s ability to handle long-range dependencies in practice.\n8. The evaluation of over-smoothing effects would be more convincing if it included better heterophilic datasets. Although the authors report results on the Texas dataset from the WebKB collection, this collection has been heavily scrutinized in recent work, and more reliable alternatives have been proposed [[2]]. I recommend including at least one of these newer datasets to provide a more solid quantitative analysis.\n\n**Conclusions**:\n\nOverall, I appreciate the theoretical framework developed by the authors. Formalizing the link between vanishing gradients, over-smoothing, and over-squashing adds valuable clarity to ongoing discussions around the limitations of MPNNs, while also building meaningful connections to the sequential modeling literature. The idea of permutation-equivariant GNN-SSMs is compelling, and the theoretical setup provides a strong justification for the model's design.\n\nHowever, I found the empirical evaluation underwhelming. The proposed kGNN-SSM shares conceptual similarities with prior works such as Drew, GRED, and to some extent, with more recent models like S2GNN [[4]], which also draws parallels between long-range graph learning and state-space models. The current evaluation does little to differentiate the proposed model or explore its capabilities in depth. As it stands, the model functions more as a theoretical proof-of-concept than a technically novel or well-tested contribution. While this framing is valid due to the more theoretical nature of the work, it feels like a missed opportunity to more fully explore the empirical potential of the proposed model. I would have preferred either a more concise theoretical discussion paired with deeper empirical analysis or a more extended version of the paper, which would maybe be better suited as a journal submission.\n\nScoring this paper was difficult. It is very well-written, and the theoretical contributions are sound and interesting. The authors demonstrate that both vanishing gradients and over-smoothing affect the long-range capabilities of MPNNs, and that they are, in fact, connected. However, the GNN-SSM model lacks technical novelty, and its empirical evaluation is limited. Despite the comprehensive comparisons between various GNN models in the Supplementary, the evaluation of the proposed GNN-SSM itself feels disconnected from the strong theoretical motivation.\n\nMy initial score is a 4 (Borderline Accept). That said, I am genuinely inclined toward accepting the paper and will raise my score to a 5 (Accept) or 6 (Strong Accept) if the authors address some of my concerns. The most valuable and \"low-hanging\" additions, in my opinion, would be evaluating GNN-SSM on the heterophilic datasets proposed in [[2]] and on more standard graph or node property prediction tasks (see Weakness 5). These datasets are relatively small, and the experiments should be feasible to run during the rebuttal period. Please note that I will not lower my score if GNN-SSM underperforms on these datasets; my concern is about completeness, not performance.\n\nI would also be excited to see variants of GNN-SSM that incorporate gating or related architectural changes, and I believe that running the mechanistic in-context learning experiment from S2GNN [[4]] would provide especially strong evidence of long-range modeling capabilities. While I understand these additions may be difficult to implement within the rebuttal timeline, I highly recommend that the authors consider them for an eventual camera-ready version. In my view, they would significantly strengthen the paper.\n\n\n[1]: https://arxiv.org/pdf/2312.01538v1\n[2]: https://arxiv.org/pdf/2312.01538v1\n[3]: https://arxiv.org/abs/2309.00367\n[4]: https://arxiv.org/pdf/2405.19121\n[5]: https://arxiv.org/pdf/2506.07624", "was_revised": true, "final_justification": "- The authors have performed new experiments on the heterophilic datasets from [Platonov2023] and on ogbn-arxiv, demonstrating that their proposed model has good results on node-level tasks.\n\n- The authors have further analyzed the role of the input matrix B.\n\n- The authors had satisfying responses to the other reviewer's comments.\n\n---\n\nThe authors have briefly discussed the behaviour of their model when gating mechanisms are included, and have concluded that they ``interfered with training dynamics in non-trivial ways''. While I do think that a discussion regarding gating is a great addition, I do not think it is necessary for the paper to be accepted, and I acknowledge the limited rebuttal time.\n\nOverall, I believe that the paper is solid and it should be accepted.", "rebuttal": "Thank you for your careful and detailed reviews. We're especially grateful that you highlighted some of the good qualities of our work and provided thoughtful suggestions on how to improve. Also, thank you for emphasizing the observation on lines 164–165, as this is a very subtle and important point, and we're glad it resonated with you. We hope that the revisions we've made in response to your comments have improved the paper and addressed your concerns.\n\n>Minor typo: line 108: GNNs are known.\nMinor typo: I believe that the authors wanted to refer to peptides-func on Line 823 - \"Conversely, on peptides-func (...)\".\nThe font for some figures should be increased. Figure 2 is particularly hard to read.\n\nThank you for pointing out these minor issues. We’ve corrected the typos at lines 108 and 823, and we’ve increased the font size in several figures, particularly in Figure 2, which we agree was difficult to read in its original form. \n\n>The authors might consider adding a related work discussion regarding the connection between their analysis and recently proposed spectral methods for modelling long-range interactions, such as [4] or [5].\n\nThank you for this valuable suggestion. We find [4] particularly interesting for its elegant combination of spatial and spectral perspectives, and we agree that exploring potential connections with our recurrent mechanism would be a worthwhile direction for future work. As for [5], it indeed builds on ideas closely related to ours regarding signal propagation, and we will definitely cite it in the revised version.\n\n>While the theoretical analysis is strong and the authors connect vanishing gradients to over-smoothing and over-squashing in a compelling way, the proposed GNN-SSM model is very similar to prior work, such as GRED [1], with the main difference being the use of a custom SSM formulation instead of an LRU. As noted by the authors in Line 215, one could easily incorporate mechanisms like gating or other constraints on the state transition matrix, but the paper does not explore such variants. This makes the model feel more like a proof of concept rather than a technically novel contribution. The paper misses an opportunity to explore these minimal architectural variations of the GNN-SSM. Even a small set of experiments testing whether design choices like gating improve performance would have helped assess the proposed approach better.\n\nThank you for this thoughtful and constructive comment. We have outlined the main conceptual and architectural differences between GNN-SSM and GRED in our response to Reviewer v1TX, particularly regarding our use of a custom SSM formulation with an emphasis on minimalism and interpretability.\n\nThat said, we found your suggestion regarding gating mechanisms particularly relevant. We deliberately avoided incorporating more complex design elements (such as gating or structured transition matrices) in the initial version of our model, as our aim was to isolate and highlight the role of vanishing gradients through targeted ablations. However, we agree that our manuscript could have explored the impact of such variations more explicitly.\n\nOne component we believe plays a critical role in gating is the input matrix B, which modulates the influence of input signals on the recurrent dynamics. To initially test the influence of this, we performed an ablation study on the Cora dataset, in which we removed the B matrix. The results are shown below: \n\n| # Layers (n) | No **B** | **B** |\n|--------------|----------|-------------------------------|\n| 2            | 80.2     | 79.6                          |\n| 4            | 77.8     | 80.4                          |\n| 8            | 80.0     | 79.8                          |\n| 16           | 74.1     | 79.8                          |\n| 32           | 31.9     | 79.9                          |\n| 64           | 31.9     | 79.9                          |\n| 128          | 14.9     | 77.9                          |\n| 256          | 13.0     | 80.2                          |\n\n\nThis behavior can be understood theoretically from the perspective of the Jacobian: While the eigenvalue structure induced by $\\Lambda$ places the system near the edge of stability (with eigenvalues close to 1 in modulus), it is B that controls how much these dynamics \"disperse\" around the critical point (1,0) shown in Figure 2. In this setting, too much dispersion can lead to instability.\n\nTo test this further, we scaled the B matrix by a constant $\\alpha=$(1/nlayers), which should, in principle, make the eigenvalues closer to the critical point by reducing dispersion while still enabling information to be processed by the network. We found that this scaled variant significantly stabilizes the loss and accelerates convergence, requiring roughly an order of magnitude fewer epochs to reach a solution on the Cora dataset. Although we are unable to include additional plots in the rebuttal, we will present these findings in the camera-ready version in a dedicated section, as this appears to be a promising direction for future research.\n\nWe also experimented with a variety of other gating mechanisms during the rebuttal, but found that many interfered with training dynamics in non-trivial ways. Nevertheless, we think that the consistent benefits we observed from appropriately modulating B underscore the importance of exploring such mechanisms, and we will likely investigate this in future work.\n\nThank you again for the insightful suggestion.\n\n> The most valuable and \"low-hanging\" additions, in my opinion, would be evaluating GNN-SSM on the heterophilic datasets proposed in [2] and on more standard graph or node property prediction tasks (see Weakness 5).\n\nAs we noted before, our goal was not to develop a high-performing model, but rather to design a variant that is deliberately minimal and controllable. This minimalism allows us to cleanly isolate and analyze the role of effective rewiring and stable gradient propagation, two mechanisms we argue are central to over-smoothing and over-squashing. That said, we fully understand your concern regarding empirical completeness, and we’ve taken it seriously in our rebuttal.\n\nRegarding the heterophilic datasets, we believe the link in reference [2] might have been a typo, as it pointed us to the GRED paper. However, we assume you were referring to the more recent benchmark introduced in [Platonov2023]. In response, we evaluated GCN-SSM on three of the datasets from that benchmark, comparing it against (i) the original GCN results reported in the paper, (ii) GCN with the same depth as our model (denoted \"GCN (Optimal L)\"), and (iii) our GCN-SSM with the same depth. Since GCN-SSM benefits from a larger number of layers, we tuned the depth for each task based on performance on the validation set. Results are shown below (for three random seeds):\n\n| Dataset         | GCN (Orig)     | GCN (Optimal L) | GCN-SSM (Optimal L) |\n|------------------|----------------|------------------|----------------------|\n| Amazon Ratings    | 47.7 ± 0.63    | 47.57  ± 0.67         | 51.72  ± 0.33            |\n| Roman Empire      | 73.69 ± 0.74   | 33.83   ± 0.41         | 88.37   ± 0.60               |\n| Minesweeper       | 89.75 ± 0.52   | 60.84     ± 0.89        | 96.02     ± 0.52            |\n\nWe used the following number of layers for each dataset:\n| Dataset         | # Layers (n) |\n|------------------|---------------|\n| Amazon Ratings    | 4             |\n| Roman Empire      | 9             |\n| Minesweeper       | 12            |\n\nWe did not run full-scale experiments on all datasets in the collection, as tuning the number of layers requires multiple training runs, and we were constrained by the rebuttal timeline. Nonetheless, we believe these results already offer meaningful evidence of GCN-SSM’s generalization to challenging heterophilic tasks.\n\nWe also evaluated GCN-SSM on some ogbn-arxiv, as suggested by the reviewer:\n\n| Dataset     | GCN             | GCN-SSM         |\n|--------------|------------------|------------------|\n| ogbn-arxiv   | 70.84 ± 0.23     | 72.49 ± 0.16     |\n\nDue to time constraints (e.g., hyperparameter tuning, optimal depth selection), we were only able to include this limited set of new experiments in the rebuttal. However, we plan to significantly expand our empirical evaluation in the camera-ready version. This will include further experiments on the heterophilic benchmarks from [Platonov2023], more standard graph-level datasets, and the mechanistic in-context learning experiment from S2GNN [4]—which we agree would provide compelling evidence of long-range modeling ability.\n\nOnce again, we greatly appreciate your thoughtful feedback. Your comments have had a clear and direct impact on the direction of this work, and we are hopeful that the revisions and additional experiments presented here will merit a more favorable assessment.\n\n[Platonov2023] Platonov, Oleg, et al. \"A critical look at the evaluation of GNNs under heterophily: Are we really making progress?.\" arXiv preprint arXiv:2302.11640 (2023)."}]

Author rebuttal:

Meta-review: Based on ideas from linear control theory, the paper presents an unified view of the problem of over-smoothing/over-squashings in GNNs through the lens of vanishing gradients. It interprets GNNs as recurrent models and empirically demonstrates that a simple state-space formulation  effectively alleviates these issues without introducing additional trainable parameters. Moreover, the paper shows theoretically and empirically that traditional GNNs are by design prone to extreme gradient vanishing, feature collapse is directly related to the mechanism causing vanishing gradients, and long-range modeling is most easily achieved by a combination of graph rewiring and vanishing gradient mitigation. 

In the rebuttal the authors convincingly replied to the concerns of the reviewers. The provided a more detailed explanation of the relation and a comparison to previous related works, experimental results analysing the scalability of the proposed architecture, new experiments on the heterophilic datasets from [Platonov2023] and on ogbn-arxiv, demonstrating that their proposed model has good results on node-level tasks. Moreover, the authors have further analyzed the role of the input matrix B. Based on these additional insights, which should be included in the revised version of the paper, all reviewers voted for acceptance.
Decision: Accept (poster)