{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T10:02:32Z","timestamp":1769076152341,"version":"3.49.0"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["No.61772492, 62072428"],"award-info":[{"award-number":["No.61772492, 62072428"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>In the realm of distributed systems tasked with managing and processing large-scale graph-structured data, optimizing graph partitioning stands as a pivotal challenge. The primary goal is to minimize communication overhead and runtime cost. However, alongside the computational complexity associated with optimal graph partitioning, a critical factor to consider is memory overhead. Real-world graphs often reach colossal sizes, making it impractical and economically unviable to load the entire graph into memory for partitioning. This is also a fundamental premise in distributed graph processing, where accommodating a graph with non-distributed systems is unattainable. Currently, existing streaming partitioning algorithms exhibit a skew-oblivious nature, yielding satisfactory partitioning results exclusively for specific graph types. In this paper, we propose a novel streaming partitioning algorithm, the Skewness-aware Vertex-cut Partitioner (S5P ), designed to leverage the skewness characteristics of real graphs for achieving high-quality partitioning. S5P offers high partitioning quality by segregating the graph's edge set into two subsets, head and tail sets. Following processing by a skewness-aware clustering algorithm, these two subsets subsequently undergo a Stackelberg graph game. Our extensive evaluations conducted on substantial real-world and synthetic graphs demonstrate that, in all instances, the partitioning quality of S5P surpasses that of existing streaming partitioning algorithms, operating within the same load balance constraints. For example, S5P can bring up to a 51% improvement in partitioning quality compared to the top partitioner among the baselines. Lastly, we showcase that the implementation of S5P results in up to an 81% reduction in communication cost and a 130% increase in runtime efficiency for distributed graph processing tasks on PowerGraph.<\/jats:p>","DOI":"10.1145\/3654965","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-27","source":"Crossref","is-referenced-by-count":9,"title":["Play like a Vertex: A Stackelberg Game Approach for Streaming Graph Partitioning"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6286-8679","authenticated-orcid":false,"given":"Zezhong","family":"Ding","sequence":"first","affiliation":[{"name":"University of Science and Technology of China &amp; Data Darkness Lab, MIRACLE Center, Suzhou Institute for Advanced Research, University of Science and Technology of China, Hefei, Anhui, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-0572-5479","authenticated-orcid":false,"given":"Yongan","family":"Xiang","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China &amp; Data Darkness Lab, MIRACLE Center, Suzhou Institute for Advanced Research, University of Science and Technology of China, Hefei, Anhui, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-5738-985X","authenticated-orcid":false,"given":"Shangyou","family":"Wang","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China &amp; Data Darkness Lab, MIRACLE Center, Suzhou Institute for Advanced Research, University of Science and Technology of China, Hefei, Anhui, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5290-5408","authenticated-orcid":false,"given":"Xike","family":"Xie","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China &amp; Data Darkness Lab, MIRACLE Center, Suzhou Institute for Advanced Research, University of Science and Technology of China, Anhui, Hefei, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6881-4444","authenticated-orcid":false,"given":"S. Kevin","family":"Zhou","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China &amp; MIRACLE Center, Suzhou Institute for Advanced Research, University of Science and Technology of China, Anhui, Hefei, China"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1038\/35019019"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749450"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3160017"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","unstructured":"Paolo Boldi Marco Rosa Massimo Santini and Sebastiano Vigna. 2011. Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. In WWW. 587--596. https:\/\/doi.org\/10.1145\/1963405.1963488","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","unstructured":"Paolo Boldi and Sebastiano Vigna. 2004. The webgraph framework I: compression techniques. In WWW. 595--602. https:\/\/doi.org\/10.1145\/988672.988752","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623660"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3298989"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-013-0749--1"},{"key":"e_1_2_1_10_1","volume-title":"Congressus Numerantium","author":"Cimikowski Robert J","year":"1992","unstructured":"Robert J Cimikowski. 1992. Graph planarization and skewness. Congressus Numerantium (1992), 21--21. https:\/\/citeseerx.ist.psu.edu\/document?repid=rep1&type=pdf&doi=98060fa1da8eb732b8095e6f731ae387671d9ebb"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.86.3682"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1080\/10691898.2011.11889611"},{"key":"e_1_2_1_14_1","volume-title":"Random graph dynamics","author":"Durrett Richard","unstructured":"Richard Durrett. 2007. Random graph dynamics. Vol. 200. Cambridge university press Cambridge. https:\/\/services.math.duke.edu\/ rtd\/RGD\/RGD.pdf"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1468-0297.2008.02185.x"},{"key":"e_1_2_1_16_1","volume-title":"Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem. Operations Research","author":"Fabio Furini","year":"2021","unstructured":"Furini Fabio, Ljubi\u0107 Ivana, Malaguti Enrico, and Paronuzzi Paolo. 2021. Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem. Operations Research (2021). https:\/\/api.semanticscholar.org\/CorpusID:219719610"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00736--2"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/05064299X"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/05064299X"},{"key":"e_1_2_1_20_1","volume-title":"the Price of Anarchy and the Fully Mixed Nash Equilibrium Conjecture","author":"Gairing Martin","unstructured":"Martin Gairing, Thomas L\u00fccking, Burkhard Monien, and Karsten Tiemann. 2005. Nash Equilibria, the Price of Anarchy and the Fully Mixed Nash Equilibrium Conjecture. In Automata, Languages and Programming, Lu\u00eds Caires, Giuseppe F. Italiano, Lu\u00eds Monteiro, Catuscia Palamidessi, and Moti Yung (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 51--65. https:\/\/link.springer.com\/chapter\/10.1007\/11523468_5"},{"key":"e_1_2_1_21_1","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 17--30. https:\/\/www.usenix.org\/conference\/osdi12\/technical-sessions\/presentation\/gonzalez"},{"key":"e_1_2_1_22_1","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 OSDI. 599--613. https:\/\/www.usenix.org\/conference\/osdi14\/technical-sessions\/presentation\/gonzalez"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00103"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1908.05855"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1712.04337"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210054"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2018.2890515"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484425.2484429"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583154"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00049"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","unstructured":"Haewoon Kwak Changhyun Lee Hosung Park and Sue Moon. 2010. What is Twitter a social network or a news media?. In WWW. 591--600. https:\/\/doi.org\/10.1145\/1772690.1772751","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_33_1","unstructured":"Alexei Ledenev. 2023. Pumba: chaos testing tool for Docker. https:\/\/github.com\/alexei-led\/pumba"},{"key":"e_1_2_1_34_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_35_1","doi-asserted-by":"publisher","unstructured":"Zemin Liu Trung-Kien Nguyen and Yuan Fang. 2021. Tail-GNN: Tail-Node Graph Neural Networks. In SIGKDD. ACM 1109--1119. https:\/\/doi.org\/10.1145\/3447548.3467276","DOI":"10.1145\/3447548.3467276"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","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 SIGMOD. ACM 135--146. https:\/\/doi.org\/10.1145\/1807167.1807184","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2018.00072"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","unstructured":"Ruben Mayer and Hans-Arno Jacobsen. 2021. Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints. In SIGMOD. ACM 1289--1302. https:\/\/doi.org\/10.1145\/3448016.3457300","DOI":"10.1145\/3448016.3457300"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00242"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3458817.3480856"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00185"},{"key":"e_1_2_1_43_1","volume-title":"Pareto distributions and Zipf's law. Contemporary physics","author":"Newman Mark EJ","year":"2005","unstructured":"Mark EJ Newman. 2005. Power laws, Pareto distributions and Zipf's law. Contemporary physics, Vol. 46, 5 (2005), 323--351. https:\/\/www.tandfonline.com\/doi\/abs\/10.1080\/00107510500052444"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064014"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806424"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00083"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2022.3226230"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1186\/s40537-019-0257--5"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","unstructured":"Nan Tang Qing Chen and Prasenjit Mitra. 2016. Graph Stream Summarization: From Big Bang to Big Crunch. In SIGMOD Fatma \u00d6zcan Georgia Koutrika and Sam Madden (Eds.). ACM 1481--1496. https:\/\/doi.org\/10.1145\/2882903.2915223","DOI":"10.1145\/2882903.2915223"},{"key":"e_1_2_1_50_1","volume-title":"Nam Sung Kim, and Yingyan Lin","author":"Wan Cheng","year":"2022","unstructured":"Cheng Wan, Youjie Li, Ang Li, Nam Sung Kim, and Yingyan Lin. 2022. BNS-GCN: Efficient Full-Graph Training of Graph Convolutional Networks with Partition-Parallelism and Random Boundary Node Sampling. In MLSys. mlsys.org. https:\/\/arxiv.org\/abs\/2203.10983"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2021.3101057"},{"key":"e_1_2_1_52_1","unstructured":"Cong Xie Ling Yan Wu-Jun Li and Zhihua Zhang. 2014. Distributed Power-law Graph Computing: Theoretical and Empirical Analysis. In NeurIPS. 1673--1681. https:\/\/dl.acm.org\/doi\/10.5555\/2968826.2969013"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733103"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00122"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2350190.2350193"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3575693.3575725"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098033"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2020.3020813"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352127"},{"key":"e_1_2_1_60_1","unstructured":"Xiaowei Zhu Wentao Han and Wenguang Chen. 2015. GridGraph: Large-Scale Graph Processing on a Single Machine Using 2-Level Hierarchical Partitioning. In ATC Shan Lu and Erik Riedel (Eds.). USENIX 375--386. https:\/\/dl.acm.org\/doi\/10.5555\/2813767.2813795"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3320127"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00246"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3533702.3534920"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654965","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654965","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:42:23Z","timestamp":1755787343000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654965"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":63,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654965"],"URL":"https:\/\/doi.org\/10.1145\/3654965","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}