Graph Neural Networks Exponentially Lose Expressive Power for Node Classification

Kenta Oono, Taiji Suzuki

TL;DR

Deep Graph Neural Networks (GNNs) often perform worse as they get deeper—a phenomenon known as "over-smoothing." This paper mathematically proves that as the number of layers increases, Graph Convolutional Network (GCN) node representations exponentially converge to a "featureless" subspace. This subspace only contains information about graph connectivity and node degrees, effectively losing all unique input feature data.

The Problem: Hitting the Depth Wall

In standard computer vision or natural language processing, "deeper is better" is a common mantra. However, researchers noticed that GCNs hit a wall very quickly; adding more than a few layers often leads to a sharp decline in performance. Node representations become increasingly similar until they are indistinguishable.

While empirical evidence for this over-smoothing was plentiful, a rigorous theoretical foundation was lacking. The authors set out to answer: Why does this happen? How fast is the information lost? And what role does the graph's actual topology play in this process?

Methodology: GCNs as Dynamical Systems

The authors treat the forward propagation of a GCN as a discrete dynamical system. By analyzing the asymptotic behavior of this system as the number of layers ($L$) tends toward infinity, they provide a formal proof of information loss.

Key technical aspects include:

  • Spectral Analysis: They relate the convergence rate to the eigenvalues (spectra) of the augmented normalized Laplacian of the graph.
  • Subspace Identification: They define an "invariant subspace" $\mathcal{M}$. If a node's representation falls into this subspace, it only carries information about which connected component it belongs to and its degree—losing all unique features that distinguish it from its neighbors.
  • ReLU as a Projection: A major hurdle in GNN theory is the non-linear activation function. The authors cleverly handle the ReLU function by treating it as a projection onto a non-negative cone, allowing them to prove that non-linearity actually accelerates the convergence to the useless subspace.

Key Insights and Ideas

The theoretical analysis yields several profound insights into GNN behavior:

  • The Loss is Exponential: The distance between the GCN output and the "information-less" subspace shrinks at a rate of $O((s\lambda)^L)$. This explains why performance drops so precipitously after just a few layers.
Log relative distance vs layer index showing exponential convergence
  • Density is a Double-Edged Sword: The authors show that on dense graphs (like a large Erdős–Rényi graph), the "mixing" happens much faster. This suggests that the inherent sparsity of real-world graphs might actually be a saving grace that allows GNNs to work at all.
  • The "Sweet Spot" for Weights: There is a theoretical "danger zone" for weight scales. If weights are too small ($s < \lambda^{-1}$), the network over-smooths exponentially. If they are too large, the model may become too complex and fail to generalize.
  • ReLU Doesn't Help: Contrary to some intuitions that non-linearity might preserve information, the authors prove that ReLU generally makes the over-smoothing problem worse by pushing signals toward the invariant subspace.

Key Results and Weight Scaling

The paper validates its theory using both synthetic (Erdős–Rényi) and real-world benchmarks (Cora, CiteSeer, PubMed), including artificially densified "noisy" variants to test the limits of their theory.

  • Theoretical Proof: The authors successfully proved that under specific conditions (related to weight singular values and graph spectra), GCNs carry zero useful information for node classification in the limit of infinite layers.
  • Weight Scaling Works: Based on their theory, they propose a principled guideline for weight normalization: to avoid information loss, the maximum singular value of the weight matrices ($s$) should be kept above a specific threshold determined by the graph's spectral gap ($\lambda^{-1}$). They demonstrated that following this guideline mitigates performance degradation in deeper architectures.
Accuracy vs Layer Size for different weight scales

Limitations and Future Work

While groundbreaking, the study has boundaries:

  • Activation Functions: The current proof relies heavily on the specific properties of the ReLU function. Extending this to other activations like Sigmoid or Leaky ReLU is non-trivial.
  • Task Scope: The study focuses strictly on node classification. The theory cannot be directly applied to graph-level classification tasks where a "readout" operation is used.
  • Residual Connections: While the paper briefly mentions that residual links turn the process into a "lazy" Markov chain (slowing but not stopping convergence), a deeper analysis of how residuals interact with non-linearity to prevent over-smoothing remains an open area.

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