Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks

Abstract

Graph convolutional network (GCN) has been successfully applied to many graph-based applications; however, training a large-scale GCN remains challenging. Current SGD-based algorithms suffer from either a high computational cost that exponentially grows with number of GCN layers, or a large space requirement for keeping the entire graph and the embedding of each node in memory. In this paper, we propose Cluster-GCN, a novel GCN algorithm that is suitable for SGD-based training by exploiting the graph clustering structure. Cluster-GCN works as the following: at each step, it samples a block of nodes that associate with a dense subgraph identified by a graph clustering algorithm, and restricts the neighborhood search within this subgraph. This simple but effective strategy leads to significantly improved memory and computational efficiency while being able to achieve comparable test accuracy with previous algorithms. To test the scalability of our algorithm, we create a new Amazon2M data with 2 million nodes and 61 million edges which is more than 5 times larger than the previous largest publicly available dataset (Reddit). For training a 3-layer GCN on this data, Cluster-GCN is faster than the previous state-of-the-art VR-GCN (1523 seconds vs 1961 seconds) and using much less memory (2.2GB vs 11.2GB). Furthermore, for training 4 layer GCN on this data, our algorithm can finish in around 36 minutes while all the existing GCN training algorithms fail to train due to the out-of-memory issue. Furthermore, Cluster-GCN allows us to train much deeper GCN without much time and memory overhead, which leads to improved prediction accuracy---using a 5-layer Cluster-GCN, we achieve state-of-the-art test F1 score 99.36 on the PPI dataset, while the previous best result was 98.71 by [16]. Our codes are publicly available at https://github.com/google-research/google-research/tree/master/cluster_gcn.

In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD'19)

References in corpus (5)

• Semi-Supervised Classification with Graph Convolutional Networks
• Inductive Representation Learning on Large Graphs
• Graph Convolutional Neural Networks for Web-Scale Recommender Systems
• FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling
• Link Prediction Based on Graph Neural Networks

Cited by in corpus (176)

