# Adaptive Sampling Towards Fast Graph Representation Learning

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

## Key facts

- Cited by 180 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Sep 2018.

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

- [G-Mixup: Graph Data Augmentation for Graph Classification](https://mlsanity.com/paper/2202.07179/) (2022)
- [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)
- [Graph Attention Multi-Layer Perceptron](https://mlsanity.com/paper/2206.04355/) (2022)
- [Hierarchical Graph Transformer with Adaptive Node Sampling](https://mlsanity.com/paper/2210.03930/) (2022)
- [Cross-Node Federated Graph Neural Network for Spatio-Temporal Data Modeling](https://mlsanity.com/paper/2106.05223/) (2021)
- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [A Survey on Graph Neural Networks and Graph Transformers in Computer Vision: A Task-Oriented Perspective](https://mlsanity.com/paper/2209.13232/) (2022)
- [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)
- [GREAD: Graph Neural Reaction-Diffusion Networks](https://mlsanity.com/paper/2211.14208/) (2022)
- [PyG 2.0: Scalable Learning on Real World Graphs](https://mlsanity.com/paper/2507.16991/) (2025)
- [BGL: GPU-Efficient GNN Training by Optimizing Graph Data I/O and Preprocessing](https://mlsanity.com/paper/2112.08541/) (2021)
- [A*Net: A Scalable Path-based Reasoning Approach for Knowledge Graphs](https://mlsanity.com/paper/2206.04798/) (2022)
- [Node Dependent Local Smoothing for Scalable Graph Learning](https://mlsanity.com/paper/2110.14377/) (2021)
- [Improving Subgraph Recognition with Variational Graph Information Bottleneck](https://mlsanity.com/paper/2112.09899/) (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)
- [VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization](https://mlsanity.com/paper/2110.14363/) (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)
- [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)
- [Graph Convolutional Module for Temporal Action Localization in Videos](https://mlsanity.com/paper/2112.00302/) (2021)
- [Recognizing Predictive Substructures with Subgraph Information Bottleneck](https://mlsanity.com/paper/2103.11155/) (2021)
- [Algorithm and System Co-design for Efficient Subgraph-based Graph Representation Learning](https://mlsanity.com/paper/2202.13538/) (2022)
- [AdaProp: Learning Adaptive Propagation for Graph Neural Network based Knowledge Graph Reasoning](https://mlsanity.com/paper/2205.15319/) (2022)
- [Survey on Graph Neural Network Acceleration: An Algorithmic Perspective](https://mlsanity.com/paper/2202.04822/) (2022)
- [LMC: Fast Training of GNNs via Subgraph Sampling with Provable Convergence](https://mlsanity.com/paper/2302.00924/) (2023)

## Abstract (arXiv)

Graph Convolutional Networks (GCNs) have become a crucial tool on learning representations of graph vertices. The main challenge of adapting GCNs on large-scale graphs is the scalability issue that it incurs heavy cost both in computation and memory due to the uncontrollable neighborhood expansion across layers. In this paper, we accelerate the training of GCNs through developing an adaptive layer-wise sampling method. By constructing the network layer by layer in a top-down passway, we sample the lower layer conditioned on the top one, where the sampled neighborhoods are shared by different parent nodes and the over expansion is avoided owing to the fixed-size sampling. More importantly, the proposed sampler is adaptive and applicable for explicit variance reduction, which in turn enhances the training of our method. Furthermore, we propose a novel and economical approach to promote the message passing over distant nodes by applying skip connections. Intensive experiments on several benchmarks verify the effectiveness of our method regarding the classification accuracy while enjoying faster convergence speed.