Abstract
Graph Neural Networks (GNNs) are a promising deep learning approach for analyzing graph-structured data. However, their predictive performance often plateaus or degrades as more layers and non-linearities are added—a phenomenon known as over-smoothing. This paper investigates the expressive power of GNNs by analyzing their asymptotic behavior as the layer size tends to infinity. By modeling the forward propagation of a Graph Convolutional Network (GCN) as a discrete dynamical system, we prove that node representations exponentially collapse into an "information-less" subspace $\mathcal{M}$ determined solely by the graph's topology. We characterize this collapse using the spectra of the augmented normalized Laplacian and provide a principled guideline for weight normalization to mitigate information loss. Experimental results on synthetic and real-world datasets confirm that our proposed weight scaling enhances the performance of deep GCNs.
Introduction: The Depth Wall in GNNs
In computer vision and natural language processing, increasing model depth typically leads to better feature hierarchies and improved performance. In contrast, GNNs often peak at just 2 or 3 layers. Beyond this depth, node representations tend to become indistinguishable, losing the unique feature information necessary for classification. While this "over-smoothing" has been observed empirically, theoretical explanations have largely been restricted to linear models. This work provides a rigorous mathematical explanation for this collapse in non-linear GCNs using ReLU activations.
The Geometry of Information Loss
The core of the paper's theory is the identification of an invariant subspace, $\mathcal{M}$, which the authors term "information-less." When a node's representation falls into this space, the network can only distinguish nodes based on their connected components and degrees; all other input features are lost.
By treating GCN propagation as a dynamical system, the authors prove that the distance between the network's output and $\mathcal{M}$ shrinks at an exponential rate of $O((s\lambda)^L)$. Here, $s$ represents the maximum singular value of the weights, $\lambda$ is a constant derived from the graph's spectral gap, and $L$ is the number of layers. Crucially, the non-linear ReLU activation does not prevent this collapse; instead, it acts as a projection that helps push signals toward the invariant subspace.
Spectral Analysis and Weight Scaling
The speed of information loss is tied to the graph's topology. On dense graphs, the spectral gap is typically larger, leading to faster "mixing" and more rapid collapse. This explains why deep GNNs struggle more on highly connected graphs than on sparse ones.
To counter this, the authors identify a critical weight-scaling threshold: $s < \lambda^{-1}$. If weights are too small relative to the graph's spectral properties, information is lost exponentially fast. Conversely, by ensuring weights stay above this threshold, the expressive power of the network can be preserved at greater depths.
Empirical Results and Guidelines
The authors validated their theory using Erdős–Rényi random graphs and standard citation datasets (Cora, CiteSeer, PubMed). In experiments on "Noisy Cora"—where random edges were added to increase density—standard GCNs with 9 layers quickly collapsed to random-chance accuracy.
As shown in the results, properly scaled weights (e.g., $s=10.0$) allowed the network to maintain significantly higher accuracy as depth increased, compared to unnormalized versions or those with small weights ($s=0.5$). This confirms that principled weight normalization is a key requirement for building effective deep GNNs.
Conclusion
This work provides a theoretical foundation for understanding the limitations of deep GNNs. By characterizing the exponential loss of expressive power through the lens of dynamical systems and spectral graph theory, it offers a clear explanation for over-smoothing. The proposed weight-scaling guidelines provide a practical path forward for researchers and practitioners looking to leverage the benefits of depth in graph-based deep learning.
Summary updated