Sampling Subgraphs with Guaranteed Treewidth for Accurate and Efficient Graphical Inference


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.



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


Name Nodes Edges Labels Description Download
Wikipedia 35,579 495,337 16 Web network Link
CoRA 23,567 91,965 10 Citation network Link
PubMed 19,717 44,324 3 Citation network Link
PolBlogs 1,222 16,714 2 Web network Link