{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,2]],"date-time":"2026-09-02T06:35:07Z","timestamp":1788330907548,"version":"build-2803163510"},"reference-count":48,"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"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>As the volume and ubiquity of graphs increase, a compact graph representation becomes essential for enabling efficient storage, transfer, and processing of graphs. Given a graph, the graph summarization problem asks for a compact representation that consists of a summary graph and the corrections, such that we can recreate the original graph from the representation exactly. Although this problem has been studied extensively, the existing works either trade summary compactness for efficiency, or vice versa. In particular, a well-known greedy method provides the most compact summary but incurs prohibitive time cost, while the state-of-the-art algorithms with practical overheads are more than 20% behind in summary compactness in our comparison with the greedy method.<\/jats:p>\n          <jats:p>This paper presents Mags and Mags-DM, two algorithms that aim to bridge the compactness and efficiency in graph summarization. Mags adopts the existing greedy paradigm that provides state-of-the-art compactness, but significantly improves its efficiency with a novel algorithm design. Meanwhile, Mags-DM follows a different paradigm with practical efficiency and overcomes its limitations in compactness. Moreover, both algorithms can support parallel computing environments. We evaluate Mags and Mags-DM on graphs up to billion-scale and demonstrate that they achieve state-of-the-art in both compactness and efficiency, rather than in one of them. Compared with the method that offers state-of-the-art compactness, Mags and Mags-DM have a small difference (&lt; 0.1% and &lt; 2.1%) in compactness. For efficiency, Mags is on average 11.1x and 4.2x faster than the two state-of-the-art algorithms with practical overheads, while Mags-DM can further reduce the running time by 13.4x compared with Mags. This shows that graph summarization algorithms can be made practical while still offering a compact summary.<\/jats:p>","DOI":"10.1145\/3654943","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-26","source":"Crossref","is-referenced-by-count":6,"title":["Graph Summarization: Compactness Meets Efficiency"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-7351-339X","authenticated-orcid":false,"given":"Deming","family":"Chu","sequence":"first","affiliation":[{"name":"University of New South Wales, Sydney, NSW, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0548-0130","authenticated-orcid":false,"given":"Fan","family":"Zhang","sequence":"additional","affiliation":[{"name":"Guangzhou University, Guangzhou, Guangdong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6572-2600","authenticated-orcid":false,"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney, NSW, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2674-1638","authenticated-orcid":false,"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Sydney, NSW, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2396-7225","authenticated-orcid":false,"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.3390\/a2031031"},{"key":"e_1_2_1_2_1","volume-title":"Scalable approximation algorithm for graph summarization","author":"Beg Maham Anwar","unstructured":"Maham Anwar Beg, Muhammad Ahmad, Arif Zaman, and Imdadullah Khan. 2018. Scalable approximation algorithm for graph summarization. In PAKDD. Springer, 502--514."},{"key":"e_1_2_1_3_1","volume-title":"Survey and taxonomy of lossless graph compression and space-efficient graph representations. arXiv preprint arXiv:1806.01799","author":"Besta Maciej","year":"2018","unstructured":"Maciej Besta and Torsten Hoefler. 2018. Survey and taxonomy of lossless graph compression and space-efficient graph representations. arXiv preprint arXiv:1806.01799 (2018)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","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.","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Paolo Boldi and Sebastiano Vigna. 2004. The webgraph framework I: compression techniques. In WWW. 595--602.","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1690"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Gregory Buehrer and Kumar Chellapilla. 2008. A scalable pattern mining approach to web graph compression with communities. In WSDM. 95--106.","DOI":"10.1145\/1341531.1341547"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0528-3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Flavio Chierichetti Ravi Kumar Silvio Lattanzi Michael Mitzenmacher Alessandro Panconesi and Prabhakar Raghavan. 2009. On compressing social networks. In KDD. 219--228.","DOI":"10.1145\/1557019.1557049"},{"key":"e_1_2_1_10_1","first-page":"1804","article-title":"One trillion edges: Graph processing at facebook-scale","volume":"8","author":"Ching Avery","year":"2015","unstructured":"Avery Ching, Sergey Edunov, Maja Kabiljo, Dionysios Logothetis, and Sambavi Muthukrishnan. 2015. One trillion edges: Graph processing at facebook-scale. VLDB, Vol. 8, 12 (2015), 1804--1815.","journal-title":"VLDB"},{"key":"e_1_2_1_11_1","volume-title":"Finding the best k in core decomposition: A time and space optimal solution","author":"Chu Deming","unstructured":"Deming Chu, Fan Zhang, Xuemin Lin, Wenjie Zhang, Ying Zhang, Yinglong Xia, and Chenyi Zhang. 2020. Finding the best k in core decomposition: A time and space optimal solution. In ICDE. IEEE, 685--696."},{"key":"e_1_2_1_12_1","volume-title":"Discovering and Maintaining the Best k in Core Decomposition. TKDE","author":"Chu Deming","year":"2024","unstructured":"Deming Chu, Fan Zhang, Xuemin Lin, Wenjie Zhang, Ying Zhang, Yinglong Xia, and Chenyi Zhang. 2024. Discovering and Maintaining the Best k in Core Decomposition. TKDE (2024)."},{"key":"e_1_2_1_13_1","volume-title":"Hierarchical core decomposition in parallel: From construction to subgraph search","author":"Chu Deming","unstructured":"Deming Chu, Fan Zhang, Wenjie Zhang, Xuemin Lin, and Ying Zhang. 2022. Hierarchical core decomposition in parallel: From construction to subgraph search. In ICDE. IEEE, 1138--1151."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Laxman Dhulipala Igor Kabiljo Brian Karrer Giuseppe Ottaviano Sergey Pupyrev and Alon Shalita. 2016. Compressing graphs and indexes with recursive graph bisection. In KDD. 1535--1544.","DOI":"10.1145\/2939672.2939862"},{"key":"e_1_2_1_15_1","first-page":"977","article-title":"Scalable summarization of data graphs","volume":"8","author":"Duan Songyun","year":"2015","unstructured":"Songyun Duan, Achille Belly Fokoue-Nkoutche, Anastasios Kementsietsidis, Wangchao Le, Feifei Li, and Kavitha Srinivas. 2015. Scalable summarization of data graphs. US Patent 8,977,650.","journal-title":"US Patent"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMI.2020.3002417"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Wenfei Fan Yuanhao Li Muyang Liu and Can Lu. 2021. Making graphs compact by lossless contraction. In SIGMOD. 472--484.","DOI":"10.1145\/3448016.3452797"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.09.031"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. In STOC. 604--613.","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3494561"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-015-0454-9"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Jihoon Ko Yunbum Kook and Kijung Shin. 2020. Incremental lossless graph summarization. In KDD. 317--327.","DOI":"10.1145\/3394486.3403074"},{"key":"e_1_2_1_23_1","volume-title":"Vog: Summarizing and understanding large graphs","author":"Koutra Danai","year":"2014","unstructured":"Danai Koutra, U Kang, Jilles Vreeken, and Christos Faloutsos. 2014. Vog: Summarizing and understanding large graphs. In ICDM. SIAM, 91--99."},{"key":"e_1_2_1_24_1","volume-title":"Ssumm: Sparse summarization of massive graphs. In KDD. 144--154.","author":"Lee Kyuhan","year":"2020","unstructured":"Kyuhan Lee, Hyeonsoo Jo, Jihoon Ko, Sungsu Lim, and Kijung Shin. 2020. Ssumm: Sparse summarization of massive graphs. In KDD. 144--154."},{"key":"e_1_2_1_25_1","volume-title":"Slugger: lossless hierarchical summarization of massive graphs","author":"Lee Kyuhan","unstructured":"Kyuhan Lee, Jihoon Ko, and Kijung Shin. 2022. Slugger: lossless hierarchical summarization of massive graphs. In ICDE. IEEE, 472--484."},{"key":"e_1_2_1_26_1","volume-title":"GraSS: Graph structure summarization","author":"LeFevre Kristen","unstructured":"Kristen LeFevre and Evimaria Terzi. 2010. GraSS: Graph structure summarization. In ICDM. SIAM, 454--465."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Xingjie Liu Yuanyuan Tian Qi He Wang-Chien Lee and John McPherson. 2014. Distributed graph summarization. In SIGMOD. 799--808.","DOI":"10.1145\/2661829.2661862"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186727"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Antonio Maccioni and Daniel J Abadi. 2016. Scalable pattern matching over compressed graphs via dedensification. In KDD. 1755--1764.","DOI":"10.1145\/2939672.2939856"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Saket Navlakha Rajeev Rastogi and Nisheeth Shrivastava. 2008. Graph summarization with bounded error. In SIGMOD. 419--432.","DOI":"10.1145\/1376616.1376661"},{"key":"e_1_2_1_31_1","volume-title":"Graph summarization with quality guarantees. Data mining and knowledge discovery","author":"Riondato Matteo","year":"2017","unstructured":"Matteo Riondato, David Garc'ia-Soriano, and Francesco Bonchi. 2017. Graph summarization with quality guarantees. Data mining and knowledge discovery, Vol. 31 (2017), 314--349."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1186\/s40537-018-0121-z"},{"key":"e_1_2_1_33_1","first-page":"420","article-title":"The ubiquity of large graphs and surprising challenges of graph processing","volume":"11","author":"Sahu Siddhartha","year":"2017","unstructured":"Siddhartha Sahu, Amine Mhedhbi, Semih Salihoglu, Jimmy Lin, and M Tamer \u00d6zsu. 2017. The ubiquity of large graphs and surprising challenges of graph processing. VLDB, Vol. 11, 4 (2017), 420--431.","journal-title":"VLDB"},{"key":"e_1_2_1_34_1","volume-title":"Sweg: Lossless and lossy summarization of web-scale graphs. In WWW. 1679--1690.","author":"Shin Kijung","year":"2019","unstructured":"Kijung Shin, Amol Ghoting, Myunghwan Kim, and Hema Raghavan. 2019. Sweg: Lossless and lossy summarization of web-scale graphs. In WWW. 1679--1690."},{"key":"e_1_2_1_35_1","volume-title":"Smaller and faster: Parallel processing of compressed graphs with Ligra","author":"Shun Julian","unstructured":"Julian Shun, Laxman Dhulipala, and Guy E Blelloch. 2015. Smaller and faster: Parallel processing of compressed graphs with Ligra. In DCC. IEEE, 403--412."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2807442"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Nan Tang Qing Chen and Prasenjit Mitra. 2016. Graph stream summarization: From big bang to big crunch. In SIGMOD. 1481--1496.","DOI":"10.1145\/2882903.2915223"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/62.2160"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Yuanyuan Tian Richard A Hankins and Jignesh M Patel. 2008. Efficient aggregation for graph summarization. In SIGMOD. 567--580.","DOI":"10.1145\/1376616.1376675"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Hannu Toivonen Fang Zhou Aleksi Hartikainen and Atte Hinkka. 2011. Compression of weighted graphs. In AKDD. 965--973.","DOI":"10.1145\/2020408.2020566"},{"key":"e_1_2_1_41_1","volume-title":"2023 b. Cohesive Subgraph Discovery over Uncertain Bipartite Graphs. TKDE","author":"Wang Kai","year":"2023","unstructured":"Kai Wang, Gengda Zhao, Wenjie Zhang, Xuemin Lin, Ying Zhang, Yizhang He, and Chunxiao Li. 2023 b. Cohesive Subgraph Discovery over Uncertain Bipartite Graphs. TKDE (2023)."},{"key":"e_1_2_1_42_1","volume-title":"2023 a. Towards efficient shortest path counting on billion-scale graphs","author":"Wang Yiqi","unstructured":"Yiqi Wang, Long Yuan, Zi Chen, Wenjie Zhang, Xuemin Lin, and Qing Liu. 2023 a. Towards efficient shortest path counting on billion-scale graphs. In ICDE. IEEE, 2579--2592."},{"key":"e_1_2_1_43_1","first-page":"1297","article-title":"Influence Maximization via Vertex Countering","volume":"17","author":"Xie Jiadong","year":"2024","unstructured":"Jiadong Xie, Zehua Chen, Deming Chu, Fan Zhang, Xuemin Lin, and Zhihong Tian. 2024. Influence Maximization via Vertex Countering. VLDB, Vol. 17, 6 (2024), 1297--1309.","journal-title":"VLDB"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781680832433"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Quinton Yong Mahdi Hajiabadi Venkatesh Srinivasan and Alex Thomo. 2021. Efficient graph summarization using weighted lsh at billion-scale. In SIGMOD. 2357--2365.","DOI":"10.1145\/3448016.3457331"},{"key":"e_1_2_1_46_1","volume-title":"Discovery-driven graph summarization","author":"Zhang Ning","unstructured":"Ning Zhang, Yuanyuan Tian, and Jignesh M Patel. 2010. Discovery-driven graph summarization. In ICDE. IEEE, 880--891."},{"key":"e_1_2_1_47_1","volume-title":"Efficient computation of cohesive subgraphs in uncertain bipartite graphs","author":"Zhao Gengda","unstructured":"Gengda Zhao, Kai Wang, Wenjie Zhang, Xuemin Lin, Ying Zhang, and Yizhang He. 2022. Efficient computation of cohesive subgraphs in uncertain bipartite graphs. In ICDE. IEEE, 2333--2345."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-021-00907-1"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654943","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654943","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:39:31Z","timestamp":1755787171000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654943"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654943"],"URL":"https:\/\/doi.org\/10.1145\/3654943","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}