{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:27:31Z","timestamp":1750220851747,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,1,20]],"date-time":"2020-01-20T00:00:00Z","timestamp":1579478400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"The Swiss NSF grant","award":["IZKSZ2 162188"],"award-info":[{"award-number":["IZKSZ2 162188"]}]},{"name":"The National Research Foundation of Korea (NRF) funded by MSIT","award":["NRF-2015K1A3A1A14021055"],"award-info":[{"award-number":["NRF-2015K1A3A1A14021055"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,1,20]]},"DOI":"10.1145\/3336191.3371815","type":"proceedings-article","created":{"date-parts":[[2020,1,22]],"date-time":"2020-01-22T19:08:16Z","timestamp":1579720096000},"page":"708-716","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Sampling Subgraphs with Guaranteed Treewidth for Accurate and Efficient Graphical Inference"],"prefix":"10.1145","author":[{"given":"Jaemin","family":"Yoo","sequence":"first","affiliation":[{"name":"Seoul National University, Seoul, Republic of Korea"}]},{"given":"U","family":"Kang","sequence":"additional","affiliation":[{"name":"Seoul National University, Seoul, Republic of Korea"}]},{"given":"Mauro","family":"Scanagatta","sequence":"additional","affiliation":[{"name":"Fondazione Bruno Kessler, Trento, Italy"}]},{"given":"Giorgio","family":"Corani","sequence":"additional","affiliation":[{"name":"IDSIA (Istituto Dalle Molle di Studi sull'Intelligenza Artificiale), Lugano, Switzerland"}]},{"given":"Marco","family":"Zaffalon","sequence":"additional","affiliation":[{"name":"IDSIA (Istituto Dalle Molle di Studi sull'Intelligenza Artificiale), Lugano, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2020,1,22]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Glance","author":"Adamic Lada A.","year":"2005","unstructured":"Lada A. Adamic and Natalie S . Glance . 2005 . The political blogosphere and the 2004 U.S. election: divided they blog. In LinkKDD . 36--43. Lada A. Adamic and Natalie S. Glance. 2005. The political blogosphere and the 2004 U.S. election: divided they blog. In LinkKDD . 36--43."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.1145\/2601438"},{"doi-asserted-by":"crossref","unstructured":"Leman Akoglu. 2014. Quantifying Political Polarity Based on Bipartite Opinion Networks. In ICWSM .  Leman Akoglu. 2014. Quantifying Political Polarity Based on Bipartite Opinion Networks. In ICWSM .","key":"e_1_3_2_1_3_1","DOI":"10.1609\/icwsm.v8i1.14524"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_4_1","DOI":"10.1137\/0608024"},{"doi-asserted-by":"crossref","unstructured":"Erman Ayday and Faramarz Fekri. 2010. A belief propagation based recommender system for online services. In RecSys . 217--220.  Erman Ayday and Faramarz Fekri. 2010. A belief propagation based recommender system for online services. In RecSys . 217--220.","key":"e_1_3_2_1_5_1","DOI":"10.1145\/1864708.1864751"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_6_1","DOI":"10.1016\/j.ic.2009.03.008"},{"doi-asserted-by":"crossref","unstructured":"Andr\u00e9 s Cano and Seraf'i n Moral. 1994. Heuristic Algorithms for the Triangulation of Graphs. In IPMU. 98--107.  Andr\u00e9 s Cano and Seraf'i n Moral. 1994. Heuristic Algorithms for the Triangulation of Graphs. In IPMU. 98--107.","key":"e_1_3_2_1_7_1","DOI":"10.1007\/BFb0035941"},{"key":"e_1_3_2_1_8_1","volume-title":"Polonium: Tera-Scale Graph Mining for Malware Detection. In SDM. 131--142.","author":"Chau Duen Horng","year":"2011","unstructured":"Duen Horng Chau , Carey Nachenberg , Jeffrey Wilhelm , Adam Wright , and Christos Faloutsos . 2011 . Polonium: Tera-Scale Graph Mining for Malware Detection. In SDM. 131--142. Duen Horng Chau, Carey Nachenberg, Jeffrey Wilhelm, Adam Wright, and Christos Faloutsos. 2011. Polonium: Tera-Scale Graph Mining for Malware Detection. In SDM. 131--142."},{"doi-asserted-by":"crossref","unstructured":"Wolfgang Gatterbauer. 2017. The Linearization of Belief Propagation on Pairwise Markov Random Fields. In AAAI . 3747--3753.  Wolfgang Gatterbauer. 2017. The Linearization of Belief Propagation on Pairwise Markov Random Fields. In AAAI . 3747--3753.","key":"e_1_3_2_1_9_1","DOI":"10.1609\/aaai.v31i1.11059"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_10_1","DOI":"10.14778\/2735479.2735490"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.5555\/1046920.1088703"},{"doi-asserted-by":"crossref","unstructured":"Min-Hee Jang Christos Faloutsos Sang-Wook Kim U. Kang and Jiwoon Ha. 2016. PIN-TRUST: Fast Trust Propagation Exploiting Positive Implicit and Negative Information. In CIKM. 629--638.  Min-Hee Jang Christos Faloutsos Sang-Wook Kim U. Kang and Jiwoon Ha. 2016. PIN-TRUST: Fast Trust Propagation Exploiting Positive Implicit and Negative Information. In CIKM. 629--638.","key":"e_1_3_2_1_12_1","DOI":"10.1145\/2983323.2983753"},{"unstructured":"Saehan Jo Jaemin Yoo and U. Kang. 2018. Fast and Scalable Distributed Loopy Belief Propagation on Real-World Graphs. In WSDM .  Saehan Jo Jaemin Yoo and U. Kang. 2018. Fast and Scalable Distributed Loopy Belief Propagation on Real-World Graphs. In WSDM .","key":"e_1_3_2_1_13_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_14_1","DOI":"10.1007\/s10618-019-00630-6"},{"key":"e_1_3_2_1_15_1","volume-title":"Duen Horng Chau, and Christos Faloutsos","author":"Kang U.","year":"2011","unstructured":"U. Kang , Duen Horng Chau, and Christos Faloutsos . 2011 . Mining large graphs: Algorithms, inference, and discoveries. In ICDE. 243--254. U. Kang, Duen Horng Chau, and Christos Faloutsos. 2011. Mining large graphs: Algorithms, inference, and discoveries. In ICDE. 243--254."},{"key":"e_1_3_2_1_16_1","volume-title":"Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 392--401","author":"Karger David","year":"2001","unstructured":"David Karger , David Karger , and Nathan Srebro . 2001 . Learning Markov networks: Maximum bounded tree-width graphs . In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 392--401 . David Karger, David Karger, and Nathan Srebro. 2001. Learning Markov networks: Maximum bounded tree-width graphs. In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 392--401."},{"volume-title":"Probabilistic Graphical Models - Principles and Techniques","author":"Koller Daphne","unstructured":"Daphne Koller and Nir Friedman . 2009. Probabilistic Graphical Models - Principles and Techniques . MIT Press . Daphne Koller and Nir Friedman. 2009. Probabilistic Graphical Models - Principles and Techniques .MIT Press.","key":"e_1_3_2_1_17_1"},{"key":"e_1_3_2_1_18_1","volume-title":"Percus","author":"Krishnamurthy Vaishnavi","year":"2005","unstructured":"Vaishnavi Krishnamurthy , Michalis Faloutsos , Marek Chrobak , Li Lao , Jun-Hong Cui , and Allon G . Percus . 2005 . Reducing Large Internet Topologies for Faster Simulations. In NETWORKING. 328--341. Vaishnavi Krishnamurthy, Michalis Faloutsos, Marek Chrobak, Li Lao, Jun-Hong Cui, and Allon G. Percus. 2005. Reducing Large Internet Topologies for Faster Simulations. In NETWORKING. 328--341."},{"doi-asserted-by":"crossref","unstructured":"Jure Leskovec and Christos Faloutsos. 2006. Sampling from large graphs. In KDD .  Jure Leskovec and Christos Faloutsos. 2006. Sampling from large graphs. In KDD .","key":"e_1_3_2_1_19_1","DOI":"10.1145\/1150402.1150479"},{"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 KDD .  Jure Leskovec Jon M. Kleinberg and Christos Faloutsos. 2005. Graphs over time: densification laws shrinking diameters and possible explanations. In KDD .","key":"e_1_3_2_1_20_1","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_3_2_1_21_1","volume-title":"Lu Qin, Rui Mao, and Tan Jin.","author":"Li Rong-Hua","year":"2015","unstructured":"Rong-Hua Li , Jeffrey Xu Yu , Lu Qin, Rui Mao, and Tan Jin. 2015 . On random walk based graph sampling. In ICDE. 927--938. Rong-Hua Li, Jeffrey Xu Yu, Lu Qin, Rui Mao, and Tan Jin. 2015. On random walk based graph sampling. In ICDE. 927--938."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_22_1","DOI":"10.1145\/3022186"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_23_1","DOI":"10.1145\/2783258.2783285"},{"unstructured":"Mary McGlohon Stephen Bay Markus G. Anderle David M. Steier and Christos Faloutsos. 2009. SNARE: a link analytic system for graph labeling and risk detection. In KDD . 1265--1274.  Mary McGlohon Stephen Bay Markus G. Anderle David M. Steier and Christos Faloutsos. 2009. SNARE: a link analytic system for graph labeling and risk detection. In KDD . 1265--1274.","key":"e_1_3_2_1_24_1"},{"key":"e_1_3_2_1_25_1","volume-title":"Kappen","author":"Mooij Joris M.","year":"2012","unstructured":"Joris M. Mooij and Hilbert J . Kappen . 2012 . Sufficient conditions for convergence of Loopy Belief Propagation. CoRR , Vol. abs\/ 1207 .1405 (2012). arxiv: 1207.1405 Joris M. Mooij and Hilbert J. Kappen. 2012. Sufficient conditions for convergence of Loopy Belief Propagation. CoRR , Vol. abs\/1207.1405 (2012). arxiv: 1207.1405"},{"doi-asserted-by":"crossref","unstructured":"Sharad Nandanwar and M. Narasimha Murty. 2016. Structural Neighborhood Based Classification of Nodes in a Network. In KDD . 1085--1094.  Sharad Nandanwar and M. Narasimha Murty. 2016. Structural Neighborhood Based Classification of Nodes in a Network. In KDD . 1085--1094.","key":"e_1_3_2_1_26_1","DOI":"10.1145\/2939672.2939782"},{"key":"e_1_3_2_1_27_1","volume-title":"Cassio Polpo de Campos, and Qiang Ji","author":"Nie Siqi","year":"2016","unstructured":"Siqi Nie , Cassio Polpo de Campos, and Qiang Ji . 2016 . Learning Bayesian Networks with Bounded Tree-width via Guided Search. In AAAI . 3294--3300. Siqi Nie, Cassio Polpo de Campos, and Qiang Ji. 2016. Learning Bayesian Networks with Bounded Tree-width via Guided Search. In AAAI . 3294--3300."},{"key":"e_1_3_2_1_28_1","volume-title":"Cassio Polpo de Campos, and Qiang Ji.","author":"Nie Siqi","year":"2014","unstructured":"Siqi Nie , Denis Deratani Mau\u00e1 , Cassio Polpo de Campos, and Qiang Ji. 2014 . Advances in Learning Bayesian Networks of Bounded Treewidth. In NIPS . Siqi Nie, Denis Deratani Mau\u00e1, Cassio Polpo de Campos, and Qiang Ji. 2014. Advances in Learning Bayesian Networks of Bounded Treewidth. In NIPS ."},{"key":"e_1_3_2_1_29_1","volume-title":"Samuel Wang, and Christos Faloutsos.","author":"Pandit Shashank","year":"2007","unstructured":"Shashank Pandit , Duen Horng Chau , Samuel Wang, and Christos Faloutsos. 2007 . Netprobe: a fast and scalable system for fraud detection in online auction networks. In WWW . 201--210. Shashank Pandit, Duen Horng Chau, Samuel Wang, and Christos Faloutsos. 2007. Netprobe: a fast and scalable system for fraud detection in online auction networks. In WWW . 201--210."},{"key":"e_1_3_2_1_30_1","first-page":"2","article-title":"On the structure of k-trees","volume":"11","author":"Patil HP","year":"1986","unstructured":"HP Patil . 1986 . On the structure of k-trees . Journal of Combinatorics, Information and System Sciences , Vol. 11 , 2 -- 4 (1986), 57--64. HP Patil. 1986. On the structure of k-trees. Journal of Combinatorics, Information and System Sciences , Vol. 11, 2--4 (1986), 57--64.","journal-title":"Journal of Combinatorics, Information and System Sciences"},{"key":"e_1_3_2_1_31_1","volume-title":"Towsley","author":"Ribeiro Bruno F.","year":"2010","unstructured":"Bruno F. Ribeiro and Donald F . Towsley . 2010 . Estimating and sampling graphs with multidimensional random walks. In IMC . 390--403. Bruno F. Ribeiro and Donald F. Towsley. 2010. Estimating and sampling graphs with multidimensional random walks. In IMC . 390--403."},{"key":"e_1_3_2_1_32_1","volume-title":"Cassio Polpo de Campos, and Marco Zaffalon","author":"Scanagatta Mauro","year":"2016","unstructured":"Mauro Scanagatta , Giorgio Corani , Cassio Polpo de Campos, and Marco Zaffalon . 2016 . Learning Treewidth-Bounded Bayesian Networks with Thousands of Variables. In NIPS . 1462--1470. Mauro Scanagatta, Giorgio Corani, Cassio Polpo de Campos, and Marco Zaffalon. 2016. Learning Treewidth-Bounded Bayesian Networks with Thousands of Variables. In NIPS . 1462--1470."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_33_1","DOI":"10.1016\/j.ijar.2018.02.004"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_34_1","DOI":"10.1609\/aimag.v29i3.2157"},{"key":"e_1_3_2_1_35_1","volume-title":"Maximum likelihood bounded tree-width Markov networks. Artificial intelligence","author":"Srebro Nathan","year":"2003","unstructured":"Nathan Srebro . 2003. Maximum likelihood bounded tree-width Markov networks. Artificial intelligence , Vol. 143 , 1 ( 2003 ), 123--138. Nathan Srebro. 2003. Maximum likelihood bounded tree-width Markov networks. Artificial intelligence , Vol. 143, 1 (2003), 123--138."},{"doi-asserted-by":"crossref","unstructured":"Acar Tamersoy Kevin A. Roundy and Duen Horng Chau. 2014. Guilt by association: large scale malware detection by mining file-relation graphs. In KDD .  Acar Tamersoy Kevin A. Roundy and Duen Horng Chau. 2014. Guilt by association: large scale malware detection by mining file-relation graphs. In KDD .","key":"e_1_3_2_1_36_1","DOI":"10.1145\/2623330.2623342"},{"key":"e_1_3_2_1_37_1","volume-title":"Yannakoudakis","author":"Voudigari Elli","year":"2016","unstructured":"Elli Voudigari , Nikos Salamanos , Theodore Papageorgiou , and Emmanuel J . Yannakoudakis . 2016 . Rank degree: An efficient algorithm for graph sampling. In ASONAM. 120--129. Elli Voudigari, Nikos Salamanos, Theodore Papageorgiou, and Emmanuel J. Yannakoudakis. 2016. Rank degree: An efficient algorithm for graph sampling. In ASONAM. 120--129."},{"doi-asserted-by":"crossref","unstructured":"Tianyi Wang Yang Chen Zengbin Zhang Tianyin Xu Long Jin Pan Hui Beixing Deng and Xing Li. 2011. Understanding Graph Sampling Algorithms for Social Network Analysis. In ICDCS . 123--128.  Tianyi Wang Yang Chen Zengbin Zhang Tianyin Xu Long Jin Pan Hui Beixing Deng and Xing Li. 2011. Understanding Graph Sampling Algorithms for Social Network Analysis. In ICDCS . 123--128.","key":"e_1_3_2_1_38_1","DOI":"10.1109\/ICDCSW.2011.34"},{"unstructured":"Jonathan S. Yedidia William T. Freeman and Yair Weiss. 2003. Understanding Belief Propagation and Its Generalizations. In Exploring Artificial Intelligence in the New Millennium. 239--269.  Jonathan S. Yedidia William T. Freeman and Yair Weiss. 2003. Understanding Belief Propagation and Its Generalizations. In Exploring Artificial Intelligence in the New Millennium. 239--269.","key":"e_1_3_2_1_39_1"},{"unstructured":"Jaemin Yoo Saehan Jo and U. Kang. 2017. Supervised Belief Propagation: Scalable Supervised Inference on Attributed Networks. In ICDM . 595--604.  Jaemin Yoo Saehan Jo and U. Kang. 2017. Supervised Belief Propagation: Scalable Supervised Inference on Attributed Networks. In ICDM . 595--604.","key":"e_1_3_2_1_40_1"}],"event":{"sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data","SIGIR ACM Special Interest Group on Information Retrieval"],"acronym":"WSDM '20","name":"WSDM '20: The Thirteenth ACM International Conference on Web Search and Data Mining","location":"Houston TX USA"},"container-title":["Proceedings of the 13th International Conference on Web Search and Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3336191.3371815","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3336191.3371815","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:14Z","timestamp":1750202594000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3336191.3371815"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,20]]},"references-count":40,"alternative-id":["10.1145\/3336191.3371815","10.1145\/3336191"],"URL":"https:\/\/doi.org\/10.1145\/3336191.3371815","relation":{},"subject":[],"published":{"date-parts":[[2020,1,20]]},"assertion":[{"value":"2020-01-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}