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

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 constant 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 be compensated. Theoretically, GNN could thus *learn* to not oversmooth. However, this 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 are also subject to oversmoothing from output to input. With non-linearities, 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. Additionally, we prove that this is *specific* to GNNs, and does not necessarily hold for Multi-Layer Perceptrons. This paper is a step toward a more complete comprehension of the optimization landscape of GNNs.