Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions

Understand

We develop a new Markov chain on graph partitions that makes relatively global moves yet is computationally feasible to be used as the proposal in the Metropolis-Hastings method.

• Our resulting algorithm can be made reversible and able to sample from a specified measure on partitions.
• Both of these properties are critical to some important applications and computational Bayesian statistics in general.
• Our proposal chain modifies the recently developed method called Recombination (ReCom), which draws spanning trees on joined partitions and then randomly cuts them to repartition.