PaperlayerView exact revision on arXiv

Source-linked AI summary

On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning

Álvaro Arroyo, Alessio Gravina, Benjamin Gutteridge, Federico Barbero, Claudio Gallicchio, Xiaowen Dong, Michael Bronstein, Pierre Vandergheynst

arXiv:2502.10818v2cs.LGcs.AI

TL;DR

GNNs suffer from over-smoothing, over-squashing, and extreme gradient vanishing, motivating a unified explanation of their depth and long-range limitations. The paper analyzes these issues through recurrent and state-space models, proposes GNN-SSM to control Jacobian dynamics, and reports that combining gradient mitigation with graph rewiring addresses the stated problems.

  • Problem

    GNNs lack a unified account of how vanishing gradients relate to over-smoothing and over-squashing, despite these phenomena limiting deep and long-range message passing.

  • Method

    The paper interprets GNNs as recurrent models and introduces GNN-SSM, a state-space formulation that controls layerwise Jacobian spectra through state-transition and input matrices.

  • Results

    The paper theoretically and empirically links vanishing gradients to over-smoothing and shows that over-squashing is best addressed by combining graph rewiring with vanishing-gradient mitigation.

  • Takeaways & Limitations

    Viewing GNNs through recurrent and state-space dynamics provides a framework for designing deeper models with controlled signal propagation and improved long-range modeling.

  • Takeaways & Limitations

    The analysis focuses long-range interactions, which are often treated synonymously with over-squashing, and does not consider the distinction between computational and topological bottlenecks particularly relevant.

Abstract

from arXiv · show

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 the over-smoothing and over-squashing phenomena, which result in representational collapse as the number of layers increases and insensitivity to the information contained at distant and poorly connected nodes, respectively. In this paper, we present a unified view of these problems 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 a GNN effectively alleviates over-smoothing and over-squashing at no extra trainable parameter cost. Further, we show theoretically and empirically that (i) GNNs are by design prone to extreme gradient vanishing even after a few layers; (ii) Over-smoothing is directly related to the mechanism causing vanishing gradients; (iii) Over-squashing is most easily alleviated 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.

1 Introduction

GNN message passing suffers from over-smoothing and over-squashing, yet lacks a unified explanation of why these failures arise and how successful remedies work. The paper addresses this gap by linking GNNs to recurrent models and vanishing gradients.

  • Over-smoothing makes node representations exponentially similar with depth, while over-squashing compresses growing long-range messages into fixed-size vectors.
  • The paper studies whether vanishing gradients explain these depth-related failures and whether recurrent-model techniques can improve long-range graph learning.
  • The paper connects GNN over-smoothing and over-squashing to recurrent-learning principles, bridging previously separated graph and sequence-modeling perspectives.
  • GNN-SSM rewrites GNN updates as state-space dynamics, enabling direct control of the Jacobian spectrum.

2 Background and Related Work

This background presents GNNs as message-passing models whose depth creates over-smoothing, over-squashing, and vanishing-gradient concerns. It motivates analyzing graph layers through the recurrent and Jacobian dynamics used in sequence models.

  • GNNs exchange information across neighboring nodes using permutation-invariant aggregation and learned updates, with GCNs and GATs as prominent examples.
  • RNNs and GNNs both propagate gradients through products of layer Jacobians, so recurrent vanishing-gradient analysis provides a framework for studying GNN trainability.
  • If each Jacobian norm is approximately λ, the overall gradient norm is bounded by λ^(K-i), requiring λ ≈ 1 to avoid vanishing or exploding gradients.
  • Over-smoothing refers to increasingly smooth representations at depth, while over-squashing limits sensitivity to distant nodes by compressing rapidly growing information.
  • The paper positions vanishing gradients as an underexamined explanation for GNN depth limitations and relates sequence-modeling techniques to over-squashing mitigation.

3 Connecting Sequence and Graph Learning through State-Space Models

