Backward Oversmoothing: why is it hard to train deep Graph Neural Networks?

Nicolas Keriven · 2025

Read Backward Oversmoothing: why is it hard to train deep Graph Neural Networks? by Nicolas Keriven (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-16736.txt.

Introduction

Nicolas Keriven, writing alone in 2025, asks why deep graph neural networks are so hard to train. Such networks pass information between linked points, layer by layer. A known flaw, oversmoothing, washes out point features in the forward pass. In theory, big enough weights could dodge that flaw. In practice, trained networks still smooth too much. Keriven turns the lens to the backward pass, where errors flow back to set the learning steps.

Those backward signals, he argues, also get smoothed away. That backward oversmoothing starves deep layers of useful gradients. The interplay between forward and backward passes is the key mechanism. Nonlinear activation functions shape how the two interact. The paper gives an optimization view of a famous puzzle. It suggests fixes should target training dynamics, not just network shape.

Catalog record

CREATORNicolas Keriven
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-16736

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Backward Oversmoothing: why is it hard to train deep Graph Neural Networks? Nicolas Keriven Abstract Oversmoothing has long been identified as a major limitation of Graph Neural Networks (GNNs): input node features are smoothed at each layer and converge to a non-informative representation, if the weights of the GNN are sufficiently bounded . This assumption is crucial: if, on the contrary, the weights are sufficiently large, then oversmoothing may not happen. Theoretically, GNN could thus learn to not oversmooth. However it does not really happen in practice, which prompts us to examine oversmoothing from an optimization point of view. In this paper, we analyze backward oversmoothing , that is, the notion that backpropagated errors used to compute gradients are also subject to oversmoothing from output to input. With non-linear activation functions, we outline the key role of the interaction between forward and backward smoothing. Moreover, we show that, due to backward oversmoothing, GNNs provably exhibit many spurious stationary points : as soon as the last layer is trained, the whole GNN is at a stationary point. As a result, we can exhibit regions where gradients are near-zero while the loss stays high. The proof relies on the fact that, unlike forward oversmoothing, backward errors are subjected to a linear oversmoothing even in the presence of non-linear activation function, such that the average of the output error plays a key role. Additionally, we show that this phenomenon is specific to deep GNNs, and exhibit counter-example Multi-Layer Perceptron. This paper is a step toward a more complete comprehension of the optimization landscape specific to GNNs. 1 Introduction Graph Neural Networks (GNNs) [ 28 , 4 ] are deep architectures that have de facto become the state-of-the-art for machine learning problems on graphs [ 3 , 13 , 34 ] , with numerous applications ranging from chemistry [ 30 ] to physics [ 20 ] , social networks analysis and epidemiology [ 21 ] , combinatorial optimization [ 5 ] , and many others. Given a graph of size n represented by a graph-matrix P\in\mathbb{R}^{n\times n} (that can be various flavors of normalized adjacency, Laplacian…) and input node features as rows of X^{(0)}\in\mathbb{R}^{n\times d_{0}} , a vanilla GNN follows the propagation equation: X^{(k+1)}=\rho(PX^{(k)}W^{(k)}) (1) where W^{(k)}\in\mathbb{R}^{d_{k}\times d_{k+1}} are learnable weights and \rho is a non-linear activation function applied element-wise. A common interpretation is that GNNs realize “message-passing” through the matrix P . Many variants of message-passing exist (including some that cannot be written as fixed matrix multiplication [ 32 ] ), but most GNNs follow some flavors of this simple architecture. While theoretical and empirical studies of GNNs form an extremely large literature, with e.g. significant progress in the understanding of GNN expressivity or generalization [ 31 ] , some early topics and fundamental issues remain, to this day, active research questions [ 22 , 23 ] . Among them, oversmoothing [ 17 , 24 , 27 ] is a long-standing problematic phenomenon. It is rather unique to GNNs, and easy to formulate: since node representations are mixed by the matrix P (“ smoothed ”) at each layer, when the GNN becomes very deep they converge to a constant, uninformative limit. This prevents regular GNNs from being too deep, which is an issue: it has been theoretically shown that GNN need depth for optimal performance [ 15 , 18 ] , and shallow GNNs are subject to under-reaching , where distant nodes do not communicate at all [ 19 ] . Oversmoothing has been the topic of a very large literature [ 27 ] , with many strategies to mitigate it, such as different flavors of skip connections [ 16 ] or normalization [ 41 ] . Nevertheless, to some extent, there are still some fundamental open questions about this phenomenon – and about GNNs depth in general. Oversmoothing is rather easy to theoretically prove [ 24 , 27 ] . For instance, when P is a stochastic matrix, assuming that the weights W^{(k)} do not expand too much the node representations’ norm , the matrix P shrinks all directions but the constant one by at least its second-largest eigenvalue \lambda<1 , and typical measures of oversmoothing [ 27 ] converge exponentially fast to 0 as k increases (see Thm. 1 ). The hypothesis on the weights is crucial: when they are large 1 1 1 A weight matrix whose spectral norm is larger than 1 will be said to be expanding . , oversmoothing may not happen. As such, the GNN could learn to not oversmooth, as suggested by [ 36 , 9 ] . However: a) it is not common to directly initialize weights with high spectral norm, as this can lead to explosion of the features or the gradients, and b) when using regular initialization and gradient descent, vanilla deep GNNs generally do not learn to counteract oversmoothing (Fig. 1 ), even though this would clearly lead to better minimizers of the loss. There is therefore a problem with the optimization process itself . Contribution. In this paper, we thus look at oversmoothing from the optimization point of view. For this we put forth the notion of backward oversmoothing : just as the node representations are oversmoothed as k increases (in the “forward”), then so are the backpropagated errors, when k decreases from output to input. We show that it is the interaction between forward smoothing and backward smoothing that eventually produces backward oversmoothing at the middle layers (Thm. 2 ), especially in the presence of a non-linear \rho . Then, our main result is that backward oversmoothing produces many spurious stationary points : we prove that, as soon as the output layer is trained, then the whole GNN is in a near stationary-point. We argue that this is the main reason why deep GNNs are “hard” to train: the last layer quickly reaches a stationary point, and the GNN gets stuck with near-zero gradients (Fig. 1 , left) in easy-to-reach local minima with provably high loss (Thm. 3 and Cor. 2 ). Moreover, we also show that regular Multi-Layer Perceptron (MLP) are not subjected to the same phenomenon (Prop. 2 and Fig. 1 , center), making our result specific to deep GNN optimization. Our results rely on a precise characterization of the smoothed limit of the backward signal – which is generally unfeasible in forward oversmoothing due to the non-linearity \rho , hence the plethora of studies that study oversmoothing only for linear GNNs [ 15 , 25 ] . This constant limit is related to the average of the output error across nodes. The proofs contains several key observations that we believe may be useful in designing methods to counteract oversmoothing from an optimization point of view in the future. Note that this paper does not propose new methods to “solve” oversmoothing: there are a great number of them already [ 27 ] and it is slightly out of scope here. Besides, our results only apply to vanilla GNNs without the strategies that are typically used to address oversmoothing, which are left for future work. Instead, we explore important aspects of oversmoothing that were relatively ignored, and hope that it may give inspirations for further developments in the

Read the complete text