Extending the Jacobian spectral theory of vanishing gradients in graph neural networks to nonlinear, learned updates and training dynamics

Arroyo, Gravina, Gutteridge, Barbero, Gallicchio, Dong, Bronstein, and Vandergheynst (arXiv:2502.10818; NeurIPS 2025) unified over-smoothing and over-squashing in graph neural networks (GNNs) as consequences of vanishing gradients, deriving exact layer-wise Jacobian spectra but only for linear graph-convolutional layers at initialization, treating graph-attention layers empirically, and handling nonlinear layers only through coarse contraction (Lipschitz) arguments. They explicitly leave as future work the extension of this analysis to other update rules and nonlinearities and their effect on training dynamics. Subsequent work provides partial but disjoint progress — backward-oversmoothing optimization analysis, bifurcation analysis of non-monotone activations, and model-specific exact sensitivity for state-space message-passing models — with no tractable, predictive characterization of the Jacobian spectrum for general learned nonlinear GNN layers or of how update and nonlinearity choices shape training dynamics. The problem remains open.

Background

Graph Neural Networks (GNNs) process data defined on nodes and edges of a graph by message passing: at each layer, every node aggregates transformed features of its neighbors. The two classical architectures are the Graph Convolutional Network (GCN), whose layer is a linear operation $\mathbf{H}^{(k)}=\tilde{\mathbf{A}}\mathbf{H}^{(k-1)}\mathbf{W}$ with $\tilde{\mathbf{A}}$ the degree-normalized adjacency matrix and $\mathbf{W}$ a weight matrix, and the Graph Attention Network (GAT), where aggregation weights are learned attention coefficients. Two failure modes are known to limit depth. Over-smoothing is the convergence of node representations toward a common (often constant or zero) vector as layers are stacked, commonly monitored by the graph Dirichlet energy $\mathcal{E}(\mathbf{H})=\sum_{(u,v)\in E}\|\mathbf{h}_u-\mathbf{h}_v\|^2$, which measures how non-uniform a graph signal is. Over-squashing is the inability of fixed-dimensional node states to absorb the exponentially growing amount of information routed through bottlenecks, formalized by Di Giovanni, Giusti, Barbero, Luise, Liò, and Bronstein (ICML 2023) through node-to-node Jacobian sensitivity bounds $\|\partial\mathbf{h}_v^{(k)}/\partial\mathbf{h}_u^{(0)}\|\le(c_\sigma wd)^k(\mathbf{O}^k)_{vu}$, where $c_\sigma$ is the Lipschitz constant of the activation $\sigma$, $w$ the largest weight-matrix entry, $d$ the embedding width, and $\mathbf{O}$ the message-passing matrix. Recurrent neural networks face an analogous vanishing/exploding gradient problem, controlled by the singular values of the product of layer-wise Jacobians (the derivative of layer-$k$ features with respect to layer-$(k-1)$ features). Arroyo et al. (arXiv:2502.10818) bridged these literatures by viewing a deep GNN as a recurrent model. Their exact results hold only in a linear, initialization-time regime: for a linear GCN layer, the squared singular values of the layer-wise Jacobian are exactly the products $\lambda_i^2\mu_j$ of squared adjacency eigenvalues and eigenvalues of $\mathbf{W}\mathbf{W}^{\top}$, so at random initialization the spectrum follows a Marchenko–Pastur-type law (the Marchenko–Pastur law is the universal limiting eigenvalue distribution of large random matrices with independent entries) modulated by the graph spectrum, which is sharply concentrated near zero — 'extreme gradient vanishing'. They then rewrite any GNN layer as a state-space model (SSM) — a discrete-time recurrence of the kind used in modern sequence models — $\mathbf{H}^{(k)}=\boldsymbol{\Lambda}\mathbf{H}^{(k-1)}+\mathbf{B}\mathbf{F}_\theta(\mathbf{H}^{(k-1)})$ with fixed (untrained) matrices $\boldsymbol{\Lambda},\mathbf{B}$ chosen so that $\|\boldsymbol{\Lambda}\|\approx1$ places the Jacobian norm near 1 (the 'edge of chaos', the regime where gradients neither vanish nor explode), and show that contractive nonlinear layers drive features to the zero fixed point (by the Banach fixed-point theorem, which guarantees that a contractive map has a unique attracting fixed point) and decrease the Dirichlet energy. In the other direction, generic nonlinear message-passing networks are covered only by the coarse Lipschitz bound above, and nothing is said about how the analysis survives weight learning during training — indeed Oono and Suzuki (ICLR 2020) had earlier shown nonlinear GCN-type models asymptotically lose rank under bounded weights, an asymptotic result that does not predict gradient dynamics. The precise gap is thus: exact spectral characterizations exist for linear layers at initialization, coarse Lipschitz inequalities exist for generic nonlinear layers, and no tractable theory connects the choice of update rule and nonlinearity to the Jacobian spectrum and to the training dynamics of deep, learned GNNs.

