GraphSAINT: Graph Sampling Based Inductive Learning Method

By Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, Viktor K. Prasanna. 2019

1,203 citations recorded by the source corpus.

Graph Convolutional Networks (GCNs) are powerful models for learning representations of attributed this http URL scale GCNs to large graphs, state-of-the-art methods use various layer sampling techniques to alleviate the "neighbor explosion" problem during minibatch training. Here we proposeGraphSAINT, a graph sampling based inductive learning method that improves training efficiency in a fundamentally different way. By a change of perspective, GraphSAINT constructs minibatches by sampling the training graph, rather than the nodes or edges across GCN layers. Each iteration, a complete GCN is built from the properly sampled subgraph. Thus, we ensure fixed number of well-connected nodes in all layers. We further propose normalization technique to eliminate bias, and sampling algorithms for variance reduction. Importantly, we can decouple the sampling process from the forward and backward propagation of training, and extend GraphSAINT with other graph samplers and GCN variants. Comparing with strong baselines using layer sampling, GraphSAINT demonstrates superior performance in both accuracy and training time on four large graphs.

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

1. Philip S. Yu
2. Jure Leskovec
3. Zhiyuan Liu
4. Maosong Sun
5. Shirui Pan
6. Xia Hu
7. Shuiwang Ji
8. Bernard Ghanem

In Information Systems

1. Philip S. Yu
2. Marinka Zitnik
3. Xia Hu
4. Qing He
5. Maosong Sun
6. Pan Li
7. Weihua Hu
8. Zhiyuan Liu

In Statistical and Nonlinear Physics

1. Marinka Zitnik
2. Philip S. Yu
3. Jure Leskovec
4. Matthias Fey
5. Yuxiao Dong
6. Pan Li
7. Le Song
8. Xia Hu

Citations in the corpus

• Auto-GNN: Neural architecture search of graph neural networks (2019, methodology): “Given the large-scale graphs in real-world application, several scalable GNNs are proposed by applying the batch training (Chang and Lin, 2010; Zeng et al., 2019).”
• Lifelong Graph Learning (2020, neutral): “Regardless of the nonlinear function, existing methods propagate neighbor features as ˆ AX , where meaning they can only propagate information element-wisely, as features in the next layer are weighted average of the current features [20, 22, 41, 57].”
• Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networks (2020, background): “However, due to the standard split sizes proposed for these benchmarks, state-of-the-art methods have already achieved F1 scores of 0.995 and 0.97 respectively (Zeng et al., 2019), making it difficult for further improvements to be properly gauged.”
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification (2023, methodology): “Table 2 presents the results on OGB-Proteins where for fair comparison mini-batch training is also used for other models except GraphSAINT.”
• Adaptive Universal Generalized PageRank Graph Neural Network (2020, methodology): “…have been proposed and used in practice, including graph convolutional layers (GCN) (Bruna et al., 2014; Kipf & Welling, 2017), graph attention layers (GAT) (Velickovic et al., 2018) and many others (Hamilton et al., 2017; Wijesinghe & Wang, 2019; Zeng et al., 2020; Abu-El-Haija et al., 2019).”
• Robust Graph Representation Learning via Neural Sparsification (2020, methodology): “Several works (Zeng et al., 2020; Hamilton et al., 2017; Chen et al., 2018) focus on downsampling under predefined dis-Robust tributions.”
• Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods (2021, positive): “As other minibatching methods are trickier to make work with these models, we use the Cluster-GCN [16] and GraphSAINT [77] minibatching methods, which sample subgraphs.”
• Bandit Samplers for Training Graph Neural Networks (2020, methodology): “We report results on 5 benchmark data that include Cora [18], Pubmed [18], PPI [11], Reddit [11], and Flickr [22].”
• Training Graph Neural Networks with 1000 Layers (2021, background): “, 2019) and GraphSAINT (Zeng et al., 2020) propose subgraph-wise sampling methods for mini-batch training with memory complexity O(LBD).”
• Open Graph Benchmark: Datasets for Machine Learning on Graphs (2020, methodology): “For example, recent GNN models (Chiang et al., 2019; Zeng et al., 2020) can already yield F1 scores of 99.5 for PPI and 97.0 for Reddit, and 90.4% accuracy for Amazon2M.”
• Enhancing Graph Neural Network-based Fraud Detectors against Camouflaged Fraudsters (2020, methodology): “learn the similarity metric based on domain knowledge. The relation filtering thresholds of CARE-GNN are optimized during training GNN which retains the end-to-end learning fashion. GNNsamplingmethods[5,46,51]alsofiltertheneighbors.While these works only consider selecting representative nodes to ac”
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning (2020, methodology): “To be evaluated over extremely large graphs [59], our models can be simply trimmed and work on the ego-networks sampled with a limited size around the target node sets, just as the strategy adopted by GraphSAGE [21] and GraphSAINT [60].”
• Graph Neural Networks: A Review of Methods and Applications (2018, background): “, 2019) samples subgraphs by graph clustering algorithms, while GraphSAINT (Zeng et al., 2020) directly samples nodes or edges to generate a subgraph.”
• Incremental Training of Graph Neural Networks on Temporal Graphs under Distribution Shift (2020, methodology): “Other works such as ClusterGCN [4] and GraphSAINT [33] suggest to sample entire sub-graphs before applying the GNNs.”