Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Deep Residual Learning for Image Recognition
He, K., Zhang, X., Ren, S., & Sun, J. (2016) · 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2016.90 · Cited by 235,474 · see citing works
Semi-supervised classification with graph convolutional networks
Kipf, T. N., & Welling, M. (2016) · arXiv · doi:10.48550/arxiv.1609.02907 · Cited by 24,853 · see citing works
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. (2017) · arXiv · doi:10.48550/arxiv.1710.10903 · Cited by 12,107
(2017) · Cited by 11,625 · see citing works
Inductive Representation Learning on Large Graphs
Hamilton, W. L., Ying, R., & Leskovec, J. (2017) · arXiv · doi:10.48550/arxiv.1706.02216 · Cited by 10,639 · see citing works
Analysis of a complex of statistical variables into principal components.
Hotelling, H. (1933) · Journal of Educational Psychology · doi:10.1037/h0071325 · Cited by 9,691 · see citing works
A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
Karypis, G., & Kumar, V. (1998) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827595287997 · Cited by 5,833 · see citing works
Graph Convolutional Neural Networks for Web-Scale Recommender Systems
Ying, R., He, R., Chen, K., Eksombatchai, P., Hamilton, W. L., & Leskovec, J. (2018) · Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining · doi:10.1145/3219819.3219890 · Cited by 3,733 · see citing works
Image-Based Recommendations on Styles and Substitutes
McAuley, J., Targett, C., Shi, Q., & van den Hengel, A. (2015) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/2766462.2767755 · Cited by 2,348 · see citing works
Link Prediction Based on Graph Neural NetworksPreprint
Zhang, M., & Chen, Y. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1802.09691 · Cited by 1,394 · see citing works
FastGCN: Fast Learning with Graph Convolutional Networks via Importance SamplingPreprint
Chen, J., Ma, T., & Xiao, C. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1801.10247 · Cited by 1,172 · see citing works
Weighted Graph Cuts without Eigenvectors A Multilevel Approach
Dhillon, I. S., Guan, Y., & Kulis, B. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.1115 · Cited by 1,037 · see citing works
Inferring Networks of Substitutable and Complementary Products
McAuley, J., Pandey, R., & Leskovec, J. (2015) · Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2783258.2783381 · Cited by 645 · see citing works
GeniePath: Graph Neural Networks with Adaptive Receptive Paths
Liu, Z., Chen, C., Li, L., Zhou, J., Li, X., Song, L., & Qi, Y. (2019) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v33i01.33014424 · Cited by 350 · see citing works
A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
KarypisGeorge, & KumarVipin (1998) · SIAM Journal on Scientific Computing · doi:10.5555/305219.305248 · Cited by 153 · see citing works
Learning Steady-States of Iterative Algorithms over Graphs
Dai, H., Kozareva, Z., Dai, B., Smola, A. J., & Song, L. (2018) · International Conference on Machine Learning · Cited by 151 · see citing works
Stochastic Training of Graph Convolutional Networks with Variance Reduction
Chen, J., Zhu, J., & Song, L. (2018) · International Conference on Machine Learning · Cited by 143 · see citing works
Chen, T., Wang, Z., Li, L., Li, D., Li, Z., Chang, X., Bian, P., Liang, G., Wang, Q., & Xie, T. (2025) · Schloss Dagstuhl – Leibniz-Zentrum für Informatik · doi:10.4230/lipics.ecoop.2025.6
Flagged first, then by citations
Research works printed but not linked: 1
- Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Dit-Yan Yeung. 2018. GaAN: Gated Attention Networks for Learning on Large and Spatiotemporal Graphs. In UAI.
Cited by
Sorted by citations
A Comprehensive Survey on Graph Neural Networks
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. S. (2021) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2020.2978386 · Cited by 11,000 · see citing works
Graph neural networks: A review of methods and applications
Zhou, J., Cui, G., Hu, S., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li, C., & Sun, M. (2020) · AI Open · doi:10.1016/j.aiopen.2021.01.001 · Cited by 6,880 · see citing works
Graph representation learning in biomedicine and healthcare
Li, M. M., Huang, K., & Zitnik, M. (2022) · Nature Biomedical Engineering · doi:10.1038/s41551-022-00942-x · Cited by 294 · see citing works
“81,82 developed sampling strategies to intelligently select small subsets of the whole local network neighbourhoods, and used them to train GNN models.”
Chen, M., Zhang, Z., Wang, T., Backes, M., Humbert, M., & Zhang, Y. (2022) · Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3548606.3559352 · Cited by 133 · see citing works
Co-embedding of edges and nodes with deep graph convolutional neural networks
Zhou, Y., Huo, H., Hou, Z., Bu, L., Mao, J., Wang, Y., Lv, X., & Bu, F. (2023) · Scientific Reports · doi:10.1038/s41598-023-44224-1 · Cited by 33 · see citing works
Li, G., Mandal, S. K., Ogras, U. Y., & Marculescu, R. (2021) · ACM Transactions on Embedded Computing Systems · doi:10.1145/3476994 · Cited by 15 · see citing works
- Authors
- Chiang, W.-L., Liu, X., Si, S., Li, Y., Bengio, S., & Hsieh, C.-J.
- Affiliations
- National Taiwan University (TW)
- Google (United States) (US)
- Google Research, Mountain View, CA, USA
- University of California, Los Angeles (US)
- Venue
- Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining
- Publisher
- ACM
- Published
- 2019-07-25
- Pages
- 257-266
- OpenAlex
- W2945827377
- Cited by
- 1,331
- References
- 18
- Citations by year
- 2026: 135 · 2025: 208 · 2024: 246 · 2023: 221 · 2022: 196 · 2021: 235 · 2020: 83 · 2019: 7
- FWCI
- 48.85
- Type
- conference paper
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Advanced Graph Neural Networks
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Graph Theory and Algorithms
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Keywords
- graph convolutional networks, graph clustering, scalable training, memory efficiency, computational efficiency, neighborhood search, protein-protein interaction prediction
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
