FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling

Abstract

The graph convolutional networks (GCN) recently proposed by Kipf and Welling are an effective graph model for semi-supervised learning. This model, however, was originally designed to be learned with the presence of both training and test data. Moreover, the recursive neighborhood expansion across layers poses time and memory challenges for training with large, dense graphs. To relax the requirement of simultaneous availability of test data, we interpret graph convolutions as integral transforms of embedding functions under probability measures. Such an interpretation allows for the use of Monte Carlo approaches to consistently estimate the integrals, which in turn leads to a batched training scheme as we propose in this work---FastGCN. Enhanced with importance sampling, FastGCN not only is efficient for training but also generalizes well for inference. We show a comprehensive set of experiments to demonstrate its effectiveness compared with GCN and related models. In particular, training is orders of magnitude more efficient while predictions remain comparably accurate.

ICLR 2018

References in corpus (6)

• Inductive Representation Learning on Large Graphs
• Spectral Networks and Locally Connected Networks on Graphs
• Graph Embedding Techniques, Applications, and Performance: A Survey
• Deep Convolutional Networks on Graph-Structured Data
• Variational Graph Auto-Encoders
• Learning Convolutional Neural Networks for Graphs

Cited by in corpus (133)

• Graph Neural Networks: A Review of Methods and Applications
• Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks
• Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks
• Enhancing Graph Neural Network-based Fraud Detectors against Camouflaged Fraudsters
• Scaling Graph Neural Networks with Approximate PageRank
• A Gentle Introduction to Deep Learning for Graphs
• Graph-Based Deep Learning for Medical Diagnosis and Analysis: Past, Present and Future
• DeeperGCN: All You Need to Train Deeper GCNs
• GaAN: Gated Attention Networks for Learning on Large and Spatiotemporal Graphs
• ETA Prediction with Graph Neural Networks in Google Maps
• LanczosNet: Multi-Scale Deep Graph Convolutional Networks
• Graph2Seq: Graph to Sequence Learning with Attention-based Neural Networks
• OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs
• HATS: A Hierarchical Graph Attention Network for Stock Movement Prediction
• Geom-GCN: Geometric Graph Convolutional Networks
• A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability
• GC-LSTM: Graph Convolution Embedded LSTM for Dynamic Link Prediction
• K-Core based Temporal Graph Convolutional Network for Dynamic Graphs
• Residual Correlation in Graph Neural Network Regression
• Scalable Graph Learning for Anti-Money Laundering: A First Look
• The Evolution of Distributed Systems for Graph Neural Networks and their Origin in Graph Processing and Deep Learning: A Survey
• DropMessage: Unifying Random Dropping for Graph Neural Networks
• Graph Convolutional Networks for Text Classification
• Accelerating Large Scale Real-Time GNN Inference using Channel Pruning
• Revisiting Over-smoothing in Deep GCNs
• Scalable Graph Neural Networks via Bidirectional Propagation
• Graph Convolutional Neural Networks with Node Transition Probability-based Message Passing and DropNode Regularization
• Graph Representation Learning via Graphical Mutual Information Maximization
• Graph-less Neural Networks: Teaching Old MLPs New Tricks via Distillation
• AEGCN: An Autoencoder-Constrained Graph Convolutional Network
• Self-supervised Auxiliary Learning with Meta-paths for Heterogeneous Graphs
• Dynamic Graph Convolutional Networks Using the Tensor M-Product
• Heterogeneous Graph Transformer
• Bag of Tricks for Node Classification with Graph Neural Networks
• GraphCL: Contrastive Self-Supervised Learning of Graph Representations
• Understanding Negative Sampling in Graph Representation Learning
• Bayesian graph convolutional neural networks via tempered MCMC
• Break the Ceiling: Stronger Multi-scale Deep Graph Convolutional Networks
• Sub-graph Contrast for Scalable Self-Supervised Graph Representation Learning
• ROD: Reception-aware Online Distillation for Sparse Graphs
• Graph Random Neural Network for Semi-Supervised Learning on Graphs
• GraphDefense: Towards Robust Graph Convolutional Networks
• Scalable and Adaptive Graph Neural Networks with Self-Label-Enhanced training
• Residual or Gate? Towards Deeper Graph Neural Networks for Inductive Graph Representation Learning
• Zoom in to where it matters: a hierarchical graph based model for mammogram analysis
• Link Prediction via Graph Attention Network
• Bayesian Graph Neural Networks with Adaptive Connection Sampling
• Structure fusion based on graph convolutional networks for semi-supervised classification
• AliGraph: A Comprehensive Graph Neural Network Platform
• Learning to Drop: Robust Graph Neural Network via Topological Denoising
• Incomplete Graph Representation and Learning via Partial Graph Neural Networks
• Residual Network and Embedding Usage: New Tricks of Node Classification with Graph Convolutional Networks
• Large-scale graph representation learning with very deep GNNs and self-supervision
• A Probabilistic Framework for Location Inference from Social Media
• NODE-SELECT: A Graph Neural Network Based On A Selective Propagation Technique
• Ripple Walk Training: A Subgraph-based training framework for Large and Deep Graph Neural Network
• Learning Graph Normalization for Graph Neural Networks
• FedGL: Federated Graph Learning Framework with Global Self-Supervision
• Generative Graph Convolutional Network for Growing Graphs
• DyGCN: Dynamic Graph Embedding with Graph Convolutional Network
• Optimization of Graph Neural Networks with Natural Gradient Descent
• Self-supervised Graph Neural Networks without explicit negative sampling
• Graph Posterior Network: Bayesian Predictive Uncertainty for Node Classification
• Rubik: A Hierarchical Architecture for Efficient Graph Learning
• Lifelong Graph Learning
• L${}^2$-GCN: Layer-Wise and Learned Efficient Training of Graph Convolutional Networks
• Robot Navigation in Crowds by Graph Convolutional Networks with Attention Learned from Human Gaze
• Cascade-BGNN: Toward Efficient Self-supervised Representation Learning on Large-scale Bipartite Graphs
• Recognizing Predictive Substructures with Subgraph Information Bottleneck
• Training Matters: Unlocking Potentials of Deeper Graph Convolutional Neural Networks
• Graph Node-Feature Convolution for Representation Learning
• GNN-XML: Graph Neural Networks for Extreme Multi-label Text Classification
• Network In Graph Neural Network
• Label-GCN: An Effective Method for Adding Label Propagation to Graph Convolutional Networks
• GE-SpMM: General-purpose Sparse Matrix-Matrix Multiplication on GPUs for Graph Neural Networks
• GraphAttacker: A General Multi-Task GraphAttack Framework
• Fusion Graph Convolutional Networks
• Heterogeneous Graph Matching Networks
• GraphTheta: A Distributed Graph Neural Network Learning System With Flexible Training Strategy
• Learning to Cluster Faces via Confidence and Connectivity Estimation
• Equivariant Entity-Relationship Networks
• Integrating Network Embedding and Community Outlier Detection via Multiclass Graph Description
• Spectral Graph Attention Network with Fast Eigen-approximation
• JITuNE: Just-In-Time Hyperparameter Tuning for Network Embedding Algorithms
• Learning on heterogeneous graphs using high-order relations
• Scalable Attack on Graph Data by Injecting Vicious Nodes
• Learning by Sampling and Compressing: Efficient Graph Representation Learning with Extremely Limited Annotations
• CommPOOL: An Interpretable Graph Pooling Framework for Hierarchical Graph Representation Learning
• FedGraph: Federated Graph Learning with Intelligent Sampling
• A Biased Graph Neural Network Sampler with Near-Optimal Regret
• Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks
• An End-to-End Neighborhood-based Interaction Model for Knowledge-enhanced Recommendation
• Learning Hierarchical Graph Neural Networks for Image Clustering
• BiGCN: A Bi-directional Low-Pass Filtering Graph Neural Network
• Stacked Graph Filter
• Tackling the Local Bias in Federated Graph Learning
• Recurrent Attention Walk for Semi-supervised Classification
• Graph Neural Networks with Composite Kernels
• Attentional Graph Convolutional Networks for Knowledge Concept Recommendation in MOOCs in a Heterogeneous View
• ImVerde: Vertex-Diminished Random Walk for Learning Network Representation from Imbalanced Data
• Skeleton-based Hand-Gesture Recognition with Lightweight Graph Convolutional Networks
• Gaussian Process Inference Using Mini-batch Stochastic Gradient Descent: Convergence Guarantees and Empirical Benefits
• Lorentzian Graph Convolutional Networks
• Jointly Learnable Data Augmentations for Self-Supervised GNNs
• Feature Correlation Aggregation: on the Path to Better Graph Neural Networks
• Simplification of Graph Convolutional Networks: A Matrix Factorization-based Perspective
• Learning Robust Representations with Graph Denoising Policy Network
• Attribute2vec: Deep Network Embedding Through Multi-Filtering GCN
• ConvDySAT: Deep Neural Representation Learning on Dynamic Graphs via Self-Attention and Convolutional Neural Networks
• A Context Integrated Relational Spatio-Temporal Model for Demand and Supply Forecasting
• Sequential Aggregation and Rematerialization: Distributed Full-batch Training of Graph Neural Networks on Large Graphs
• LSP : Acceleration and Regularization of Graph Neural Networks via Locality Sensitive Pruning of Graphs
• Learn to Propagate Reliably on Noisy Affinity Graphs
• SAS: A Simple, Accurate and Scalable Node Classification Algorithm
• Decoupled Variational Embedding for Signed Directed Networks
• Fully Linear Graph Convolutional Networks for Semi-Supervised Learning and Clustering
• LFGCN: Levitating over Graphs with Levy Flights
• Temporal Graph Offset Reconstruction: Towards Temporally Robust Graph Representation Learning
• Network representation learning: A macro and micro view
• geoGAT: Graph Model Based on Attention Mechanism for Geographic Text Classification
• Action Recognition with Kernel-based Graph Convolutional Networks
• A Variance Controlled Stochastic Method with Biased Estimation for Faster Non-convex Optimization
• MG-DVD: A Real-time Framework for Malware Variant Detection Based on Dynamic Heterogeneous Graph Learning
• Network Representation Learning: From Traditional Feature Learning to Deep Learning
• Partitioned Graph Convolution Using Adversarial and Regression Networks for Road Travel Speed Prediction
• Training Graph Neural Networks by Graphon Estimation
• A Semi-Personalized System for User Cold Start Recommendation on Music Streaming Apps
• Lovasz Convolutional Networks
• On the Global Self-attention Mechanism for Graph Convolutional Networks
• DNA-GCN: Graph convolutional networks for predicting DNA-protein binding
• Tracing the Propagation Path: A Flow Perspective of Representation Learning on Graphs
• Learning Chebyshev Basis in Graph Convolutional Networks for Skeleton-based Action Recognition
• Label-Aware Graph Convolutional Networks