The paper interprets GNN layers as recurrent state updates and shows that normalized graph propagation creates highly contractive Jacobians. GNN-SSM introduces state-space memory and input dynamics to control the Jacobian spectrum and improve signal propagation.

  • Stacking node representations makes GNN layers iterative state updates, establishing a connection between graph learning and recurrent sequence models.
  • GCN and GAT layer Jacobians are highly contractive, preventing effective gradient and information propagation beyond a few layers.
  • Because normalized adjacency eigenvalues have modulus at most 1, repeated graph convolutions shrink most Jacobian spectrum toward zero faster than classical deep linear or nonlinear networks.
  • GNN-SSM expresses each update with a state transition matrix Λ, input matrix B, and neighborhood coupling function Fθ, interpreting Λ as memory and aggregation as injected input.
  • The eigenvalues of Λ control memory dynamics, while B controls which node-feature components enter the hidden state at each layer.
  • Fixing shared Λ and B preserves controlled dynamics without adding trainable parameters, while the coupling function remains trainable and any MPNN layer can serve as Fθ.
  • When the coupling spectrum is near zero, choosing eig(Λ) ≈ 1 brings the vectorized Jacobian to the edge of chaos and controls signal propagation.

4 How does Extreme Gradient Vanishing affect Over-smoothing?

Contractive GNN layers link extreme gradient vanishing to over-smoothing: repeated application drives node features toward a unique zero fixed point and lowers Dirichlet energy. Jacobian spectra therefore characterize whether deep GNNs collapse, remain stable, or diverge, while GNN-SSM can control these dynamics.

  • A contractive GNN leads to node feature collapse: When every layer is contractive, repeated application converges monotonically to the unique fixed point 0, producing zero feature collapse.The contraction assumption is ∥f_k∥_Lip < 1, and the zero fixed point follows for nonlinearities satisfying σ(0)=0.
  • A contractive GNN leads to node feature collapse: Contractive layers decrease unnormalized Dirichlet energy toward zero because node features shrink in norm while evolving toward the zero fixed point.Dirichlet energy is minimized when the graph signal is constant across nodes; the theoretical bound ties its decrease to the input norm and layer contraction.
  • Connection between vanishing gradients and over-smoothing: The same layerwise Jacobian mechanism causes both vanishing gradients and over-smoothing, making feature collapse an artifact of contraction rather than a separate phenomenon.The paper connects the Lipschitz constant and vanishing gradients through the Jacobian and proposes Jacobian eigenanalysis as an empirical test for over-smoothing.
  • Empirical validation of theoretical results: GNN-SSM controls Dirichlet-energy evolution through the spectrum of Λ, and node-classification performance does not deteriorate when eig(Λ) ≪ 1.In the reported setting, it also improves over an unmodulated SSM layer and an ungated residual connection.
  • Empirical validation of theoretical results: Jacobian spectra distinguish deep-GNN failure modes: contraction yields feature collapse, whereas unstable eigenvalues can cause Dirichlet-energy divergence and exploding features.GIN shows occasional eigenvalue outliers with |λ| > 1, while Gated-GCN has a sizeable spectral mass above the unit circle.

5 The Impact of Vanishing Gradients on Over-squashing

Over-squashing reflects both graph topology and model dynamics: distant-node information must reach a node through the graph while surviving gradient dissipation. The proposed kGNN-SSM combines increased connectivity with non-dissipative dynamics, improving long-range modeling.

  • Sensitivity and mechanisms: Theorem 5.1 decomposes node-embedding sensitivity into graph-topology and model-dynamics terms, with over-squashing occurring when their bound becomes too small.MPNN message normalization adds an information-dissipation step beyond the standard recurrent product Jacobian.
  • Sensitivity and mechanisms: MPNNs must enhance graph connectivity and modify their dynamics simultaneously to mitigate vanishing and exploding gradients.Recurrent architectures primarily adjust dynamics for long memory, whereas MPNNs face both requirements.
  • Method: kGNN-SSM combines GNN-SSM with k-hop aggregation to provide high connectivity and non-dissipative dynamics.The k-hop scheme is intended to reduce the number of message-passing steps needed for long-range interactions.
  • Empirical validation: On RingTransfer, kGNN-SSM achieves state-of-the-art performance only when strong connectivity is combined with an edge-of-chaos Jacobian.Making the model more dissipative directly worsens long-range modeling capabilities.
  • Empirical validation: Across the evaluated tasks, kGNN-SSM matches or outperforms DRew-Delay, while removing high connectivity and non-dissipativity generally causes significant performance decreases.The ablations support the individual importance of both components; larger memory also matters substantially for peptides-func.

6 Conclusion

