{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T00:15:03Z","timestamp":1758672903185,"version":"3.44.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"Hong Kong RGC","award":["HKU 17207621 and 17203522"],"award-info":[{"award-number":["HKU 17207621 and 17203522"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Perform. Eval. Comput. Syst."],"published-print":{"date-parts":[[2025,12,31]]},"abstract":"<jats:p>Graph Neural Networks (GNNs) have become increasingly popular for their ability to learn the complex features of graph-structured data effectively. However, many real-world graphs are dynamic and change over time in terms of graph structures and features. A large dynamic graph is commonly stored in distributed graph stores and learned through distributed GNN training. Classical graph partition algorithms focus on partition balance and cross-partition edge reduction, which do not serve the need of distributed dynamic GNN learning well. We propose DistDy, a novel online graph partition framework tailored for distributed dynamic GNN learning, aiming to minimize dynamic graph storage overhead and inter-server communication. We design distributed additive storage to store changes in the large dynamic graph, and decide graph partition (aka change storage) on the go by formulating it into a communication utility maximization problem. An efficient online graph partition algorithm is proposed, which computes near-optimal partition strategies according to refined resource prices and additive storage rewards, achieving a proven competitive ratio. Experiments on various real-world and synthetic dynamic graph datasets show that DistDy can achieve 92.2% storage saving and up to 1.39\u00d7 speed-up in distributed GNN training as compared to using representative graph partition algorithms.<\/jats:p>","DOI":"10.1145\/3760772","type":"journal-article","created":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T12:33:56Z","timestamp":1755779636000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Online Graph Partition for Distributed Dynamic GNN Training"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-1582-2346","authenticated-orcid":false,"given":"Zhe","family":"Zhang","sequence":"first","affiliation":[{"name":"Department of Computer Science, The University of Hong Kong","place":["Hong Kong, Hong Kong"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3144-4398","authenticated-orcid":false,"given":"Chuan","family":"Wu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, The University of Hong Kong","place":["Hong Kong, Hong Kong"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,23]]},"reference":[{"key":"e_1_3_1_2_2","first-page":"120","volume-title":"SPAA 2004: Proceedings of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures","author":"Andreev Konstantin","year":"2004","unstructured":"Konstantin Andreev and Harald R\u00e4cke. 2004. Balanced graph partitioning. In SPAA 2004: Proceedings of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures. Phillip B. Gibbons and Micah Adler (Eds.), ACM, 120\u2013124. DOI:10.1145\/1007912.1007931"},{"key":"e_1_3_1_3_2","volume-title":"Convex Optimization","author":"Boyd Stephen P.","year":"2014","unstructured":"Stephen P. Boyd and Lieven Vandenberghe. 2014. Convex Optimization. Cambridge University Press."},{"key":"e_1_3_1_4_2","first-page":"1","volume-title":"SC\u201921","author":"Chakaravarthy Venkatesan T.","year":"2021","unstructured":"Venkatesan T. Chakaravarthy, Shivmaran S. Pandian, Saurabh Raje, Yogish Sabharwal, Toyotaro Suzumura, and Shashanka Ubaru. 2021. Efficient scaling of dynamic graph neural networks. In SC\u201921. 1\u201315."},{"key":"e_1_3_1_5_2","first-page":"145","volume-title":"CIKM\u201920: Proceedings of the 29th ACM International Conference on Information and Knowledge Management, Virtual Event","author":"Chang Xiaofu","year":"2020","unstructured":"Xiaofu Chang, Xuqin Liu, Jianfeng Wen, Shuang Li, Yanming Fang, Le Song, and Yuan Qi. 2020. Continuous-time dynamic graph learning via neural interaction processes. In CIKM\u201920: Proceedings of the 29th ACM International Conference on Information and Knowledge Management, Virtual Event. Mathieu d\u2019Aquin, Stefan Dietze, Claudia Hauff, Edward Curry, and Philippe Cudr\u00e9-Mauroux (Eds.), ACM, 145\u2013154. DOI:10.1145\/3340531.3411946"},{"key":"e_1_3_1_6_2","volume-title":"ICLR\u201918","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 ICLR\u201918."},{"key":"e_1_3_1_7_2","unstructured":"Connected Papers. 2020. In Retrieved Sep. 3 2025 from https:\/\/www.connectedpapers.com\/"},{"key":"e_1_3_1_8_2","volume-title":"ICLR 2019 (RLGM Workshop)","author":"Fey Matthias","year":"2019","unstructured":"Matthias Fey and Jan E. Lenssen. 2019. Fast graph representation learning with PyTorch geometric. In ICLR 2019 (RLGM Workshop)."},{"key":"e_1_3_1_9_2","volume-title":"OSDI\u201921","author":"Gandhi Swapnil","year":"2021","unstructured":"Swapnil Gandhi and Anand Padmanabha Iyer. 2021. P3: Distributed deep graph learning at scale. In OSDI\u201921. USENIX."},{"key":"e_1_3_1_10_2","volume-title":"Deep Learning","author":"Goodfellow Ian J.","year":"2016","unstructured":"Ian J. Goodfellow, Yoshua Bengio, and Aaron C. Courville. 2016. Deep Learning. MIT Press."},{"key":"e_1_3_1_11_2","volume-title":"NeurIPS\u201919","author":"Hajiramezanali Ehsan","year":"2019","unstructured":"Ehsan Hajiramezanali, Arman Hasanzadeh, Krishna R. Narayanan, Nick Duffield, Mingyuan Zhou, and Xiaoning Qian. 2019. Variational graph recurrent neural networks. In NeurIPS\u201919."},{"issue":"3","key":"e_1_3_1_12_2","first-page":"52","article-title":"Representation learning on graphs: Methods and applications","volume":"40","author":"Hamilton William L.","year":"2017","unstructured":"William L. Hamilton, Rex Ying, and Jure Leskovec. 2017. Representation learning on graphs: Methods and applications. IEEE Data Eng. Bull. 40, 3 (2017), 52\u201374.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_3_1_13_2","volume-title":"NeurIPS\u201917","author":"Hamilton William L.","year":"2017","unstructured":"William L. Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In NeurIPS\u201917."},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2827872"},{"key":"e_1_3_1_15_2","volume-title":"NeurIPS","author":"Hu Weihua","year":"2020","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. In NeurIPS."},{"key":"e_1_3_1_16_2","article-title":"LEOPARD: Lightweight edge-oriented partitioning and replication for dynamic graphs","author":"Huang Jiewen","year":"2016","unstructured":"Jiewen Huang and Daniel Abadi. 2016. LEOPARD: Lightweight edge-oriented partitioning and replication for dynamic graphs. Proc. VLDB Endow. 9, 7 (2016), 540\u2013551. http:\/\/www.vldb.org\/pvldb\/vol9\/p540-huang.pdf","journal-title":"Proc. VLDB Endow."},{"key":"e_1_3_1_17_2","unstructured":"Shenyang Huang Farimah Poursafaei Jacob Danovitch Matthias Fey Weihua Hu Emanuele Rossi Jure Leskovec Michael Bronstein Guillaume Rabusseau and Reihaneh Rabbany. 2023. Temporal graph benchmark for machine learning on temporal graphs. Proceedings of the 37th International Conference on Neural Information Processing Systems (NIPS\u201923). 18."},{"key":"e_1_3_1_18_2","volume-title":"NSDI\u201921","author":"Iyer Anand Padmanabha","year":"2021","unstructured":"Anand Padmanabha Iyer, Qifan Pu, Kishan Patel, Joseph E. Gonzalez, and Ion Stoica. 2021. TEGRA: Efficient ad-hoc analytics on evolving graphs. In NSDI\u201921. USENIX."},{"key":"e_1_3_1_19_2","volume-title":"Technical Report","author":"Karypis G.","year":"1995","unstructured":"G. Karypis and V. Kumar.1995. Metis\u2013unstructured Graph Partitioning and Sparse Matrix Ordering System. Technical Report. Department of Computer Science, University of Minnesota."},{"key":"e_1_3_1_20_2","volume-title":"CEAS\u201904","author":"Klimt Bryan","year":"2004","unstructured":"Bryan Klimt and Yiming Yang. 2004. Introducing the Enron corpus. In CEAS\u201904."},{"key":"e_1_3_1_21_2","volume-title":"SODA 2009","author":"Krauthgamer Robert","year":"2009","unstructured":"Robert Krauthgamer, Joseph Naor, and Roy Schwartz. 2009. Partitioning graphs into balanced components. In SODA 2009."},{"key":"e_1_3_1_22_2","volume-title":"ICDE 2013","author":"Leis Viktor","year":"2013","unstructured":"Viktor Leis, Alfons Kemper, and Thomas Neumann. 2013. The adaptive radix tree: ARTful indexing for main-memory databases. In ICDE 2013. IEEE Computer Society."},{"key":"e_1_3_1_23_2","first-page":"583","volume-title":"OSDI","author":"Li Mu","year":"2014","unstructured":"Mu Li, David G. Andersen, Jun Woo Park, Alexander J. Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J. Shekita, and Bor-Yiing Su. 2014. Scaling distributed machine learning with the parameter server. In OSDI. USENIX Association, 583\u2013598."},{"key":"e_1_3_1_24_2","volume-title":"NSDI\u201923","author":"Liu Tianfeng","year":"2023","unstructured":"Tianfeng Liu, Yangrui Chen, Dan Li, Chuan Wu, Yibo Zhu, Jun He, Yanghua Peng, Hongzheng Chen, Hongzhi Chen, and Chuanxiong Guo. 2023. BGL: GPU-efficient GNN training by optimizing graph data I\/O and preprocessing. In NSDI\u201923."},{"key":"e_1_3_1_25_2","volume-title":"ICDE\u201917","author":"Martella Claudio","year":"2017","unstructured":"Claudio Martella, Dionysios Logothetis, Andreas Loukas, and Georgos Siganos. 2017. Spinner: Scalable graph partitioning in the cloud. In ICDE\u201917. IEEE Computer Society."},{"key":"e_1_3_1_26_2","first-page":"1363","volume-title":"ACL (1)","author":"Mehta Nikhil","year":"2022","unstructured":"Nikhil Mehta, Maria Leonor Pacheco, and Dan Goldwasser. 2022. Tackling fake news detection by continually improving social context representations using graph neural networks. In ACL (1). Association for Computational Linguistics, 1363\u20131380."},{"key":"e_1_3_1_27_2","volume-title":"WWW\u201918","author":"Nguyen Giang Hoang","year":"2018","unstructured":"Giang Hoang Nguyen, John Boaz Lee, Ryan A. Rossi, Nesreen K. Ahmed, Eunyee Koh, and Sungchul Kim. 2018. Continuous-time dynamic network embeddings. In WWW\u201918. ACM."},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1002\/asi.21015"},{"key":"e_1_3_1_29_2","volume-title":"NeurIPS\u201919","author":"Paszke Adam","year":"2019","unstructured":"Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et\u00a0al. 2019. PyTorch: An imperative style, high-performance deep learning library. In NeurIPS\u201919."},{"key":"e_1_3_1_30_2","unstructured":"Emanuele Rossi Ben Chamberlain Fabrizio Frasca Davide Eynard Federico Monti and Michael Bronstein. 2020. Temporal graph networks for deep learning on dynamic graphs. Retrieved from https:\/\/arxiv.org\/abs\/2006.10637"},{"key":"e_1_3_1_31_2","volume-title":"WSDM\u201920","author":"Sankar Aravind","year":"2020","unstructured":"Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. 2020. DySAT: Deep neural representation learning on dynamic graphs via self-attention networks. In WSDM\u201920. ACM."},{"key":"e_1_3_1_32_2","volume-title":"SODA\u201914","author":"Stanton Isabelle","year":"2014","unstructured":"Isabelle Stanton. 2014. Streaming balanced graph partitioning algorithms for random graphs. In SODA\u201914. SIAM."},{"key":"e_1_3_1_33_2","volume-title":"KDD\u201912","author":"Stanton Isabelle","year":"2012","unstructured":"Isabelle Stanton and Gabriel Kliot. 2012. Streaming graph partitioning for large distributed graphs. In KDD\u201912. ACM."},{"key":"e_1_3_1_34_2","first-page":"495","volume-title":"OSDI","author":"Thorpe John","year":"2021","unstructured":"John Thorpe, Yifan Qiao, Jonathan Eyolfson, Shen Teng, Guanzhou Hu, Zhihao Jia, Jinliang Wei, Keval Vora, Ravi Netravali, Miryung Kim, and Guoqing Harry Xu. 2021. Dorylus: Affordable, scalable, and accurate GNN training with distributed CPU servers and serverless threads. In OSDI. USENIX Association, 495\u2013514."},{"key":"e_1_3_1_35_2","volume-title":"ICLR\u201919","author":"Trivedi Rakshit","year":"2019","unstructured":"Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. 2019. DyRep: Learning representations over dynamic graphs. In ICLR\u201919."},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1002\/asi.21015"},{"key":"e_1_3_1_37_2","volume-title":"ICLR\u201918","author":"Velickovic Petar","year":"2018","unstructured":"Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li\u00f2, and Yoshua Bengio. 2018. Graph attention networks. In ICLR\u201918."},{"key":"e_1_3_1_38_2","first-page":"67","volume-title":"EuroSys","author":"Wang Lei","year":"2021","unstructured":"Lei Wang, Qiang Yin, Chao Tian, Jianbang Yang, Rong Chen, Wenyuan Yu, Zihang Yao, and Jingren Zhou. 2021. FlexGraph: A flexible and efficient distributed framework for GNN training. In EuroSys. ACM, 67\u201382."},{"key":"e_1_3_1_39_2","unstructured":"Minjie Wang Da Zheng Zihao Ye Quan Gan Mufei Li Xiang Song Jinjing Zhou Chao Ma Lingfan Yu Yu Gai Tianjun Xiao Tong He George Karypis Jinyang Li and Zheng Zhang. 2020. Deep graph library: A graph-centric highly-performant package for graph neural networks. Retrieved from https:\/\/arxiv.org\/abs\/1909.01315"},{"key":"e_1_3_1_40_2","volume-title":"ICLR\u201921","author":"Wang Yanbang","year":"2021","unstructured":"Yanbang Wang, Yen-Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. 2021. Inductive representation learning in temporal networks via causal anonymous walks. In ICLR\u201921."},{"key":"e_1_3_1_41_2","first-page":"31","volume-title":"Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2021, Virtual Conference","author":"Wheatman Brian","year":"2021","unstructured":"Brian Wheatman and Helen Xu. 2021. A parallel packed memory array to store dynamic graphs. In Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2021, Virtual Conference. Martin Farach-Colton and Sabine Storandt (Eds.), SIAM, 31\u201345. DOI:10.1137\/1.9781611976472.3"},{"key":"e_1_3_1_42_2","first-page":"1054","volume-title":"Proceedings of the 34th AAAI Conference on Artificial Intelligence, AAAI 2020, The 32nd Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The 10th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020","author":"Wu Yongji","year":"2020","unstructured":"Yongji Wu, Defu Lian, Yiheng Xu, Le Wu, and Enhong Chen. 2020. Graph convolutional networks with Markov random field reasoning for social spammer detection. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, AAAI 2020, The 32nd Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The 10th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020. AAAI Press, 1054\u20131061. DOI:10.1609\/AAAI.V34I01.5455"},{"key":"e_1_3_1_43_2","volume-title":"ICLR 2020","author":"Xu Da","year":"2020","unstructured":"Da Xu, Chuanwei Ruan, Evren K\u00f6rpeoglu, Sushant Kumar, and Kannan Achan. 2020. Inductive representation learning on temporal graphs. In ICLR 2020. OpenReview.net."},{"key":"e_1_3_1_44_2","volume-title":"KDD\u201921","author":"Yang Menglin","year":"2021","unstructured":"Menglin Yang, Min Zhou, Marcus Kalander, Zengfeng Huang, and Irwin King. 2021. Discrete-time temporal network embedding via implicit hierarchical learning in hyperbolic space. In KDD\u201921. ACM."},{"key":"e_1_3_1_45_2","volume-title":"SIGKDD\u201918","author":"Ying Rex","year":"2018","unstructured":"Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. 2018. Graph convolutional neural networks for web-scale recommender systems. In SIGKDD\u201918. ACM."},{"key":"e_1_3_1_46_2","first-page":"5171","volume-title":"NeurIPS","author":"Zhang Muhan","year":"2018","unstructured":"Muhan Zhang and Yixin Chen. 2018. Link prediction based on graph neural networks. In NeurIPS. 5171\u20135181."},{"key":"e_1_3_1_47_2","first-page":"1352","volume-title":"WWW","author":"Zhang Yanfu","year":"2022","unstructured":"Yanfu Zhang, Hongchang Gao, Jian Pei, and Heng Huang. 2022. Robust self-supervised structural graph neural network for social network prediction. In WWW. ACM, 1352\u20131361."},{"key":"e_1_3_1_48_2","unstructured":"Hongkuan Zhou Da Zheng Israt Nisa Vasileios Ioannidis Xiang Song and George Karypis. 2022. TGL: A general framework for temporal GNN training on billion-scale graphs. Retrieved from https:\/\/arxiv.org\/abs\/2203.14883"}],"container-title":["ACM Transactions on Modeling and Performance Evaluation of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3760772","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T11:44:29Z","timestamp":1758627869000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3760772"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,23]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1145\/3760772"],"URL":"https:\/\/doi.org\/10.1145\/3760772","relation":{},"ISSN":["2376-3639","2376-3647"],"issn-type":[{"type":"print","value":"2376-3639"},{"type":"electronic","value":"2376-3647"}],"subject":[],"published":{"date-parts":[[2025,9,23]]},"assertion":[{"value":"2023-07-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-28","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-23","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}