{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:42:53Z","timestamp":1787017373360,"version":"build-2736575974"},"reference-count":85,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2024,4,26]],"date-time":"2024-04-26T00:00:00Z","timestamp":1714089600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Korea government (MSIT) grant funded by the Korea government","award":["2020R1C1C1008296"],"award-info":[{"award-number":["2020R1C1C1008296"]}]},{"name":"Institute of Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korea government","award":["2019-0-00075"],"award-info":[{"award-number":["2019-0-00075"]}]}],"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                    Graphs are widely used for representing pairwise interactions in complex systems. Since such real-world graphs are large and often evergrowing, sampling subgraphs is useful for various purposes, including simulation, visualization, stream processing, representation learning, and crawling. However, many complex systems consist of group interactions (e.g., collaborations of researchers and discussions on online Q&amp;A platforms) and thus are represented more naturally and accurately by hypergraphs than by ordinary graphs. Motivated by the prevalence of large-scale hypergraphs, we study the problem of sampling from real-world hypergraphs, aiming at answering (Q1) how can we measure the goodness of sub-hypergraphs, and (Q2) how can we efficiently find a \u201cgood\u201d sub-hypergraph. Regarding Q1, we distinguish between two goals: (a)\n                    <jats:italic>representative sampling<\/jats:italic>\n                    , which aims at capturing the characteristics of the input hypergraph, and (b)\n                    <jats:italic>back-in-time sampling<\/jats:italic>\n                    , which aims at closely approximating a past snapshot of the input time-evolving hypergraph. To evaluate the similarity of the sampled sub-hypergraph to the target (i.e., the input hypergraph or its past snapshot), we consider 10 graph-level, hyperedge-level, and node-level statistics. Regarding Q2, we first conduct a thorough analysis of various intuitive approaches using 11 real-world hypergraphs. Then, based on this analysis, we propose\n                    <jats:sc>MiDaS<\/jats:sc>\n                    and\n                    <jats:sc>MiDaS-B<\/jats:sc>\n                    , designed for representative sampling and back-in-time sampling, respectively. Regarding representative sampling, we demonstrate through extensive experiments that\n                    <jats:sc>MiDaS<\/jats:sc>\n                    , which employs a sampling bias toward high-degree nodes in hyperedge selection, is (a)\n                    <jats:bold>Representative<\/jats:bold>\n                    : finding overall the most representative samples among 15 considered approaches, (b)\n                    <jats:bold>Fast<\/jats:bold>\n                    : several orders of magnitude faster than the strongest competitors, and (c)\n                    <jats:bold>Automatic<\/jats:bold>\n                    : automatically tuning the degree of sampling bias. Regarding back-in-time sampling, we demonstrate that\n                    <jats:sc>MiDaS-B<\/jats:sc>\n                    inherits the strengths of\n                    <jats:sc>MiDaS<\/jats:sc>\n                    despite an additional challenge\u2014the unavailability of the target (i.e., past snapshot). It effectively handles this challenge by focusing on replicating universal evolutionary patterns, rather than directly replicating the target.\n                  <\/jats:p>","DOI":"10.1145\/3653306","type":"journal-article","created":{"date-parts":[[2024,3,19]],"date-time":"2024-03-19T07:00:55Z","timestamp":1710831655000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Representative and Back-In-Time Sampling from Real-world Hypergraphs"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0819-7923","authenticated-orcid":false,"given":"Minyoung","family":"Choe","sequence":"first","affiliation":[{"name":"Kim Jaechul Graduate School of AI, KAIST, Seoul, Korea (the Republic of)"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7237-5117","authenticated-orcid":false,"given":"Jaemin","family":"Yoo","sequence":"additional","affiliation":[{"name":"School of Electrical Engineering, KAIST, Daejeon Korea (the Republic of)"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6339-9758","authenticated-orcid":false,"given":"Geon","family":"Lee","sequence":"additional","affiliation":[{"name":"Kim Jaechul Graduate School of AI, KAIST, Seoul Korea (the Republic of)"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-6828-6227","authenticated-orcid":false,"given":"Woonsung","family":"Baek","sequence":"additional","affiliation":[{"name":"School of Electrical Engineering, KAIST, Daejeon Korea (the Republic of)"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8774-6950","authenticated-orcid":false,"given":"U","family":"Kang","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science and Engineering, Seoul National University, Seoul Korea (the Republic of)"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2872-1526","authenticated-orcid":false,"given":"Kijung","family":"Shin","sequence":"additional","affiliation":[{"name":"Kim Jaechul Graduate School of AI, KAIST, Seoul Korea (the Republic of)"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,4,26]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767885"},{"key":"e_1_3_3_3_2","article-title":"Network sampling via edge-based node selection with graph induction","author":"Ahmed Nesreen","year":"2011","unstructured":"Nesreen Ahmed, Jennifer Neville, and Ramana Rao Kompella. 2011. Network sampling via edge-based node selection with graph induction. Department of Computer Science Technical Reports 11-016 (2011), 1747\u20131756. Retrieved from https:\/\/docs.lib.purdue.edu\/cstech\/1747\/","journal-title":"Department of Computer Science Technical Reports"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3605776"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59051-2_9"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1800683115"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220100"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jvlc.2011.02.002"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-021-86469-8"},{"key":"e_1_3_3_10_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Chen Jie","year":"2018","unstructured":"Jie Chen, Tengfei Ma, and Cao Xiao. 2018. Fastgcn: Fast learning with graph convolutional networks via importance sampling. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_3_11_2","unstructured":"Jianfei Chen Jun Zhu and Le Song. 2018. Stochastic training of graph convolutional networks with variance reduction. arXiv:1710.10568. Retrieved from https:\/\/arxiv.org\/abs\/1710.10568"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330925"},{"key":"e_1_3_3_13_2","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Chitra Uthsav","year":"2019","unstructured":"Uthsav Chitra and Benjamin Raphael. 2019. Random walks on hypergraphs with edge-dependent vertex weights. In Proceedings of the International Conference on Machine Learning."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1093\/comnet\/cnaa018"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3512157"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977172.19"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM51629.2021.00019"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2006.161"},{"key":"e_1_3_3_19_2","unstructured":"Antoine Deza Asaf Levin Syed M. Meesum and Shmuel Onn. 2019. Hypergraphic degree sequences are hard. Bulletin of the European Association for Theoretical Computer Science 127 (2019) 63\u201364."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403060"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2021.112566"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2018.00117"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33013558"},{"key":"e_1_3_3_24_2","volume-title":"Proceedings of the LinkKDD workshop at the 10th ACM Conference on KDD","author":"Gilbert Anna C.","year":"2004","unstructured":"Anna C. Gilbert and Kirill Levchenko. 2004. Compressing network graphs. In Proceedings of the LinkKDD workshop at the 10th ACM Conference on KDD."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2011.111011"},{"key":"e_1_3_3_26_2","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","author":"Hamilton William L.","year":"2017","unstructured":"William L. Hamilton, Rex Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Proceedings of the Advances in Neural Information Processing Systems."},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132907"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.124"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2008.151"},{"key":"e_1_3_3_30_2","doi-asserted-by":"crossref","unstructured":"Jianwen Jiang Yuxuan Wei Yifan Feng Jingxuan Cao and Yue Gao. 2019. Dynamic hypergraph neural networks. In Proceedings of the International Joint Conference on Artificial Intelligence. 2635\u20132641.","DOI":"10.24963\/ijcai.2019\/366"},{"key":"e_1_3_3_31_2","unstructured":"Wei Jin Lingxiao Zhao Shichang Zhang Yozen Liu Jiliang Tang and Neil Shah. 2022. Graph condensation for graph neural networks. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195422"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3580305.3599382"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM54844.2022.00122"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30115-8_22"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM50108.2020.00036"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2007.06.004"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/11422778_27"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2342549.2342556"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2318857.2254795"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00624-7"},{"key":"e_1_3_3_42_2","unstructured":"Geon Lee Fanchen Bu Tina Eliassi-Rad and Kijung Shin. 2024. A survey on hypergraph mining: Patterns tools and generators. arXiv:2401.08878. Retrieved from https:\/\/arxiv.org\/abs\/2401.08878"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3450010"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407823"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM51629.2021.00042"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401948"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150479"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"issue":"2","key":"e_1_3_3_49_2","first-page":"1","article-title":"Exploiting conversation-branch-tweet hypergraph structure to detect misinformation on social media","volume":"18","author":"Li Fangfang","year":"2023","unstructured":"Fangfang Li, Zhi Liu, Junwen Duan, Xingliang Mao, Heyuan Shi, and Shichao Zhang. 2023. Exploiting conversation-branch-tweet hypergraph structure to detect misinformation on social media. ACM Transactions on Knowledge Discovery from Data 18, 2 (2023), 1\u201320.","journal-title":"ACM Transactions on Knowledge Discovery from Data"},{"key":"e_1_3_3_50_2","article-title":"Quantum KNN classification with K Value selection and neighbor selection","author":"Li Jiaye","year":"2023","unstructured":"Jiaye Li, Jian Zhang, Jilian Zhang, and Shichao Zhang. 2023. Quantum KNN classification with K Value selection and neighbor selection. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (2023).","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113345"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783285"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3488560.3498391"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772762"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0136497"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1001119"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_3_3_58_2","volume-title":"Proceedings of the IEEE Visualization","author":"Rafiei Davood","year":"2005","unstructured":"Davood Rafiei. 2005. Effectively visualizing large networks through sampling. In Proceedings of the IEEE Visualization."},{"key":"e_1_3_3_59_2","volume-title":"Artificial Intelligence: A Modern Approach","author":"Russell Stuart","year":"2002","unstructured":"Stuart Russell and Peter Norvig. 2002. Artificial Intelligence: A Modern Approach. Pearson."},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1002\/sam.11224"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/2740908.2742839"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/3059194"},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0023176"},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-007-0094-2"},{"key":"e_1_3_3_66_2","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2016.7752223"},{"key":"e_1_3_3_67_2","doi-asserted-by":"publisher","DOI":"10.1007\/0-306-47815-3_5"},{"key":"e_1_3_3_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/3397271.3401133"},{"key":"e_1_3_3_69_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2016.7761624"},{"key":"e_1_3_3_70_2","doi-asserted-by":"crossref","unstructured":"Xin Xu Chul-Ho Lee and Young Eun Do. 2014. A general framework of hybrid graph sampling for complex network analysis. In Proceedings of the IEEE International Conference on Computer Communications. 2795\u20132803.","DOI":"10.1109\/INFOCOM.2014.6848229"},{"key":"e_1_3_3_71_2","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313635"},{"key":"e_1_3_3_72_2","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098069"},{"key":"e_1_3_3_73_2","doi-asserted-by":"publisher","DOI":"10.1145\/3336191.3371815"},{"key":"e_1_3_3_74_2","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380016"},{"key":"e_1_3_3_75_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.9.041056"},{"key":"e_1_3_3_76_2","unstructured":"Hanqing Zeng Hongkuan Zhou Ajitesh Srivastava Rajgopal Kannan and Viktor Prasanna. 2020. Graphsaint: Graph sampling based inductive learning method. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_3_77_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2023.103570"},{"key":"e_1_3_3_78_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-023-01178-8"},{"key":"e_1_3_3_79_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00102"},{"issue":"03","key":"e_1_3_3_80_2","first-page":"2711","article-title":"KNN classification with one-step computation","volume":"35","author":"Zhang Shichao","year":"2023","unstructured":"Shichao Zhang and Jiaye Li. 2023. KNN classification with one-step computation. IEEE Transactions on Knowledge & Data Engineering 35, 03 (2023), 2711\u20132723.","journal-title":"IEEE Transactions on Knowledge & Data Engineering"},{"issue":"07","key":"e_1_3_3_81_2","first-page":"7382","article-title":"Reachable distance function for KNN classification","volume":"35","author":"Zhang Shichao","year":"2023","unstructured":"Shichao Zhang, Jiaye Li, and Yangding Li. 2023. Reachable distance function for KNN classification. IEEE Transactions on Knowledge and Data Engineering 35, 07 (2023), 7382\u20137396.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_3_3_82_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2022.06.082"},{"key":"e_1_3_3_83_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2017.2673241"},{"key":"e_1_3_3_84_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498270"},{"issue":"6","key":"e_1_3_3_85_2","first-page":"3016","article-title":"Unsupervised spectral feature selection with dynamic hyper-graph learning","volume":"34","author":"Zhu Xiaofeng","year":"2020","unstructured":"Xiaofeng Zhu, Shichao Zhang, Yonghua Zhu, Pengfei Zhu, and Yue Gao. 2020. Unsupervised spectral feature selection with dynamic hyper-graph learning. IEEE Transactions on Knowledge and Data Engineering 34, 6 (2020), 3016\u20133028.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_3_3_86_2","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","author":"Zou Difan","year":"2019","unstructured":"Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. 2019. Layer-dependent importance sampling for training deep and large graph convolutional networks. In Proceedings of the Advances in Neural Information Processing Systems."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3653306","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3653306","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:44:25Z","timestamp":1750275865000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3653306"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,26]]},"references-count":85,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,7,31]]}},"alternative-id":["10.1145\/3653306"],"URL":"https:\/\/doi.org\/10.1145\/3653306","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,26]]},"assertion":[{"value":"2023-09-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-09","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}