Spanning tree methods for sampling graph partitions

• URL: http://arxiv.org/abs/2210.01401v1
• Date: Tue, 4 Oct 2022 06:18:33 GMT
• Title: Spanning tree methods for sampling graph partitions
• Authors: Sarah Cannon, Moon Duchin, Dana Randall, and Parker Rule
• Abstract summary: A districting plan can be viewed as a balanced partition of a graph into connected subsets. RevReCom converges to the simple, natural distribution that ReCom was originally designed to approximate.
• Score: 0.7658085223797904
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the last decade, computational approaches to graph partitioning have made a major impact in the analysis of political redistricting, including in U.S. courts of law. Mathematically, a districting plan can be viewed as a balanced partition of a graph into connected subsets. Examining a large sample of valid alternative districting plans can help us recognize gerrymandering against an appropriate neutral baseline. One algorithm that is widely used to produce random samples of districting plans is a Markov chain called recombination (or ReCom), which repeatedly fuses adjacent districts, forms a spanning tree of their union, and splits that spanning tree with a balanced cut to form new districts. One drawback is that this chain's stationary distribution has no known closed form when there are three or more districts. In this paper, we modify ReCom slightly to give it a property called reversibility, resulting in a new Markov chain, RevReCom. This new chain converges to the simple, natural distribution that ReCom was originally designed to approximate: a plan's stationary probability is proportional to the product of the number of spanning trees of each district. This spanning tree score is a measure of district "compactness" (or shape) that is also aligned with notions of community structure from network science. After deriving the steady state formally, we present diagnostic evidence that the convergence is efficient enough for the method to be practically useful, giving high-quality samples for full-sized problems within several hours. In addition to the primary application of benchmarking of redistricting plans (i.e., describing a normal range for statistics), this chain can also be used to validate other methods that target the spanning tree distribution.

Related papers

• Matrix Factorization Framework for Community Detection under the Degree-Corrected Block Model [48.989531198582704]
  We show that DCBM inference can be reformulated as a constrained nonnegative matrix factorization problem.<n>Our approach is to any specific network structure and applies to graphs with any structure representable by a DCBM.<n> Experiments on synthetic and real benchmark networks show that our method detects communities comparable to those found by DCBM inference.
  arXiv  Detail & Related papers  (2026-01-09T19:16:29Z)
• Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities (II) [51.320599504997745]
  We show that when the number $K$ of communities remains smaller than $sqrtn$, non-trivial community recovery is possible in time above the Kesten--Stigum threshold.<n>We also show that, in moderately sparse settings, the optimal algorithms appear to be fundamentally different from spectral methods.
  arXiv  Detail & Related papers  (2025-11-26T15:54:17Z)
• The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions [0.0]
  We introduce a novel MCMC algorithm for sampling from the space of graph partitions under a tunable distribution.<n>The walk operates on the space of spanning trees with marked edges, allowing for calculable transition probabilities.
  arXiv  Detail & Related papers  (2025-10-20T16:28:42Z)
• Balanced Spanning Tree Distributions Have Separation Fairness [9.543463140987361]
  We introduce the notion of separation fairness, which asks whether adjacent geographic units are separated with at most a constant probability (bounded away from one) in sampled redistricting plans.<n>We prove that a smooth variant of the balanced spanning tree distribution satisfies separation fairness.<n>Our results also provide theoretical support for popular MCMC methods like ReCom, suggesting that they maintain fairness at a granular level in the sampling process.
  arXiv  Detail & Related papers  (2025-09-18T16:48:43Z)
• The Traveling Mailman: Topological Optimization Methods for User-Centric Redistricting [0.0]
  This study introduces a new districting approach using the US Postal Service network to measure community connectivity. We combine Topological Data Analysis with Markov Chain Monte Carlo methods to assess district boundaries' impact on community integrity.
  arXiv  Detail & Related papers  (2024-07-28T16:50:45Z)
• Multiscale Parallel Tempering for Fast Sampling on Redistricting Plans [1.1233768932957773]
  A persuasive method is to compare the plan with an ensemble of neutrally drawn redistricting plans. To audit the partisan difference between the ensemble and a given plan, one must ensure that the non-partisan criteria are matched. In this work, we generate a multiscale parallel tempering approach that makes local moves at each scale.
  arXiv  Detail & Related papers  (2024-01-30T21:33:05Z)
