The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions Journal: Journal of Theoretical Computer Science

Atticus McWhorter, Daryl DeFord · 2025

Read The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions Journal: Journal of Theoretical Computer Science by Atticus McWhorter, Daryl DeFord (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-17714.txt.

Introduction

Atticus McWhorter and Daryl DeFord introduce a new sampling walk for redistricting maps in a 2025 arXiv paper. Analysts model district plans as partitions of a graph built from map units. Random sampling methods generate large ensembles of plans for comparison. Popular methods lean heavily toward plans favored by a spanning tree count, which can bias the ensemble. A spanning tree is a skeleton linking all units without loops.

Their Marked Edge Walk moves across spanning trees that carry marked edges. Its transition chances can be computed exactly, which suits the Metropolis-Hastings sampling method. Tests on real map graphs for New Hampshire and Texas showed broad convergence. Target goals like competitiveness and compactness could be aimed at directly. The spanning tree bias shrank compared with older methods.

Catalog record

CREATORAtticus McWhorter, Daryl DeFord
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-17714

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions Journal: Journal of Theoretical Computer Science Atticus McWhorter, Daryl DeFord Abstract 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. 1 Introduction Recent advances in computational capabilities have greatly increased legislators’ abilities to optimize political redistricting plans. In efforts to develop a baseline of ‘typical’ plans, researchers have largely turned to Markov Chain Monte Carlo (MCMC) methods to generate large ensembles of allowable plans [ 1 , 2 , 3 , 4 , 5 ] . In these algorithms, states are encoded as planar graphs, and random walks explore the space of balanced graph partitions, corresponding to redistricting plans. A number of different algorithms are available to researchers who hope to generate an ensemble of redistricting plans; however all current algorithms have their drawbacks. Recombination (ReCom) [ 6 ] has gained significant popularity [ 3 , 7 , 2 , 8 , 9 ] due to its favorable mixing properties, and studies using ReCom have been used to argue the constitutionality of districting plans in courts as high as the U.S. Supreme Court [ 10 ] . However, the invariant distribution of ReCom is unknown [ 11 ] . The Reversible Recombination (RevReCom) algorithm tailors ReCom to satisfy the detailed balance condition and target the spanning tree distribution, a distribution which weights each graph partition according to the product of the number of spanning trees of each part. Great attention has been devoted to the spanning tree distribution [ 11 , 12 , 13 , 14 ] . Ref. [ 15 ] showed that the spanning tree distribution is inversely exponentially related to the total boundary lengths of the districts, and Ref. [ 16 ] developed an algorithm that can sample from the distribution in polynomial time. Despite great attention to the spanning tree distribution, there is still an open problem of sampling from any distribution. Metropolized Forest Recombination (MFR) [ 17 ] attempts to do exactly that, utilizing the powerful tools of the Metropolis-Hastings algorithm to target any desired invariant distribution. To achieve this, the authors ‘lift’ to an expanded state space of spanning forests that allows for easier calculation of the forward and reverse transition probabilities. However, it is still an open question what distributions can effectively be sampled using this method. Recently, a preprint was released that introduces a novel walk on the lifted space that appears to reduce the reliance on the spanning tree distribution [ 18 ] . In this paper, we present the marked edge walk (MEW), an algorithm for sampling from the space of balanced graph partitions under a tuneable distribution that displays fast mixing, even when sampling from distributions that are unrelated to the spanning tree distribution. 2 Procedure The space of interest of MEW is the space of balanced graph partitions of a fixed graph G=(V,E) . In our application, we choose G to have a finite set of vertices V and undirected edges E . A graph partition \xi:V\rightarrow\{1,2,...,d\} sorts each vertex into a part. However, instead of representing each state as a graph partition, as in Ref. [ 6 ] , we instead lift to the space of spanning trees with marked edges. More formally, the state space of MEW is: \mathcal{X}=\{(T,M):T\text{ is a spanning tree of }G,M\subseteq T\}. (1) We will enforce that the forest F=T\setminus M is balanced, where a forest F is balanced if each connected component D_{i} satisfies |D_{i}|=n/d\pm\epsilon (node balance) or \sum_{v\in D_{i}}w(v)=W/d\pm\epsilon (population balance) for vertex weights w:V\rightarrow\mathbb{R}_{\geq 0} and total weight W=\sum_{v\in V}w(v) . In this work, we enforce population balance by rejecting proposals that yield unbalanced forests, similar to the approach in [ 6 ] . Another approach can be found in [ 17 , 19 ] , where the authors incorporate balance conditions in the target distribution, allowing for both hard and soft balance constraints. From a state x\in\mathcal{X} , the MEW transition consists of two parts: 1. Cycle basis step: Choose an edge e_{+}\in E\setminus T according to some distribution \nu_{1} . Let C be the unique cycle in T\cup\{e_{+}\} . Choose an edge e_{-}\in C according to some distribution \nu_{2} and subject to the constraint that e_{-}\notin M (marked edges cannot be removed), and set T^{\prime}=(T\cup\{e_{+}\})\setminus\{e_{-}\} . 2. Marked edge step: Choose a marked edge m\in M according to some distribution \mu_{1} . Choose an endpoint u\in m according to some distribution \mu_{2} . Choose a neighbor v\in N_{T^{\prime}}(u) according to some distribution \mu_{3} , and let m^{\prime}=\{u,v\} . Set M^{\prime}=(M\cup\{m^{\prime}\})\setminus\{m\} . For the current study and the following calculations, we choose \nu_{1},\nu_{2},\mu_{1},\mu_{2}, and \mu_{3} to be uniform, but one could easily incorporate other distributions to, for example, avoid repeated selection of high-degree vertices, incentivize the selection of plans with low isoperimetric scores, or disincentivize the splitting of counties or towns as in Ref. [ 2 , 9 ] . A schematic of the procedure as chosen in our study is shown in Figure 1 . Figure 1: Illustration of MEW’s two-step procedure. (Top-left) Initial state with spanning tree (black edges) and marked edges (red) that create a balanced partition when removed. (Top-right) Cycle basis step: adding edge e_{+} (green) creates cycle C (blue), then removing edge e_{-} (orange) yields new tree T^{\prime} . (Bottom-left) Marked edge step: the right vertex of the marked edge (red) is chosen, and its right neighbor is chosen, yielding a new marked edge (pink). (Bottom-right) These two steps create a new partition, completing one step of the MEW procedure. An alternate formulation of MEW could take a probabilistic choice between the cycle basis step and the marked edge step. In this variant, with probability p , one would take a cycle basis step, and with probability 1-p , a marked edge step. This approach has the benefit of symmetric transitions, adding computational simplicity and yielding the theoretical result that, if the walk is irreducible, the unique stationary distribution is the uniform distribution on \mathcal{X} . 3 Transition Probabilities While the probabilistic variant targets the uniform distribution, for redistricting applications, we often want to target alternative distributions p(x) . To achieve this, we employ MEW (performing both a cycle basis step and a marked edge step sequentially) as a proposal in the Metropolis-Hastings algorithm. The algorithm generates samples from a target distribution p(x) by rejection sampling according to an acceptance probability: a=1\wedge\frac{p(x^{\prime})}{p(x)}\frac{P(x|x^{\prime})}{P(x^{\prime}|x)} (2) where P(x^{\prime}|x) and P(x|x^{\prime}) are the forward and backward transition probabilities of MEW. Given two states x=(T,M) and x^{\prime}=(T^{\prime},M^{\prime}) , the transition probability P(x^{\prime}|x) decomposes naturally according to the two components

Read the complete text