{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T15:56:05Z","timestamp":1782316565481,"version":"3.54.5"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,12,28]],"date-time":"2024-12-28T00:00:00Z","timestamp":1735344000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["IIS 2212143"],"award-info":[{"award-number":["IIS 2212143"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2025,1,31]]},"abstract":"<jats:p>\n            Distributed graph neural network (GNN) training facilitates learning on massive graphs that surpass the storage and computational capabilities of a single machine. Traditional distributed frameworks strive for performance parity with centralized training by maximally recovering cross-instance node dependencies, relying either on inter-instance communication or periodic fallback to centralized training. However, these processes create overhead and constrain the scalability of the framework. In this work, we propose a streamlined framework for distributed GNN training that eliminates these costly operations, yielding improved scalability, convergence speed, and performance over state-of-the-art approaches. Our framework (1) comprises independent trainers that\n            <jats:italic>asynchronously<\/jats:italic>\n            learn local models from locally available parts of the training graph and (2) synchronizes these local models only through periodic (time-based) model aggregation. Contrary to prevailing belief, our theoretical analysis shows that it is not essential to maximize the recovery of cross-instance node dependencies to achieve performance parity with centralized training. Instead, our framework leverages randomized assignment of nodes or super-nodes (i.e., collections of original nodes) to partition the training graph in order to enhance data uniformity and minimize discrepancies in gradient and loss function across instances. Experiments on social and e-commerce networks with up to 1.3 billion edges show that our proposed framework achieves state-of-the-art performance and 2.31\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\times\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            speedup compared to the fastest baseline despite using less training data.\n          <\/jats:p>","DOI":"10.1145\/3701563","type":"journal-article","created":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T13:42:03Z","timestamp":1731073323000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Simplifying Distributed Neural Network Training on Massive Graphs: Randomized Partitions Improve Model Aggregation"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6145-3295","authenticated-orcid":false,"given":"Jiong","family":"Zhu","sequence":"first","affiliation":[{"name":"Amazon, Palo Alto, CA, USA and University of Michigan, Ann Arbor, MI, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-0989-1406","authenticated-orcid":false,"given":"Aishwarya","family":"Reganti","sequence":"additional","affiliation":[{"name":"Amazon, Palo Alto, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4461-8545","authenticated-orcid":false,"given":"Edward W.","family":"Huang","sequence":"additional","affiliation":[{"name":"Amazon, Palo Alto, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0368-6859","authenticated-orcid":false,"given":"Charles","family":"Dickens","sequence":"additional","affiliation":[{"name":"University of California, Santa Cruz, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0281-932X","authenticated-orcid":false,"given":"Nikhil","family":"Rao","sequence":"additional","affiliation":[{"name":"Microsoft, Redmond, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9023-2248","authenticated-orcid":false,"given":"Karthik","family":"Subbian","sequence":"additional","affiliation":[{"name":"Amazon, Palo Alto, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3206-8179","authenticated-orcid":false,"given":"Danai","family":"Koutra","sequence":"additional","affiliation":[{"name":"Amazon, Palo Alto, CA, USA and University of Michigan, Ann Arbor, MI, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,12,28]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"Alexandra Angerd Keshav Balasubramanian and Murali Annavaram. 2020. Distributed training of graph convolutional networks using subgraph approximation. arXiv:2012.04930. Retrieved from https:\/\/arxiv.org\/abs\/2012.04930"},{"key":"e_1_3_3_3_2","unstructured":"Jimmy Lei Ba Jamie Ryan Kiros and Geoffrey E. Hinton. 2016. Layer normalization. arXiv:1607.06450. Retrieved from https:\/\/arxiv.org\/abs\/1607.06450"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380204"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3336191.3371834"},{"key":"e_1_3_3_6_2","first-page":"942","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Chen Jianfei","year":"2018","unstructured":"Jianfei Chen, Jun Zhu, and Le Song. 2018. Stochastic training of graph convolutional networks with variance reduction. In Proceedings of the International Conference on Machine Learning. PMLR, 942\u2013950."},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330925"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3589335.3651920"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3411903"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313488"},{"key":"e_1_3_3_11_2","first-page":"3294","volume-title":"Proceedings of theInternational Conference on Machine Learning","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 Proceedings of theInternational Conference on Machine Learning. PMLR, 3294\u20133304."},{"key":"e_1_3_3_12_2","volume-title":"Proceedings of the Workshop of Graph Representation Learning and Beyond (GRL+)","author":"Frasca Fabrizio","year":"2020","unstructured":"Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. 2020. Sign: Scalable inception graph neural networks. In Proceedings of the Workshop of Graph Representation Learning and Beyond (GRL+)."},{"key":"e_1_3_3_13_2","first-page":"551","volume-title":"Proceedings of the 15th  \\(\\{\\) USENIX \\(\\}\\)  Symposium on Operating Systems Design and Implementation ( \\(\\{\\) OSDI \\(\\}\\)  \u201921)","author":"Gandhi Swapnil","year":"2021","unstructured":"Swapnil Gandhi and Anand Padmanabha Iyer. 2021. P3: Distributed deep graph learning at scale. In Proceedings of the 15th \\(\\{\\) USENIX \\(\\}\\) Symposium on Operating Systems Design and Implementation ( \\(\\{\\) OSDI \\(\\}\\) \u201921), 551\u2013568."},{"key":"e_1_3_3_14_2","unstructured":"Priya Goyal Piotr Doll\u00e1r Ross Girshick Pieter Noordhuis Lukasz Wesolowski Aapo Kyrola Andrew Tulloch Yangqing Jia and Kaiming He. 2017. Accurate large minibatch sgd: Training imagenet in 1 hour. arXiv:1706.02677. Retrieved from https:\/\/arxiv.org\/abs\/1706.02677"},{"key":"e_1_3_3_15_2","volume-title":"Proceedings of the International Conference on Neural Information Processing Systems (NeurIPS \u201917)","author":"Hamilton Will","year":"2017","unstructured":"Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Proceedings of the International Conference on Neural Information Processing Systems (NeurIPS \u201917)."},{"key":"e_1_3_3_16_2","unstructured":"Weihua Hu Matthias Fey Hongyu Ren Maho Nakata Yuxiao Dong and Jure Leskovec. 2021. OGB-LSC: A large-scale challenge for machine learning on graphs. arXiv:2103.09430. Retrieved from https:\/\/arxiv.org\/abs\/2103.09430"},{"key":"e_1_3_3_17_2","unstructured":"Weihua Hu Matthias Fey Marinka Zitnik Yuxiao Dong Hongyu Ren Bowen Liu Michele Catasta and Jure Leskovec. 2020. Open graph benchmark: Datasets for machine learning on graphs. arXiv:2005.00687. Retrieved from https:\/\/arxiv.org\/abs\/2005.00687"},{"key":"e_1_3_3_18_2","first-page":"14679","volume-title":"Proceedings of the International Conference on Machine Learning.","author":"Jaiswal Ajay Kumar","year":"2023","unstructured":"Ajay Kumar Jaiswal, Shiwei Liu, Tianlong Chen, Ying Ding, and Zhangyang Wang. 2023. Graph ladling: Shockingly simple parallel GNN training without intermediate communication. In Proceedings of the International Conference on Machine Learning. PMLR, 14679\u201314690."},{"key":"e_1_3_3_19_2","unstructured":"Peng Jiang and Masuma Akter Rumi. 2021. Communication-efficient sampling for distributed training of graph convolutional networks. arXiv:2101.07706. Retrieved from https:\/\/arxiv.org\/abs\/2101.07706"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3534678.3539429"},{"key":"e_1_3_3_21_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Jin Wei","year":"2022","unstructured":"Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. 2022. Graph condensation for graph neural networks. In Proceedings of the International Conference on Learning Representations. Retrieved from https:\/\/openreview.net\/forum?id=WLEx3Jo4QaB"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_3_3_23_2","volume-title":"Proceedings of the International Conference on Learning Representations (ICLR)","author":"Kipf Thomas N.","year":"2017","unstructured":"Thomas N. Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. In Proceedings of the International Conference on Learning Representations (ICLR)."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3065386"},{"key":"e_1_3_3_25_2","unstructured":"Juanhui Li Harry Shomer Jiayuan Ding Yiqi Wang Yao Ma Neil Shah Jiliang Tang and Dawei Yin. 2022. Are graph neural networks really helpful for knowledge graph completion? arXiv:2205.10652. Retrieved from https:\/\/arxiv.org\/abs\/2205.10652"},{"key":"e_1_3_3_26_2","article-title":"Communication efficient distributed machine learning with the parameter server","author":"Li Mu","year":"2014","unstructured":"Mu Li, David G. Andersen, Alexander J. Smola, and Kai Yu. 2014. Communication efficient distributed machine learning with the parameter server. In Proceedings of the 27th International Conference on Neural Information Processing Systems.","journal-title":"Proceedings of the 27th International Conference on Neural Information Processing Systems"},{"issue":"3","key":"e_1_3_3_27_2","first-page":"62:1","article-title":"Graph summarization methods and applications: A survey","volume":"51","author":"Liu Yike","year":"2018","unstructured":"Yike Liu, Tara Safavi, Abhilash Dighe, and Danai Koutra. 2018. Graph summarization methods and applications: A survey. ACM Computing Surveys 51, 3 (2018), 62:1\u201362:34.","journal-title":"ACM Computing Surveys"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.5555\/3600270.3601557"},{"key":"e_1_3_3_29_2","first-page":"1273","volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics","author":"McMahan Brendan","year":"2017","unstructured":"Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. 2017. Communication-efficient learning of deep networks from decentralized data. In Proceedings of the International Conference on Artificial Intelligence and Statistics. PMLR, 1273\u20131282."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3458817.3480856"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359646"},{"key":"e_1_3_3_32_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Narayanan S Deepak","year":"2021","unstructured":"S Deepak Narayanan, Aditya Sinha, Prateek Jain, Purushottam Kar, and Sundararajan Sellamanickam. 2021. IGLU: Efficient GCN training via lazy updates. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/0330046"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220077"},{"key":"e_1_3_3_35_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Ramezani Morteza","year":"2021","unstructured":"Morteza Ramezani, Weilin Cong, Mehrdad Mahdavi, Mahmut Kandemir, and Anand Sivasubramaniam. 2021. Learn locally, correct globally: A distributed algorithm for training graph neural networks. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-93417-4_38"},{"key":"e_1_3_3_37_2","unstructured":"Sebastian U Stich. 2018. Local SGD converges fast and communicates little. arXiv:1805.09767. Retrieved from https:\/\/arxiv.org\/abs\/1805.09767"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.5555\/3433701.3433794"},{"key":"e_1_3_3_39_2","unstructured":"Rianne van den Berg Thomas N. Kipf and Max Welling. 2017. Graph convolutional matrix completion. arXiv:1706.02263. Retrieved from https:\/\/arxiv.org\/abs\/1706.02263"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3308560.3316586"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1162\/qss_a_00021"},{"key":"e_1_3_3_42_2","first-page":"165","volume-title":"Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR \u201919)","author":"Wang Xiang","year":"2018","unstructured":"Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. 2018. Neural graph collaborative filtering. In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR \u201919). 165\u2013174."},{"key":"e_1_3_3_43_2","first-page":"23965","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Wortsman Mitchell","year":"2022","unstructured":"Mitchell Wortsman, Gabriel Ilharco, Samir Ya Gadre, Rebecca Roelofs, Raphael Gontijo-Lopes, Ari S. Morcos, Hongseok Namkoong, Ali Farhadi, Yair Carmon, Simon Kornblith, et al. 2022. Model soups: Averaging weights of multiple fine-tuned models improves accuracy without increasing inference time. In Proceedings of the International Conference on Machine Learning. PMLR, 23965\u201323998."},{"key":"e_1_3_3_44_2","volume-title":"Proceedings of the 36th International Conference on Machine Learning (ICML)","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 (ICML)."},{"key":"e_1_3_3_45_2","volume-title":"Proceedings of the International Conference on Learning Representations (ICLR)","author":"Yang Bishan","year":"2015","unstructured":"Bishan Yang, Scott Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2015. Embedding entities and relations for learning and inference in knowledge bases. In Proceedings of the International Conference on Learning Representations (ICLR)."},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219890"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.5555\/3495724.3497151"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33015693"},{"key":"e_1_3_3_49_2","unstructured":"Lingfan Yu Jiajun Shen Jinyang Li and Adam Lerer. 2020. Scalable graph neural networks for heterogeneous graphs. arXiv:2011.09679. Retrieved from https:\/\/arxiv.org\/abs\/2011.09679"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.5555\/3540261.3541765"},{"key":"e_1_3_3_51_2","volume-title":"Proceedings of the 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 inductive learning method. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3511923"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1109\/IA351965.2020.00011"},{"key":"e_1_3_3_54_2","unstructured":"Da Zheng Xiang Song Chengru Yang Dominique LaSalle and George Karypis. 2021. Distributed hybrid CPU and GPU training for graph neural networks on billion-scale graphs. arXiv:2112.15345. Retrieved from https:\/\/arxiv.org\/abs\/2112.15345"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v37i4.25621"},{"key":"e_1_3_3_56_2","unstructured":"Jiong Zhu Gaotang Li Yao-An Yang Jing Zhu Xuehao Cui and Danai Koutra. 2024. On the impact of feature heterophily on link prediction with graph neural networks. arXiv:2409.17475. Retrieved from https:\/\/arxiv.org\/abs\/2409.17475"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/3626772.3657978"},{"key":"e_1_3_3_58_2","volume-title":"Proceedings of the 34th International Conference on Neural Information Processing Systems (NeurIPS \u201920)","author":"Zhu Jiong","year":"2020","unstructured":"Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. 2020. Beyond homophily in graph neural networks: Current limitations and effective designs. In Proceedings of the 34th International Conference on Neural Information Processing Systems (NeurIPS \u201920)."},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/3616855.3635786"},{"key":"e_1_3_3_60_2","unstructured":"Rong Zhu Kun Zhao Hongxia Yang Wei Lin Chang Zhou Baole Ai Yong Li and Jingren Zhou. 2019. Aligraph: A comprehensive graph neural network platform. arXiv:1902.08730. Retrieved from https:\/\/arxiv.org\/abs\/1902.08730"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3701563","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3701563","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:00Z","timestamp":1750295880000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3701563"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,28]]},"references-count":59,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1,31]]}},"alternative-id":["10.1145\/3701563"],"URL":"https:\/\/doi.org\/10.1145\/3701563","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,28]]},"assertion":[{"value":"2023-10-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}