{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T01:32:24Z","timestamp":1769045544947,"version":"3.49.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,5]]},"abstract":"<jats:p>\n            Partitioning a large graph into smaller subgraphs by minimizing the number of cutting vertices and edges, namely cut size or replication factor, plays a crucial role in distributed graph processing tasks. However, many prior works have primarily focused on optimizing the cut size by considering only vertex balance or edge balance, leading to significant workload imbalance and consequently hindering the performance of downstream tasks. Therefore, in this paper, we address the dual-balanced graph partition problem that minimizes the cut size while simultaneously guaranteeing both vertex and edge balance. We propose a lightweight effective two-phase framework, namely fine-grained splitting and merging (FSM), which decomposes the graph into more and smaller partitions and then merges them. FSM offers the flexibility of integrating with various state-of-the-art single-balanced techniques. We develop two efficient algorithms\n            <jats:italic>Fast Merging and Precise Merging<\/jats:italic>\n            to enable trade-offs between computational efficiency and partitioning quality. Experimental results on large real-world graphs demonstrate that FSM achieves state-of-the-art cut size while maintaining dual balance. The runtime for downstream tasks PageRank, connected component, and diameter estimation, can be reduced by a large proportion, up to 9.43%, 11.35%, and 17.94%, respectively.\n          <\/jats:p>","DOI":"10.14778\/3665844.3665864","type":"journal-article","created":{"date-parts":[[2024,8,6]],"date-time":"2024-08-06T22:19:07Z","timestamp":1722982747000},"page":"2378-2391","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["FSM: A Fine-Grained Splitting and Merging Framework for Dual-Balanced Graph Partition"],"prefix":"10.14778","volume":"17","author":[{"given":"Chengjun","family":"Liu","sequence":"first","affiliation":[{"name":"School of Data Science, Fudan University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhuo","family":"Peng","sequence":"additional","affiliation":[{"name":"School of Data Science, Fudan University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weiguo","family":"Zheng","sequence":"additional","affiliation":[{"name":"School of Data Science, Fudan University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lei","family":"Zou","sequence":"additional","affiliation":[{"name":"Wangxuan Institute of Computer Technology, Peking University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,8,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/3324301.3324307"},{"key":"e_1_2_1_2_1","volume-title":"23rd International World Wide Web Conference, WWW '14","author":"Boldi Paolo","year":"2014","unstructured":"Paolo Boldi, Andrea Marino, Massimo Santini, and Sebastiano Vigna. 2014. BUb-iNG: massive crawling for the masses. In 23rd International World Wide Web Conference, WWW '14, Seoul, Republic of Korea, April 7--11, 2014, Companion Volume, Chin-Wan Chung, Andrei Z. Broder, Kyuseok Shim, and Torsten Suel (Eds.). ACM, 227--228. 10.1145\/2567948.2577304"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 20th International Conference on World Wide Web, WWW 2011","author":"Boldi Paolo","year":"2011","unstructured":"Paolo Boldi, Marco Rosa, Massimo Santini, and Sebastiano Vigna. 2011. Layered label propagation: a multiresolution coordinate-free ordering for compressing social networks. In Proceedings of the 20th International Conference on World Wide Web, WWW 2011, Hyderabad, India, March 28 - April 1, 2011, Sadagopan Srinivasan, Krithi Ramamritham, Arun Kumar, M. P. Ravindra, Elisa Bertino, and Ravi Kumar (Eds.). ACM, 587--596. 10.1145\/1963405.1963488"},{"key":"e_1_2_1_4_1","volume-title":"Proc. of the Thirteenth International World Wide Web Conference (WWW","author":"Boldi Paolo","year":"2004","unstructured":"Paolo Boldi and Sebastiano Vigna. 2004. The WebGraph Framework I: Compression Techniques. In Proc. of the Thirteenth International World Wide Web Conference (WWW 2004). ACM Press, Manhattan, USA, 595--601."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Bourse Florian","year":"2014","unstructured":"Florian Bourse, Marc Lelarge, and Milan Vojnovic. 2014. Balanced Graph Edge Partition. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (New York, New York, USA) (KDD '14). Association for Computing Machinery, New York, NY, USA, 1456--1465. 10.1145\/2623330.2623660"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the Tenth European Conference on Computer Systems","author":"Chen Rong","year":"2015","unstructured":"Rong Chen, Jiaxin Shi, Yanzhe Chen, and Haibo Chen. 2015. PowerLyra: differentiated graph computation and partitioning on skewed graphs. In Proceedings of the Tenth European Conference on Computer Systems (Bordeaux, France) (EuroSys '15). Association for Computing Machinery, New York, NY, USA, Article 1, 15 pages. 10.1145\/2741948.2741970"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043652.2043654"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00736-2"},{"key":"e_1_2_1_10_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1990","unstructured":"Michael R. Garey and David S. Johnson. 1990. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA."},{"key":"e_1_2_1_11_1","volume-title":"PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs","author":"Gonzalez Joseph E.","unstructured":"Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. 2012. PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs. In OSDI. USENIX Association, 17--30."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation","author":"Gonzalez Joseph E.","year":"2014","unstructured":"Joseph E. Gonzalez, Reynold S. Xin, Ankur Dave, Daniel Crankshaw, Michael J. Franklin, and Ion Stoica. 2014. GraphX: Graph Processing in a Distributed Dataflow Framework. In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation (Broomfield, CO) (OSDI'14). USENIX Association, USA, 599--613."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1609\/AAAI.V35I14.17464"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3358701.3358706"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2904483.2904486"},{"key":"e_1_2_1_17_1","volume-title":"GraphBuilder: Scalable Graph ETL Framework. In First International Workshop on Graph Data Management Experiences and Systems","author":"Jain Nilesh","unstructured":"Nilesh Jain, Guangdeng Liao, and Theodore L. Willke. 2013. GraphBuilder: Scalable Graph ETL Framework. In First International Workshop on Graph Data Management Experiences and Systems (New York, New York) (GRADES '13). Association for Computing Machinery, New York, NY, USA, Article 4, 6 pages. 10.1145\/2484425.2484429"},{"key":"e_1_2_1_18_1","volume-title":"Christos Faloutsos, and Jure Leskovec.","author":"Kang U.","year":"2008","unstructured":"U. Kang, Charalampos Tsourakakis, Ana Paula Appel, Christos Faloutsos, and Jure Leskovec. 2008. HADI: Fast Diameter Estimation and Mining in Massive Graphs with Hadoop. Journal Acm Transactions on Knowledge Discovery from Data (2008)."},{"key":"e_1_2_1_19_1","first-page":"1","article-title":"A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs","volume":"20","author":"Karypis George","year":"1998","unstructured":"George Karypis and Vipin Kumar. 1998. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM J. Sci. Comput. 20, 1 (dec 1998), 359--392.","journal-title":"SIAM J. Sci. Comput."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 8th ACM European Conference on Computer Systems (Prague, Czech Republic) (EuroSys '13)","author":"Khayyat Zuhair","year":"2013","unstructured":"Zuhair Khayyat, Karim Awara, Amani Alonazi, Hani Jamjoom, Dan Williams, and Panos Kalnis. 2013. Mizan: A System for Dynamic Load Balancing in Large-Scale Graph Processing. In Proceedings of the 8th ACM European Conference on Computer Systems (Prague, Czech Republic) (EuroSys '13). Association for Computing Machinery, New York, NY, USA, 169--182. 10.1145\/2465351.2465369"},{"key":"e_1_2_1_21_1","volume-title":"Clustering-based Partitioning for Large Web Graphs. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). 593--606","author":"Kong Deyu","year":"2022","unstructured":"Deyu Kong, Xike Xie, and Zhuoxu Zhang. 2022. Clustering-based Partitioning for Large Web Graphs. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). 593--606. 10.1109\/ICDE53745.2022.00049"},{"key":"e_1_2_1_22_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3324301.3324306"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 51st International Conference on Parallel Processing","author":"Lin Shuai","year":"2023","unstructured":"Shuai Lin, Rui Wang, Yongkun Li, Yinlong Xu, John C.S. Lui, Fei Chen, Pengcheng Wang, and Lei Han. 2023. Towards Fast Large-Scale Graph Analysis via Two-Dimensional Balanced Partitioning. In Proceedings of the 51st International Conference on Parallel Processing (Bordeaux, France) (ICPP '22). Association for Computing Machinery, New York, NY, USA, Article 37, 11 pages. 10.1145\/3545008.3545060"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data","author":"Malewicz Grzegorz","year":"2010","unstructured":"Grzegorz Malewicz, Matthew H. Austern, Aart J.C Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. 2010. Pregel: A System for Large-Scale Graph Processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data (Indianapolis, Indiana, USA) (SIGMOD '10). Association for Computing Machinery, New York, NY, USA, 135--146. 10.1145\/1807167.1807184"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 2021 International Conference on Management of Data","author":"Mayer Ruben","year":"2021","unstructured":"Ruben Mayer and Hans-Arno Jacobsen. 2021. Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints. In Proceedings of the 2021 International Conference on Management of Data (Virtual Event, China) (SIGMOD '21). Association for Computing Machinery, New York, NY, USA, 1289--1302. 10.1145\/3448016.3457300"},{"key":"e_1_2_1_27_1","volume-title":"2022 IEEE 38th International Conference on Data Engineering (ICDE). 2629--2642","author":"Mayer Ruben","year":"2022","unstructured":"Ruben Mayer, Kamil Orujzade, and Hans-Arno Jacobsen. 2022. Out-of-Core Edge Partitioning at Linear Run-Time. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). 2629--2642. 10.1109\/ICDE53745.2022.00242"},{"key":"e_1_2_1_28_1","volume-title":"Shahin Kamali Khuzaima Daudjee, and Lei Chen","author":"Nicoara Daniel","year":"2015","unstructured":"Daniel Nicoara, Shahin Kamali Khuzaima Daudjee, and Lei Chen. 2015. Hermes: Dynamic Partitioning for Distributed Social Network Graph Databases. (2015)."},{"key":"e_1_2_1_29_1","volume-title":"The PageRank Citation Ranking: Bringing Order to the Web. Stanford Digital Libraries Working Paper","author":"Page Lawrence","year":"1998","unstructured":"Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1998. The PageRank Citation Ranking: Bringing Order to the Web. Stanford Digital Libraries Working Paper (1998)."},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the International Conference and Exhibition on High-Performance Computing and Networking (HPCN Europe","author":"Pellegrini Fran\u00e7ois","year":"1996","unstructured":"Fran\u00e7ois Pellegrini and Jean Roman. 1996. SCOTCH: A Software Package for Static Mapping by Dual Recursive Bipartitioning of Process and Architecture Graphs. In Proceedings of the International Conference and Exhibition on High-Performance Computing and Networking (HPCN Europe 1996). Springer-Verlag, Berlin, Heidelberg, 493--498."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 24th ACM International on Conference on Information and Knowledge Management","author":"Petroni Fabio","year":"2015","unstructured":"Fabio Petroni, Leonardo Querzoni, Khuzaima Daudjee, Shahin Kamali, and Giorgio Iacoboni. 2015. HDRF: Stream-Based Partitioning for Power-Law Graphs. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management (Melbourne, Australia) (CIKM '15). Association for Computing Machinery, New York, NY, USA, 243--252. 10.1145\/2806416.2806424"},{"key":"e_1_2_1_32_1","volume-title":"Ahmed","author":"Rossi Ryan A.","year":"2015","unstructured":"Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. In AAAI. https:\/\/networkrepository.com"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 19th European Conference on Algorithms","author":"Sanders Peter","year":"2011","unstructured":"Peter Sanders and Christian Schulz. 2011. Engineering Multilevel Graph Partitioning Algorithms. In Proceedings of the 19th European Conference on Algorithms (Saarbr\u00fccken, Germany) (ESA'11). Springer-Verlag, Berlin, Heidelberg, 469--480."},{"key":"e_1_2_1_34_1","volume-title":"2013 IEEE 29th International Conference on Data Engineering (ICDE). 553--564","author":"Shang Zechao","year":"2013","unstructured":"Zechao Shang and Jeffrey Xu Yu. 2013. Catch the Wind: Graph workload balancing on cloud. In 2013 IEEE 29th International Conference on Data Engineering (ICDE). 553--564. 10.1109\/ICDE.2013.6544855"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Stanton Isabelle","year":"2012","unstructured":"Isabelle Stanton and Gabriel Kliot. 2012. Streaming Graph Partitioning for Large Distributed Graphs. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Beijing, China) (KDD '12). Association for Computing Machinery, New York, NY, USA, 1222--1230. 10.1145\/2339530.2339722"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 7th ACM International Conference on Web Search and Data Mining","author":"Tsourakakis Charalampos","year":"2014","unstructured":"Charalampos Tsourakakis, Christos Gkantsidis, Bozidar Radunovic, and Milan Vojnovic. 2014. FENNEL: Streaming Graph Partitioning for Massive Scale Graphs. In Proceedings of the 7th ACM International Conference on Web Search and Data Mining (New York, New York, USA) (WSDM '14). Association for Computing Machinery, New York, NY, USA, 333--342. 10.1145\/2556195.2556213"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","first-page":"493","DOI":"10.14778\/3055540.3055543","article-title":"An experimental comparison of partitioning strategies in distributed graph processing","volume":"10","author":"Verma Shiv","year":"2017","unstructured":"Shiv Verma, Luke M. Leslie, Yosub Shin, and Indranil Gupta. 2017. An experimental comparison of partitioning strategies in distributed graph processing. Proceedings of the Vldb Endowment 10, 5 (2017), 493--504.","journal-title":"Proceedings of the Vldb Endowment"},{"key":"e_1_2_1_38_1","volume-title":"Distributed Power-law Graph Computing: Theoretical and Empirical Analysis. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014","author":"Xie Cong","year":"2014","unstructured":"Cong Xie, Ling Yan, Wu-Jun Li, and Zhihua Zhang. 2014. Distributed Power-law Graph Computing: Theoretical and Empirical Analysis. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8--13 2014, Montreal, Quebec, Canada. 1673--1681. https:\/\/proceedings.neurips.cc\/paper\/2014\/hash\/67d16d00201083a2b118dd5128dd6f59-Abstract.html"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Halifax, NS, Canada) (KDD '17)","author":"Zhang Chenzi","year":"2017","unstructured":"Chenzi Zhang, Fan Wei, Qin Liu, Zhihao Gavin Tang, and Zhenguo Li. 2017. Graph Edge Partitioning via Neighborhood Heuristic. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Halifax, NS, Canada) (KDD '17). Association for Computing Machinery, New York, NY, USA, 605--614. 10.1145\/3097983.3098033"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","unstructured":"Shuai Zhang Zite Jiang Xingzhong Hou Zhen Guan Mengting Yuan and Haihang You. 2021. An Efficient and Balanced Graph Partition Algorithm for the Subgraph-Centric Programming Model on Large-scale Power-law Graphs. In 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS). 68--78. 10.1109\/ICDCS51616.2021.00016","DOI":"10.1109\/ICDCS51616.2021.00016"},{"key":"e_1_2_1_41_1","volume-title":"2016 IEEE 32nd International Conference on Data Engineering (ICDE). 121--132","author":"Zheng Angen","year":"2016","unstructured":"Angen Zheng, Alexandros Labrinidis, and Panos K. Chrysanthis. 2016. Planar: Parallel lightweight architecture-aware adaptive graph repartitioning. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE). 121--132. 10.1109\/ICDE.2016.7498234"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3665844.3665864","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,6]],"date-time":"2024-08-06T22:23:50Z","timestamp":1722983030000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3665844.3665864"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5]]},"references-count":41,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["10.14778\/3665844.3665864"],"URL":"https:\/\/doi.org\/10.14778\/3665844.3665864","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,5]]},"assertion":[{"value":"2024-08-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}