The paper reframes GNN representational collapse and over-squashing through recurrent and state-space perspectives. It attributes these problems to extreme gradient vanishing and proposes controlling layerwise Jacobians with GNN-SSM.

  • Conclusion: GNNs are prone to extreme gradient vanishing, producing ill-conditioned signal propagation after only a few layers.The analysis focuses on the singular values of layerwise Jacobians in graph convolutional and attentional models.
  • Conclusion: The paper proposes GNN-SSM, a state-space-inspired GNN that controls the spectrum of the layerwise Jacobian.Its formulation is motivated by the recurrent-model view of GNN depth.
  • Conclusion: Vanishing gradients produce a form of over-smoothing in which all signals converge exactly to a unique fixed point.The appendix establishes convergence under layerwise contraction conditions.
  • Conclusion: The paper argues that mitigating over-squashing is best achieved through strong graph connectivity combined with non-dissipative dynamics.This conclusion follows from the separate topology and model-dynamics components of sensitivity.

A.2 Proofs to Smoothing Theorems

The smoothing proofs connect Lipschitz contraction to both feature convergence and decreasing Dirichlet energy. Under uniform contraction, GNN representations converge to the zero fixed point as depth grows.

  • Proof framework: A Lipschitz constant bounds a function’s rate of change through the norm of its Jacobian.This links layerwise Jacobian control to contraction-based smoothing analysis.
  • Convergence to a fixed point: When every layer has Lipschitz constant at most 1 − ϵ, repeated application converges to a unique fixed point, specifically zero under the stated activation condition.The zero fixed point follows from σ(0)=0.
  • Dirichlet energy: If every layer is contracted by at least ϵ, the network’s Dirichlet energy tends to zero as the number of layers grows.The contraction factor decays geometrically with depth.
  • Proof framework: The proof procedure generalizes beyond GCNs because it uses the network’s input-output Jacobian and Lipschitz constant rather than a specific internal architecture.This permits analysis of how arbitrary GNNs affect Dirichlet energy.
  • kGNN-SSM construction: The proposed kGNN-SSM uses k-hop aggregation to avoid compressing large amounts of information into a single vector.Nodes aggregate information from nodes at graph distance k, and the resulting model is wrapped with the SSM layer.

C Experimental Details

The experiments evaluate smoothing, graph-property prediction, and long-range graph benchmarks using established datasets and controlled training procedures. The appendix also reports additional empirical evaluations of smoothing and Jacobian spectra.

  • Experimental tasks: The over-smoothing task measures Dirichlet-energy dynamics on Cora, Texas, and a 10 × 10 grid graph.These graphs represent citation, webpage, and regular-grid topologies.
  • Experimental tasks: Graph-property prediction covers node-level eccentricity and single-source shortest path, plus graph-level diameter, on synthetic graphs from multiple graph families.The dataset contains graphs with 25–35 nodes and uniformly sampled node features.
  • Training protocol: Models are selected by grid search and trained with Adam or AdamW, using early stopping where specified and four runs with different weight initializations.The reported results average across the four runs.
  • Experimental tasks: The long-range benchmark uses peptides-func and peptides-struct, each containing 15,535 peptide graphs.The tasks evaluate peptide-function prediction and peptide-structure regression.
  • Additional evaluation: The appendix adds empirical results on over-smoothing, over-squashing, and layerwise-Jacobian eigendistributions for standard GNNs.It also includes a hyperparameter grid for GraphProp and the two peptide tasks.

D.1 Additional Over-Smoothing Results

Additional experiments link stable Jacobian dynamics and near-edge-of-chaos behavior to reduced over-smoothing and stronger long-range propagation. Combining connectivity improvements with controlled dynamics also yields strong graph-property prediction results.

  • Additional over-smoothing experiments: Lower Jacobian norms rapidly reduce Dirichlet energy, while norms closer to one produce more stable energy across graph topologies.This pattern appears for GCN-SSM and GAT-SSM, while ADGN, SWAN, and PHDGN maintain stable energy across layers.
  • Delay and long-range propagation: Adding the delay term to GCN prevents over-smoothing, while lower DRew-SSM Jacobian norms cause rapid performance decay on RingTransfer.The delay mechanism is connected to Jacobian eigenvalue behavior and long-range propagation.
  • Edge-of-chaos behavior: Methods closer to the edge-of-chaos region propagate information over larger graph radii and achieve superior performance across all three graph-property tasks.The comparison evaluates average Jacobian eigenvalue distance to the edge-of-chaos region alongside task performance.
  • Graph-property prediction: The proposed method consistently surpasses MPNN, differential-equation-inspired, and multi-hop baselines on all three graph-property prediction tasks.Table 4 reports mean test log10(MSE) and standard deviation over four random initializations, with lower values better.

D.4 Additional comments on LRGB tasks

