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.

Minor typo: line 108: GNNs are known. Minor typo: I believe that the authors wanted to refer to peptides-func on Line 823 - "Conversely, on peptides-func (...)". The font for some figures should be increased. Figure 2 is particularly hard to read.

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

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

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

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.

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

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

One 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:

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

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

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

Thank you again for the insightful suggestion.

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

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

Regarding 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):

We used the following number of layers for each dataset:

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

We also evaluated GCN-SSM on some ogbn-arxiv, as suggested by the reviewer:

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

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

[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).

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.

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.

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

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

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

How are the state transition matrices $\Lambda$ computed, and how do you control their eigenvalues? Are these matrices learnable or fixed?

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

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

In Figure 3, middle, what is model is this plotting the features for?

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

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

Thank you for the feedback. We agree that Figure 1 can be clarified further. To address your questions:

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

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

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 Line 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"

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

[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).

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.

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.

Thank 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:

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

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

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

Regarding our theoretical treatment of over-squashing, we highlight key distinctions from [2]:

(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:

“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.”

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

This perspective contrasts with [2], which explicitly cautions against mitigating vanishing gradients via the model term:

“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...”

Moreover, [2] hints toward the need to explore ideas from RNNs in this context:

“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.”

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

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

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

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

Having said this, we also note several important differences:

(i) Aggregation scope: GRED aggregates information from several neighborhoods at each layer. In contrast, our approach aggregates from a single-hop neighborhood per layer.

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

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

(iv) Weight sharing. We do not perform weight sharing when performing k-hop aggregation, as in GRED.

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

Nonetheless, in response to the reviewer’s comment, we now include the following results on the Peptides dataset:

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

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

[1] Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. ICLR 2020.

[2] On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology. ICML 2023.

[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).

[4] Defferrard, M., et. al. "Convolutional neural networks on graphs with fast localized spectral filtering." NeurIPS 2016.

[5] Gutteridge, B., et al. "Drew: Dynamically rewired message passing with delay." ICML 2023.

Thank you for your constructive review. We respond to your questions and comments below.

Does the proposed method scale to very large scale GNN where the challenges of vanishing gradient and homogenization are even more pronounced. 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.

Thank you for your question regarding scalability and comparison with more sophisticated GNN training strategies. In 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.

To further assess scalability and performance, we also evaluated GCN-SSM on the large-scale ogbn-arxiv benchmark.

To contextualize this, we compare it with published results from a range of MPNN and Graph Transformer baselines, see [4]

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

Furthermore, 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:

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

Provide a discussion between the functional differences in the proposed method to avoid vanishing gradient in comparison with the known approaches in literature.

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

[1] Alessio Gravina, Davide Bacciu, and Claudio Gallicchio. Anti-Symmetric DGN: A Stable Architecture for Deep Graph Networks. ICLR, 2023.

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

[3] T. Konstantin Rusch, Ben Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael Bronstein. Graph-Coupled Oscillator Networks. ICML, 2023.

[4] Luo, Yuankai, et al. "Enhancing graph transformers with hierarchical distance structural encoding." Advances in Neural Information Processing Systems 37 (2024): 57150-57182.

[5] Gutteridge, Benjamin, et al. "Drew: Dynamically rewired message passing with delay." International Conference on Machine Learning. PMLR, 2023.