Sampling From Gaussian Markov Random Fields Using Stationary and Non-Stationary Subgraph Perturbations

Gaussian Markov random fields (GMRFs) or Gaussian graphical models have been widely used in many applications. Efficiently drawing samples from GMRFs has been an important research problem. In this paper, we introduce the subgraph perturbation sampling algorithm, which makes use of any pre-existing tractable inference algorithm for a subgraph by perturbing this algorithm so as to yield asymptotically exact samples for the intended distribution. We study the stationary version where a single fixed subgraph is used in all iterations, as well as the non-stationary version where tractable subgraphs are adaptively selected. The subgraphs used can have any structure for which efficient inference algorithms exist: for example, tree-structured, low tree-width, or having a small feedback vertex set. We present new theoretical results that give convergence guarantees for both stationary and non-stationary graphical splittings. Our experiments using both simulated models and large-scale real models demonstrate that this subgraph perturbation algorithm efficiently yields accurate samples for many graph topologies.