Research map / Graph learning / GNN architectures

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

NeurIPS 2025 · Graph learning › GNN architectures · approach: Expressive equivariant message passing · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Frames GNN depth issues (over-smoothing, over-squashing) as vanishing gradients via Jacobian spectra, and proposes GNN-SSM, a fixed state-space wrapper around any MPNN that keeps the Jacobian near the edge of chaos, combined with k-hop rewiring (kGNN-SSM) for long-range tasks.

Problem

GNNs suffer representational collapse (over-smoothing) with depth and insensitivity to distant nodes (over-squashing); the paper asks whether a common underlying cause, vanishing gradients, explains both and how to mitigate them.

Approach

Normalized adjacency makes GCN/GAT layer Jacobians contractive ("extreme gradient vanishing"); rewriting any GNN as a state-space model with a fixed, spectrally controlled state transition matrix Lambda (eigenvalues near 1) places the Jacobian at the edge of chaos, and combining this with k-hop connectivity mitigates over-squashing.

Key results

• On graph property prediction, GCN-SSM with eig(Lambda)≈1 reaches log10 MSE -2.444 on Diameter and -3.593 on SSSP, and kGCN-SSM (k-hop) achieves -3.075 / -3.604 / -4.265 on Diameter/SSSP/Eccentricity, versus GCN at 0.742 / 0.950 / 0.847.
• On peptides-func, kGCN-SSM reaches 69.02 AP vs 60.93 for GCN, and 72.12 AP with added latent dimensions, outperforming DRew-GCN+delay (68.04).
• The paper reports that GCN/GAT Jacobians are contractive so Dirichlet energy and features collapse to a zero fixed point, while GIN and Gated-GCN show unstable eigenvalues above the unit circle.

Measured effects reported in the paper

Surprising findings

• Over-smoothing in GCN and GAT is argued to be an artifact of feature collapse to zero rather than convergence to a rank-one subspace.
• Dissipative (contractive) SSM dynamics hurt long-range modeling even when connectivity is high.

Limitations

• Theoretical Jacobian analysis is for linear GCN layers and Marchenko-Pastur asymptotics for large widths; extension to nonlinear and attention models is argued empirically.
• Empirical validation is limited to small benchmarks (Cora, Texas, synthetic graph property tasks, peptides) rather than large-scale node or graph tasks.
• Fixed untrained Lambda and B are a simplification; learned or gated state transitions are left to future work.

Experimental setup

Datasets: Cora Texas grid graph (10x10) synthetic graph property prediction (RingTransfer-style GraphProp) peptides-func peptides-struct

Benchmarks: Cora Dirichlet energy RingTransfer Graph property prediction (Diameter, SSSP, Eccentricity) peptides-func peptides-struct

Metrics: Dirichlet energy node classification accuracy log10 MSE average precision mean absolute error

Baselines: GCN GAT GIN GraphSAGE GCNII DRew-GCN ADGN SWAN PH-DGN GPS

Builds on: GCN DRew Banach fixed point theorem dynamical isometry

Closest papers by meaning

• Locality-Aware Graph Rewiring in GNNs (ICLR 2024 · similarity 0.90)
• How Graph Neural Networks Learn: Lessons from Training Dynamics (ICML 2024 · similarity 0.89)
• Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence (ICML 2025 · similarity 0.89)
• Recurrent Graph Neural Networks and Their Connections to Bisimulation and Logic (AAAI 2024 · similarity 0.89)
• Dynamic Rescaling for Training GNNs (NeurIPS 2024 · similarity 0.89)
• Graph Neural Networks Do Not Always Oversmooth (NeurIPS 2024 · similarity 0.89)