• A Comprehensive Survey on Graph Neural Networks
• Graph Neural Networks: A Review of Methods and Applications
• Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks
• Open Graph Benchmark: Datasets for Machine Learning on Graphs
• Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning
• Scaling Graph Neural Networks with Approximate PageRank
• GraphSAINT: Graph Sampling Based Inductive Learning Method
• Graph Representation Learning in Biomedicine
• Graph-Based Deep Learning for Medical Diagnosis and Analysis: Past, Present and Future
• Benchmarking Graph Neural Networks
• DeepGCNs: Making GCNs Go as Deep as CNNs
• SumGNN: Multi-typed Drug Interaction Prediction via Efficient Knowledge Graph Summarization
• SIGN: Scalable Inception Graph Neural Networks
• Graph Neural Networks: Taxonomy, Advances and Trends
• ConsisRec: Enhancing GNN for Social Recommendation via Consistent Neighbor Aggregation
• Rapid protein assignments and structures from raw NMR spectra with the deep learning technique ARTINA
• A Survey on Graph-Based Deep Learning for Computational Histopathology
• Graph Unlearning
• Differentiable Graph Module (DGM) for Graph Convolutional Networks
• OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs
• Graph Convolutional Networks for Graphs Containing Missing Features
• Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks
• Graph Attention Multi-Layer Perceptron
• Trustworthy Graph Neural Networks: Aspects, Methods and Trends
• Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification
• Machine Learning on Graphs: A Model and Comprehensive Taxonomy
• K-Core based Temporal Graph Convolutional Network for Dynamic Graphs
• Spatial-Temporal Fusion Graph Neural Networks for Traffic Flow Forecasting
• The Evolution of Distributed Systems for Graph Neural Networks and their Origin in Graph Processing and Deep Learning: A Survey
• Tackling Over-Smoothing for General Graph Convolutional Networks
• TIMME: Twitter Ideology-detection via Multi-task Multi-relational Embedding
• HET: Scaling out Huge Embedding Model Training via Cache-enabled Distributed Framework
• Bi-GCN: Binary Graph Convolutional Network
• Revisiting Over-smoothing in Deep GCNs
• Scalable Graph Neural Networks via Bidirectional Propagation
• Domain Adversarial Graph Convolutional Network Based on RSSI and Crowdsensing for Indoor Localization
• C-SAW: A Framework for Graph Sampling and Random Walk on GPUs
• Label Information Enhanced Fraud Detection against Low Homophily in Graphs
• Scalable Graph Neural Network Training: The Case for Sampling
• Topology-Imbalance Learning for Semi-Supervised Node Classification
• PaSca: a Graph Neural Architecture Search System under the Scalable Paradigm
• Approximate Graph Propagation
• Subgraph Neural Networks
• Learning Strong Graph Neural Networks with Weak Information
• ClusterEA: Scalable Entity Alignment with Stochastic Training and Normalized Mini-batch Similarities
• HP-GNN: Generating High Throughput GNN Training Implementation on CPU-FPGA Heterogeneous Platform
• Grain: Improving Data Efficiency of Graph Neural Networks via Diversified Influence Maximization
• Graph-based Modeling of Online Communities for Fake News Detection
• Differentially Private Graph Classification with GNNs
• GraphFL: A Federated Learning Framework for Semi-Supervised Node Classification on Graphs
• Knowing your FATE: Friendship, Action and Temporal Explanations for User Engagement Prediction on Social Apps
• Deep learning for dynamic graphs: models and benchmarks
• CatGCN: Graph Convolutional Networks with Categorical Node Features
• FreeKD: Free-direction Knowledge Distillation for Graph Neural Networks
• Algorithm and System Co-design for Efficient Subgraph-based Graph Representation Learning
• Graph Deep Learning for Time Series Forecasting
• Accelerating Sampling and Aggregation Operations in GNN Frameworks with GPU Initiated Direct Storage Accesses
• Scalable Graph Neural Networks for Heterogeneous Graphs
• Graph Neural Networks for Knowledge Enhanced Visual Representation of Paintings
• Lifelong Learning of Graph Neural Networks for Open-World Node Classification
• Large-scale Entity Alignment via Knowledge Graph Merging, Partitioning and Embedding
• Coupled Layer-wise Graph Convolution for Transportation Demand Prediction
• ROD: Reception-aware Online Distillation for Sparse Graphs
• Accelerating Training and Inference of Graph Neural Networks with Fast Sampling and Pipelining
• Reinforced Neighborhood Selection Guided Multi-Relational Graph Neural Networks
• Scalable and Adaptive Graph Neural Networks with Self-Label-Enhanced training
• A Network Science perspective of Graph Convolutional Networks: A survey
• SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization
• PDE-GCN: Novel Architectures for Graph Neural Networks Motivated by Partial Differential Equations
• Topology-aware Embedding Memory for Continual Learning on Expanding Networks
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution
• Joint Item Recommendation and Attribute Inference: An Adaptive Graph Convolutional Network Approach
• Unsupervised Graph Outlier Detection: Problem Revisit, New Insight, and Superior Method
• Residual Network and Embedding Usage: New Tricks of Node Classification with Graph Convolutional Networks
• Pre-Training and Prompting for Few-Shot Node Classification on Text-Attributed Graphs
• Large-scale graph representation learning with very deep GNNs and self-supervision
• Node Dependent Local Smoothing for Scalable Graph Learning
• Say No to the Discrimination: Learning Fair Graph Neural Networks with Limited Sensitive Attribute Information
• Sampling methods for efficient training of graph convolutional networks: A survey
• Model Extraction Attacks on Graph Neural Networks: Taxonomy and Realization
• Equivariant Subgraph Aggregation Networks
• How the Galaxy-Halo Connection Depends on Large-Scale Environment
• SCG-Net: Self-Constructing Graph Neural Networks for Semantic Segmentation
• Optimizing Task Placement and Online Scheduling for Distributed GNN Training Acceleration
• Ripple Walk Training: A Subgraph-based training framework for Large and Deep Graph Neural Network
• Graph Meta Learning via Local Subgraphs
• VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization
• Advancing Biomedicine with Graph Representation Learning: Recent Progress, Challenges, and Future Directions
• FedGL: Federated Graph Learning Framework with Global Self-Supervision
• Lifelong Graph Learning
• Graph-Skeleton: ~1% Nodes are Sufficient to Represent Billion-Scale Graph
• You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks
• A Review of Graph-Powered Data Quality Applications for IoT Monitoring Sensor Networks
• Rubik: A Hierarchical Architecture for Efficient Graph Learning
• i-Align: an interpretable knowledge graph alignment model
• Identifying Autism Spectrum Disorder Based on Individual-Aware Down-Sampling and Multi-Modal Learning
• Graph Neural Pre-training for Enhancing Recommendations using Side Information
• Self-Enhanced GNN: Improving Graph Neural Networks Using Model Outputs
• CARL-G: Clustering-Accelerated Representation Learning on Graphs
• Constant Time Graph Neural Networks
• L${}^2$-GCN: Layer-Wise and Learned Efficient Training of Graph Convolutional Networks
• Auto-STGCN: Autonomous Spatial-Temporal Graph Convolutional Network Search Based on Reinforcement Learning and Existing Research Results
• Network In Graph Neural Network
• Hierarchical Message-Passing Graph Neural Networks
• Mask-GVAE: Blind Denoising Graphs via Partition
• FastGL: A GPU-Efficient Framework for Accelerating Sampling-Based GNN Training at Large Scale
• Self-supervised edge features for improved Graph Neural Network training
• Node Masking: Making Graph Neural Networks Generalize and Scale Better
• Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction
• Semi-supervised Hyperspectral Image Classification with Graph Clustering Convolutional Networks
• Distributed Training of Graph Convolutional Networks using Subgraph Approximation
• Communication-Efficient Sampling for Distributed Training of Graph Convolutional Networks
• GMLP: Building Scalable and Flexible Graph Neural Networks with Feature-Message Passing
• SMASH: Sparse Matrix Atomic Scratchpad Hashing
• Spatiotemporal Tile-based Attention-guided LSTMs for Traffic Video Prediction
• Accelerating SpMM Kernel with Cache-First Edge Sampling for Graph Neural Networks
• GraphTheta: A Distributed Graph Neural Network Learning System With Flexible Training Strategy
• Adaptive Graph Auto-Encoder for General Data Clustering
• Recognizing Unseen Objects via Multimodal Intensive Knowledge Graph Propagation
• A pipeline for fair comparison of graph neural networks in node classification tasks
• Fast and Effective GNN Training through Sequences of Random Path Graphs
• A Versatile Framework for Attributed Network Clustering via K-Nearest Neighbor Augmentation
• RegionGCN: Spatial-Heterogeneity-Aware Graph Convolutional Networks
• Graph Coordinates and Conventional Neural Networks -- An Alternative for Graph Neural Networks
• Are Negative Samples Necessary in Entity Alignment? An Approach with High Performance, Scalability and Robustness
• Adversarial Attack on Large Scale Graph
• Isometric Transformation Invariant and Equivariant Graph Convolutional Networks
• BlockGNN: Towards Efficient GNN Acceleration Using Block-Circulant Weight Matrices
• CAP: Co-Adversarial Perturbation on Weights and Features for Improving Generalization of Graph Neural Networks
• D3-GNN: Dynamic Distributed Dataflow for Streaming Graph Neural Networks
• Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks
• Implicit SVD for Graph Representation Learning
• Finding Counterfactual Evidences for Node Classification
• Meta-path Free Semi-supervised Learning for Heterogeneous Networks
• A Biased Graph Neural Network Sampler with Near-Optimal Regret
• A Comparative Study of Using Spatial-Temporal Graph Convolutional Networks for Predicting Availability in Bike Sharing Schemes
• Structure-Aware Label Smoothing for Graph Neural Networks
• Scaling Large-scale GNN Training to Thousands of Processors on CPU-based Supercomputers
• Tackling the Local Bias in Federated Graph Learning
• LG4AV: Combining Language Models and Graph Neural Networks for Author Verification
• GNNSampler: Bridging the Gap between Sampling Algorithms of GNN and Hardware
• Edgeless-GNN: Unsupervised Representation Learning for Edgeless Nodes
• Local2Global: Scaling global representation learning on graphs via local training
• Distributed Optimization of Graph Convolutional Network using Subgraph Variance
• MG-GCN: Fast and Effective Learning with Mix-grained Aggregators for Training Large Graph Convolutional Networks
• Semi-Supervised Node Classification on Graphs: Markov Random Fields vs. Graph Neural Networks
• Graph Traversal with Tensor Functionals: A Meta-Algorithm for Scalable Learning
• Hop Sampling: A Simple Regularized Graph Learning for Non-Stationary Environments
• Analyzing the Performance of Graph Neural Networks with Pipe Parallelism
• Simplification of Graph Convolutional Networks: A Matrix Factorization-based Perspective
• Mixture-of-Partitions: Infusing Large Biomedical Knowledge Graphs into BERT
• FLASH: Fast Neural Architecture Search with Hardware Optimization
• On the Importance of Sampling in Training GCNs: Tighter Analysis and Variance Reduction
• Deep Neural Network for 3D Surface Segmentation based on Contour Tree Hierarchy
• LW-GCN: A Lightweight FPGA-based Graph Convolutional Network Accelerator
• GAIN: Graph Attention & Interaction Network for Inductive Semi-Supervised Learning over Large-scale Graphs
• Inductive Subgraph Embedding for Link Prediction
• CompanyKG: A Large-Scale Heterogeneous Graph for Company Similarity Quantification
• Accelerating Graph Sampling for Graph Machine Learning using GPUs
• Scaling Up Graph Neural Networks Via Graph Coarsening
• Partitioned Graph Convolution Using Adversarial and Regression Networks for Road Travel Speed Prediction
• Structure-Aware Face Clustering on a Large-Scale Graph with $10^7$ Nodes
• SAS: A Simple, Accurate and Scalable Node Classification Algorithm
• An Uncoupled Training Architecture for Large Graph Learning
• Urban Traffic Flow Forecast Based on FastGCRNN
• Bidirectional group random walk based network embedding for asymmetric proximity
• Non-Recursive Graph Convolutional Networks
• Toward Efficient Testing of Graph Neural Networks via Test Input Prioritization
• Graph Embedding with Hierarchical Attentive Membership
• Link prediction on multi-relational graphs from an influence propagation perspective
• IGLU: Efficient GCN Training via Lazy Updates
• Towards Self-Explainable Graph Neural Network
• SPAN: Subgraph Prediction Attention Network for Dynamic Graphs
• How much progress have we made in neural network training? A New Evaluation Protocol for Benchmarking Optimizers
• Graph-based Active Learning for Entity Cluster Repair
• HyperGraphX: Graph Transductive Learning with Hyperdimensional Computing and Message Passing