[Talks@IDSIA] PIDSIA - 18 July h 12

*Speaker: Jeamin Yoo (Seoul National University) *Title: Sampling Graphs with Bounded Treewdith *Abstract: How can we efficiently compute marginal distributions of random variables in a large graph? The problem of graphical inference is a crucial task in data mining and machine learning to understand random variables and their stochastic natures. Especially, the computation of exact inference has been a challenging problem since it requires exponential time with the treewidth of a given graph. Many researches focused on loopy belief propagation (BP), a widely known approximate inference algorithm to solve the problem; however, the lack of theoretical guarantees on its convergence leads to unstable results. In this talk, I introduce BTS (Bounded Treewidth Sampling), a novel graph sampling algorithm for efficient inference. BTS generates subgraphs with bounded treewidth and makes exact inference, specifically the junction tree algorithm, run in linear time with the number of vertices. This leads to more accurate and stable inference, resulting in increased accuracy of vertex classification. Furthermore, BTS 1) speeds up the computation of loopy BP by removing redundant edges in a graph and 2) generates connected and more balanced subgraphs compared with other graph sampling algorithms. *Bio: Jaemin Yoo is a PhD student at Seoul National University, advised by Prof. U Kang. He obtained the B.S. (2016) degree in Computer Science and Engineering at the Seoul National University in Korea. He is a data mining researcher with particular interests in designing supervised and efficient graphical inference algorithms. He submitted papers in top-tier conferences in the field of data mining such as IEEE International Conference on Data Mining (ICDM) 2017 and ACM International Conference on Web Search and Data Mining (WSDM) 2018. *When: 18th of July 2018, 12:00-12:30 *Location: Manno, Galleria 1, 2nd floor, room G1-204 *Registration: Pizza (or alternative food) and drinks will be offered at the end of the talk. If you plan to attend, please register in a timely fashion at the following link so that we will have no shortage of food: https://doodle.com/poll/q28v5yqm9iwrcxsh