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

2020/02/17 by Jiyang Bai, Bai, Jiyang, Yuxiang Ren +3 · 12 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Neural Networks #Algorithm #Artificial intelligence #Artificial neural network #Computer science #Data mining #FOS: Computer and information sciences #Ferroelectric and Negative Capacitance Devices #Graph #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and ELM #Machine learning #Mathematics #Random walk #Sampling (signal processing) #Statistics #Theoretical computer science #Training (meteorology) #Training set #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.2002.07206

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2020/02/17 · arxiv created 2021/05/04 · arxiv updated 2021/05/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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

Citations

• Deep Convolutional Networks on Graph-Structured Data
• Spectral Networks and Locally Connected Networks on Graphs
• On Small-Sample Estimation
• Neural Network for Graphs: A Contextual Constructive Approach
• Collective Classification in Network Data
• Supervised neural networks for the classification of structures
• Inductive Representation Learning on Large Graphs
• Adaptive Sampling Towards Fast Graph Representation Learning
• MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing
• Graph Star Net for Generalized Multi-Task Learning
• GraphSAINT: Graph Sampling Based Inductive Learning Method
• Detecting Functionality-Specific Vulnerabilities via Retrieving Individual Functionality-Equivalent APIs in Open-Source Repositories
• GResNet: Graph Residual Network for Reviving Deep GNNs from Suspended Animation
• PairNorm: Tackling Oversmoothing in GNNs
• Fake News Detection on News-Oriented Heterogeneous Information Networks through Hierarchical Graph Attention

Cited by

• Geometric deep learning assists protein engineering. Opportunities and Challenges
• Empowering Credit Risk Detection in Weixin Pay with Billion-Scale Deep Graph Learning
• Scalable Graph Neural Network Training

Related

• SpanGNN: Towards Memory-Efficient Graph Neural Networks via Spanning Subgraph Training
• Measuring and Sampling: A Metric-guided Subgraph Learning Framework for Graph Neural Network
• Graph Learning at Scale: Characterizing and Optimizing Pre-Propagation GNNs
• LMC: Fast Training of GNNs via Subgraph Sampling with Provable Convergence
• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking