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

By Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, Cho-Jui Hsieh. 2019

1,573 citations recorded by the source corpus.

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~\citezhang2018gaan.

Subfields: Artificial Intelligence, Computer Networks and Communications, Information Systems, Graph Learning, Efficiency & Compression

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

In Computer Networks and Communications

In Information Systems

In Graph Learning

In Efficiency & Compression

Citations in the corpus

Auto-GNN: Neural architecture search of graph neural networks (2019, background): “, 2017), Cluster-GCN (Chiang et al., 2019), and GraphSAINT (Zeng et al.”
Isometric Transformation Invariant and Equivariant Graph Convolutional Networks (2020, neutral): “, 2019), Cluster-GCN (Chiang et al., 2019), and GCNII (Chen et al.”
Lifelong Graph Learning (2020, neutral): “[8] sampled a block of nodes in a dense sub-graph identified by a clustering algorithm and restricted the neighborhood search within the subgraph.”
ELLA-V: Stable Neural Codec Language Modeling with Alignment-guided Sequence Reordering (2024, background): “Recently, deep generative AI has achieved remarkable results in various tasks, leading to the emergence of many transformative real-world applications (Brown et al., 2020; Ramesh et al., 2022; Ho et al., 2020; Rombach et al., 2022; Borsos et al., 2023; Kim et al., 2021; Chiang et al., 2019).”
A Comprehensive Survey on Graph Neural Networks (2019, methodology): “Complexity GCN [22] GraphSage [42] FastGCN [49] StoGCN [50] Cluster-GCN [58]”
Simple and Deep Graph Convolutional Networks (2020, methodology): “Following the setting in (Pei et al., 2020), we use 7 datasets: Cora, Citeseer, Pubmed, Chameleon, Method PPI GraphSAGE (Hamilton et al., 2017) 61.2 VR-GCN (Chen et al., 2018b) 97.8 GaAN (Zhang et al., 2018) 98.71 GAT (Veliˇckovi´c et al., 2018) 97.3 JKNet (Xu et al., 2018) 97.6 GeniePath (Liu et al”
Benchmarking Graph Neural Networks (2023, background): “[19] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh.”
Open Graph Benchmark: Datasets for Machine Learning on Graphs (2020, methodology): “• CLUSTERGCN (optional): A mini-batch training technique of GNNs (Chiang et al., 2019) that partitions the graphs into a fixed number of subgraphs and draws mini-batches from them.”
Spatial-Temporal Fusion Graph Neural Networks for Traffic Flow Forecasting (2020, background): “Graph convolution networks are widely applied in many graph-based tasks such as classification (Kipf and Welling 2016) and clustering (Chiang et al. 2019), which has two types.”
The Klarna Product Page Dataset: A Realistic Benchmark for Web Representation Learning (2021, background): “GCNs have shown notable performance on social network graphs [39, 6, 5], citation networks [43, 9], and biochemical graphs [6, 39, 24].”
Bandit Samplers for Training Graph Neural Networks (2020, methodology): “(4) ClusterGCN [7] and GraphSAINT [22] are “graph sampling” techniques that first partition or sample the graph into small subgraphs, then train each subgraph using the batch algorithm [13].”
Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks (2019, background): “Cluster-GCN [5] considers restricting the sampled neighbors within some dense subgraphs, which are identified by a graph clustering algorithm before the training of GCN.”
Graph Representation Learning in Biomedicine and Healthcare (2021, neutral): “81,82 developed sampling strategies to intelligently select small subsets of the whole local network neighbourhoods, and used them to train GNN models.”
A Survey of Graph Neural Networks for Recommender Systems: Challenges, Methods, and Directions (2021, methodology): “The sampling strategy is also adopted in a few other works [22, 29], which reduces the computation complexity of GNN and improves the scalability.”
Say No to the Discrimination: Learning Fair Graph Neural Networks with Limited Sensitive Attribute Information (2020, methodology): “red data, have shown great success for various applications [2, 18, 26, 47, 50, 51]. Generally, GNNs can be categorized into two categories, i.e., spectral-based [5, 10, 21, 26, 27] and spatial-based [7, 8, 19, 45, 51]. Spectral-based GNNs define graph convolution based on spectral graph theory, whi”
OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs (2021, background): “Effectively training these models at scale requires sophisticated algorithms that are well beyond standard SGD over i.i.d. data (Hamilton et al., 2017; Chen et al., 2018; Chiang et al., 2019; Zeng et al., 2020).”