{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,9]],"date-time":"2025-07-09T22:49:14Z","timestamp":1752101354510,"version":"3.41.0"},"reference-count":45,"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:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"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 is a useful tool for analyzing large-scale graphs. Some works tried to preserve original node embeddings encoding rich structural information of nodes on the summary graph. However, their algorithms are designed heuristically and not theoretically guaranteed. In this article, we theoretically study the problem of preserving node embeddings on summary graph. We prove that three matrix-factorization-based node embedding methods of the original graph can be approximated by that of the summary graph, and we propose a novel graph summarization method, named\n            <jats:sc>HCSumm<\/jats:sc>\n            , based on this analysis. Extensive experiments are performed on real-world datasets to evaluate the effectiveness of our proposed method. The experimental results show that our method outperforms the state-of-the-art methods in preserving node embeddings.\n          <\/jats:p>","DOI":"10.1145\/3649505","type":"journal-article","created":{"date-parts":[[2024,3,8]],"date-time":"2024-03-08T09:19:44Z","timestamp":1709889584000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Node Embedding Preserving Graph Summarization"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-5810-8579","authenticated-orcid":false,"given":"Houquan","family":"Zhou","sequence":"first","affiliation":[{"name":"CAS Key Laboratory of AI Security, Institute of Computing Technology, Chinese Academy of Sciences, Haidian District, China, and University of Chinese Academy of Sciences, Huairou District, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2120-3598","authenticated-orcid":false,"given":"Shenghua","family":"Liu","sequence":"additional","affiliation":[{"name":"CAS Key Laboratory of AI Security, Institute of Computing Technology, Chinese Academy of Sciences, Haidian District, China, and University of Chinese Academy of Sciences, Huairou District, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1081-8119","authenticated-orcid":false,"given":"Huawei","family":"Shen","sequence":"additional","affiliation":[{"name":"CAS Key Laboratory of AI Security, Institute of Computing Technology, Chinese Academy of Sciences, Haidian District, China, and University of Chinese Academy of Sciences, Huairou District, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5201-8195","authenticated-orcid":false,"given":"Xueqi","family":"Cheng","sequence":"additional","affiliation":[{"name":"CAS Key Laboratory of AI Security, Institute of Computing Technology, Chinese Academy of Sciences, Haidian District, China, and University of Chinese Academy of Sciences, Huairou District, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,4,12]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974973.47"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-93040-4_40"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11849"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_3_3_6_2","volume-title":"Proceedings of the ICLR","author":"Deng Chenhui","year":"2020","unstructured":"Chenhui Deng, Zhiqiang Zhao, Yongyu Wang, Zhiru Zhang, and Zhuo Feng. 2020. GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding. In Proceedings of the ICLR."},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.5486\/PMD.1959.6.3-4.12"},{"key":"e_1_3_3_8_2","volume-title":"Proceedings of the ICML","author":"Fahrbach Matthew","year":"2020","unstructured":"Matthew Fahrbach, Gramoz Goranci, Richard Peng, Sushant Sachdeva, and Chi Wang. 2020. Faster graph embeddings via coarsening. In Proceedings of the ICML."},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213855"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/IJCNN.2019.8851893"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38562-9_55"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90021-7"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2019.2921572"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.83.016107"},{"key":"e_1_3_3_16_2","first-page":"359392","article-title":"A fast and high quality multilevel scheme for partitioning irregular graphs","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. (1998), 359392.","journal-title":"SIAM J. Sci. Comput."},{"key":"e_1_3_3_17_2","first-page":"543","article-title":"Set-based unified approach for summarization of a multi-attributed graph","author":"Khan Kifayat Ullah","year":"2017","unstructured":"Kifayat Ullah Khan, Waqas Nawaz, and Young-Koo Lee. 2017. Set-based unified approach for summarization of a multi-attributed graph. In Proceedings of the WWW. 543\u2013570.","journal-title":"Proceedings of the WWW"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403074"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973440.11"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403057"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972801.40"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i04.5906"},{"key":"e_1_3_3_23_2","doi-asserted-by":"crossref","unstructured":"Jiongqian Liang Saket Gurukar and Srinivasan Parthasarathy. 2020. MILE: A multi-level framework for scalable graph embedding. Retrieved from https:\/\/arXiv:1802.09612","DOI":"10.1609\/icwsm.v15i1.18067"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2020.02.028"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3336191.3371781"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3186727"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835873"},{"key":"e_1_3_3_28_2","volume-title":"Proceedings of the 16th ACM International Conference On Web Search And Data Mining","author":"Merchant Arpit","year":"2022","unstructured":"Arpit Merchant, Michael Mathioudakis, and Yanhao Wang. 2022. Graph summarization via node grouping: A spectral algorithm. In Proceedings of the 16th ACM International Conference On Web Search And Data Mining."},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376661"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2021.06.050"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198805090.001.0001"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0601602103"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159706"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44851-9_38"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-016-0468-8"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2017.06.001"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783321"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.056111"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313402"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741093"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915223"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/InfoSEEE.2014.6948163"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330921"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457331"},{"key":"e_1_3_3_46_2","article-title":"DPGS: Degree-preserving graph summarization","author":"Zhou Houquan","year":"2021","unstructured":"Houquan Zhou, Shenghua Liu, Kyuhan Lee, Kijung Shin, Huawei Shen, and Xueqi Cheng. 2021. DPGS: Degree-preserving graph summarization. In Proceedings of the SDM (2021).","journal-title":"Proceedings of the SDM"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649505","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3649505","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:56:53Z","timestamp":1750291013000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649505"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,12]]},"references-count":45,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,7,31]]}},"alternative-id":["10.1145\/3649505"],"URL":"https:\/\/doi.org\/10.1145\/3649505","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2024,4,12]]},"assertion":[{"value":"2023-04-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-29","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-12","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}