{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T01:22:10Z","timestamp":1769044930115,"version":"3.49.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T00:00:00Z","timestamp":1687219200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>\n            Graph optimization problems (such as minimum vertex cover, maximum cut, traveling salesman problems) appear in many fields including social sciences, power systems, chemistry, and bioinformatics. Recently, deep reinforcement learning (DRL) has shown success in automatically learning good heuristics to solve graph optimization problems. However, the existing RL systems either do not support graph RL environments or do not support multiple or many GPUs in a distributed setting. This has compromised the ability of reinforcement learning in solving large-scale graph optimization problems due to lack of parallelization and high scalability. To address the challenges of parallelization and scalability, we develop\n            <jats:italic>RL4GO<\/jats:italic>\n            , a high-performance distributed-GPU DRL framework for solving graph optimization problems. RL4GO focuses on a class of computationally demanding RL problems, where both the RL environment and policy model are highly computation intensive. Traditional reinforcement learning systems often assume either the RL environment is of low time complexity or the policy model is small.\n          <\/jats:p>\n          <jats:p>\n            In this work, we distribute large-scale graphs across distributed GPUs and use the spatial parallelism and data parallelism to achieve scalable performance. We compare and analyze the performance of the spatial parallelism and data parallelism and show their differences. To support graph neural network (GNN) layers that take as input data samples partitioned across distributed GPUs, we design parallel mathematical kernels to perform operations on distributed 3D sparse and 3D dense tensors. To handle costly RL environments, we design a parallel graph environment to scale up all RL-environment-related operations. By combining the scalable GNN layers with the scalable RL environment, we are able to develop high-performance RL4GO training and inference algorithms in parallel. Furthermore, we propose two optimization techniques\u2014replay buffer on-the-fly graph generation and adaptive multiple-node selection\u2014to minimize the spatial cost and accelerate reinforcement learning. This work also conducts in-depth analyses of parallel efficiency and memory cost and shows that the designed RL4GO algorithms are scalable on numerous distributed GPUs. Evaluations on large-scale graphs show that (1) RL4GO training and inference can achieve good parallel efficiency on 192 GPUs, (2) its training time can be 18 times faster than the state-of-the-art Gorila distributed RL framework\u00a0[\n            <jats:xref ref-type=\"bibr\">34<\/jats:xref>\n            ], and (3) its inference performance achieves a 26 times improvement over Gorila.\n          <\/jats:p>","DOI":"10.1145\/3589188","type":"journal-article","created":{"date-parts":[[2023,3,23]],"date-time":"2023-03-23T12:22:38Z","timestamp":1679574158000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A Distributed-GPU Deep Reinforcement Learning System for Solving Large Graph Optimization Problems"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2791-0031","authenticated-orcid":false,"given":"Weijian","family":"Zheng","sequence":"first","affiliation":[{"name":"Purdue University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6806-5108","authenticated-orcid":false,"given":"Dali","family":"Wang","sequence":"additional","affiliation":[{"name":"Oak Ridge National Laboratory, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7382-093X","authenticated-orcid":false,"given":"Fengguang","family":"Song","sequence":"additional","affiliation":[{"name":"Indiana University Purdue University Indianapolis, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-92040-5_19"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.025103"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.74.47"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i04.5723"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature08932"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1038\/nrn2575"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835934"},{"key":"e_1_3_1_9_2","volume-title":"Linear Programming","author":"Chvatal Vasek","year":"1983","unstructured":"Vasek Chvatal, Vaclav Chvatal. 1983. Linear Programming. Macmillan."},{"key":"e_1_3_1_10_2","first-page":"2702","volume-title":"International Conference on Machine Learning","author":"Dai Hanjun","year":"2016","unstructured":"Hanjun Dai, Bo Dai, and Le Song. 2016. Discriminative embeddings of latent variable models for structured data. In International Conference on Machine Learning. 2702\u20132711."},{"key":"e_1_3_1_11_2","first-page":"6348","volume-title":"Advances in Neural Information Processing Systems","author":"Dai Hanjun","year":"2017","unstructured":"Hanjun Dai, Elias Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. 2017. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems. 6348\u20136358."},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"issue":"1","key":"e_1_3_1_13_2","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s Paul","year":"1960","unstructured":"Paul Erd\u0151s and Alfr\u00e9d R\u00e9nyi. 1960. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci 5, 1 (1960), 17\u201360.","journal-title":"Publ. Math. Inst. Hung. Acad. Sci"},{"key":"e_1_3_1_14_2","first-page":"1407","volume-title":"International Conference on Machine Learning","author":"Espeholt Lasse","year":"2018","unstructured":"Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, Iain Dunning, et\u00a0al. 2018. IMPALA: Scalable distributed deep-RL with importance weighted actor-learner architectures. In International Conference on Machine Learning. PMLR, 1407\u20131416."},{"key":"e_1_3_1_15_2","unstructured":"Matthias Fey and Jan Eric Lenssen. 2019. Fast graph representation learning with PyTorch Geometric. (2019). https:\/\/arxiv.org\/abs\/1903.02428."},{"key":"e_1_3_1_16_2","unstructured":"Yoav Goldberg and Omer Levy. 2014. word2vec Explained: Deriving Mikolov et\u00a0al.\u2019s negative-sampling word-embedding method. (2014). https:\/\/arxiv.org\/pdf\/1402.3722."},{"key":"e_1_3_1_17_2","unstructured":"Graph Nets. 2019. https:\/\/github.com\/deepmind\/graph_nets."},{"key":"e_1_3_1_18_2","volume-title":"Exploring Network Structure, Dynamics, and Function Using NetworkX","author":"Hagberg Aric","year":"2008","unstructured":"Aric Hagberg, Pieter Swart, and Daniel S. Chult. 2008. Exploring Network Structure, Dynamics, and Function Using NetworkX. Technical Report. Los Alamos National Lab (LANL), Los Alamos, NM."},{"key":"e_1_3_1_19_2","unstructured":"Matt Hoffman Bobak Shahriari John Aslanides Gabriel Barth-Maron Feryal Behbahani Tamara Norman Abbas Abdolmaleki Albin Cassirer Fan Yang Kate Baumli Sarah Henderson Alex Novikov Sergio G\u00f3mez Colmenarejo Serkan Cabi Caglar Gulcehre Tom Le Paine Andrew Cowie Ziyu Wang Bilal Piot and Nando de Freitas. 2020. Acme: A Research Framework for Distributed Reinforcement Learning. (2020). https:\/\/arxiv.org\/abs\/2006.00979."},{"key":"e_1_3_1_20_2","unstructured":"Christian D. Hubbs Hector D. Perez Owais Sarwar Nikolaos V. Sahinidis Ignacio E. Grossmann and John M. Wassick. 2020. OR-Gym: A Reinforcement Learning Library for Operations Research Problem. (2020). https:\/\/arxiv.org\/abs\/2008.06319."},{"key":"e_1_3_1_21_2","volume-title":"V20.1.0: User\u2019s Manual for CPLEX","author":"CPLEX IBM ILOG","year":"2020","unstructured":"IBM ILOG CPLEX. 2020. V20.1.0: User\u2019s Manual for CPLEX."},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.5555\/1622737.1622748"},{"key":"e_1_3_1_23_2","unstructured":"George Karypis and Vipin Kumar. 1995. METIS\u2013Unstructured graph partitioning and sparse matrix ordering system version 2.0. (1995)."},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1232722.1232727"},{"key":"e_1_3_1_26_2","unstructured":"Jure Leskovec and Andrej Krevl. 2023. SNAP Datasets: Stanford Large Network Dataset Collection. (Jan.2023). http:\/\/snap.stanford.edu\/data."},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_3_1_28_2","unstructured":"Eric Liang Richard Liaw Robert Nishihara Philipp Moritz Roy Fox Joseph Gonzalez Ken Goldberg and Ion Stoica. 2017. Ray RLlib: A composable and scalable reinforcement learning library. (2017). https:\/\/arxiv.org\/abs\/1712.09381."},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3419111.3421281"},{"key":"e_1_3_1_30_2","volume-title":"Exponential Random Graph Models for Social Networks: Theory, Methods, and Applications","author":"Lusher Dean","year":"2013","unstructured":"Dean Lusher, Johan Koskinen, and Garry Robins. 2013. Exponential Random Graph Models for Social Networks: Theory, Methods, and Applications. Vol. 35. Cambridge University Press."},{"key":"e_1_3_1_31_2","first-page":"443","volume-title":"2019 USENIX Annual Technical Conference","author":"Ma Lingxiao","year":"2019","unstructured":"Lingxiao Ma, Zhi Yang, Youshan Miao, Jilong Xue, Ming Wu, Lidong Zhou, and Yafei Dai. 2019. NeuGraph: Parallel deep neural network computation on large graphs. In 2019 USENIX Annual Technical Conference. 443\u2013458. https:\/\/www.usenix.org\/conference\/atc19\/presentation\/ma."},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2766462.2767755"},{"key":"e_1_3_1_33_2","volume-title":"Advances in Neural Information Processing Systems","author":"McAuley Julian J.","year":"2012","unstructured":"Julian J. McAuley and Jure Leskovec. 2012. Learning to discover social circles in ego networks. In Advances in Neural Information Processing Systems, Vol. 25."},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/tnn.2008.2010350"},{"key":"e_1_3_1_35_2","unstructured":"Arun Nair Praveen Srinivasan Sam Blackwell Cagdas Alcicek Rory Fearon Alessandro De Maria Vedavyas Panneershelvam Mustafa Suleyman Charles Beattie Stig Petersen et\u00a0al. 2015. Massively parallel methods for deep reinforcement learning. (2015). https:\/\/arxiv.org\/abs\/1507.04296."},{"key":"e_1_3_1_36_2","unstructured":"PaddlePaddle PARL. 2020. https:\/\/github.com\/PaddlePaddle\/PARL."},{"key":"e_1_3_1_37_2","first-page":"8026","volume-title":"Advances in Neural Information Processing Systems","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 Advances in Neural Information Processing Systems. 8026\u20138037."},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_3_1_39_2","unstructured":"Antoine Prouvost Justin Dumouchelle Lara Scavuzzo Maxime Gasse Didier Ch\u00e9telat and Andrea Lodi. 2020. Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solvers. (2020). https:\/\/arxiv.org\/abs\/2011.06069."},{"key":"e_1_3_1_40_2","first-page":"9367","volume-title":"Proceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research)","volume":"119","author":"Tang Yunhao","year":"2020","unstructured":"Yunhao Tang, Shipra Agrawal, and Yuri Faenza. 2020. Reinforcement learning for integer programming: Learning to cut. In Proceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research), Vol. 119. PMLR, 9367\u20139376."},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1177894"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1201\/9781315139111"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.5555\/3433701.3433794"},{"key":"e_1_3_1_44_2","unstructured":"Minjie Wang Lingfan Yu Da Zheng Quan Gan Yu Gai Zihao Ye Mufei Li Jinjing Zhou Qi Huang Chao Ma et\u00a0al. 2019. Deep graph library: Towards efficient and scalable deep learning on graphs. (2019). https:\/\/arxiv.org\/abs\/1909.01315."},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2020.2978386"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2017.330"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3340404"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/1935826.1935863"},{"key":"e_1_3_1_49_2","article-title":"Design space for graph neural networks","author":"You Jiaxuan","year":"2020","unstructured":"Jiaxuan You, Zhitao Ying, and Jure Leskovec. 2020. Design space for graph neural networks. Advances in Neural Information Processing Systems (2020).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_1_50_2","first-page":"36","volume-title":"2020 IEEE\/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3\u201920)","author":"Zheng Da","year":"2020","unstructured":"Da Zheng, Chao Ma, Minjie Wang, Jinjing Zhou, Qidong Su, Xiang Song, Quan Gan, Zheng Zhang, and George Karypis. 2020. DistDGL: Distributed graph neural network training for billion-scale graphs. In 2020 IEEE\/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3\u201920). IEEE, 36\u201344."},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-50426-7_33"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589188","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589188","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:53Z","timestamp":1750182533000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589188"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,20]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1145\/3589188"],"URL":"https:\/\/doi.org\/10.1145\/3589188","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,20]]},"assertion":[{"value":"2022-09-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-22","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}