Break the Ceiling: Stronger Multi-scale Deep Graph Convolutional Networks

Sitao Luan, Mingde Zhao, Xiao-Wen Chang, Doina Precup

Graph Convolutional Networks (GCNs) have revolutionized how we handle non-Euclidean data, but they have long hit a "performance ceiling." While standard ImageNet-style Convolutional Neural Networks can be hundreds of layers deep, GCNs usually start failing after just two or three. This paper from researchers at McGill, Mila, and DeepMind diagnoses why this happens and introduces two new architectures—Snowball and Truncated Krylov—that finally allow graph networks to scale in depth.

The Over-Smoothing and Rank Collapse Problems

If you stack too many layers in a standard GCN, you encounter the over-smoothing problem. Mathematically, graph convolution acts like a Laplacian smoothing operator. As you increase the number of layers toward infinity, the features of all nodes in a connected component converge to the same value. Essentially, the network "forgets" the local, unique information of each node and only remembers the global graph structure.

The authors also point out a second, often overlooked issue: rank collapse. They prove that in deep GCNs, the rank of the output feature matrix collapses to the number of connected components in the graph. This means the network loses the expressive power needed to distinguish between different nodes within the same cluster.

Methods: Overcoming the Ceiling

The authors tackle these issues through both theoretical analysis and architectural innovation.

1. Activation Function Analysis

They demonstrate that the ubiquitous ReLU activation function actually accelerates rank collapse. They propose (and prove mathematically) that the Tanh activation function is much better at preserving linear independence among features in deep architectures.

Rank collapse across different architectures and activation functions

2. The Krylov Connection

The paper generalizes spectral graph convolution into a block Krylov subspace form. A Krylov subspace is formed by repeatedly applying a matrix (like the graph Laplacian) to a vector. This provides a mathematical framework for capturing "multi-scale" information—incorporating 1-hop, 2-hop, and $n$-hop neighbors simultaneously.

3. Two New Architectures

Building on these insights, the authors propose two novel architectures designed to maintain feature diversity at depth:

Architectures of Snowball and Truncated Block Krylov GCNs
  • Snowball GCN: Inspired by DenseNet, this architecture incrementally concatenates features from all previous layers into the current one. As the network gets deeper, the feature "snowball" grows, ensuring that the original local features are never lost.
  • Truncated Krylov GCN: Instead of incremental stacking, each layer directly computes a multi-scale representation by concatenating the results of different powers of the graph operator (e.g., $L^0X, L^1X, L^2X$).

Datasets and Evaluation

The researchers evaluated their models on standard citation network benchmarks for node classification: Cora, CiteSeer, and PubMed. They tested these across various training split sizes (from a tiny 0.5% up to standard public splits) to see how the models perform when labeled data is scarce.

Key Insights and Results

The proposed architectures achieved State-of-the-Art (SOTA) performance across almost all tested scenarios.

  • Small Data Dominance: The models performed astonishingly better than existing methods when training data was very limited. For example, on Cora with a 0.5% split, the Truncated Krylov model achieved 71.8% accuracy, while the standard GCN managed only 42.6%.
  • Depth Scalability: Unlike standard GCNs that peak at 2 layers, the authors successfully trained models with up to 50 layers without experiencing a sharp drop in performance.
  • Multi-scale is the Antidote to Smoothing: By keeping "local" features alongside "global" features, the network avoids the information loss inherent in pure smoothing.
  • Visual Proof: t-SNE visualizations in the paper show that the proposed models create much tighter, more distinct clusters of nodes compared to traditional methods.

Limitations and Future Work

While the results are strong, the authors acknowledge a few areas for future exploration:

  • Simple Truncation: The current "Truncated Krylov" approach is a simplified version of more complex Krylov algorithms (like Lanczos). More sophisticated ways of leveraging these subspaces could yield even better numerical stability.
  • Activation Search: While Tanh performed well, there may be even better, perhaps learned, activation functions specifically suited for preserving graph feature diversity.
  • Computational Cost: Stacking features increases the number of parameters and memory usage. Finding more memory-efficient ways to maintain multi-scale information is a logical next step.

Summary updated

Abstract

Recently, neural network based approaches have achieved significant progress for solving large, complex, graph-structured problems. Nevertheless, the advantages of multi-scale information and deep architectures have not been sufficiently exploited. In this paper, we first analyze key factors constraining the expressive power of existing Graph Convolutional Networks (GCNs), including the activation function and shallow learning mechanisms. Then, we generalize spectral graph convolution and deep GCN in block Krylov subspace forms, upon which we devise two architectures, both scalable in depth however making use of multi-scale information differently. On several node classification tasks, the proposed architectures achieve state-of-the-art performance.
BibTeX
@inproceedings{luan2019break,
  author = {Sitao Luan and Mingde Zhao and Xiao-Wen Chang and Doina Precup},
  title = {{Break the Ceiling: Stronger Multi-scale Deep Graph Convolutional Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=Vjha_PUIu2},
}
Figure