Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks

Abstract

Graph convolutional networks (GCNs) have recently received wide attentions, due to their successful applications in different graph tasks and different domains. Training GCNs for a large graph, however, is still a challenge. Original full-batch GCN training requires calculating the representation of all the nodes in the graph per GCN layer, which brings in high computation and memory costs. To alleviate this issue, several sampling-based methods have been proposed to train GCNs on a subset of nodes. Among them, the node-wise neighbor-sampling method recursively samples a fixed number of neighbor nodes, and thus its computation cost suffers from exponential growing neighbor size; while the layer-wise importance-sampling method discards the neighbor-dependent constraints, and thus the nodes sampled across layer suffer from sparse connection problem. To deal with the above two problems, we propose a new effective sampling algorithm called LAyer-Dependent ImportancE Sampling (LADIES). Based on the sampled nodes in the upper layer, LADIES selects their neighborhood nodes, constructs a bipartite subgraph and computes the importance probability accordingly. Then, it samples a fixed number of nodes by the calculated probability, and recursively conducts such procedure per layer to construct the whole computation graph. We prove theoretically and experimentally, that our proposed sampling algorithm outperforms the previous sampling methods in terms of both time and memory costs. Furthermore, LADIES is shown to have better generalization accuracy than original full-batch GCN, due to its stochastic nature.

Published in NeurIPS 2019

Cited by in corpus (31)

• Graph Neural Networks: A Review of Methods and Applications
• Graph Contrastive Learning with Augmentations
• SIGN: Scalable Inception Graph Neural Networks
• Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks
• GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training
• GPT-GNN: Generative Pre-Training of Graph Neural Networks
• The Evolution of Distributed Systems for Graph Neural Networks and their Origin in Graph Processing and Deep Learning: A Survey
• Relational Fusion Networks: Graph Convolutional Networks for Road Networks
• Scalable Graph Neural Networks via Bidirectional Propagation
• Scalable Graph Neural Network Training: The Case for Sampling
• Approximate Graph Propagation
• Graph-less Neural Networks: Teaching Old MLPs New Tricks via Distillation
• Bag of Tricks for Node Classification with Graph Neural Networks
• Scalable Graph Neural Networks for Heterogeneous Graphs
• Accelerating Sampling and Aggregation Operations in GNN Frameworks with GPU Initiated Direct Storage Accesses
• DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs
• Accelerating Training and Inference of Graph Neural Networks with Fast Sampling and Pipelining
• Sampling methods for efficient training of graph convolutional networks: A survey
• Self-supervised Graph Neural Networks without explicit negative sampling
• L${}^2$-GCN: Layer-Wise and Learned Efficient Training of Graph Convolutional Networks
• Constant Time Graph Neural Networks
• Deoscillated Graph Collaborative Filtering
• Communication-Efficient Sampling for Distributed Training of Graph Convolutional Networks
• A Biased Graph Neural Network Sampler with Near-Optimal Regret
• Tackling the Local Bias in Federated Graph Learning
• Local2Global: Scaling global representation learning on graphs via local training
• MG-GCN: Fast and Effective Learning with Mix-grained Aggregators for Training Large Graph Convolutional Networks
• GIPA: A General Information Propagation Algorithm for Graph Learning
• On the Importance of Sampling in Training GCNs: Tighter Analysis and Variance Reduction
• IGLU: Efficient GCN Training via Lazy Updates
• Hierarchical graph sampling based minibatch learning with chain preservation and variance reduction