Towards Deeper Graph Neural Networks

Meng Liu, Hongyang Gao, Shuiwang Ji

TL;DR

Standard Graph Neural Networks (GNNs) typically fail when they go deeper than two or three layers due to "over-smoothing" and the entanglement of feature transformation with neighbor propagation. This paper introduces Deep Adaptive Graph Neural Network (DAGNN), which decouples these operations and uses a learned adaptive weighting scheme to successfully leverage information from up to 200 hops away, setting new state-of-the-art results on several benchmarks.

What Problem Does This Paper Address?

In the world of deep learning, "deeper is better" is a common mantra. However, Graph Convolutional Networks (GCNs) have historically been the exception. When researchers try to stack more than a few layers, performance usually falls off a cliff.

The community has largely blamed this on over-smoothing: the idea that as you aggregate information from neighbors over many iterations, every node’s representation eventually converges to the same value, making them indistinguishable. This paper argues that while over-smoothing is a real theoretical limit, the immediate cause of failure in shallow-to-medium depths is actually the entanglement of representation transformation (the weights and non-linearities) and propagation (the graph-based averaging). Because each layer in a standard GCN couples these two, adding layers exponentially increases the number of parameters and makes the model incredibly difficult to train.

Methods

The authors propose a two-pronged solution embodied in DAGNN:

  1. Decoupling Transformation and Propagation: Instead of interleaving weight matrices with graph aggregations, DAGNN first applies a multi-layer perceptron (MLP) to the node features to produce a "base" representation ($Z$). Then, it performs $k$ steps of graph propagation on $Z$ without any additional trainable weights or non-linearities in the propagation steps. This allows the model to reach a massive receptive field (e.g., 100+ hops) without a parameter explosion.
  2. Adaptive Adjustment Mechanism: Not every node needs information from 100 hops away; some are better defined by their immediate neighbors. DAGNN learns a "retainment score" for each hop. It calculates a weighted sum of the representations from all hops (from 0 to $k$), allowing the model to adaptively balance local and global information for every individual node.

The authors also provide a rigorous theoretical proof (Theorems 3.1 and 3.2) showing exactly what node representations converge to as depth goes to infinity, providing a "gentle" mathematical description of the over-smoothing phenomenon.

Datasets

The researchers evaluated DAGNN on seven widely used datasets across three categories:

  • Citation Networks: Cora, CiteSeer, and PubMed.
  • Co-authorship Graphs: Coauthor CS and Coauthor Physics.
  • Co-purchase Graphs: Amazon Computers and Amazon Photo.

These datasets vary significantly in "edge density," which the authors show is a key factor in how quickly a graph over-smooths.

Key Insights and Ideas

  • The Entanglement Trap: The "aha moment" is realizing that GCNs fail early not just because of the graph topology, but because we are trying to learn complex transformations at the same time as we are diffusing information. By doing the "thinking" (MLP) first and the "diffusing" (propagation) second, we can go much deeper.
  • Over-smoothing is a Choice: The t-SNE visualizations in the paper show that even at 50 hops, decoupled models still produce distinct, clusterable representations, whereas standard GCNs become a "blob" after just 6 layers.
  • Receptive Fields Matter for Small Data: One of the most striking insights is that deeper models are significantly more robust when training labels are scarce. If you only have one labeled node per class, you need a large receptive field to propagate that signal across the graph.

Key Results

  • Superior Accuracy: DAGNN outperformed state-of-the-art baselines (like GCN, GAT, APPNP, and SGC) across all seven datasets.
  • Low-Label Performance: On the Cora dataset with only one training node per class, DAGNN improved accuracy over GCN by a staggering 23.7%.
  • Depth Stability: While GCN performance plummeted after 3 layers, DAGNN remained stable or even improved as the number of hops increased to 100 or 200.
  • Efficiency: Because the propagation steps have no trainable parameters, DAGNN is more parameter-efficient than stacking standard GCN layers.

Limitations and Future Work

The authors note that graph topology still dictates the ultimate limits. In densely connected graphs (like the Amazon co-purchase datasets), performance still eventually degrades as depth increases because the "mixing time" of the graph is much shorter—information spreads so fast that nodes become similar very quickly.

Future work might involve exploring more sophisticated ways to calculate the adaptive retainment scores or investigating how to handle extremely dense graphs where the over-smoothing limit is reached in very few hops regardless of decoupling.

Summary updated

Abstract

Graph neural networks have shown significant success in the field of graph representation learning. Graph convolutions perform neighborhood aggregation and represent one of the most important graph operations. Nevertheless, one layer of these neighborhood aggregation methods only consider immediate neighbors, and the performance decreases when going deeper to enable larger receptive fields. Several recent studies attribute this performance deterioration to the over-smoothing issue, which states that repeated propagation makes node representations of different classes indistinguishable. In this work, we study this observation systematically and develop new insights towards deeper graph neural networks. First, we provide a systematical analysis on this issue and argue that the key factor compromising the performance significantly is the entanglement of representation transformation and propagation in current graph convolution operations. After decoupling these two operations, deeper graph neural networks can be used to learn graph node representations from larger receptive fields. We further provide a theoretical analysis of the above observation when building very deep models, which can serve as a rigorous and gentle description of the over-smoothing issue. Based on our theoretical and empirical analysis, we propose Deep Adaptive Graph Neural Network (DAGNN) to adaptively incorporate information from large receptive fields. A set of experiments on citation, co-authorship, and co-purchase datasets have confirmed our analysis and insights and demonstrated the superiority of our proposed methods.
BibTeX
@inproceedings{liu2020towards,
  author = {Meng Liu and Hongyang Gao and Shuiwang Ji},
  title = {{Towards Deeper Graph Neural Networks}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2020},
  doi = {10.1145/3394486.3403076},
}

Loading related content...

Figure