On Addressing the Limitations of Graph Neural Networks

Sitao LuanarXiv 2023 · DOI · arXiv

Graph Neural Networks (GNNs) have revolutionized fields ranging from drug discovery to social network analysis. However, they frequently encounter a "performance ceiling." Increasing the depth of a Graph Convolutional Network (GCN) often leads to over-smoothing, where node representations become indistinguishable. Furthermore, GNNs often struggle with heterophilous graphs, where connected nodes possess different labels, sometimes performing worse than simple multi-layer perceptrons (MLPs).

This paper by Sitao Luan et al. provides a comprehensive analysis of these limitations and proposes architectural and theoretical solutions to create deeper, more expressive, and adaptive GNNs.

Overcoming the Depth Bottleneck

The primary obstacle to deep GNNs is rank collapse. As networks grow deeper, the expressive power of hidden layers diminishes. The authors demonstrate that standard GCNs lose rank rapidly, a process accelerated by the ubiquitous ReLU activation function.

To combat this, the researchers introduce the Snowball and Truncated Block Krylov architectures. Unlike traditional stacked layers, these designs utilize a block Krylov form, concatenating multi-scale information at each layer. By "stacking" features from various neighborhood sizes, these architectures effectively prevent the loss of rank and preserve information across deep layers.

Architectural diagrams of the proposed Snowball and Truncated Block Krylov networks.

The "ReLU Conspirator" and Activation Functions

A key theoretical insight is the role of activation functions in over-smoothing. While over-smoothing is often viewed as an inherent property of graph filters, the authors identify ReLU as a "conspirator" that hastens rank collapse. Through theoretical and numerical analysis, they show that Tanh and Identity functions are significantly better at maintaining the linear independence of hidden features over many layers.

Rank collapse across different architectures and activation functions.

Adaptive Channel Mixing (ACM) for Heterophily

Standard GNNs typically assume homophily—the tendency of similar nodes to be connected. In heterophilous settings (e.g., predator-prey networks), standard aggregation fails. The authors propose the Adaptive Channel Mixing (ACM) framework, which employs a "filterbank" approach. Each layer extracts features through three distinct channels:

  1. Low-Pass: Standard neighborhood aggregation.
  2. High-Pass: Captures differences between neighbors.
  3. Identity: Preserves the node's own features.

A node-wise attention mechanism then adaptively mixes these channels, allowing the model to prioritize different types of information based on local graph structure.

Degree-Aware Weight Initialization

Standard initialization methods like Xavier or He do not account for the variance-shifting effects of graph aggregation. The authors derive a new degree-aware initialization scheme. By scaling weight variance based on the average node degree, they ensure stable variance propagation, enabling the training of GCNs up to 100 layers deep without vanishing or exploding gradients.

Key Results and Insights

The proposed methods were evaluated across diverse benchmarks, including standard homophily datasets (Cora, CiteSeer, PubMed) and various heterophily benchmarks.

  • State-of-the-Art Performance: The Truncated Krylov model achieved state-of-the-art results on semi-supervised tasks, particularly when labeled data was limited.
  • Heterophily Robustness: The ACM framework significantly improved baseline GNN performance on heterophilous datasets like Cornell, surpassing previous SOTA models by 4.1%.
  • Redefining Heterophily: The authors introduced Aggregation Homophily ($H_{agg}$), a new metric that distinguishes between "harmful" heterophily and "harmless" heterophily (e.g., bipartite structures), providing a more accurate measure of graph difficulty for GNNs.

Conclusion

By addressing rank collapse through new architectures and activation choices, and tackling heterophily with adaptive filterbanks, this work provides a robust blueprint for the next generation of GNNs. Future research will focus on Adjacency Learning to dynamically optimize graph structures for specific tasks and exploring GNN applications in accelerating Reinforcement Learning.

Summary updated

Abstract

This report gives a summary of two problems about graph convolutional networks (GCNs): over-smoothing and heterophily challenges, and outlines future directions to explore.
BibTeX
@misc{luan2023addressing,
  author = {Sitao Luan},
  title = {{On Addressing the Limitations of Graph Neural Networks}},
  year = {2023},
  eprint = {2306.12640},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.12640},
}
Figure