Stochastic Training of Graph Convolutional Networks with Variance Reduction

Abstract

Graph convolutional networks (GCNs) are powerful deep neural networks for graph-structured data. However, GCN computes the representation of a node recursively from its neighbors, making the receptive field size grow exponentially with the number of layers. Previous attempts on reducing the receptive field size by subsampling neighbors do not have a convergence guarantee, and their receptive field size per node is still in the order of hundreds. In this paper, we develop control variate based algorithms which allow sampling an arbitrarily small neighbor size. Furthermore, we prove new theoretical guarantee for our algorithms to converge to a local optimum of GCN. Empirical results show that our algorithms enjoy a similar convergence with the exact algorithm using only two neighbors per node. The runtime of our algorithms on a large Reddit dataset is only one seventh of previous neighbor sampling algorithms.

References in corpus (3)

• Inductive Representation Learning on Large Graphs
• Graph Convolutional Matrix Completion
• Variational Graph Auto-Encoders

Cited by in corpus (37)

• Inductive Representation Learning on Large Graphs
• Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks
• Scaling Graph Neural Networks with Approximate PageRank
• Graph-Based Deep Learning for Medical Diagnosis and Analysis: Past, Present and Future
• DeeperGCN: All You Need to Train Deeper GCNs
• DeepGCNs: Making GCNs Go as Deep as CNNs
• Graph Attention Multi-Layer Perceptron
• Batch Virtual Adversarial Training for Graph Convolutional Networks
• Scalable Graph Neural Network Training: The Case for Sampling
• Company-as-Tribe: Company Financial Risk Assessment on Tribe-Style Graph with Hierarchical Graph Neural Networks
• HP-GNN: Generating High Throughput GNN Training Implementation on CPU-FPGA Heterogeneous Platform
• Ginex: SSD-enabled Billion-scale Graph Neural Network Training on a Single Machine via Provably Optimal In-memory Caching
• Scalable Graph Neural Networks for Heterogeneous Graphs
• Lifelong Learning of Graph Neural Networks for Open-World Node Classification
• Improving Graph Attention Networks with Large Margin-based Constraints
• Bayesian graph convolutional neural networks via tempered MCMC
• Lifelong Learning on Evolving Graphs Under the Constraints of Imbalanced Classes and New Classes
• Learned Low Precision Graph Neural Networks
• Structure fusion based on graph convolutional networks for semi-supervised classification
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution
• Accurate, Efficient and Scalable Training of Graph Neural Networks
• Identifying Illicit Accounts in Large Scale E-payment Networks -- A Graph Representation Learning Approach
• L${}^2$-GCN: Layer-Wise and Learned Efficient Training of Graph Convolutional Networks
• Constant Time Graph Neural Networks
• i-Align: an interpretable knowledge graph alignment model
• Training Matters: Unlocking Potentials of Deeper Graph Convolutional Neural Networks
• FastGL: A GPU-Efficient Framework for Accelerating Sampling-Based GNN Training at Large Scale
• Virtual Adversarial Training on Graph Convolutional Networks in Node Classification
• Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks
• Benchmark Tests of Convolutional Neural Network and Graph Convolutional Network on HorovodRunner Enabled Spark Clusters
• Graph Feature Gating Networks
• Modeling Multi-Destination Trips with Sketch-Based Model
• Partitioned Graph Convolution Using Adversarial and Regression Networks for Road Travel Speed Prediction
• Action Recognition with Kernel-based Graph Convolutional Networks
• Contributions to Representation Learning with Graph Autoencoders and Applications to Music Recommendation
• Network Representation Learning: From Traditional Feature Learning to Deep Learning
• Decoupled Variational Embedding for Signed Directed Networks