Fast and Deep Graph Neural Networks

Claudio Gallicchio, Alessio Micheli

Abstract

This research addresses the efficiency challenges in constructing deep Graph Neural Networks (GNNs). By representing input graphs as fixed points of a dynamical system implemented through recurrent units, the authors introduce Fast and Deep Graph Neural Networks (FDGNN). Efficiency is achieved by using small, sparse networks where recurrent unit weights remain untrained under a specific stability condition. Experimental results demonstrate that this architecture, despite its untrained connections, achieves or improves upon state-of-the-art performance in graph classification tasks while offering significant computational speedups.

Introduction

Graph Neural Networks (GNNs) have become the standard for processing relational data, such as molecular structures or social graphs. However, scaling these models to greater depths introduces significant computational overhead and structural complexities, particularly when handling cycles within graphs. Traditional deep GNNs require intensive backpropagation through time or iterative solvers that are slow to train.

The authors of this paper explore a fundamental question: is the success of deep GNNs derived from the optimization of internal weights, or from the intrinsic hierarchical structure of the architecture itself? To investigate this, they propose a model that leverages randomized, untrained weights within a deep architectural framework.

Methodology: Reservoir Computing for Graphs

The FDGNN approach is grounded in the "Reservoir Computing" paradigm, specifically Echo State Networks. The core idea is to treat the graph embedding process as a dynamical system that converges to a stable state.

Architecture

FDGNN consists of multiple stacked layers of recurrent units. Each layer processes the graph to produce an embedding, which then serves as the input for the subsequent layer. This stacking allows the model to capture increasingly complex, hierarchical features of the graph topology.

Architecture of the Fast and Deep Graph Neural Network (FDGNN) showing the stacking of hidden layers.

Stability and Efficiency

To ensure the system produces reliable and unique embeddings, the authors define a Graph Embedding Stability (GES) condition. By constraining the spectral radius of the weight matrices relative to the graph's maximum degree ($k$), the system is guaranteed to reach a unique fixed point regardless of the initial state.

Key efficiency gains come from:

  • Untrained Weights: Only the final "readout" layer is trained using simple linear methods like Tikhonov regularization.
  • Sparsity: Internal connectivity is kept extremely sparse (often just one connection per neuron), reducing the number of operations required per iteration.

Key Results

The model was evaluated on nine benchmark datasets, including chemical compounds (e.g., MUTAG, NCI1) and social networks (e.g., IMDB, REDDIT).

Performance and Accuracy

Despite using randomized internal weights, FDGNN achieved state-of-the-art or competitive results on 7 out of 9 benchmarks. The results suggest that the architectural design—specifically the depth and the way information aggregates—is a primary driver of GNN performance.

Classification accuracy of FDGNN compared to state-of-the-art models across multiple benchmarks.

Computational Speedup

The most striking result is the training efficiency. On the MUTAG dataset, FDGNN was approximately 360 times faster than standard GNNs and nearly 890 times faster than Graph Isomorphism Networks (GIN). This speedup is attributed to the avoidance of backpropagation in the hidden layers and the use of efficient linear readouts.

Conclusion

FDGNN demonstrates that deep GNNs do not necessarily require fully trained internal layers to be effective. By prioritizing architectural stability and depth, the model achieves high accuracy with a fraction of the computational cost. This work provides a new lens through which to view GNN design, suggesting that the "intrinsic power" of the architecture is a potent tool for efficient graph representation learning.

Summary updated

Abstract

We address the efficiency issue for the construction of a deep graph neural network (GNN). The approach exploits the idea of representing each input graph as a fixed point of a dynamical system (implemented through a recurrent neural network), and leverages a deep architectural organization of the recurrent units. Efficiency is gained by many aspects, including the use of small and very sparse networks, where the weights of the recurrent units are left untrained under the stability condition introduced in this work. This can be viewed as a way to study the intrinsic power of the architecture of a deep GNN, and also to provide insights for the set-up of more complex fully-trained models. Through experimental results, we show that even without training of the recurrent connections, the architecture of small deep GNN is surprisingly able to achieve or improve the state-of-the-art performance on a significant set of tasks in the field of graphs classification.
BibTeX
@inproceedings{gallicchio2020fast,
  author = {Claudio Gallicchio and Alessio Micheli},
  title = {{Fast and Deep Graph Neural Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i04.5803},
}
Figure