{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,15]],"date-time":"2025-10-15T18:07:43Z","timestamp":1760551663128,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2022,7,30]],"date-time":"2022-07-30T00:00:00Z","timestamp":1659139200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NCSOFT Co"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            What are the key structures existing in a large real-world MMORPG (Massively Multiplayer Online Role-Playing Game) graph? How can we compactly summarize an MMORPG graph with hierarchical node labels, considering substructures at different levels of hierarchy? Recent MMORPGs generate complex interactions between entities inducing a heterogeneous graph where each entity has hierarchical labels. Succinctly summarizing a heterogeneous MMORPG graph is crucial to better understand its structure; however it is a challenging task since it needs to handle complex interactions and hierarchical labels efficiently. Although there exist few methods to summarize a large-scale graph, they do not deal with heterogeneous graphs with hierarchical node labels.We propose\n            <jats:sc>GSHL<\/jats:sc>\n            , a novel method that summarizes a heterogeneous graph with hierarchical labels. We formulate the encoding cost of hierarchical labels using MDL (Minimum Description Length).\n            <jats:sc>GSHL<\/jats:sc>\n            exploits the formulation to identify and segment subgraphs, and discovers compact and consistent structures in the graph. Experiments on a large real-world MMORPG graph with multi-million edges show that\n            <jats:sc>GSHL<\/jats:sc>\n            is a useful and scalable tool for summarizing the graph, finding important structures in the graph, and finding similar users.\n          <\/jats:p>","DOI":"10.1145\/3522691","type":"journal-article","created":{"date-parts":[[2022,3,18]],"date-time":"2022-03-18T18:13:12Z","timestamp":1647627192000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Finding Key Structures in MMORPG Graph with Hierarchical Graph Summarization"],"prefix":"10.1145","volume":"16","author":[{"given":"Jun-Gi","family":"Jang","sequence":"first","affiliation":[{"name":"Seoul National University, Gwanak-gu, Seoul, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chaeheum","family":"Park","sequence":"additional","affiliation":[{"name":"Deeping Source, Gangnam-gu, Seoul, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Changwon","family":"Jang","sequence":"additional","affiliation":[{"name":"NCSOFT Co., Seongnam-si, Gyeonggi-do, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Geonsoo","family":"Kim","sequence":"additional","affiliation":[{"name":"NCSOFT Co., Seongnam-si, Gyeonggi-do, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8774-6950","authenticated-orcid":false,"given":"U.","family":"Kang","sequence":"additional","affiliation":[{"name":"Seoul National University, Gwanak-gu, Seoul, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,30]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_1_2_2","DOI":"10.1109\/FiCloud.2015.61"},{"doi-asserted-by":"publisher","key":"e_1_3_1_3_2","DOI":"10.1145\/3102254.3102263"},{"doi-asserted-by":"publisher","key":"e_1_3_1_4_2","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"unstructured":"\u0160ejla \u010cebiri\u0107 Fran\u00e7ois Goasdou\u00e9 Pawel Guzewicz and Ioana Manolescu. 2018. Compact Summaries of Rich Heterogeneous Graphs . Ph.D. Dissertation. INRIA Saclay; Universit\u00e9 Rennes 1.","key":"e_1_3_1_5_2"},{"doi-asserted-by":"crossref","unstructured":"Deepayan Chakrabarti Spiros Papadimitriou Dharmendra S. Modha and Christos Faloutsos. 2004. Fully automatic cross-associations. In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . 79\u201388.","key":"e_1_3_1_6_2","DOI":"10.1145\/1014052.1014064"},{"doi-asserted-by":"crossref","unstructured":"Diane J. Cook and Lawrence B. Holder. 1993. Substructure discovery using minimum description length and background knowledge. Journal of Artificial Intelligence Research 1 1 (1993) 231\u2013255.","key":"e_1_3_1_7_2","DOI":"10.1613\/jair.43"},{"doi-asserted-by":"crossref","unstructured":"Anders Drachen Rafet Sifa Christian Bauckhage and Christian Thurau. 2012. Guns swords and data: Clustering of player behavior in computer games in the wild. In Proceedings of the 2012 IEEE conference on Computational Intelligence and Games . 163\u2013170.","key":"e_1_3_1_8_2","DOI":"10.1109\/CIG.2012.6374152"},{"doi-asserted-by":"publisher","key":"e_1_3_1_9_2","DOI":"10.1007\/s10618-006-0057-3"},{"doi-asserted-by":"crossref","unstructured":"Jinhong Jung Namyong Park Lee Sael and U. Kang. 2017. BePI: Fast and memory-efficient method for billion-scale random walk with restart. In Proceedings of the 2017 ACM International Conference on Management of Data . 789\u2013804.","key":"e_1_3_1_10_2","DOI":"10.1145\/3035918.3035950"},{"doi-asserted-by":"publisher","key":"e_1_3_1_11_2","DOI":"10.1109\/ICDM.2011.26"},{"doi-asserted-by":"crossref","unstructured":"Danai Koutra U. Kang Jilles Vreeken and Christos Faloutsos. 2014. VOG: Summarizing and understanding large graphs. In Proceedings of the 2014 SIAM International Conference on Data Mining . 91\u201399.","key":"e_1_3_1_12_2","DOI":"10.1137\/1.9781611973440.11"},{"doi-asserted-by":"crossref","unstructured":"Danai Koutra Tai-You Ke U. Kang Duen Horng Chau Hsing-Kuo Kenneth Pao and Christos Faloutsos. 2011. Unifying guilt-by-association approaches: Theorems and fast algorithms. In Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases . 245\u2013260.","key":"e_1_3_1_13_2","DOI":"10.1007\/978-3-642-23783-6_16"},{"doi-asserted-by":"crossref","unstructured":"Jure Leskovec Jon M. Kleinberg and Christos Faloutsos. 2005. Graphs over time: Densification laws shrinking diameters and possible explanations. In Proceedings of the 11th ACM SIGKDD international conference on Knowledge discovery in data mining . 177\u2013187.","key":"e_1_3_1_14_2","DOI":"10.1145\/1081870.1081893"},{"doi-asserted-by":"crossref","unstructured":"Kaichun Mo Paul Guerrero Li Yi Hao Su Peter Wonka Niloy J. Mitra and Leonidas J. Guibas. 2019. StructureNet: hierarchical graph networks for 3D shape generation. ACM Trans. Graph. 38 6 (2019) 242:1\u2013242:19.","key":"e_1_3_1_15_2","DOI":"10.1145\/3355089.3356527"},{"doi-asserted-by":"publisher","key":"e_1_3_1_16_2","DOI":"10.1016\/0005-1098(78)90005-5"},{"key":"e_1_3_1_17_2","first-page":"416","article-title":"A universal prior for integers and estimation by minimum description length","author":"Rissanen Jorma","year":"1983","unstructured":"Jorma Rissanen. 1983. A universal prior for integers and estimation by minimum description length. The Annals of Statistics 11, 2 (1983), 416\u2013431.","journal-title":"The Annals of Statistics"},{"doi-asserted-by":"publisher","key":"e_1_3_1_18_2","DOI":"10.1109\/ICDM.2014.36"},{"doi-asserted-by":"publisher","key":"e_1_3_1_19_2","DOI":"10.1145\/2783258.2783321"},{"doi-asserted-by":"crossref","unstructured":"Kijung Shin Jinhong Jung Lee Sael and U. Kang. 2015. BEAR: Block elimination approach for random walk with restart on large graphs. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data . 1571\u20131585.","key":"e_1_3_1_20_2","DOI":"10.1145\/2723372.2723716"},{"doi-asserted-by":"publisher","key":"e_1_3_1_21_2","DOI":"10.1016\/j.knosys.2017.09.022"},{"doi-asserted-by":"publisher","key":"e_1_3_1_22_2","DOI":"10.1145\/2835776.2835780"},{"doi-asserted-by":"publisher","key":"e_1_3_1_23_2","DOI":"10.1145\/2433396.2433471"},{"doi-asserted-by":"publisher","key":"e_1_3_1_24_2","DOI":"10.1109\/BigData.2018.8622067"},{"key":"e_1_3_1_25_2","first-page":"4800","volume-title":"Proceedings of the Advances in Neural Information Processing Systems 31","author":"Ying Zhitao","year":"2018","unstructured":"Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. 2018. Hierarchical graph representation learning with differentiable pooling. In Proceedings of the Advances in Neural Information Processing Systems 31. 4800\u20134810."},{"doi-asserted-by":"publisher","key":"e_1_3_1_26_2","DOI":"10.1016\/j.patcog.2017.05.007"},{"doi-asserted-by":"crossref","unstructured":"Zhen Zhang Jiajun Bu Martin Ester Jianfeng Zhang Zhao Li Chengwei Yao Dai Huifen Zhi Yu and Can Wang. 2021. Hierarchical multi-view graph pooling with structure learning. IEEE Transactions on Knowledge and Data Engineering (2021).","key":"e_1_3_1_27_2","DOI":"10.1109\/TKDE.2021.3090664"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3522691","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3522691","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:15Z","timestamp":1750188615000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3522691"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,30]]},"references-count":26,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3522691"],"URL":"https:\/\/doi.org\/10.1145\/3522691","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2022,7,30]]},"assertion":[{"value":"2021-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}