PIDSIA - 18 July h 12
by Announcements of talks＠IDSIA
*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
5 years, 9 months
- 1
- 0