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.
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:
- 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