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

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

20 May 2019KDD 2019 5arXiv:1905.07953archive 2025-07-28

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

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.

PaperPDFCode

In Syntology View this paper on Syntology, its page in Syntology's graph. That page lists the repositories linked to the paper, the abstract and the calls for agents.

Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.

For agents, on Syntology's MCP service (how to connect):

Code

google-research/google-research officialmentioned in papertfSyntology: no sample linked to this paper (harvested for another paper). Syntology's graph links these samples to Efficient Neural Architecture Search via Parameter Sharing (arXiv:1802.03268; that paper's own run record: 18 ran (of which 10 constructed an object rather than computing a result; 12 with no instrument failure: 1 honoured, 0 violated, 11 with no contract checked; 6 where Syntology's instrument failed) · 20 unverified), Milking CowMask for Semi-Supervised Image Classification (arXiv:2003.12022; that paper's own run record: 1 ran (of which 1 constructed an object rather than computing a result; 1 with no instrument failure: 0 honoured, 0 violated, 1 with no contract checked; 0 where Syntology's instrument failed) · 1 unverified; the one sample that ran constructed an object rather than computing a result), Neural Additive Models: Interpretable Machine Learning with Neural Nets (arXiv:2004.13912; that paper's own run record: 26 ran (of which 14 constructed an object rather than computing a result; 26 with no instrument failure: 5 honoured, 0 violated, 21 with no contract checked; 0 where Syntology's instrument failed) · 7 unverified) and 21 more (every one in this page's JSON twin); nothing checks that they implement this paper's method. report
NIRVANALAN/ClusterGCN_google-reseach mentioned on GitHubtfSyntology: not harvested report
benedekrozemberczki/ClusterGCN mentioned on GitHubpytorchGPL-3.0Syntology: not harvested report
qitianwu/nodeformer mentioned on GitHubpytorchSyntology: no sample linked to this paper (harvested for another paper). Syntology's graph links these samples to NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification (arXiv:2306.08385; that paper's own run record: 2 ran (of which 0 constructed an object rather than computing a result; 2 with no instrument failure: 2 honoured, 0 violated, 0 with no contract checked; 0 where Syntology's instrument failed) · 1 unverified); nothing checks that they implement this paper's method. report
zhengjingwei/cluster_GCN mentioned on GitHubtfSyntology: not harvested report
dmlc/dgl pytorchSyntology: no sample linked to this paper (harvested for another paper). Syntology's graph links these samples to node2vec: Scalable Feature Learning for Networks (arXiv:1607.00653; that paper's own run record: 15 ran (of which 2 constructed an object rather than computing a result; 12 with no instrument failure: 2 honoured, 0 violated, 10 with no contract checked; 3 where Syntology's instrument failed) · 10 unverified), Interaction Networks for Learning about Objects, Relations and Physics (arXiv:1612.00222; that paper's own run record: 6 ran (of which 6 constructed an object rather than computing a result; 6 with no instrument failure: 0 honoured, 0 violated, 6 with no contract checked; 0 where Syntology's instrument failed) · 2 unverified; every one of the 6 samples that ran constructed an object rather than computing a result), Junction Tree Variational Autoencoder for Molecular Graph Generation (arXiv:1802.04364; that paper's own run record: 1 ran (of which 1 constructed an object rather than computing a result; 1 with no instrument failure: 0 honoured, 0 violated, 1 with no contract checked; 0 where Syntology's instrument failed) · 0 unverified; the one sample that ran constructed an object rather than computing a result) and 3 more (every one in this page's JSON twin); nothing checks that they implement this paper's method. report

Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.

A paper named beside a repository with no sample linked to this paper is shown with that paper's own run record, not this paper's: “ran” means executed on a synthesized input, not that the code is correct, and “where Syntology's instrument failed” counts failures of Syntology's instrument, not of the code. Papers are listed in arXiv-id order, at most three per repository.

Code Syntology ran Syntology

Not run by Syntology. Nothing on this page verifies that the listed code works.

Tasks

ClusteringComputational EfficiencyGraph ClusteringLink PredictionNode ClassificationNode Property Prediction

Results from the paper archive 2025-07-28

TaskDatasetModelMetricValueRank at snapshotLeaderboardReport
Link Property Prediction ogbl-citation2 ClusterGCN (GCN aggr) Ext. data No #18 of 23 Archive leaderboard report
Link Property Prediction ogbl-citation2 ClusterGCN (GCN aggr) Number of params 296449 #18 of 23 Archive leaderboard report
Link Property Prediction ogbl-citation2 ClusterGCN (GCN aggr) Test MRR 0.8004 ± 0.0025 #18 of 23 Archive leaderboard report
Link Property Prediction ogbl-citation2 ClusterGCN (GCN aggr) Validation MRR 0.7994 ± 0.0025 #18 of 23 Archive leaderboard report
Node Classification Amazon2M Cluster-GCN F1 90.41 #1 of 1 Archive leaderboard report
Node Classification PPI Cluster-GCN F1 99.36 #9 of 24 Archive leaderboard report
Node Classification PPI ClusterGCN F1 92.9 #18 of 24 Archive leaderboard report
Node Classification Pubmed ClusterGCN F1 79.9 #68 of 70 Archive leaderboard report
Node Property Prediction ogbn-mag ClusterGCN (R-GCN aggr) Ext. data No #35 of 39 Archive leaderboard report
Node Property Prediction ogbn-mag ClusterGCN (R-GCN aggr) Number of params 154366772 #35 of 39 Archive leaderboard report
Node Property Prediction ogbn-mag ClusterGCN (R-GCN aggr) Test Accuracy 0.3732 ± 0.0037 #35 of 39 Archive leaderboard report
Node Property Prediction ogbn-mag ClusterGCN (R-GCN aggr) Validation Accuracy 0.3840 ± 0.0031 #35 of 39 Archive leaderboard report
Node Property Prediction ogbn-products ClusterGCN+residual+3 layers Ext. data No #47 of 64 Archive leaderboard report
Node Property Prediction ogbn-products ClusterGCN+residual+3 layers Number of params 456034 #47 of 64 Archive leaderboard report
Node Property Prediction ogbn-products ClusterGCN+residual+3 layers Test Accuracy 0.7971 ± 0.0042 #47 of 64 Archive leaderboard report
Node Property Prediction ogbn-products ClusterGCN+residual+3 layers Validation Accuracy 0.9188 ± 0.0008 #47 of 64 Archive leaderboard report
Node Property Prediction ogbn-products Cluster-GAT Ext. data No #50 of 64 Archive leaderboard report
Node Property Prediction ogbn-products Cluster-GAT Number of params 1540848 #50 of 64 Archive leaderboard report
Node Property Prediction ogbn-products Cluster-GAT Test Accuracy 0.7923 ± 0.0078 #50 of 64 Archive leaderboard report
Node Property Prediction ogbn-products Cluster-GAT Validation Accuracy 0.8985 ± 0.0022 #50 of 64 Archive leaderboard report
Node Property Prediction ogbn-products ClusterGCN (SAGE aggr) Ext. data No #52 of 64 Archive leaderboard report
Node Property Prediction ogbn-products ClusterGCN (SAGE aggr) Number of params 206895 #52 of 64 Archive leaderboard report
Node Property Prediction ogbn-products ClusterGCN (SAGE aggr) Test Accuracy 0.7897 ± 0.0033 #52 of 64 Archive leaderboard report
Node Property Prediction ogbn-products ClusterGCN (SAGE aggr) Validation Accuracy 0.9212 ± 0.0009 #52 of 64 Archive leaderboard report

Ranks are positions in the archive's leaderboards as they stood at the 2025-07-28 snapshot. Results published since then are not among these rows, so a rank here is not a current standing.

Methods

Introduced by this paper: Cluster-GCN

Cluster-GCNGCN

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections