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

arXiv: https://arxiv.org/abs/1911.07323 · HTML: https://mlsanity.com/paper/1911.07323/

## Key facts

- Cited by 177 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Nov 2019.

## Built on by (most cited first, 30 of 177)

- [Graph-less Neural Networks: Teaching Old MLPs New Tricks via Distillation](https://mlsanity.com/paper/2110.08727/) (2021)
- [NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphs](https://mlsanity.com/paper/2206.04910/) (2022)
- [Data Augmentation for Deep Graph Learning: A Survey](https://mlsanity.com/paper/2202.08235/) (2022)
- [GraphMAE2: A Decoding-Enhanced Masked Self-Supervised Graph Learner](https://mlsanity.com/paper/2304.04779/) (2023)
- [Decoupling the Depth and Scope of Graph Neural Networks](https://mlsanity.com/paper/2201.07858/) (2022)
- [GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings](https://mlsanity.com/paper/2106.05609/) (2021)
- [Scaling Up Graph Neural Networks Via Graph Coarsening](https://mlsanity.com/paper/2106.05150/) (2021)
- [SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning](https://mlsanity.com/paper/2308.02565/) (2023)
- [Hierarchical Graph Transformer with Adaptive Node Sampling](https://mlsanity.com/paper/2210.03930/) (2022)
- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [Cold Brew: Distilling Graph Node Representations with Incomplete or Missing Neighborhoods](https://mlsanity.com/paper/2111.04840/) (2021)
- [A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking](https://mlsanity.com/paper/2210.07494/) (2022)
- [Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth](https://mlsanity.com/paper/2105.04550/) (2021)
- [Scalable and Adaptive Graph Neural Networks with Self-Label-Enhanced training](https://mlsanity.com/paper/2104.09376/) (2021)
- [BNS-GCN: Efficient Full-Graph Training of Graph Convolutional Networks with Partition-Parallelism and Random Boundary Node Sampling](https://mlsanity.com/paper/2203.10983/) (2022)
- [Sampling methods for efficient training of graph convolutional networks: A survey](https://mlsanity.com/paper/2103.05872/) (2021)
- [Bag of Tricks for Node Classification with Graph Neural Networks](https://mlsanity.com/paper/2103.13355/) (2021)
- [Accelerating Training and Inference of Graph Neural Networks with Fast Sampling and Pipelining](https://mlsanity.com/paper/2110.08450/) (2021)
- [VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization](https://mlsanity.com/paper/2110.14363/) (2021)
- [Bag of Tricks for Training Deeper Graph Neural Networks: A Comprehensive Benchmark Study](https://mlsanity.com/paper/2108.10521/) (2021)
- [VQGraph: Rethinking Graph Representation Space for Bridging GNNs and MLPs](https://mlsanity.com/paper/2308.02117/) (2023)
- [FedGraph: Federated Graph Learning with Intelligent Sampling](https://mlsanity.com/paper/2111.01370/) (2021)
- [Double-Scale Self-Supervised Hypergraph Learning for Group Recommendation](https://mlsanity.com/paper/2109.04200/) (2021)
- [Distributed Graph Neural Network Training: A Survey](https://mlsanity.com/paper/2211.00216/) (2022)
- [GraphFM: Improving Large-Scale GNN Training via Feature Momentum](https://mlsanity.com/paper/2206.07161/) (2022)
- [Linear-Time Graph Neural Networks for Scalable Recommendations](https://mlsanity.com/paper/2402.13973/) (2024)
- [Parallel and Distributed Graph Neural Networks: An In-Depth Concurrency Analysis](https://mlsanity.com/paper/2205.09702/) (2022)
- [Hierarchical Prototype Networks for Continual Graph Representation Learning](https://mlsanity.com/paper/2111.15422/) (2021)
- [Bringing Your Own View: Graph Contrastive Learning without Prefabricated Data Augmentations](https://mlsanity.com/paper/2201.01702/) (2022)
- [AdaProp: Learning Adaptive Propagation for Graph Neural Network based Knowledge Graph Reasoning](https://mlsanity.com/paper/2205.15319/) (2022)

## Abstract (arXiv)

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.