GraphSAINT: Graph Sampling Based Inductive Learning Method

Abstract

Graph Convolutional Networks (GCNs) are powerful models for learning representations of attributed graphs. To scale GCNs to large graphs, state-of-the-art methods use various layer sampling techniques to alleviate the "neighbor explosion" problem during minibatch training. We propose GraphSAINT, a graph sampling based inductive learning method that improves training efficiency and accuracy in a fundamentally different way. By changing 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 from the forward and backward propagation, and extend GraphSAINT with many architecture variants (e.g., graph attention, jumping connection). GraphSAINT demonstrates superior performance in both accuracy and training time on five large graphs, and achieves new state-of-the-art F1 scores for PPI (0.995) and Reddit (0.970).

Published at ICLR 2020; Code release: github.com/GraphSAINT/GraphSAINT

References in corpus (12)

• Adam: A Method for Stochastic Optimization
• TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
• Inductive Representation Learning on Large Graphs
• Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks
• Representation Learning on Graphs with Jumping Knowledge Networks
• MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing
• GaAN: Gated Attention Networks for Learning on Large and Spatiotemporal Graphs
• Adaptive Sampling Towards Fast Graph Representation Learning
• A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications
• Accurate, Efficient and Scalable Graph Embedding
• Graph Star Net for Generalized Multi-Task Learning
• Just Jump: Dynamic Neighborhood Aggregation in Graph Neural Networks

Cited by in corpus (60)

• Graph Convolutional Networks for Hyperspectral Image Classification
• Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning
• SumGNN: Multi-typed Drug Interaction Prediction via Efficient Knowledge Graph Summarization
• SIGN: Scalable Inception Graph Neural Networks
• Differentiable Graph Module (DGM) for Graph Convolutional Networks
• Graph Attention Multi-Layer Perceptron
• Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification
• Unnoticeable Backdoor Attacks on Graph Neural Networks
• The Evolution of Distributed Systems for Graph Neural Networks and their Origin in Graph Processing and Deep Learning: A Survey
• RoSGAS: Adaptive Social Bot Detection with Reinforced Self-Supervised GNN Architecture Search
• DropMessage: Unifying Random Dropping for Graph Neural Networks
• Label Information Enhanced Fraud Detection against Low Homophily in Graphs
• Scalable Graph Neural Network Training: The Case for Sampling
• Approximate Graph Propagation
• PaSca: a Graph Neural Architecture Search System under the Scalable Paradigm
• Learning Strong Graph Neural Networks with Weak Information
• Model Degradation Hinders Deep Graph Neural Networks
• How Attentive are Graph Attention Networks?
• HP-GNN: Generating High Throughput GNN Training Implementation on CPU-FPGA Heterogeneous Platform
• Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networks
• Designing the Topology of Graph Neural Networks: A Novel Feature Fusion Perspective
• Scalable Graph Neural Networks for Heterogeneous Graphs
• Lifelong Learning of Graph Neural Networks for Open-World Node Classification
• Sub-graph Contrast for Scalable Self-Supervised Graph Representation Learning
• ROD: Reception-aware Online Distillation for Sparse Graphs
• gIM: GPU Accelerated RIS-based Influence Maximization Algorithm
• Structure-Aware DropEdge Towards Deep Graph Convolutional Networks
• Scalable and Adaptive Graph Neural Networks with Self-Label-Enhanced training
• Geometer: Graph Few-Shot Class-Incremental Learning via Prototype Representation
• Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Networks
• A Network Science perspective of Graph Convolutional Networks: A survey
• Residual Network and Embedding Usage: New Tricks of Node Classification with Graph Convolutional Networks
• RPT: Toward Transferable Model on Heterogeneous Researcher Data via Pre-Training
• Large-scale graph representation learning with very deep GNNs and self-supervision
• Graph Coarsening with Neural Networks
• Ripple Walk Training: A Subgraph-based training framework for Large and Deep Graph Neural Network
• Optimizing Task Placement and Online Scheduling for Distributed GNN Training Acceleration
• Advancing Biomedicine with Graph Representation Learning: Recent Progress, Challenges, and Future Directions
• Clarify Confused Nodes via Separated Learning
• A pipeline for fair comparison of graph neural networks in node classification tasks
• Accelerating Backward Aggregation in GCN Training with Execution Path Preparing on GPUs
• Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks
• How effective are Graph Neural Networks in Fraud Detection for Network Data?
• PyTorch-Direct: Enabling GPU Centric Data Access for Very Large Graph Neural Network Training with Irregular Accesses
• MuG: A Multimodal Classification Benchmark on Game Data with Tabular, Textual, and Visual Fields
• Deep Generative Modeling in Network Science with Applications to Public Policy Research
• Structure-Aware Label Smoothing for Graph Neural Networks
• EWasteNet: A Two-Stream Data Efficient Image Transformer Approach for E-Waste Classification
• Analyzing the Performance of Graph Neural Networks with Pipe Parallelism
• Jointly Learnable Data Augmentations for Self-Supervised GNNs
• Global Neighbor Sampling for Mixed CPU-GPU Training on Giant Graphs
• Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal
• CompanyKG: A Large-Scale Heterogeneous Graph for Company Similarity Quantification
• SAS: A Simple, Accurate and Scalable Node Classification Algorithm
• Graph Feature Gating Networks
• Contributions to Representation Learning with Graph Autoencoders and Applications to Music Recommendation
• Hierarchical graph sampling based minibatch learning with chain preservation and variance reduction
• Data-Driven Self-Supervised Graph Representation Learning
• Non-Recursive Graph Convolutional Networks
• Sequential Aggregation and Rematerialization: Distributed Full-batch Training of Graph Neural Networks on Large Graphs