Sampling Subgraphs with Guaranteed Treewidth for Accurate and Efficient Graphical Inference

Overview

How can we run graphical inference on large graphs efficiently and accurately? Many real-world networks are modeled as graphical models, and graphical inference is fundamental to understand the properties of those networks. In this work, we propose a novel approach for fast and accurate inference, which first samples a small subgraph and then runs inference over the subgraph instead of the given graph. This is done by the bounded treewidth (BTW) sampling, our novel algorithm that generates a subgraph with guaranteed bounded treewidth while retaining as many edges as possible. We first analyze the properties of BTW theoretically. Then, we evaluate our approach on node classification and compare it with the baseline which is to run loopy belief propagation (LBP) on the original graph. Our approach can be coupled with various inference algorithms: it shows higher accuracy up to 13.7% with the junction tree algorithm, and allows faster inference up to 23.8 times with LBP. We further compare BTW with previous graph sampling algorithms and show that it gives the best accuracy.

Paper

• Sampling Subgraphs with Guaranteed Treewidth for Accurate and Efficient Graphical Inference
  Jaemin Yoo, U Kang, Mauro Scanagatta, Giorgio Corani, and Marco Zaffalon
  ACM International Conference on Web Search and Data Mining (WSDM) 2020, Houston, Texas, USA.
  [PDF] [BibTeX]

Code

The code used in the paper is available. [Download]

Datasets

People

• Jaemin Yoo (Seoul National University)
• U Kang (Seoul National University)
• Mauro Scanagatta (Fondazione Bruno Kessler)
• Giorgio Corani (IDSIA)
• Marco Zaffalon (IDSIA)