Ripple Walk Training: A Subgraph-based training framework for Large and Deep Graph Neural Network

Jiyang Bai, Yuxiang Ren, Jiawei Zhang

Abstract

Graph neural networks (GNNs) have achieved outstanding performance in learning graph-structured data and various tasks. However, many current GNNs suffer from three common problems when facing large-size graphs or using a deeper structure: neighbors explosion, node dependence, and oversmoothing. Such problems attribute to the data structures of the graph itself or the designing of the multi-layers GNNs framework, and can lead to low training efficiency and high space complexity. To deal with these problems, in this paper, we propose a general subgraph-based training framework, namely Ripple Walk Training (RWT), for deep and large graph neural networks. RWT samples subgraphs from the full graph to constitute a mini-batch, and the full GNN is updated based on the mini-batch gradient. We analyze the high-quality subgraphs to train GNNs in a theoretical way. A novel sampling method Ripple Walk Sampler works for sampling these high-quality subgraphs to constitute the mini-batch, which considers both the randomness and connectivity of the graph-structured data. Extensive experiments on different sizes of graphs demonstrate the effectiveness and efficiency of RWT in training various GNNs (GCN & GAT).

Introduction

Standard Graph Neural Networks (GNNs) face significant challenges when scaling to large datasets or increasing network depth. These challenges are primarily categorized into three areas:

  1. Neighbors Explosion: Recursive information aggregation causes the number of nodes in a single calculation to grow exponentially with depth, making deep GNNs computationally prohibitive.
  2. Node Dependence: The interconnected nature of graphs often requires loading the entire adjacency matrix into memory, creating a bottleneck for massive datasets.
  3. Oversmoothing: As depth increases, node representations converge into indistinguishable averages, preventing the effective use of deep architectures.

While existing methods like GraphSAGE or Cluster-GCN address some of these issues, they often compromise on connectivity or struggle with memory overhead. Ripple Walk Training (RWT) is proposed as a general subgraph-based framework to overcome these limitations.

Ripple Walk Training (RWT)

RWT shifts the training paradigm from the full graph to high-quality mini-batch subgraphs. The core of this framework is the Ripple Walk Sampler.

The sampler begins by randomly selecting a seed node and expands outward in a "ripple-like" fashion. At each step, it identifies neighbors of the current subgraph and selects a fraction, determined by an expansion ratio $r$, to be added. This process balances randomness (ensuring unbiased estimation and preventing neighbor explosion) with connectivity (preserving local structural information).

The Ripple Walk Sampler expansion process, illustrating how subgraphs are constructed from a seed node through successive expansion steps.

By calculating gradients within these sampled subgraphs rather than the full graph, RWT maintains a constant and significantly smaller memory footprint, regardless of the total graph size. For instance, on the Reddit dataset, RWT reduces memory requirements from 212 GB to just 1.1 GB—a 200x reduction.

Experimental Evaluation

The effectiveness of RWT was evaluated on five benchmark datasets:

  • Citation Networks: Cora, Citeseer, and Pubmed.
  • Flickr: Images sharing common metadata.
  • Reddit: Large-scale social media posts and community labels.

The experiments covered both transductive and inductive tasks, comparing RWT against state-of-the-art baselines like GraphSAGE and Cluster-GCN.

Results and Discussion

RWT demonstrates significant improvements in both efficiency and the ability to train deep networks.

Mitigating Oversmoothing

A key finding is that training on subgraphs helps maintain distinct node representations. Each subgraph represents a "local steady state," preventing the global averaging that causes oversmoothing in deep architectures. As shown in Figure 2, RWT-GCN maintains high test accuracy even as the number of layers increases to 6, whereas standard GCN performance typically drops significantly after 3 layers.

Comparison of test accuracy between GCN with RWT and GCN with the full graph as the number of layers increases, showing RWT's robustness to oversmoothing.

The Expansion Ratio $r$

The expansion ratio $r$ is a critical hyperparameter. The authors found that $r=0.5$ generally provides the optimal balance. Lower values result in disconnected nodes lacking context, while higher values approach a Breadth-First Search, increasing the risk of neighbor explosion and reducing the benefits of randomness.

Conclusion

Ripple Walk Training provides a robust and efficient framework for training deep GNNs on large-scale graphs. By balancing randomness and connectivity through its unique sampling strategy, it overcomes the traditional bottlenecks of neighbor explosion and oversmoothing. Future work will focus on reducing hyperparameter sensitivity and exploring RWT's application to more complex heterogeneous graph architectures.

Summary updated

Abstract

Graph neural networks (GNNs) have achieved outstanding performance in learning graph-structured data and various tasks. However, many current GNNs suffer from three common problems when facing large-size graphs or using a deeper structure: neighbors explosion, node dependence, and oversmoothing. Such problems attribute to the data structures of the graph itself or the designing of the multi-layers GNNs framework, and can lead to low training efficiency and high space complexity. To deal with these problems, in this paper, we propose a general subgraph-based training framework, namely Ripple Walk Training (RWT), for deep and large graph neural networks. RWT samples subgraphs from the full graph to constitute a mini-batch, and the full GNN is updated based on the mini-batch gradient. We analyze the high-quality subgraphs to train GNNs in a theoretical way. A novel sampling method Ripple Walk Sampler works for sampling these high-quality subgraphs to constitute the mini-batch, which considers both the randomness and connectivity of the graph-structured data. Extensive experiments on different sizes of graphs demonstrate the effectiveness and efficiency of RWT in training various GNNs (GCN & GAT).
BibTeX
@inproceedings{bai2021ripple,
  author = {Jiyang Bai and Yuxiang Ren and Jiawei Zhang},
  title = {{Ripple Walk Training: A Subgraph-based training framework for Large and Deep Graph Neural Network}},
  booktitle = {IJCNN},
  year = {2021},
  url = {https://openreview.net/forum?id=nl0zmL-qiY6},
}
Figure