Adaptive Sampling Towards Fast Graph Representation Learning

By Wen-bing Huang, Tong Zhang, Yu Rong, Junzhou Huang. 2018

553 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Information Systems, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Statistical and Nonlinear Physics

Citations in the corpus

Lifelong Graph Learning (2020, neutral): “[17] sampled lower layer conditioned on the top one ensuring higher accuracy and fixed-size sampling.”
Simple and Deep Graph Convolutional Networks (2020, background): “, 2017) uses a fixed size of neighborhood samples through layers, (Chen et al., 2018a; Huang et al., 2018) propose efficient variants based on importance sampling.”
HyGCN: A GCN Accelerator with Hybrid Architecture (2020, methodology): “The former indices for edge sampling are based on dynamic generation while the latter ones are predefined and can be read from offchip memory like in [11, 26].”
GNNExplainer: Generating Explanations for Graph Neural Networks (2019, methodology): “Thus, GNNEXPLAINER can be applied to: Graph Convolutional Networks [21], Gated Graph Sequence Neural Networks [26], Jumping Knowledge Networks [36], Attention Networks [33], Graph Networks [4], GNNs with various node aggregation schemes [7, 5, 18, 16, 40, 39, 35], Line-Graph NNs [8], position-aware ”
Learning to Drop: Robust Graph Neural Network via Topological Denoising (2020, methodology): “d to suboptimal performance in generalization. Recently, graph sampling has been investigated in GNNs for fast computation and better generalization capacity, including neighborlevel [17], node-level [6, 20, 52], and edge-level sampling methods [38]. Unlike these methods that randomly sample edges i”
DropEdge: Towards Deep Graph Convolutional Networks on Node Classification (2019, methodology): “We apply the full-supervised training fashion used in Huang et al. (2018) and Chen et al. (2018) on all datasets in our experiments.”
Graph Convolutional Networks for Temporal Action Localization (2019, methodology): “To accelerate the training of GCNs, several approaches [7, 23, 20] have been proposed based on neighbourhood sampling.”
GraphSAINT: Graph Sampling Based Inductive Learning Method (2019, methodology): “The sampler of AS-GCN is expensive to execute, making its overall training time even longer than vanilla GCN.”
Robust Graph Convolutional Networks Against Adversarial Attacks (2019, background): “Further improvements include adding an attention mechanism to assign different weights in aggregating node neighborhoods [28, 30, 31, 34], adding residual and jumping connections [32], sampling to improve efficiency [4, 5, 14, 33] considering edge attributes [15, 23, 26], disentangling node represen”
SIGN: Scalable Inception Graph Neural Networks (2020, methodology): “Layer-wise sampling [10, 28] avoids over-expansion of neighborhoods to overcome the redundancy of node-wise sampling.”
Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, methodology): “…al., 2018), novel techniques for pooling node representations in order perform graph classiﬁcation, e.g., (Cangea et al., 2018; Gao & Ji, 2019; Ying et al., 2018; Zhang et al., 2018), incorporating distance information (You et al., 2019), and non-euclidian geometry approaches (Chami et al., 2019).”
Bandit Samplers for Training Graph Neural Networks (2020, methodology): “However, the optimal sampler [12], q ij = αij‖h j ‖ 2 ∑ k∈Ni αik‖h k ‖2 for vertex vi, to minimize the variance”
Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks (2019, background): “As is pointed out in [11], the recursive nature of node-wise sampling brings in redundancy for calculating embeddings.”
Deep Learning on Graphs: A Survey (2018, unknown): “Adapt [69] further proposed sampling nodes in the lower layers conditioned on their top layer; this approach was more adaptive and applicable to explicitly reduce variances.”
Scaling Graph Neural Networks with Approximate PageRank (2020, methodology): “5.4) •How efficient is the proposed sparse inference scheme? (§ 5.5) 5.1 Large-Scale Datasets The majority of previous approaches are evaluated on a small set of publicly available benchmark datasets [2, 13, 14, 21, 25, 27, 41, 49]. The size of these datasets is relatively small, with the Reddit gra”
Deep multi-view learning methods: A review (2021, background): “Recently, GNN has achieved outstanding performance in graph-structured data analysis, such as social network [74] and knowledge graphs [75].”
Incremental Training of Graph Neural Networks on Temporal Graphs under Distribution Shift (2020, methodology): “Finally, results from papers on sampling-based graph convolution such as [11,3] can be directly applied to our approach, too, as the sampling can be restricted to the window size given.”