mlsanityData to 14 Oct 2026

The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions

arXiv 2510.17714 ↗First posted 20 Oct 2025cs.DS cs.LG physics.soc-phcited by 0

Not on the map. Why?

Abstract (arXiv)

Novel Markov Chain Monte Carlo (MCMC) methods have enabled the generation of large ensembles of redistricting plans modeled as a graph partitioning problem. However, existing algorithms such as Reversible Recombination (RevReCom) and Metropolized Forest Recombination (MFR) have strong preferences for distributions related to the spanning tree measure. In this paper we introduce the Marked Edge Walk (MEW), a novel Markov chain proposal for sampling from the space of graph partitions. 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 a broad class of target distributions less constrained by spanning tree counts, including policy-based distributions, such as competitiveness on New Hampshire that are independent of spanning trees, and compactness and partisan symmetry distributions on New Hampshire and Texas that, while related to spanning trees, can now be properly targeted with a smaller degree of spanning tree bias, which represents an advancement in flexible ensemble generation.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 23 of its 40 references that are in the map. First posted on arXiv 20 Oct 2025.

Builds on

23 of 40 references.

References · 23

  1. 2019Recombination: A family of Markov chains for redistrictingcited by 11
  2. 2020Sequential Monte Carlo for Sampling Balanced and Compact Redistricting Planscited by 8
  3. 2016Assessing significance in a Markov chain without mixingcited by 5
  4. 2019Complexity and Geometry of Sampling Connected Graph Partitionscited by 3
  5. 2019Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitionscited by 3
  6. 2021Compact Redistricting Plans Have Many Spanning Treescited by 2
  7. 2022Mathematically Quantifying Non-responsiveness of the 2021 Georgia Congressional Districting Plancited by 2
  8. 2019Optimal Legislative County Clustering in North Carolinacited by 1
  9. 2020A Computational Approach to Measuring Vote Elasticity and Competitivenesscited by 1
  10. 2020Mathematics of Nested Districts: The Case of Alaskacited by 1
  11. 2020The Essential Role of Empirical Validation in Legislative Redistricting Simulationcited by 1
  12. 2020Colorado in Context: Congressional Redistricting and Competing Fairness Criteria in Coloradocited by 1
11 more
  1. 2021Compactness statistics for spanning tree recombinationcited by 1
  2. 2022Subexponential mixing for partition chains on grid-like graphscited by 1
  3. 2022On the Complexity of Sampling Redistricting Planscited by 1
  4. 2023Sampling Balanced Forests of Grids in Polynomial Timecited by 1
  5. 2024Multiscale Parallel Tempering for Fast Sampling on Redistricting Planscited by 1
  6. 2024A Uniformly Random Solution to Algorithmic Redistrictingcited by 1
  7. 2024Bounds and Bugs: The Limits of Symmetry Metrics to Detect Partisan Gerrymanderingcited by 1
  8. 2024Don't Trust A Single Gerrymandering Metriccited by 1
  9. 2025Sampling Tree-Weighted Partitions Without Sampling Treescited by 1
  10. 2025Free Elections in the Free State: Ensemble Analysis of Redistricting in New Hampshirecited by 1
  11. 2025A Cycle Walk for Sampling Measures on Spanning Forests for Redistrictingcited by 1

Built on by

Not cited yet.