Bonsai: A class of effective methods for independent sampling of graph partitions

1. Problem Statement

The paper addresses the challenge of generating ensembles of redistricting plans (graph partitions) to evaluate the fairness of enacted voting maps. Current legal and academic standards rely on comparing enacted maps against thousands of "random" maps generated by algorithms.

• Limitations of Existing Methods: Most standard algorithms, such as ReCom (Recursive Combinations) and Forest ReCom, rely on Markov Chain Monte Carlo (MCMC) methods. These methods suffer from several critical issues:
  • Ergodicity and Mixing Times: There is often no rigorous proof that these chains are ergodic (able to reach all valid states) or that they mix quickly enough to produce independent samples. In some cases, chains are known to be slow-mixing or non-ergodic.
  • Autocorrelation: Samples generated by MCMC are correlated. To achieve a statistically significant "effective sample size," the chains must run for billions of steps, making the process computationally expensive.
  • Sequential Nature: MCMC generates plans sequentially, limiting the ability to parallelize computation.
• Goal: The authors aim to develop a method for independent sampling of district plans. Independent sampling bypasses mixing time concerns, allows for massive parallelization, and ensures the effective sample size equals the actual sample size.

2. Methodology

The authors propose a new class of algorithms named Bonsai, inspired by the art of shaping trees. The core philosophy is to build a district plan by recursively cutting a graph (representing precincts) into smaller connected components, rather than walking through a state space via a Markov chain.

A. The "Complete Cut" Baseline

The authors first analyze a naive approach called Complete Cut:

• Mechanism: Generate a uniform spanning tree of the graph. If the tree contains exactly $k-1$ "valid cut edges" (edges whose removal splits the tree into subtrees with populations that are integer multiples of the ideal district population), remove them to form the districts.
• Failure Mode: Empirical results show that for large graphs, the probability of a random spanning tree being "completely cuttable" drops precipitously (often to 0%). This makes the method infeasible for practical use.

B. The Bonsai Algorithm

To overcome the inefficiency of Complete Cut, the authors introduce Bonsai, a recursive, divide-and-conquer algorithm.

1. Recursive Partitioning:

   • Start with the full graph $G$ and a spanning tree $T$.
   • Identify "valid cut edges" in $T$ that split the graph into two subgraphs, each capable of being further partitioned into the required number of districts.
   • Simultaneous vs. Sequential Cuts: The algorithm can either make all possible valid cuts simultaneously (Algorithm 2) or iteratively remove the "best" valid cut edge, keeping the resulting spanning trees for the subgraphs (Algorithm 3).
   • Recursion: The process repeats recursively on the resulting subgraphs until each subgraph represents a single district.

2. Handling Imperfect Population Balance ($\epsilon > 0$):

   • In real-world scenarios, perfect population balance is impossible. The algorithm introduces a tolerance multiplier function $\phi(n)$ to define what constitutes a "valid" cut.
   • A cut is valid if the population deviation of the resulting subgraphs is within a scaled tolerance $\phi(k_i) \cdot \epsilon$.
   • Selection Strategy: When multiple valid cuts exist, the algorithm selects the "best" triple (edge, district count split) based on criteria such as minimizing the difference in district counts ($|k_1 - k_2|$) and minimizing population deviation.

3. Backtracking Mechanism:

   • To prevent the algorithm from getting "stuck" (e.g., creating a subgraph that cannot be further partitioned), Bonsai includes a backtracking feature.
   • Parameters MaxTrees (max spanning trees drawn before giving up) and MaxFails (max failed partition attempts) trigger a backtrack to the previous split level, allowing the algorithm to try a different cut.

4. Spanning Tree Variations:

   • The algorithm can utilize Uniform Spanning Trees (sampled via Wilson's algorithm) or Minimum Spanning Trees (via Kruskal's algorithm).
   • Minimum Spanning Trees allow for edge weighting, enabling the incorporation of redistricting priorities (e.g., minimizing county splits).

3. Key Contributions

• Independent Sampling Framework: Bonsai provides a mathematically rigorous method for generating independent samples of graph partitions, eliminating the need for long Markov chains and the associated uncertainties of mixing times.
• Theoretical Guarantees:
  • For the case of perfect population balance ($\epsilon=0$), the authors provide an explicit description of the probability distribution from which Bonsai samples.
  • For imperfect balance, they prove (Proposition 2) that if the selection of cuts has full support, any valid district plan has a non-zero probability of being generated. This addresses the irreducibility concerns often plaguing MCMC methods.
• Algorithmic Efficiency: By reusing spanning trees for subgraphs and employing backtracking, Bonsai avoids the exponential failure rates of the "Complete Cut" method.
• Flexibility: The framework accommodates both perfect and imperfect population balance and allows for various spanning tree generation strategies.

4. Empirical Results

The authors tested Bonsai against four variants of ReCom (using uniform/minimum spanning trees and different selection heuristics) on several datasets:

• Grid Graphs: $7\times7$ and $50\times50$ grids with varying numbers of districts.
• Real-World Maps: 2010 Voting District (VTD) graphs for Pennsylvania (18 Congressional districts) and North Carolina (99 State House districts).

Findings:

1. Statistical Similarity: The ensemble statistics generated by Bonsai (specifically regarding cut edges, district perimeters, and partisan vote share distributions) are extremely similar to those generated by ReCom.
2. Positioning: Bonsai's statistics consistently lie between the two main ReCom variants (cut-edge selection vs. district-pair selection), but are generally closer to the district-pair selection variant.
3. Robustness: The results hold true regardless of whether uniform or minimum spanning trees are used, and across different numbers of districts and map sizes.
4. Partisan Metrics: In the Pennsylvania and North Carolina tests, Bonsai produced Democratic vote share distributions nearly identical to ReCom, suggesting it generates substantively comparable baselines for detecting gerrymandering.

5. Significance

• Computational Advantage: Bonsai enables full parallelization. Since each plan is generated independently, thousands of plans can be generated simultaneously on different processors, drastically reducing computation time compared to sequential MCMC chains.
• Statistical Rigor: By guaranteeing independent samples, Bonsai ensures that the effective sample size equals the actual sample size. This removes the need for massive over-sampling to compensate for autocorrelation, making statistical analysis more efficient and reliable.
• Legal and Research Utility: The method offers a transparent, mathematically grounded alternative to "black box" MCMC methods. Its ability to prove that all valid plans are reachable (non-zero probability) strengthens the defensibility of ensemble analysis in court cases regarding voting rights and gerrymandering.
• Validation of Ensemble Analysis: The fact that Bonsai (a fundamentally different algorithmic paradigm) produces results consistent with ReCom strengthens the confidence that ensemble-based metrics are robust to the specific choice of sampling algorithm, provided the algorithm is based on spanning trees.

In conclusion, Bonsai represents a significant advancement in redistricting analysis, offering a faster, more parallelizable, and theoretically transparent method for generating independent samples of district plans, while maintaining statistical equivalence to established Markov Chain-based approaches.