• Region Rebalance for Long-Tailed Semantic Segmentation [89.84860341946283]
  We first investigate and identify the main challenges of addressing this issue through pixel rebalance. Then a simple and yet effective region rebalance scheme is derived based on our analysis. With the proposed region rebalance scheme, state-of-the-art BEiT receives +0.7% gain in terms of mIoU on the ADE20K val set.
  arXiv  Detail & Related papers  (2022-04-05T03:47:47Z)
• Compact Redistricting Plans Have Many Spanning Trees [39.779544988993294]
  In the design and analysis of political redistricting maps, it is often useful to be able to sample from the space of all partitions of the graph of census blocks into connected subgraphs of equal population. In this paper, we establish an inverse exponential relationship between the total length of the boundaries separating districts and the probability that such a map will be sampled.
  arXiv  Detail & Related papers  (2021-09-27T23:36:01Z)
• Direct Measure Matching for Crowd Counting [59.66286603624411]
  We propose a new measure-based counting approach to regress the predicted density maps to the scattered point-annotated ground truth directly. In this paper, we derive a semi-balanced form of Sinkhorn divergence, based on which a Sinkhorn counting loss is designed for measure matching.
  arXiv  Detail & Related papers  (2021-07-04T06:37:33Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  We improve the scalability of Branch and Bound (BaB) algorithms for formally proving input-output properties of neural networks. We present a novel activation-based branching strategy and a BaB framework, named Branch and Dual Network Bound (BaDNB) BaDNB outperforms previous complete verification systems by a large margin, cutting average verification times by factors up to 50 on adversarial properties.
  arXiv  Detail & Related papers  (2021-04-14T09:22:42Z)
• Compactness statistics for spanning tree recombination [0.0]
  "ReCom" method produces plans with more compact districts than some other methods. We construct ensembles of 2-district plans for two grid graphs and for the precinct graph of Boulder County, CO. This is an important step towards understanding compactness properties for districting plans produced by the ReCom method.
  arXiv  Detail & Related papers  (2021-03-03T21:39:51Z)
• SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples [75.32013242448151]
  We consider learning Ising tree models when the observations from the nodes are corrupted by independent but non-identically distributed noise. Katiyar et al. (2020) showed that although the exact tree structure cannot be recovered, one can recover a partial tree structure. We propose Symmetrized Geometric Averaging (SGA), a more statistically robust algorithm for partial tree recovery.
  arXiv  Detail & Related papers  (2021-01-22T01:57:35Z)
• Convex Polytope Trees [57.56078843831244]
  convex polytope trees (CPT) are proposed to expand the family of decision trees by an interpretable generalization of their decision boundary. We develop a greedy method to efficiently construct CPT and scalable end-to-end training algorithms for the tree parameters when the tree structure is given.
  arXiv  Detail & Related papers  (2020-10-21T19:38:57Z)
• Sequential Monte Carlo for Sampling Balanced and Compact Redistricting Plans [0.0]
  We present a new Sequential Monte Carlo (SMC) algorithm that generates a sample of redistricting plans converging to a realistic target distribution. We validate the accuracy of the proposed algorithm by using a small map where all redistricting plans can be enumerated. We then apply the SMC algorithm to evaluate the partisan implications of several maps submitted by relevant parties in a recent high-profile redistricting case in the state of Pennsylvania.
  arXiv  Detail & Related papers  (2020-08-13T23:26:34Z)
• Convolutional Ordinal Regression Forest for Image Ordinal Estimation [52.67784321853814]
  We propose a novel ordinal regression approach, termed Convolutional Ordinal Regression Forest or CORF, for image ordinal estimation. The proposed CORF integrates ordinal regression and differentiable decision trees with a convolutional neural network for obtaining precise and stable global ordinal relationships. The effectiveness of the proposed CORF is verified on two image ordinal estimation tasks, showing significant improvements and better stability over the state-of-the-art ordinal regression methods.
  arXiv  Detail & Related papers  (2020-08-07T10:41:17Z)
• Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
  Local features provide region-to-region rather than point-to-point correspondences. We propose guidelines for effective use of region-to-region matches in the course of a full model estimation pipeline. Experiments show that affine solvers can achieve accuracy comparable to point-based solvers at faster run-times.
  arXiv  Detail & Related papers  (2020-07-20T12:07:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.