The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions
This provides a more flexible method for generating redistricting ensembles, addressing a domain-specific need in political science and computational geometry.
The authors tackled the problem of sampling graph partitions for redistricting by introducing the marked edge walk (MEW), a novel MCMC algorithm that operates on spanning trees with marked edges, enabling sampling under tunable distributions and showing convergence on real-world dual graphs.
Novel Markov Chain Monte Carlo (MCMC) methods have enabled the generation of large ensembles of redistricting plans through graph partitioning. However, existing algorithms such as Reversible Recombination (RevReCom) and Metropolized Forest Recombination (MFR) are constrained to sampling from distributions related to spanning trees. We introduce the marked edge walk (MEW), a novel MCMC algorithm for sampling from the space of graph partitions under a tunable distribution. The walk operates on the space of spanning trees with marked edges, allowing for calculable transition probabilities for use in the Metropolis-Hastings algorithm. Empirical results on real-world dual graphs show convergence under target distributions unrelated to spanning trees. For this reason, MEW represents an advancement in flexible ensemble generation.