{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:31:26Z","timestamp":1772119886356,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":63,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T00:00:00Z","timestamp":1650844800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["NRF-2020R1C1C1008296"],"award-info":[{"award-number":["NRF-2020R1C1C1008296"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Institute of Information & Communications Technology Planning & Evaluation","award":["2019-0-00075"],"award-info":[{"award-number":["2019-0-00075"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,4,25]]},"DOI":"10.1145\/3485447.3512157","type":"proceedings-article","created":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T05:13:07Z","timestamp":1650863587000},"page":"1080-1092","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["MiDaS: Representative Sampling from Real-world Hypergraphs"],"prefix":"10.1145","author":[{"given":"Minyoung","family":"Choe","sequence":"first","affiliation":[{"name":"Korea Advanced Institute of Science and Technology, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jaemin","family":"Yoo","sequence":"additional","affiliation":[{"name":"Seoul National University, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Geon","family":"Lee","sequence":"additional","affiliation":[{"name":"Korea Advanced Institute of Science and Technology, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Woonsung","family":"Baek","sequence":"additional","affiliation":[{"name":"Korea Advanced Institute of Science and Technology, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"U","family":"Kang","sequence":"additional","affiliation":[{"name":"Seoul National University, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kijung","family":"Shin","sequence":"additional","affiliation":[{"name":"Korea Advanced Institute of Science and Technology, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,4,25]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"2022. Code datasets and supplementary document. Avaliable online: https:\/\/github.com\/young917\/MiDaS."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Charu\u00a0C Aggarwal Yuchen Zhao and S\u00a0Yu Philip. 2011. Outlier detection in graph streams. In ICDE.","DOI":"10.1109\/ICDE.2011.5767885"},{"key":"e_1_3_2_1_3_1","unstructured":"Nesreen Ahmed Jennifer Neville and Ramana\u00a0Rao Kompella. 2011. Network sampling via edge-based node selection with graph induction. (2011)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Nesreen\u00a0K Ahmed Nick Duffield Jennifer Neville and Ramana Kompella. 2014. Graph sample and hold: A framework for big-graph analytics. In KDD.","DOI":"10.1145\/2623330.2623757"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Naheed\u00a0Anjum Arafat Debabrota Basu Laurent Decreusefond and St\u00e9phane Bressan. 2020. Construction and Random Generation of Hypergraphs with Prescribed Degree and Dimension Sequences. In DEXA.","DOI":"10.1007\/978-3-030-59051-2_9"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1800683115"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jvlc.2011.02.002"},{"key":"e_1_3_2_1_8_1","unstructured":"Jie Chen Tengfei Ma and Cao Xiao. 2018. Fastgcn: fast learning with graph convolutional networks via importance sampling. In ICLR."},{"key":"e_1_3_2_1_9_1","unstructured":"Jianfei Chen Jun Zhu and Le Song. 2018. Stochastic training of graph convolutional networks with variance reduction. ICML."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330925"},{"key":"e_1_3_2_1_11_1","unstructured":"Uthsav Chitra and Benjamin Raphael. 2019. Random walks on hypergraphs with edge-dependent vertex weights. In ICML."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1093\/comnet\/cnaa018"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2006.161"},{"key":"e_1_3_2_1_14_1","unstructured":"Antoine Deza Asaf Levin Syed\u00a0M Meesum and Shmuel Onn. 2019. Hypergraphic degree sequences are hard. arXiv preprint arXiv:1901.02272(2019)."},{"key":"e_1_3_2_1_15_1","unstructured":"Manh\u00a0Tuan Do Se-eun Yoon Bryan Hooi and Kijung Shin. 2020. Structural patterns and generative models of real-world hypergraphs. In KDD."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2021.112566"},{"key":"e_1_3_2_1_17_1","volume-title":"Sedanspot: Detecting anomalies in edge streams. In ICDM.","author":"Eswaran Dhivya","year":"2018","unstructured":"Dhivya Eswaran and Christos Faloutsos. 2018. Sedanspot: Detecting anomalies in edge streams. In ICDM."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Yifan Feng Haoxuan You Zizhao Zhang Rongrong Ji and Yue Gao. 2019. Hypergraph neural networks. In AAAI.","DOI":"10.1609\/aaai.v33i01.33013558"},{"key":"e_1_3_2_1_19_1","unstructured":"Anna\u00a0C Gilbert and Kirill Levchenko. 2004. Compressing network graphs. In LinkKDD Vol.\u00a0124."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Minas Gjoka Maciej Kurant Carter\u00a0T Butts and Athina Markopoulou. 2010. Walking in facebook: A case study of unbiased sampling of osns. In INFOCOM.","DOI":"10.1109\/INFCOM.2010.5462078"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2011.111011"},{"key":"e_1_3_2_1_22_1","unstructured":"William\u00a0L Hamilton Rex Ying and Jure Leskovec. 2017. Inductive representation learning on large graphs. In NIPS."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Shuguang Hu Xiaowei Wu and TH\u00a0Hubert Chan. 2017. Maintaining densest subsets efficiently in evolving hypergraphs. In CIKM.","DOI":"10.1145\/3132847.3132907"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Christian H\u00fcbler Hans-Peter Kriegel Karsten Borgwardt and Zoubin Ghahramani. 2008. Metropolis algorithms for representative subgraph sampling. In ICDM.","DOI":"10.1109\/ICDM.2008.124"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2008.151"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Jianwen Jiang Yuxuan Wei Yifan Feng Jingxuan Cao and Yue Gao. 2019. Dynamic Hypergraph Neural Networks.. In IJCAI.","DOI":"10.24963\/ijcai.2019\/366"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Liran Katzir Edo Liberty and Oren Somekh. 2011. Estimating sizes of social networks via biased sampling. In WWW.","DOI":"10.1145\/1963405.1963489"},{"key":"e_1_3_2_1_28_1","volume-title":"The enron corpus: A new dataset for email classification research","author":"Klimt Bryan","unstructured":"Bryan Klimt and Yiming Yang. 2004. The enron corpus: A new dataset for email classification research. In ECML. Springer."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Yunbum Kook Jihoon Ko and Kijung Shin. 2020. Evolution of Real-world Hypergraphs: Patterns and Models without Oracles. In ICDM.","DOI":"10.1109\/ICDM50108.2020.00036"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2007.06.004"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/11422778_27"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Maciej Kurant Minas Gjoka Yan Wang Zack\u00a0W Almquist Carter\u00a0T Butts and Athina Markopoulou. 2012. Coarse-grained topology estimation via graph sampling. In WOSN.","DOI":"10.1145\/2342549.2342556"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2011.111005"},{"key":"e_1_3_2_1_34_1","first-page":"319","article-title":"Beyond random walk and metropolis-hastings samplers: why you should not backtrack for unbiased graph sampling","volume":"40","author":"Lee Chul-Ho","year":"2012","unstructured":"Chul-Ho Lee, Xin Xu, and Do\u00a0Young Eun. 2012. Beyond random walk and metropolis-hastings samplers: why you should not backtrack for unbiased graph sampling. PER 40, 1 (2012), 319\u2013330.","journal-title":"PER"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00624-7"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Geon Lee Minyoung Choe and Kijung Shin. 2021. How Do Hyperedges Overlap in Real-World Hypergraphs?-Patterns Measures and Generators. In WWW.","DOI":"10.1145\/3442381.3450010"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407823"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Jure Leskovec and Christos Faloutsos. 2006. Sampling from large graphs. In KDD.","DOI":"10.1145\/1150402.1150479"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Jure Leskovec Jon Kleinberg and Christos Faloutsos. 2005. Graphs over time: densification laws shrinking diameters and possible explanations. In KDD.","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_3_2_1_40_1","unstructured":"Rong-Hua Li Jeffrey\u00a0Xu Yu Lu Qin Rui Mao and Tan Jin. 2015. On random walk based graph sampling. In ICDE."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783285"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Arun\u00a0S Maiya and Tanya\u00a0Y Berger-Wolf. 2010. Sampling community structure. In WWW.","DOI":"10.1145\/1772690.1772762"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0136497"},{"key":"e_1_3_2_1_44_1","unstructured":"Davood Rafiei. 2005. Effectively visualizing large networks through sampling. In VIS."},{"key":"e_1_3_2_1_45_1","unstructured":"Stuart Russell and Peter Norvig. 2002. Artificial intelligence: a modern approach."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1002\/sam.11224"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Arnab Sinha Zhihong Shen Yang Song Hao Ma Darrin Eide Bo-June Hsu and Kuansan Wang. 2015. An overview of microsoft academic service (mas) and applications. In WWW.","DOI":"10.1145\/2740908.2742839"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3059194"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0023176"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-007-0094-2"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Charalampos\u00a0E Tsourakakis U Kang Gary\u00a0L Miller and Christos Faloutsos. 2009. Doulion: counting triangles in massive graphs with a coin. In KDD.","DOI":"10.1145\/1557019.1557111"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Elli Voudigari Nikos Salamanos Theodore Papageorgiou and Emmanuel\u00a0J Yannakoudakis. 2016. Rank degree: An efficient algorithm for graph sampling. In ASONAM.","DOI":"10.1109\/ASONAM.2016.7752223"},{"key":"e_1_3_2_1_53_1","volume-title":"A practical approach to microarray data analysis","author":"Wall E","unstructured":"Michael\u00a0E Wall, Andreas Rechtsteiner, and Luis\u00a0M Rocha. 2003. Singular value decomposition and principal component analysis. In A practical approach to microarray data analysis. Springer, 91\u2013109."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"crossref","unstructured":"Jianling Wang Kaize Ding Liangjie Hong Huan Liu and James Caverlee. 2020. Next-item recommendation with sequential hypergraphs. In SIGIR.","DOI":"10.1145\/3397271.3401133"},{"key":"e_1_3_2_1_55_1","unstructured":"Michael\u00a0M Wolf Alicia\u00a0M Klinvex and Daniel\u00a0M Dunlavy. 2016. Advantages to modeling relational data using hypergraphs versus graphs. In HPEC."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"crossref","unstructured":"Xin Xu Chul-Ho Lee 2014. A general framework of hybrid graph sampling for complex network analysis. In INFOCOM.","DOI":"10.1109\/INFOCOM.2014.6848229"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"crossref","unstructured":"Dingqi Yang Bingqing Qu Jie Yang and Philippe Cudre-Mauroux. 2019. Revisiting user mobility and social relationships in lbsns: a hypergraph embedding approach. In WWW.","DOI":"10.1145\/3308558.3313635"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"crossref","unstructured":"Hao Yin Austin\u00a0R Benson Jure Leskovec and David\u00a0F Gleich. 2017. Local higher-order graph clustering. In KDD.","DOI":"10.1145\/3097983.3098069"},{"key":"e_1_3_2_1_59_1","unstructured":"Jaemin Yoo U Kang Mauro Scanagatta Giorgio Corani and Marco Zaffalon. 2020. Sampling Subgraphs with Guaranteed Treewidth for Accurate and Efficient Graphical Inference. In WSDM."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"crossref","unstructured":"Se-eun Yoon Hyungseok Song Kijung Shin and Yung Yi. 2020. How Much and When Do We Need Higher-order Information in Hypergraphs? A Case Study on Hyperedge Prediction. In WWW.","DOI":"10.1145\/3366423.3380016"},{"key":"e_1_3_2_1_61_1","volume-title":"Graphsaint: Graph sampling based inductive learning method. In ICLR.","author":"Zeng Hanqing","year":"2020","unstructured":"Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. 2020. Graphsaint: Graph sampling based inductive learning method. In ICLR."},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"crossref","unstructured":"Peixiang Zhao Charu Aggarwal and Gewen He. 2016. Link prediction in graph streams. In ICDE.","DOI":"10.1109\/ICDE.2016.7498270"},{"key":"e_1_3_2_1_63_1","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 NIPS."}],"event":{"name":"WWW '22: The ACM Web Conference 2022","location":"Virtual Event, Lyon France","acronym":"WWW '22","sponsor":["SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web"]},"container-title":["Proceedings of the ACM Web Conference 2022"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485447.3512157","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485447.3512157","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:14Z","timestamp":1750188674000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485447.3512157"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,25]]},"references-count":63,"alternative-id":["10.1145\/3485447.3512157","10.1145\/3485447"],"URL":"https:\/\/doi.org\/10.1145\/3485447.3512157","relation":{},"subject":[],"published":{"date-parts":[[2022,4,25]]},"assertion":[{"value":"2022-04-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}