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

• 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)

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.