Adaptive Sampling Towards Fast Graph Representation Learning

Abstract

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.

Cited by in corpus (89)

• Graph Neural Networks: A Review of Methods and Applications
• GNNExplainer: Generating Explanations for Graph Neural Networks
• DropEdge: Towards Deep Graph Convolutional Networks on Node Classification
• Scaling Graph Neural Networks with Approximate PageRank
• GraphSAINT: Graph Sampling Based Inductive Learning Method
• SIGN: Scalable Inception Graph Neural Networks
• Deep Learning on Graphs: A Survey
• Graph Neural Networks: Taxonomy, Advances and Trends
• Differentiable Graph Module (DGM) for Graph Convolutional Networks
• Graph Attention Multi-Layer Perceptron
• Relational Fusion Networks: Graph Convolutional Networks for Road Networks
• Heterogeneous Deep Graph Infomax
• Tackling Over-Smoothing for General Graph Convolutional Networks
• Graph Convolutional Networks for Temporal Action Localization
• Scalable Graph Neural Network Training: The Case for Sampling
• Multi-View Graph Neural Networks for Molecular Property Prediction
• Adversarial Attack Framework on Graph Embedding Models with Limited Knowledge
• Lifelong Learning of Graph Neural Networks for Open-World Node Classification
• Beyond Low-Pass Filters: Adaptive Feature Propagation on Graphs
• Improving Graph Attention Networks with Large Margin-based Constraints
• Graph Random Neural Network for Semi-Supervised Learning on Graphs
• DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs
• Lifelong Learning on Evolving Graphs Under the Constraints of Imbalanced Classes and New Classes
• Distilling Knowledge from Graph Convolutional Networks
• Geometer: Graph Few-Shot Class-Incremental Learning via Prototype Representation
• Scalable and Adaptive Graph Neural Networks with Self-Label-Enhanced training
• Learning to Drop: Robust Graph Neural Network via Topological Denoising
• Sampling methods for efficient training of graph convolutional networks: A survey
• Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification
• Node Dependent Local Smoothing for Scalable Graph Learning
• Deep Graph Neural Networks with Shallow Subgraph Samplers
• SCG-Net: Self-Constructing Graph Neural Networks for Semantic Segmentation
• Training Robust Graph Neural Networks with Topology Adaptive Edge Dropping
• Ripple Walk Training: A Subgraph-based training framework for Large and Deep Graph Neural Network
• Accurate, Efficient and Scalable Training of Graph Neural Networks
• VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization
• Lifelong Graph Learning
• Rubik: A Hierarchical Architecture for Efficient Graph Learning
• Relation Matters in Sampling: A Scalable Multi-Relational Graph Neural Network for Drug-Drug Interaction Prediction
• Cascade-BGNN: Toward Efficient Self-supervised Representation Learning on Large-scale Bipartite Graphs
• Constant Time Graph Neural Networks
• Convolutional Geometric Matrix Completion
• A comparative study of similarity-based and GNN-based link prediction approaches
• Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art
• GCN-SL: Graph Convolutional Networks with Structure Learning for Graphs under Heterophily
• GraphTheta: A Distributed Graph Neural Network Learning System With Flexible Training Strategy
• Policy-GNN: Aggregation Optimization for Graph Neural Networks
• Accelerating SpMM Kernel with Cache-First Edge Sampling for Graph Neural Networks
• Communication-Efficient Sampling for Distributed Training of Graph Convolutional Networks
• Pre-Training Graph Neural Networks for Cold-Start Users and Items Representation
• Unsupervised Adversarial Graph Alignment with Graph Embedding
• Spectral Graph Attention Network with Fast Eigen-approximation
• Graph Cross Networks with Vertex Infomax Pooling
• Equivariant Entity-Relationship Networks
• Sampling and Recovery of Graph Signals based on Graph Neural Networks
• Dimensional Reweighting Graph Convolutional Networks
• CommPOOL: An Interpretable Graph Pooling Framework for Hierarchical Graph Representation Learning
• HyGCN: A GCN Accelerator with Hybrid Architecture
• A Biased Graph Neural Network Sampler with Near-Optimal Regret
• GCN-LASE: Towards Adequately Incorporating Link Attributes in Graph Convolutional Networks
• On Self-Distilling Graph Neural Network
• GNNSampler: Bridging the Gap between Sampling Algorithms of GNN and Hardware
• Skeleton-based Hand-Gesture Recognition with Lightweight Graph Convolutional Networks
• LEReg: Empower Graph Neural Networks with Local Energy Regularization
• Cross-Node Federated Graph Neural Network for Spatio-Temporal Data Modeling
• Explicit Pairwise Factorized Graph Neural Network for Semi-Supervised Node Classification
• Distributed Optimization of Graph Convolutional Network using Subgraph Variance
• Tackling Graphical NLP problems with Graph Recurrent Networks
• MG-GCN: Fast and Effective Learning with Mix-grained Aggregators for Training Large Graph Convolutional Networks
• Hop Sampling: A Simple Regularized Graph Learning for Non-Stationary Environments
• Feature Correlation Aggregation: on the Path to Better Graph Neural Networks
• Contrastive Adaptive Propagation Graph Neural Networks for Efficient Graph Learning
• GIPA: A General Information Propagation Algorithm for Graph Learning
• Single-Layer Graph Convolutional Networks For Recommendation
• On the Importance of Sampling in Training GCNs: Tighter Analysis and Variance Reduction
• Learning Robust Representations with Graph Denoising Policy Network
• Which Samples Should be Learned First: Easy or Hard?
• BGADAM: Boosting based Genetic-Evolutionary ADAM for Neural Network Optimization
• Label-Aware Graph Convolutional Networks
• Non-Recursive Graph Convolutional Networks
• Network representation learning: A macro and micro view
• A Consistent Diffusion-Based Algorithm for Semi-Supervised Classification on Graphs
• AN-GCN: An Anonymous Graph Convolutional Network Defense Against Edge-Perturbing Attack
• Learning Chebyshev Basis in Graph Convolutional Networks for Skeleton-based Action Recognition
• Tracing the Propagation Path: A Flow Perspective of Representation Learning on Graphs
• Action Recognition with Kernel-based Graph Convolutional Networks
• Spectral Transform Forms Scalable Transformer
• Graph Convolutional Module for Temporal Action Localization in Videos
• IGLU: Efficient GCN Training via Lazy Updates