{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T23:21:05Z","timestamp":1776122465356,"version":"3.50.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2024,4,12]],"date-time":"2024-04-12T00:00:00Z","timestamp":1712880000000},"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. Knowl. Discov. Data"],"published-print":{"date-parts":[[2024,7,31]]},"abstract":"<jats:p>\n            Graph summarization has become integral for managing and analyzing large-scale graphs in diverse real-world applications, including social networks, biological networks, and communication networks. Existing methods for graph summarization often face challenges, being either computationally expensive, limiting their applicability to large graphs, or lacking the incorporation of node attributes. In response, we introduce\n            <jats:sc>SsAG<\/jats:sc>\n            , an efficient and scalable lossy graph summarization method designed to preserve the essential structure of the original graph.\n          <\/jats:p>\n          <jats:p\/>\n          <jats:p>\n            <jats:sc>SsAG<\/jats:sc>\n            computes a sparse representation (summary) of the input graph, accommodating graphs with node attributes. The summary is structured as a graph on supernodes (subsets of vertices of\n            <jats:italic>G<\/jats:italic>\n            ), where weighted superedges connect pairs of supernodes. The methodology focuses on constructing a summary graph with\n            <jats:italic>k<\/jats:italic>\n            supernodes, aiming to minimize the reconstruction error (the difference between the original graph and the graph reconstructed from the summary) while maximizing homogeneity with respect to the node attributes. The construction process involves iteratively merging pairs of nodes.\n          <\/jats:p>\n          <jats:p\/>\n          <jats:p>To enhance computational efficiency, we derive a closed-form expression for efficiently computing the reconstruction error (RE) after merging a pair, enabling constant-time approximation of this score. We assign a weight to each supernode, quantifying their contribution to the score of pairs, and utilize a weighted sampling strategy to select the best pair for merging. Notably, a logarithmic-sized sample achieves a summary comparable in quality based on various measures. Additionally, we propose a sparsification step for the constructed summary, aiming to reduce storage costs to a specified target size with a marginal increase in RE.<\/jats:p>\n          <jats:p\/>\n          <jats:p>\n            Empirical evaluations across diverse real-world graphs demonstrate that\n            <jats:sc>SsAG<\/jats:sc>\n            exhibits superior speed, being up to 17 \u00d7 faster, while generating summaries of comparable quality. This work represents a significant advancement in the field, addressing computational challenges and showcasing the effectiveness of\n            <jats:sc>SsAG<\/jats:sc>\n            in graph summarization.\n          <\/jats:p>","DOI":"10.1145\/3651619","type":"journal-article","created":{"date-parts":[[2024,3,6]],"date-time":"2024-03-06T12:06:40Z","timestamp":1709726800000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["<scp>SsAG<\/scp>\n            : Summarization and Sparsification of Attributed Graphs"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8121-2168","authenticated-orcid":false,"given":"Sarwan","family":"Ali","sequence":"first","affiliation":[{"name":"Georgia State University, Atlanta, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6017-1037","authenticated-orcid":false,"given":"Muhammad","family":"Ahmad","sequence":"additional","affiliation":[{"name":"Lahore University of Management Sciences, Lahore, Pakistan"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-5402-5755","authenticated-orcid":false,"given":"Maham Anwer","family":"Beg","sequence":"additional","affiliation":[{"name":"Lahore University of Management Sciences, Lahore, Pakistan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6955-6168","authenticated-orcid":false,"given":"Imdad Ullah","family":"Khan","sequence":"additional","affiliation":[{"name":"Lahore University of Management Sciences, Lahore, Pakistan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0367-7370","authenticated-orcid":false,"given":"Safiullah","family":"Faizullah","sequence":"additional","affiliation":[{"name":"Islamic University, Madinah, KSA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7963-6615","authenticated-orcid":false,"given":"Muhammad Asad","family":"Khan","sequence":"additional","affiliation":[{"name":"Hazara University, Mansehra, Pakistan"}]}],"member":"320","published-online":{"date-parts":[[2024,4,12]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.3127\/ajis.v21i0.1563"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3442390"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-93040-4_40"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00521-023-09052-4"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2022.3210233"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2018.01.002"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2021.102659"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3524105"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-47426-3_60"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-017-0443-4"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2019.102054"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2017.07.033"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-015-0454-9"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-016-0388-y"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403074"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973440.11"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403057"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972801.40"},{"key":"e_1_3_2_22_2","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2320716"},{"issue":"3","key":"e_1_3_2_24_2","first-page":"62:1\u201362:34","article-title":"Graph summarization methods and applications: A survey","volume":"51","author":"Liu Yike","year":"2018","unstructured":"Yike Liu, Tara Safavi, Abhilash Dighe, and Danai Koutra. 2018. Graph summarization methods and applications: A survey. Comput. Surv. 51, 3 (2018), 62:1\u201362:34.","journal-title":"Comput. Surv."},{"issue":"1","key":"e_1_3_2_25_2","first-page":"77","article-title":"Approximate homogeneous graph summarization","volume":"20","author":"Liu Zheng","year":"2012","unstructured":"Zheng Liu, Jeffrey Xu Yu, and Hong Cheng. 2012. Approximate homogeneous graph summarization. J. Inf. Process. 20, 1 (2012), 77\u201388.","journal-title":"J. Inf. Process."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376661"},{"key":"e_1_3_2_27_2","volume-title":"Association for the Advancement of Artificial Intelligence","author":"Papalampidi Pinelopi","year":"2021","unstructured":"Pinelopi Papalampidi, Frank Keller, and Mirella Lapata. 2021. Movie summarization via sparse graph construction. In Association for the Advancement of Artificial Intelligence."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.136"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2601611"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-016-0371-8"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2017.04.012"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-016-0468-8"},{"key":"e_1_3_2_33_2","volume-title":"AAAI","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. Retrieved from https:\/\/networkrepository.com"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2019.00063"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-018-2245-5"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2453957"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313402"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2021.102712"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915223"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376675"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2016.7840704"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1137\/0209009"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41629-3_1"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113411"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1080\/0952813X.2017.1280089"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651619","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651619","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:49:09Z","timestamp":1750286949000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651619"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,12]]},"references-count":44,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,7,31]]}},"alternative-id":["10.1145\/3651619"],"URL":"https:\/\/doi.org\/10.1145\/3651619","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,12]]},"assertion":[{"value":"2023-07-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-03","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}