{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T13:07:23Z","timestamp":1765544843809,"version":"3.41.0"},"reference-count":87,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2022,3,9]],"date-time":"2022-03-09T00:00:00Z","timestamp":1646784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"MOE Tier1 and Tier2","award":["RG117\/19 and MOE2019T2-2-042"],"award-info":[{"award-number":["RG117\/19 and MOE2019T2-2-042"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>Graph summarization is beneficial in a wide range of applications, such as visualization, interactive and exploratory analysis, approximate query processing, reducing the on-disk storage footprint, and graph processing in modern hardware. However, the bulk of the literature on graph summarization surprisingly overlooks the possibility of having edges of different types. In this article, we study the novel problem of producing summaries of multi-relation networks, i.e., graphs where multiple edges of different types may exist between any pair of nodes. Multi-relation graphs are an expressive model of real-world activities, in which a relation can be a topic in social networks, an interaction type in genetic networks, or a snapshot in temporal graphs.<\/jats:p>\n          <jats:p>\n            The first approach that we consider for multi-relation graph summarization is a two-step method based on summarizing each relation in isolation, and then aggregating the resulting summaries in some clever way to produce a final unique summary. In doing this, as a side contribution, we provide the first polynomial-time approximation algorithm based on the\n            <jats:sans-serif>\n              <jats:italic>k<\/jats:italic>\n              -Median\n            <\/jats:sans-serif>\n            clustering for the classic problem of lossless single-relation graph summarization.\n          <\/jats:p>\n          <jats:p>\n            Then, we demonstrate the shortcomings of these two-step methods, and propose holistic approaches, both approximate and heuristic algorithms, to compute a summary directly for multi-relation graphs. In particular, we prove that the approximation bound of\n            <jats:sans-serif>\n              <jats:italic>k<\/jats:italic>\n              -Median\n            <\/jats:sans-serif>\n            clustering for the single relation solution can be maintained in a multi-relation graph with proper aggregation operation over adjacency matrices corresponding to its multiple relations. Experimental results and case studies (on co-authorship networks and brain networks) validate the effectiveness and efficiency of the proposed algorithms.\n          <\/jats:p>","DOI":"10.1145\/3494561","type":"journal-article","created":{"date-parts":[[2022,3,10]],"date-time":"2022-03-10T14:03:20Z","timestamp":1646921000000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Multi-relation Graph Summarization"],"prefix":"10.1145","volume":"16","author":[{"given":"Xiangyu","family":"Ke","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Nanyang Avenue, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arijit","family":"Khan","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Nanyang Avenue, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesco","family":"Bonchi","sequence":"additional","affiliation":[{"name":"ISI Foundation and Eurecat, Calle Bilbao, Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,3,9]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.40"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213560"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1195618"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033116.57574.95"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-93040-4_40"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/070705970"},{"key":"e_1_3_2_8_2","article-title":"Survey and taxonomy of lossless graph compression and space-efficient graph representations","volume":"1806","author":"Besta M.","year":"2018","unstructured":"M. Besta and T. Hoefler. 2018. Survey and taxonomy of lossless graph compression and space-efficient graph representations. arXiv : 1806.01799 (2018). Retrieved from https:\/\/arxiv.org\/abs\/1806.01799","journal-title":"arXiv"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339726"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03784-9_3"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1690"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1341531.1341547"},{"key":"e_1_3_2_15_2","doi-asserted-by":"crossref","unstructured":"A. Cardillo J. G\u00f3mez-Garde\u00f1es M. Zanin M. Romance D. Papo F. del Pozo and S. Boccaletti. 2012. Emergence of network features from multiplexity. Scientific Reports 3 1 (2013) 1\u20136.","DOI":"10.1038\/srep01344"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.012"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687711"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6515-8_18"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.30"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557049"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2173710"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.43"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065201"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2492517.2492537"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.3389\/conf.fninf.2013.09.00041\/event_abstract"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139941907"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213855"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/070683155"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132993"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3369872"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217303"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2789987"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00103"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38562-9_55"},{"key":"e_1_3_2_35_2","article-title":"A survey and taxonomy of graph sampling","author":"Hu P.","year":"2013","unstructured":"P. Hu and W. C. Lau. 2013. A survey and taxonomy of graph sampling. arXiv: 1308.5865. Retrieved from https:\/\/arxiv.org\/abs\/1308.5865","journal-title":"arXiv: 1308.5865. Retrieved from https:\/\/arxiv.org\/abs\/1308.5865"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2426696"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3397271.3401072"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330992"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403057"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.26"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020580"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/224170.224229"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3199670"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-017-0443-4"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.14778\/3137765.3137825"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/BDCloud.2014.108"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973440.11"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1002\/sam.11267"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2018.00141"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.14778\/3297753.3297755"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972801.40"},{"key":"e_1_3_2_52_2","volume-title":"Proceedings of the SDM","author":"Lin S.-D.","year":"2013","unstructured":"S.-D. Lin, M.-Y. Yeh, and C.-T. Li. 2013. Sampling and summarization for social networks. In Proceedings of the SDM."},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2661862"},{"issue":"3","key":"e_1_3_2_54_2","first-page":"62:1\u201362:34","article-title":"Graph summarization methods and applications: A survey","volume":"51","author":"Liu Y.","year":"2018","unstructured":"Y. Liu, T. Safavi, A. Dighe, and D. Koutra. 2018. Graph summarization methods and applications: A survey. ACM Computing Surveys 51, 3 (2018), 62:1\u201362:34.","journal-title":"ACM Computing Surveys"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2016.2595620"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835873"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.14"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376661"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026113"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2016.02.003"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623701"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44851-9_38"},{"key":"e_1_3_2_63_2","volume-title":"Proceedings of the ICDE","author":"Raghavan S.","year":"2003","unstructured":"S. Raghavan and H. Garcia-Molina. 2003. Representing web graphs. In Proceedings of the ICDE."},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2014.56"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-016-0468-8"},{"key":"e_1_3_2_66_2","doi-asserted-by":"crossref","DOI":"10.1016\/0005-1098(78)90005-5","article-title":"Modelling by the shortest data description","volume":"14","author":"Rissanen J.","year":"1978","unstructured":"J. Rissanen. 1978. Modelling by the shortest data description. Automatica 14, 5 (1978), 465\u2013471.","journal-title":"Automatica"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1186\/s40537-018-0121-z"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ymeth.2014.06.012"},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-13-S3-S10"},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783321"},{"key":"e_1_3_2_71_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498314"},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313402"},{"issue":"3","key":"e_1_3_2_73_2","first-page":"486","article-title":"Parasite spreading in spatial ecological multiplex networks","volume":"5","author":"Stella M.","year":"2017","unstructured":"M. Stella, C. S. Andreazzi, S. Selakovic, A. Goudarzi, and A. Antonioni. 2017. Parasite spreading in spatial ecological multiplex networks. Journal of Complex Networks 5, 3 (2017), 486\u2013511.","journal-title":"Journal of Complex Networks"},{"key":"e_1_3_2_74_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915223"},{"key":"e_1_3_2_75_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289263"},{"key":"e_1_3_2_76_2","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376675"},{"key":"e_1_3_2_77_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6515-8_15"},{"key":"e_1_3_2_78_2","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020566"},{"key":"e_1_3_2_79_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2016.7840704"},{"key":"e_1_3_2_80_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972757.25"},{"key":"e_1_3_2_81_2","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556561"},{"key":"e_1_3_2_82_2","volume-title":"Proceedings of the AAAI","author":"Xia L.","year":"2021","unstructured":"L. Xia, C. Huang, Y. Xu, P. Dai, X. Zhang, H. Yang, J. Pei, and L. Bo. 2021. Knowledge-enhanced hierarchical graph transformer network for multi-behavior recommendation. In Proceedings of the AAAI."},{"key":"e_1_3_2_83_2","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081908"},{"key":"e_1_3_2_84_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2021.3067901"},{"key":"e_1_3_2_85_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113411"},{"key":"e_1_3_2_86_2","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303756"},{"key":"e_1_3_2_87_2","doi-asserted-by":"publisher","DOI":"10.14778\/2078331.2078335"},{"key":"e_1_3_2_88_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.133"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3494561","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3494561","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:16Z","timestamp":1750188676000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3494561"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,9]]},"references-count":87,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3494561"],"URL":"https:\/\/doi.org\/10.1145\/3494561","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2022,3,9]]},"assertion":[{"value":"2021-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}