Graph Neural Networks Exponentially Lose Expressive Power for Node Classification

Kenta Oono, Taiji Suzuki

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.

Log relative distance to the invariant subspace $\mathcal{M}$ across layers, demonstrating the exponential convergence of node representations.

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.

Accuracy vs Layer Size for various weight scaling factors $s$ (left) and the evolution of singular values during training (right).

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

Abstract

Graph Neural Networks (graph NNs) are a promising deep learning approach for analyzing graph-structured data. However, it is known that they do not improve (or sometimes worsen) their predictive performance as we pile up many layers and add non-lineality. To tackle this problem, we investigate the expressive power of graph NNs via their asymptotic behaviors as the layer size tends to infinity. Our strategy is to generalize the forward propagation of a Graph Convolutional Network (GCN), which is a popular graph NN variant, as a specific dynamical system. In the case of a GCN, we show that when its weights satisfy the conditions determined by the spectra of the (augmented) normalized Laplacian, its output exponentially approaches the set of signals that carry information of the connected components and node degrees only for distinguishing nodes. Our theory enables us to relate the expressive power of GCNs with the topological information of the underlying graphs inherent in the graph spectra. To demonstrate this, we characterize the asymptotic behavior of GCNs on the Erdős -- Rényi graph. We show that when the Erdős -- Rényi graph is sufficiently dense and large, a broad range of GCNs on it suffers from the "information loss" in the limit of infinite layers with high probability. Based on the theory, we provide a principled guideline for weight normalization of graph NNs. We experimentally confirm that the proposed weight scaling enhances the predictive performance of GCNs in real data. Code is available at https://github.com/delta2323/gnn-asymptotics.
BibTeX
@inproceedings{oono2020graph,
  author = {Kenta Oono and Taiji Suzuki},
  title = {{Graph Neural Networks Exponentially Lose Expressive Power for Node Classification}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
  url = {https://openreview.net/forum?id=vtSfZkUD8wY},
}
Figure