The LRGB experiments distinguish task-dependent depth and dynamical requirements. The paper also frames its model as a minimal, controllable framework rather than a direct pursuit of state-of-the-art performance.

  • Task-dependent dynamics: Peptides-func benefits from edge-of-chaos initialization and additional depth, reaching optimal results at forty layers.Peptides-struct instead performs best away from the edge of chaos and with fewer layers.
  • Evaluation constraint: The 500k parameter budget limits hidden dimensions and layer counts, which can disadvantage models needing depth or larger hidden representations for long-range learning.Increasing the hidden dimension to 256 exceeds the budget even though the model has the same parameter count as a regular GCN.
  • Comparison with GRED: GNN-SSM outperforms GRED on peptides-func, whereas GRED performs better on peptide-struct.The methods also differ in neighborhood aggregation and the direction of their state-space updates.
  • Experimental objective: The model is designed as a minimal and controllable framework for isolating specific phenomena rather than primarily targeting state-of-the-art performance.

D.5 Scalability Results

GNN-SSM retains the computational simplicity of its backbone while improving performance, and its empirical behavior supports the role of controlled dynamics in deep propagation. Alternative smoothness measurements show similar qualitative trends, though formal equivalence is not established.

  • Runtime and scalability: GNN-SSM adds two fixed matrices, one element-wise addition, and two matrix multiplications per layer, with negligible memory and runtime impact.The formulation retains backbone complexity while improving reported performance.
  • Evaluation scope: The reported scalability comparisons include Cora runtime, ogbn-arxiv accuracy, design-choice ablations, and heterophilic datasets.The corresponding tables compare epoch time, accuracy, design choices, and GCN-SSM against original and depth-matched GCN results.
  • Fixed dynamics: Sharing a fixed Λ across layers preserves performance and keeps the system at the edge of chaos during training.Training separate Λ_i matrices with identical dynamics produced the same accuracy empirically.
  • Smoothness measures: The alternative smoothness measure reproduces the qualitative trends predicted by the unnormalized-energy analysis, although formal equivalence to the collapse proofs is not established.The evidence supports broader empirical applicability rather than a formal equivalence result.

E.2 The effect of the Jacobian spectrum on node classification performance

Node-classification experiments show that keeping the backbone Jacobian spectrum near unity supports stable deep propagation, while spectrum tuning alone does not reproduce the full GCN-SSM gains. Residual connections are characterized as a restricted special case.

  • Jacobian spectrum: Moving Λ’s spectrum away from unity causes pronounced accuracy degradation on Cora, indicating that eigenvalues near one support stable propagation across many layers.The experiment varies maximal Λ eigenvalues across depths from 5 to 60 layers.
  • Ablation: Spectrally tuning a vanilla GCN’s weight matrix near the stability edge fails to achieve the accuracy improvements of the full GCN-SSM backbone.This isolates the contribution of structured state-space dynamics rather than spectrum placement alone.
  • Relation to residual designs: Residual GNNs correspond to the special case Λ = I, outperforming a memoryless GCN through unstructured accumulation of node features.
  • Propagation matrix: The propagation matrix B improves deeper-network performance by controlling incoming-signal damping while Λ places the system near the stability edge.The ablation removes B and evaluates performance across different layer counts.

F Supplementary Related Work and Limitations

Existing approaches improve long-range graph communication, but this work frames their underlying challenge through vanishing gradients and connects graph learning with sequence-modeling methods. The analysis focuses mainly on GCN- and GAT-type updates, leaving broader update and nonlinearity choices for future study.

  • Long-range propagation: Graph rewiring methods improve connectivity and information flow, but primarily mitigate long-range propagation without providing a unified theoretical account of its underlying cause.The paper positions its vanishing-gradient perspective as such a framework.
  • Sequence modelling: Recurrent-model research addresses vanishing or exploding gradients that hinder learning and retaining information over long sequences through architectures such as Unitary, Orthogonal, and Linear Recurrent Units.These methods motivate adapting sequence-modeling strategies to GNNs.
  • Dynamical systems: Dynamical-systems ideas in neural networks include continuous-time and state-space approaches, with related applications spanning static and temporal graph neural networks.Examples cited include PDE-GCN, GRAND, BLEND, Neural Sheaf Diffusion, CTAN, and TG-ODE.
  • Limitations and future work: The paper mainly studies GCN- and GAT-type updates and leaves extensions to other update choices and nonlinearities for future work.The authors frame these extensions as a way to further understand effects on training dynamics.
Loading 2502.10818v2…