Parallel sampling of decomposable graphs using Markov chain on junction trees

Bayesian inference for undirected graphical models is mostly restricted to the class of decomposable graphs, as they enjoy a rich set of properties making them amenable to high-dimensional problems. While parameter inference, in this setup, is straightforward, inferring the underlying graph is a challenge driven by the computational difficultly in exploring the space of decomposable graphs. This work makes two contributions to address this problem. First, we provide sufficient and necessary conditions for when multi-edge perturbations maintain decomposability of the graph. With which, we characterize a simple family of partitions that efficiently classify all edge-perturbations in whether they maintain decomposability. Second, we propose a new parallel non-reversible Markov chain Monte Carlo sampler for distributions over junction tree representations of the graph, where at every step, all edge-perturbations within a partition are carried simultaneous. Through simulations, we demonstrate the efficiency of our edge perturbation-conditions and partitions. We find improved mixing properties of our parallel sampler when compared to a single-move sampler, a variate of it, and when compared to current methods.