Problem Statement

Extend the vanishing-gradient/Jacobian-spectral analysis of deep graph neural networks beyond the regime covered by Arroyo et al. (arXiv:2502.10818) — linear GCN-type layers at initialization, GAT layers treated empirically, and generic nonlinear layers covered only by coarse Lipschitz/contraction bounds. Specifically, for a bounded class of GNN layers with learned update rules and nonlinear activation functions — trained weight matrices applied to a normalized-adjacency (GCN-type) or learned-attention (GAT-type) aggregation, a nonlinear activation drawn from a stated family (ReLU, GELU, or tanh), and at least one nonlinear recurrent update of the state-space form $\mathbf{H}^{(k)}=\boldsymbol{\Lambda}\mathbf{H}^{(k-1)}+\mathbf{B}\mathbf{F}_\theta(\mathbf{H}^{(k-1)})$ with learned parameters — characterize the layer-wise Jacobian spectrum in a single tractable and predictive form: an exact closed form in a stated regime, or an explicit bound supported by a proof of tightness (or of convergence of the approximation). The characterization must make explicit its dependence on the graph spectrum, the width, the activation, and the learned weights, and must yield its evolution with depth. Use this characterization to explain and predict how the choice of update rule and nonlinearity affects the training dynamics of deep GNNs: gradient propagation through depth (vanishing versus exploding), representation collapse toward fixed points, and trainability of deep stacks. The characterization is exact or carries the stated tightness/convergence proof, reduces provably to the exact linear theory as the nonlinearity is removed, and yields verifiable predictions of these training-dynamics quantities. This is the extension that Arroyo et al. explicitly state they 'leave for future work'.

References

1. Álvaro Arroyo, Alessio Gravina, Benjamin Gutteridge, Federico Barbero, Claudio Gallicchio, Xiaowen Dong, Michael Bronstein, Pierre Vandergheynst. On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning. arXiv:2502.10818 (2025; v2 October 2025; NeurIPS 2025). DOI: 10.48550/arXiv.2502.10818. https://arxiv.org/abs/2502.10818
2. Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Liò, Michael Bronstein. On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology. ICML 2023. arXiv:2302.02941. DOI: 10.48550/arXiv.2302.02941. https://arxiv.org/abs/2302.02941
3. Kenta Oono, Taiji Suzuki. Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. ICLR 2020. arXiv:1905.10947. DOI: 10.48550/arXiv.1905.10947. https://arxiv.org/abs/1905.10947
4. Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv:2111.14522 (2021). DOI: 10.48550/arXiv.2111.14522. https://arxiv.org/abs/2111.14522
5. Alessio Gravina, Moshe Eliasof, Claudio Gallicchio, Davide Bacciu, 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 (2025). DOI: 10.1609/aaai.v39i16.33858. https://doi.org/10.1609/aaai.v39i16.33858
6. Nicolas Keriven. Backward Oversmoothing: why is it hard to train deep Graph Neural Networks? arXiv:2505.16736 (2025). DOI: 10.48550/arXiv.2505.16736. https://arxiv.org/abs/2505.16736
7. Erkan Turan, Gaspard Abel, Maysam Behmanesh, Emery Pierson, Maks Ovsjanikov. Beyond ReLU: Bifurcation, Oversmoothing, and Topological Priors. arXiv:2602.15634 (2026). DOI: 10.48550/arXiv.2602.15634. https://arxiv.org/abs/2602.15634
8. Andrea Ceni, Alessio Gravina, Claudio Gallicchio, Davide Bacciu, Carola-Bibiane Schönlieb, Moshe Eliasof. Message-Passing State-Space Models: Improving Graph Learning with Modern Sequence Modeling. arXiv:2505.18728 (2025). DOI: 10.48550/arXiv.2505.18728. https://arxiv.org/abs/2505.18728
9. MoonJeong Park, Sunghyun Choi, Jaeseung Heo, Eunhyeok Park, Dongwoo Kim. The Oversmoothing Fallacy: A Misguided Narrative in GNN Research. arXiv:2506.04653 (2025). DOI: 10.48550/arXiv.2506.04653. https://arxiv.org/abs/2506.04653
10. Adrian Arnaiz-Rodriguez, Federico Errica. Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning. arXiv:2505.15547 (2025). DOI: 10.48550/arXiv.2505.15547. https://arxiv.org/abs/2505.15547
11. Anna Bison, Alessandro Sperduti. Analysis of Dirichlet Energies as Over-smoothing Measures. arXiv:2512.09890 (2025). DOI: 10.48550/arXiv.2512.09890. https://arxiv.org/abs/2512.09890
12. Haiquan Qiu, Quanming Yao. Graph Unitary Message Passing. Transactions on Machine Learning Research (2026). arXiv:2403.11199 (2024). DOI: 10.48550/arXiv.2403.11199. https://arxiv.org/abs/2403.11199. https://openreview.net/forum?id=dvNMDkSBIA