Abstract
The computational paradigm of a graph neural network (GNN) can be abstracted as a computation graph (CG). Directly constructing CGs for large-scale graphs is computationally expensive and memory-intensive. Consequently, numerous sampling techniques aim to generate diverse CGs in a minibatch style. However, their CGs are overly large due to neighbor explosion problem, or excessively sparse in structure, causing insufficient representation of node embedding. To achieve a balance between the cost and expressive ability of CGs, we introduce a two-phase framework called NESC to build lightweight and powerful CGs. Initially, one simple yet efficient method is applied for selecting minimal, yet representative subsets of nodes from layer to layer, which restricts the size of CGs. Then, a novel resampling technique is utilized to establish edges between selected node sets, which is equivalent to sampling nodes from a subset of original neighbor sets. These restored edges help to mitigate the sampling bias of collecting nodes, guaranteeing adequate information aggregated for each node. We evaluate NESC against five competitive sampling-based algorithms on six large graphs. Experimental results demonstrate that our approach achieves superior test accuracy, along with 1.43x–5.32x speedups compared to other algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Balin, M.F., Çatalyürek, U.: Layer-neighbor sampling — defusing neighborhood explosion in GNNs. In: Advances in Neural Information Processing Systems (2023)
Chen, J., Zhu, J., Song, L.: Stochastic training of graph convolutional networks with variance reduction. In: International Conference on Machine Learning (2018)
Chen, J., Li, Z., Zhu, Y., Zhang, J., Pu, J.: From node interaction to hop interaction: New effective and scalable graph learning paradigm. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (2023)
Chen, J., Ma, T., Xiao, C.: FastGCN: fast learning with graph convolutional networks via importance sampling. In: International Conference on Learning Representations (2018)
Chen, J., Gao, K., Li, G., He, K.: NAGphormer: a tokenized graph transformer for node classification in large graphs. In: The Eleventh International Conference on Learning Representations (2023)
Chiang, W.L., Liu, X., Si, S., Li, Y., Bengio, S., Hsieh, C.J.: Cluster-GCN: an efficient algorithm for training deep and large graph convolutional networks. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2019)
Chien, E., Peng, J., Li, P., Milenkovic, O.: Adaptive universal generalized pagerank graph neural network. In: International Conference on Learning Representations (2021)
Cong, W., Forsati, R., Kandemir, M., Mahdavi, M.: Minimal variance sampling with provable guarantees for fast training of graph neural networks. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2020)
Duan, K., et al.: A comprehensive study on large-scale graph training: benchmarking and rethinking. In: Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (2022)
Fey, M., Lenssen, J.E., Weichert, F., Leskovec, J.: GNNAutoScale: scalable and expressive graph neural networks via historical embeddings. In: International Conference on Machine Learning (2021)
Frasca, F., Rossi, E., Eynard, D., Chamberlain, B., Bronstein, M., Monti, F.: Sign: scalable inception graph neural networks. In: ICML 2020 Workshop on Graph Representation Learning and Beyond (2020)
Gilmer, J., Schoenholz, S.S., Riley, P.F., Vinyals, O., Dahl, G.E.: Neural message passing for quantum chemistry. In: International Conference on Machine Learning (2017)
Hamilton, W.L., Ying, Z., Leskovec, J.: Inductive representation learning on large graphs. In: Advances in Neural Information Processing Systems (2017)
Hu, W., et al.: Open graph benchmark: datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687 (2020)
Huang, K., et al.: FreshGNN: reducing memory access via stable historical embeddings for graph neural network training. In: The Second Learning on Graphs Conference (2023)
Huang, W., Zhang, T., Rong, Y., Huang, J.: Adaptive sampling towards fast graph representation learning. In: Advances in Neural Information Processing Systems (2018)
Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20(1), 359–392 (1998)
Klicpera, J., Bojchevski, A., Günnemann, S.: Predict then propagate: graph neural networks meet personalized pagerank. In: International Conference on Learning Representations (2018)
Rong, Y., bing Huang, W., Xu, T., Huang, J.: DropEdge: towards deep graph convolutional networks on node classification. In: International Conference on Learning Representations (2019)
Shi, Z., Liang, X., Wang, J.: LMC: fast training of GNNs via subgraph sampling with provable convergence. In: International Conference on Learning Representations (2023)
Sun, C., Wu, G.: Scalable and adaptive graph neural networks with self-label-enhanced training. arXiv preprint arXiv:2104.09376 (2021)
Wang, M., et al.: Deep graph library: towards efficient and scalable deep learning on graphs. arXiv preprint arXiv:1909.01315 (2019)
Wu, F., Souza, A., Zhang, T., Fifty, C., Yu, T., Weinberger, K.: Simplifying graph convolutional networks. In: International Conference on Machine Learning (2019)
Yu, H., Wang, L., Wang, B., Liu, M., Yang, T., Ji, S.: GraphFM: improving large-scale GNN training via feature momentum. In: International Conference on Machine Learning (2022)
Zeng, H., et al.: Decoupling the depth and scope of graph neural networks. In: Advances in Neural Information Processing Systems (2021)
Zeng, H., Zhou, H., Srivastava, A., Kannan, R., Prasanna, V.: GraphSAINT: graph sampling based inductive learning method. In: International Conference on Learning Representations (2020)
Zhou, J., et al.: Graph neural networks: a review of methods and applications. AI Open 1, 57–81 (2020)
Zou, D., Hu, Z., Wang, Y., Jiang, S., Sun, Y., Gu, Q.: Layer-dependent importance sampling for training deep and large graph convolutional networks. In: Advances in Neural Information Processing Systems (2019)
Acknowledgments
This work was substantially supported by Key Projects of the National Natural Science Foundation of China (Grant No. U23A20496) and Shanghai Science and Technology Innovation Action Plan (Grant No. 21511100401). Weiguo Zheng is the corresponding author.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2025 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Gong, C. et al. (2025). Towards Building a Lightweight and Powerful Computation Graph for Scalable GNN. In: Barhamgi, M., Wang, H., Wang, X. (eds) Web Information Systems Engineering – WISE 2024. WISE 2024. Lecture Notes in Computer Science, vol 15437. Springer, Singapore. https://doi.org/10.1007/978-981-96-0567-5_14
Download citation
DOI: https://doi.org/10.1007/978-981-96-0567-5_14
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-96-0566-8
Online ISBN: 978-981-96-0567-5
eBook Packages: Computer ScienceComputer Science (R0)