{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,4]],"date-time":"2026-09-04T00:45:35Z","timestamp":1788482735136,"version":"build-2803163510"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:p>Recent advances in data processing have stimulated the demand for learning graphs of very large scales. Graph Neural Networks (GNNs), being an emerging and powerful approach in solving graph learning tasks, are known to be difficult to scale up. Most scalable models apply node-based techniques in simplifying the expensive graph message-passing propagation procedure of GNN. However, we find such acceleration insufficient when applied to million- or even billion-scale graphs. In this work, we propose SCARA, a scalable GNN with feature-oriented optimization for graph computation. SCARA efficiently computes graph embedding from node features, and further selects and reuses feature computation results to reduce overhead. Theoretical analysis indicates that our model achieves sub-linear time complexity with a guaranteed precision in propagation process as well as GNN training and inference. We conduct extensive experiments on various datasets to evaluate the efficacy and efficiency of SCARA. Performance comparison with baselines shows that SCARA can reach up to 100x graph propagation acceleration than current state-of-the-art methods with fast convergence and comparable accuracy. Most notably, it is efficient to process precomputation on the largest available billion-scale GNN dataset Papers100M (111M nodes, 1.6B edges) in 100 seconds.<\/jats:p>","DOI":"10.14778\/3551793.3551866","type":"journal-article","created":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T22:25:03Z","timestamp":1664490303000},"page":"3240-3248","source":"Crossref","is-referenced-by-count":21,"title":["SCARA"],"prefix":"10.14778","volume":"15","author":[{"given":"Ningyi","family":"Liao","sequence":"first","affiliation":[{"name":"Nanyang Technological University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dingheng","family":"Mo","sequence":"additional","affiliation":[{"name":"Nanyang Technological University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Siqiang","family":"Luo","sequence":"additional","affiliation":[{"name":"Nanyang Technological University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiang","family":"Li","sequence":"additional","affiliation":[{"name":"East China Normal University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pengcheng","family":"Yin","sequence":"additional","affiliation":[{"name":"Google Research"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,9,29]]},"reference":[{"key":"e_1_2_1_2_1","volume-title":"DDGK: Learning Graph Representations for Deep Divergence Graph Kernels. In The World Wide Web Conference","author":"Al-Rfou Rami","year":"2019","unstructured":"Rami Al-Rfou , Bryan Perozzi , and Dustin Zelle . 2019 . DDGK: Learning Graph Representations for Deep Divergence Graph Kernels. In The World Wide Web Conference ( San Francisco, CA, USA). 37--48. Rami Al-Rfou, Bryan Perozzi, and Dustin Zelle. 2019. DDGK: Learning Graph Representations for Deep Divergence Graph Kernels. In The World Wide Web Conference (San Francisco, CA, USA). 37--48."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.44"},{"key":"e_1_2_1_4_1","volume-title":"29th Advances in Neural Information Processing Systems (2016)","author":"Atwood James","year":"2016","unstructured":"James Atwood and Don Towsley . 2016 . Diffusion-convolutional neural networks . 29th Advances in Neural Information Processing Systems (2016) , 2001--2009. arXiv:1511.02136 James Atwood and Don Towsley. 2016. Diffusion-convolutional neural networks. 29th Advances in Neural Information Processing Systems (2016), 2001--2009. arXiv:1511.02136"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.","author":"van den Berg Rianne","year":"2018","unstructured":"Rianne van den Berg , Thomas N Kipf , and Max Welling . 2018 . Graph convolutional matrix completion . In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. Rianne van den Berg, Thomas N Kipf, and Max Welling. 2018. Graph convolutional matrix completion. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403296"},{"key":"e_1_2_1_7_1","volume-title":"International Conference on Learning Representations.","author":"Chen Jie","year":"2018","unstructured":"Jie Chen , Tengfei Ma , and Cao Xiao . 2018 . FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling . In International Conference on Learning Representations. Jie Chen, Tengfei Ma, and Cao Xiao. 2018. FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling. In International Conference on Learning Representations."},{"key":"e_1_2_1_8_1","volume-title":"35th International Conference on Machine Learning 3","author":"Chen Jianfei","year":"2018","unstructured":"Jianfei Chen , Jun Zhu , and Le Song . 2018 . Stochastic training of graph convolutional networks with variance reduction . 35th International Conference on Machine Learning 3 (2018), 1503--1532. arXiv:1710.10568 Jianfei Chen, Jun Zhu, and Le Song. 2018. Stochastic training of graph convolutional networks with variance reduction. 35th International Conference on Machine Learning 3 (2018), 1503--1532. arXiv:1710.10568"},{"key":"e_1_2_1_9_1","volume-title":"Scalable graph neural networks via bidirectional propagation. 33rd Advances in Neural Information Processing Systems","author":"Chen Ming","year":"2020","unstructured":"Ming Chen , Zhewei Wei , Bolin Ding , Yaliang Li , Ye Yuan , Xiaoyong Du , and Ji Rong Wen . 2020. Scalable graph neural networks via bidirectional propagation. 33rd Advances in Neural Information Processing Systems ( 2020 ). Ming Chen, Zhewei Wei, Bolin Ding, Yaliang Li, Ye Yuan, Xiaoyong Du, and Ji Rong Wen. 2020. Scalable graph neural networks via bidirectional propagation. 33rd Advances in Neural Information Processing Systems (2020)."},{"key":"e_1_2_1_10_1","volume-title":"7th International Conference on Learning Representations","author":"Chen Zhengdao","year":"2019","unstructured":"Zhengdao Chen , Joan Bruna , and Lisha Li . 2019 . Supervised community detection with line graph neural networks . 7th International Conference on Learning Representations (2019). Zhengdao Chen, Joan Bruna, and Lisha Li. 2019. Supervised community detection with line graph neural networks. 7th International Conference on Learning Representations (2019)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330925"},{"key":"e_1_2_1_12_1","volume-title":"VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization. 34th Advances in Neural Information Processing Systems","author":"Ding Mucong","year":"2021","unstructured":"Mucong Ding , Kezhi Kong , Jingling Li , Chen Zhu , John P Dickerson , Furong Huang , and Tom Goldstein . 2021. VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization. 34th Advances in Neural Information Processing Systems ( 2021 ). Mucong Ding, Kezhi Kong, Jingling Li, Chen Zhu, John P Dickerson, Furong Huang, and Tom Goldstein. 2021. VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization. 34th Advances in Neural Information Processing Systems (2021)."},{"key":"e_1_2_1_13_1","volume-title":"38th International Conference on Machine Learning. PMLR 139","author":"Fey Matthias","year":"2021","unstructured":"Matthias Fey , Jan E. Lenssen , Frank Weichert , and Jure Leskovec . 2021 . GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings . In 38th International Conference on Machine Learning. PMLR 139 . Matthias Fey, Jan E. Lenssen, Frank Weichert, and Jure Leskovec. 2021. GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings. In 38th International Conference on Machine Learning. PMLR 139."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129104"},{"key":"e_1_2_1_15_1","volume-title":"Inductive Representation Learning in Large Attributed Graphs. 30th Advances in Neural Information Processing Systems (oct","author":"Hamilton William L","year":"2017","unstructured":"William L Hamilton , Rex Ying , and Jure Leskovec . 2017. Inductive Representation Learning in Large Attributed Graphs. 30th Advances in Neural Information Processing Systems (oct 2017 ). arXiv:1710.09471 William L Hamilton, Rex Ying, and Jure Leskovec. 2017. Inductive Representation Learning in Large Attributed Graphs. 30th Advances in Neural Information Processing Systems (oct 2017). arXiv:1710.09471"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 31st International Conference on Neural Information Processing Systems. 1025--1035","author":"Hamilton William L","year":"2017","unstructured":"William L Hamilton , Rex Ying , and Jure Leskovec . 2017 . Inductive representation learning on large graphs . In Proceedings of the 31st International Conference on Neural Information Processing Systems. 1025--1035 . William L Hamilton, Rex Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems. 1025--1035."},{"key":"e_1_2_1_17_1","volume-title":"Open Graph Benchmark : Datasets for Machine Learning on Graphs. 33rd Advances in Neural Information Processing Systems","author":"Hu Weihua","year":"2020","unstructured":"Weihua Hu , Matthias Fey , Marinka Zitnik , Yuxiao Dong , Hongyu Ren , Bowen Liu , Michele Catasta , Jure Leskovec , Regina Barzilay , Peter Battaglia , Yoshua Bengio , Michael Bronstein , Stephan G\u00fcnnemann , Will Hamilton , Tommi Jaakkola , Stefanie Jegelka , Maximilian Nickel , Chris Re , Le Song , Jian Tang , Max Welling , and Rich Zemel . 2020. Open Graph Benchmark : Datasets for Machine Learning on Graphs. 33rd Advances in Neural Information Processing Systems ( 2020 ). Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, Jure Leskovec, Regina Barzilay, Peter Battaglia, Yoshua Bengio, Michael Bronstein, Stephan G\u00fcnnemann, Will Hamilton, Tommi Jaakkola, Stefanie Jegelka, Maximilian Nickel, Chris Re, Le Song, Jian Tang, Max Welling, and Rich Zemel. 2020. Open Graph Benchmark : Datasets for Machine Learning on Graphs. 33rd Advances in Neural Information Processing Systems (2020)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467256"},{"key":"e_1_2_1_19_1","volume-title":"International Conference on Learning Representations.","author":"Kipf Thomas N","year":"2017","unstructured":"Thomas N Kipf and Max Welling . 2017 . Semi-supervised classification with graph convolutional networks . In International Conference on Learning Representations. Thomas N Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations."},{"key":"e_1_2_1_20_1","volume-title":"7th International Conference on Learning Representations","author":"Klicpera Johannes","year":"2019","unstructured":"Johannes Klicpera , Aleksandar Bojchevski , and Stephan G\u00fcnnemann . 2019 . Predict then propagate: Graph neural networks meet personalized PageRank . 7th International Conference on Learning Representations (2019), 1--15. Johannes Klicpera, Aleksandar Bojchevski, and Stephan G\u00fcnnemann. 2019. Predict then propagate: Graph neural networks meet personalized PageRank. 7th International Conference on Learning Representations (2019), 1--15."},{"key":"e_1_2_1_21_1","volume-title":"Finding Global Homophily in Graph Neural Networks When Meeting Heterophily. In 39th International Conference on Machine Learning. arXiv:2205","author":"Li Xiang","year":"2022","unstructured":"Xiang Li , Renyu Zhu , Yao Cheng , Caihua Shan , Siqiang Luo , Dongsheng Li , and Weining Qian . 2022 . Finding Global Homophily in Graph Neural Networks When Meeting Heterophily. In 39th International Conference on Machine Learning. arXiv:2205 .07308 Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. 2022. Finding Global Homophily in Graph Neural Networks When Meeting Heterophily. In 39th International Conference on Machine Learning. arXiv:2205.07308"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00084"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2740908.2742839"},{"key":"e_1_2_1_25_1","volume-title":"Adversarial Attack and Defense on Graph Data: A Survey. arXiv e-prints","author":"Sun Lichao","year":"2018","unstructured":"Lichao Sun , Yingtong Dou , Carl Yang , Ji Wang , Philip S. Yu , Lifang He , and Bo Li. 2018. Adversarial Attack and Defense on Graph Data: A Survey. arXiv e-prints ( 2018 ). Lichao Sun, Yingtong Dou, Carl Yang, Ji Wang, Philip S. Yu, Lifang He, and Bo Li. 2018. Adversarial Attack and Defense on Graph Data: A Survey. arXiv e-prints (2018)."},{"key":"e_1_2_1_26_1","volume-title":"Attention-based graph neural network for semi-supervised learning. arXiv e-prints","author":"Thekumparampil Kiran K","year":"2018","unstructured":"Kiran K Thekumparampil , Chong Wang , Sewoong Oh , and Li-Jia Li. 2018. Attention-based graph neural network for semi-supervised learning. arXiv e-prints ( 2018 ). arXiv:1803.03735v1 Kiran K Thekumparampil, Chong Wang, Sewoong Oh, and Li-Jia Li. 2018. Attention-based graph neural network for semi-supervised learning. arXiv e-prints (2018). arXiv:1803.03735v1"},{"key":"e_1_2_1_27_1","volume-title":"8th International Conference on Learning Representations.","author":"Veli\u010dkovi\u0107 Petar","year":"2017","unstructured":"Petar Veli\u010dkovi\u0107 , Guillem Cucurull , Arantxa Casanova , Adriana Romero , Pietro Lio , and Yoshua Bengio . 2017 . Graph attention networks . In 8th International Conference on Learning Representations. Petar Veli\u010dkovi\u0107, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017. Graph attention networks. In 8th International Conference on Learning Representations."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132967"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467243"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360902"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098072"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning, Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.)","volume":"97","author":"Wu Felix","year":"2019","unstructured":"Felix Wu , Amauri Souza , Tianyi Zhang , Christopher Fifty , Tao Yu , and Kilian Weinberger . 2019 . Simplifying Graph Convolutional Networks . In Proceedings of the 36th International Conference on Machine Learning, Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.) , Vol. 97 . 6861--6871. Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. 2019. Simplifying Graph Convolutional Networks. In Proceedings of the 36th International Conference on Machine Learning, Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.), Vol. 97. 6861--6871."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457298"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2020.2978386"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421430"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219890"},{"key":"e_1_2_1_37_1","volume-title":"GraphSAINT: Graph Sampling Based Learning Method. In International Conference on Learning Representations.","author":"Zeng Hanqing","year":"2019","unstructured":"Hanqing Zeng , Hongkuan Zhou , Ajitesh Srivastava , Rajgopal Kannan , and Viktor Prasanna . 2019 . GraphSAINT: Graph Sampling Based Learning Method. In International Conference on Learning Representations. Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. 2019. GraphSAINT: Graph Sampling Based Learning Method. In International Conference on Learning Representations."},{"key":"e_1_2_1_38_1","volume-title":"Graph-bert: Only attention is needed for learning graph representations. arXiv e-prints","author":"Zhang Jiawei","year":"2020","unstructured":"Jiawei Zhang , Haopeng Zhang , Congying Xia , and Li Sun . 2020 . Graph-bert: Only attention is needed for learning graph representations. arXiv e-prints (2020). arXiv:2008.08617 Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. 2020. Graph-bert: Only attention is needed for learning graph representations. arXiv e-prints (2020). arXiv:2008.08617"},{"key":"e_1_2_1_39_1","first-page":"5165","article-title":"Link prediction based on graph neural networks","volume":"31","author":"Zhang Muhan","year":"2018","unstructured":"Muhan Zhang and Yixin Chen . 2018 . Link prediction based on graph neural networks . Advances in Neural Information Processing Systems 31 (2018), 5165 -- 5175 . Muhan Zhang and Yixin Chen. 2018. Link prediction based on graph neural networks. Advances in Neural Information Processing Systems 31 (2018), 5165--5175.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2981333"},{"key":"e_1_2_1_41_1","volume-title":"Spiking Graph Convolutional Networks. In 31th International Joint Conference on Artificial Intelligence. arXiv:2205","author":"Zhu Zulun","year":"2022","unstructured":"Zulun Zhu , Jiaying Peng , Jintang Li , Liang Chen , Qi Yu , and Siqiang Luo . 2022 . Spiking Graph Convolutional Networks. In 31th International Joint Conference on Artificial Intelligence. arXiv:2205 .02767 Zulun Zhu, Jiaying Peng, Jintang Li, Liang Chen, Qi Yu, and Siqiang Luo. 2022. Spiking Graph Convolutional Networks. In 31th International Joint Conference on Artificial Intelligence. arXiv:2205.02767"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220078"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3551793.3551866","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:56:11Z","timestamp":1672224971000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3551793.3551866"}},"subtitle":["scalable graph neural networks with feature-oriented optimization"],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":40,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["10.14778\/3551793.3551866"],"URL":"https:\/\/doi.org\/10.14778\/3551793.3551866","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,7]]}}}