{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T15:34:03Z","timestamp":1784388843382,"version":"3.55.0"},"reference-count":93,"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":[[2025,5]]},"abstract":"<jats:p>k-way edge based partitioning algorithms for processing large streaming graphs, such as social networks and web crawls, assign each arriving edge to one of the k partitions. This can result in vertices being replicated on multiple partitions. Typically, such partitioning algorithms aim to balance the edge counts across partitions while minimizing the vertex replication. However, such objectives ignore the community structure inherently embedded in the graph, which is an important quality metric for clustering and graph mining applications that subsequently operate on the partitions. To address this gap, we propose a novel optimization goal to maximize the number of local triangles in the partitions as an additional objective. Triangle count is an effective metric to measure the conservation of community structure. Further, we propose TriParts a family of heuristics for online partitioning over an edge stream. They use three complementary state data structures: Bloom Filters, Triangle Map and High degree Map. Each state adds tangible value to meet our objectives. We validate TriParts on six diverse real world graphs with up to 1.6B edges and varying triangle densities. Our best heuristic outperforms the state-of-the-art DBH and HDRF streaming graph partitioners on the triangle-count metric by up to 4\u20138.3x while maintaining competitive vertex replication factor and edge-balancing. We achieve an ingest rate of 500k edges\/sec on a 16 node cluster. We also offer detailed results on the configuration parameters, scalability and overheads of TriParts, and its practical benefits for distributed graph analytics.<\/jats:p>","DOI":"10.14778\/3746405.3746423","type":"journal-article","created":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T17:06:20Z","timestamp":1756919180000},"page":"2992-3006","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Triparts: Scalable Streaming Graph Partitioning to Enhance Community Structure"],"prefix":"10.14778","volume":"18","author":[{"given":"Ruchi","family":"Bhoot","sequence":"first","affiliation":[{"name":"Indian Institute of Science (IISc), Bangalore, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tuhin","family":"Khare","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manoj","family":"Agarwal","sequence":"additional","affiliation":[{"name":"GiKA.AI, Bangalore, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Siddharth","family":"Jaiswal","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology (IIT), Kharagpur, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yogesh","family":"Simmhan","sequence":"additional","affiliation":[{"name":"Indian Institute of Science (IISc), Bangalore, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,9,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236208"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236208"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2336664.2336671"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2020.3001645"},{"key":"e_1_2_1_5_1","volume-title":"Evans","author":"Amunts Katrin","year":"2013","unstructured":"Katrin Amunts, Claude Lepage, Louis Borgeat, Hartmut Mohlberg, Timo Dickscheid, Marc-\u00c9tienne Rousseau, Sebastian Bludau, Pierre-Louis Bazin, Lindsay B. Lewis, Ana-Maria Oros-Peusquens, Nadim J. Shah, Thomas Lippert, Karl Zilles, and Alan C. Evans. 2013. BigBrain: An Ultrahigh-Resolution 3D Human Brain Model. Science 340, 6139 (2013), 1472\u20131475."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1350-7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-76298-0_52"},{"key":"e_1_2_1_8_1","volume-title":"Technical Report 2007.08869. https:\/\/arxiv.org\/abs\/2007.08869","author":"Banerjee Arindam","year":"2021","unstructured":"Arindam Banerjee and D. Yogeshwaran. 2021. Edge ideals of Erd\u00f6s-R\u00e9nyi random graphs: Linear resolution, unmixedness and regularity. Technical Report 2007.08869. https:\/\/arxiv.org\/abs\/2007.08869"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/widm.1178"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/WODES.2016.7497841"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2024.3471574"},{"key":"e_1_2_1_13_1","unstructured":"Ivan A. Bliznets and Nikolai Karpov. 2017. Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters. Technical Report 6. 6:1\u20136:14 pages."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623660"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1609\/icwsm.v4i1.14033"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3298989"},{"key":"e_1_2_1_17_1","volume-title":"PT-Scotch: A tool for efficient parallel graph ordering. Parallel computing 34, 6\u20138","author":"Chevalier C\u00e9dric","year":"2008","unstructured":"C\u00e9dric Chevalier and Fran\u00e7ois Pellegrini. 2008. PT-Scotch: A tool for efficient parallel graph ordering. Parallel computing 34, 6\u20138 (2008), 318\u2013331."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Adil Chhabra Florian Kurpicz Christian Schulz Dominik Schweisgut and Daniel Seemaier. 2024. Partitioning Trillion Edge Graphs on Edge Devices. Technical Report. https:\/\/arxiv.org\/abs\/2410.07732","DOI":"10.1137\/1.9781611978759.6"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824077"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382577.2382581"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432624"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434393"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2013.107"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872518.2890525"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389745"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389142"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2019.122058"},{"key":"e_1_2_1_28_1","article-title":"Graph partitioning and sparse matrix ordering using reinforcement learning and graph neural networks","volume":"23","author":"Gatti Alice","year":"2022","unstructured":"Alice Gatti, Zhixiong Hu, Tess Smidt, Esmond G. Ng, and Pieter Ghysels. 2022. Graph partitioning and sparse matrix ordering using reinforcement learning and graph neural networks. J. Mach. Learn. Res. 23, 1 (2022), 28 pages.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_2_1_31_1","volume-title":"PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs. In 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12)","author":"Gonzalez Joseph E.","year":"2012","unstructured":"Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. 2012. PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs. In 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12). 17\u201330. https:\/\/www.usenix.org\/conference\/osdi12\/technical-sessions\/presentation\/gonzalez"},{"key":"e_1_2_1_32_1","volume-title":"10th USENIX Conference on Operating Systems Design and Implementation. 17\u201330","author":"Gonzalez Joseph E.","year":"2012","unstructured":"Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. 2012. PowerGraph: distributed graph-parallel computation on natural graphs. In 10th USENIX Conference on Operating Systems Design and Implementation. 17\u201330."},{"key":"e_1_2_1_33_1","volume-title":"USENIX Conference on Operating Systems Design and Implementation. 599\u2013613","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 USENIX Conference on Operating Systems Design and Implementation. 599\u2013613."},{"key":"e_1_2_1_34_1","volume-title":"CUTTANA: Scalable Graph Partitioning for Faster Distributed Graph Databases and Analytics. Technical Report. https:\/\/arxiv.org\/abs\/2312.08356","author":"Hajidehi Milad Rezaei","year":"2024","unstructured":"Milad Rezaei Hajidehi, Sraavan Sridhar, and Margo Seltzer. 2024. CUTTANA: Scalable Graph Partitioning for Faster Distributed Graph Databases and Analytics. Technical Report. https:\/\/arxiv.org\/abs\/2312.08356"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.phpro.2011.05.051"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2777598.2777604"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00142-3"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2019.00054"},{"key":"e_1_2_1_39_1","volume-title":"Statistical, nonlinear, and soft matter physics 65 2 Pt 2","author":"Holme Petter","year":"2001","unstructured":"Petter Holme and Beom Jun Kim. 2001. Growing scale-free networks with tunable clustering. Physical review. E, Statistical, nonlinear, and soft matter physics 65 2 Pt 2 (2001), 026107. https:\/\/api.semanticscholar.org\/CorpusID:4643442"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/2904483.2904486"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2960414.2960419"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2960414.2960419"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484425.2484429"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/305219.305248"},{"key":"e_1_2_1_45_1","first-page":"315","article-title":"Parmetis parallel graph partitioning and sparse matrix ordering library, In https:\/\/api.semanticscholar.org\/CorpusID:9818727","volume":"1","author":"Karypis George","year":"1997","unstructured":"George Karypis, Kirk Schloegel, and Vipin Kumar. 1997. Parmetis parallel graph partitioning and sparse matrix ordering library, In https:\/\/api.semanticscholar.org\/CorpusID:9818727. University of Minnesota 1, 1 315\u2013320.","journal-title":"University of Minnesota"},{"key":"e_1_2_1_46_1","volume-title":"An efficient heuristic procedure for partitioning graphs. The Bell system technical journal 49, 2","author":"Kernighan Brian W","year":"1970","unstructured":"Brian W Kernighan and Shen Lin. 1970. An efficient heuristic procedure for partitioning graphs. The Bell system technical journal 49, 2 (1970), 291\u2013307."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465369"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0037-7"},{"key":"e_1_2_1_49_1","unstructured":"Christine Klymko David Gleich and Tamara G Kolda. 2014. Using triangles to improve community detection in directed networks. Technical Report. arxiv pages. https:\/\/arxiv.org\/abs\/1404.5874"},{"key":"e_1_2_1_50_1","volume-title":"The art of computer programming","author":"Knuth Donald E.","unstructured":"Donald E. Knuth. 1997. The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms.","edition":"3"},{"key":"e_1_2_1_51_1","volume-title":"Clustering-based Partitioning for Large Web Graphs. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). 593\u2013606","author":"Kong Deyu","year":"2022","unstructured":"Deyu Kong. 2022. Clustering-based Partitioning for Large Web Graphs. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). 593\u2013606. https:\/\/github.com\/USTC-DataDarknessLab\/GraphPartitioning\/tree\/main\/CLUGP"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00049"},{"key":"e_1_2_1_53_1","volume-title":"United States. Department of Energy. Office of Scientific, and Technical Information","author":"Los Alamos National Laboratory","year":"2008","unstructured":"Los Alamos National Laboratory, United States. Department of Energy. Office of Scientific, and Technical Information. 2008. Exploring Network Structure, Dynamics, and Function Using Networkx. https:\/\/books.google.co.in\/books?id=yOiJAQAACAAJ"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2013.50"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/2938782.2938865"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2025.3547976"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129111"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3084451"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3449989"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_62_1","unstructured":"Anna Mastikhina Oleg Senkevich Dmitry Sirotkin Danila Demin and Stanislav Moiseev. 2024. An improvement of degree-based hashing (DBH) graph partition method using a novel metric. Technical Report. 1\u201315 pages. https:\/\/api.semanticscholar.org\/CorpusID:269043059"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2018.00072"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2018.00072"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00242"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00242"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2671868"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339540"},{"key":"e_1_2_1_69_1","volume-title":"GAP: Generalizable Approximate Graph Partitioning Framework. Technical Report. https:\/\/api.semanticscholar.org\/CorpusID:67855909","author":"Nazi Azade","year":"2019","unstructured":"Azade Nazi, Will Hang, Anna Goldie, Sujith Ravi, and Azalia Mirhoseini. 2019. GAP: Generalizable Approximate Graph Partitioning Framework. Technical Report. https:\/\/api.semanticscholar.org\/CorpusID:67855909"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2012.12.001"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0601602103"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.066133"},{"key":"e_1_2_1_73_1","volume-title":"24th ACM international on conference on information and knowledge management. 243\u2013252","author":"Petroni Fabio","year":"2015","unstructured":"Fabio Petroni. 2015. VGP : Vertex-cut balanced Graph Partitioning. In 24th ACM international on conference on information and knowledge management. 243\u2013252. https:\/\/github.com\/fabiopetroni\/VGP"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806424"},{"key":"e_1_2_1_75_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. all. http:\/\/networkrepository.com\/road-road-usa.php"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/2740908.2744715"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975499.17"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09873-9_38"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339722"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589334.3645609"},{"key":"e_1_2_1_81_1","unstructured":"Rahul Swamy Douglas M. King and Sheldon H. Jacobson. 2024. Highly Connected Graph Partitioning: Exact Formulation and Solution Methods. Technical Report. https:\/\/arxiv.org\/abs\/2406.08329"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735507"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556213"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1109\/tetci.2019.2952908"},{"key":"e_1_2_1_87_1","volume-title":"27th International Conference on Neural Information Processing Systems -","volume":"1","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 27th International Conference on Neural Information Processing Systems - Volume 1. 1673\u20131681."},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2023.120971"},{"key":"e_1_2_1_89_1","doi-asserted-by":"crossref","unstructured":"Jaewon Yang and Jure Leskovec. 2012. Defining and Evaluating Network Communities based on Ground-truth. Technical Report. https:\/\/snap.stanford.edu\/data\/com-Orkut.html","DOI":"10.1145\/2350190.2350193"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3093240"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCGRID.2018.00033"},{"key":"e_1_2_1_92_1","unstructured":"Da Zheng Chao Ma Minjie Wang Jinjing Zhou Qidong Su Xiang Song Quan Gan Zheng Zhang and George Karypis. 2021. DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs. Technical Report. https:\/\/arxiv.org\/abs\/2010.05337"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1145\/3533702.3534920"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3746405.3746423","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T19:50:38Z","timestamp":1757015438000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3746405.3746423"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5]]},"references-count":93,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["10.14778\/3746405.3746423"],"URL":"https:\/\/doi.org\/10.14778\/3746405.3746423","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,5]]},"assertion":[{"value":"2025-09-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}