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

By Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, Quanquan Gu. Neural Information Processing Systems, 2019

339 citations recorded by the source corpus.

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 are 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 across layers; 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 nodes that are in the neighborhood of these nodes and uses the constructed bipartite graph to compute the importance probability. Then, it samples a fixed number of nodes according to the probability for the whole layer, 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 regarding both time and memory. Furthermore, LADIES is shown to have better generalization accuracy than original full-batch GCN, due to its stochastic nature.

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

View Paper: https://www.semanticscholar.org/paper/9dccd22276aaad5b6ec24e68bb7d29d954226a54

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

Enhancing Graph Neural Network-based Fraud Detectors against Camouflaged Fraudsters (2020, neutral): “GNN samplingmethods [5, 46, 51] also filter the neighbors.”
SIGN: Scalable Inception Graph Neural Networks (2020, background): “So far, various graph sampling approaches (Hamilton et al., 2017a; Ying et al., 2018; Chen et al., 2018; Huang et al., 2018; Chen & Zhu, 2018; Chiang et al., 2019; Zeng et al., 2019; Zou et al., 2019) have been proposed as a way to alleviate the cost of training graph neural networks by selecting a ”
Graph Neural Networks: A Review of Methods and Applications (2018, background): “LADIES (Zou et al., 2019) intends to alleviate the sparsity issue in layer-wise sampling by generating samples from the union of neighbors of the nodes.”
Bandit Samplers for Training Graph Neural Networks (2020, methodology): “The basic idea of layer sampling approaches [11, 6, 12, 23] was to recast the evaluation of Eq.”
Graph Contrastive Learning with Augmentations (2020, background): “Numerous variants of GNNs have been proposed to achieve state-of-the-art performances in graph-based tasks, such as node or link classiﬁcation [1, 2, 4, 5, 6], link prediction [7] and graph classiﬁcation [8, 3].”
GPT-GNN: Generative Pre-Training of Graph Neural Networks (2020, methodology): “ are too large to fit into the hardware, we sample subgraphs for training. In particular, we propose to sample a dense subgraph from homogeneous and heterogeneous graphs by using the LADIES algorithm [45] and its heterogeneous version HGSampling [15], respectively. Both methods theoretically guarant”
Graph Random Neural Networks for Semi-Supervised Learning on Graphs (2020, methodology): “k of over-smoothing and overfitting. Recent efforts have also been devoted to performing node sampling for fast and scalable GNN training, such as GraphSAGE [22], FastGCN [9], AS-GCN [24], and LADIES [52]. Different from these work, in this paper, a new sampling strategy DropNode, is proposed for im”
DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs (2020, background): “strategies to sample graphs for mini-batch training [3], [4], [24]–[26].”