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

• URL: http://arxiv.org/abs/2603.18347v1
• Date: Wed, 18 Mar 2026 23:13:05 GMT
• Title: Bonsai: A class of effective methods for independent sampling of graph partitions
• Abstract summary: We develop effective methods for constructing an ensemble of district plans via independent sampling from a reasonable probability distribution on the space of graph partitions.<n>We compare our algorithms to that of standard Markov Chain based algorithms in the context of grid graphs and state congressional and legislative maps.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We develop effective methods for constructing an ensemble of district plans via independent sampling from a reasonable probability distribution on the space of graph partitions. We compare the performance of our algorithms to that of standard Markov Chain based algorithms in the context of grid graphs and state congressional and legislative maps. For the case of perfect population balance between districts, we provide an explicit description of the distribution from which our method samples.

Related papers

• 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)
• Learning local neighborhoods of non-Gaussian graphical models: A measure transport approach [0.3749861135832072]
  We propose a scalable algorithm to infer the conditional independence relationships of each variable by exploiting the local Markov property.<n>The proposed method, named Localized Sparsity Identification for Non-Gaussian Distributions (L-SING), estimates the graph by using flexible classes of transport maps.
  arXiv  Detail & Related papers  (2025-03-18T04:53:22Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Spanning tree methods for sampling graph partitions [0.7658085223797904]
  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.
  arXiv  Detail & Related papers  (2022-10-04T06:18:33Z)
• Wrapped Distributions on homogeneous Riemannian manifolds [58.720142291102135]
  Control over distributions' properties, such as parameters, symmetry and modality yield a family of flexible distributions. We empirically validate our approach by utilizing our proposed distributions within a variational autoencoder and a latent space network model.
  arXiv  Detail & Related papers  (2022-04-20T21:25:21Z)
• Bayesian Graph Contrastive Learning [55.36652660268726]
  We propose a novel perspective of graph contrastive learning methods showing random augmentations leads to encoders. Our proposed method represents each node by a distribution in the latent space in contrast to existing techniques which embed each node to a deterministic vector. We show a considerable improvement in performance compared to existing state-of-the-art methods on several benchmark datasets.
  arXiv  Detail & Related papers  (2021-12-15T01:45:32Z)
• 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)
• A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms [67.67377846416106]
  We present a distributional approach to theoretical analyses of reinforcement learning algorithms for constant step-sizes. We show that value-based methods such as TD($lambda$) and $Q$-Learning have update rules which are contractive in the space of distributions of functions.
  arXiv  Detail & Related papers  (2020-03-27T05:13:29Z)
• Stein Variational Inference for Discrete Distributions [70.19352762933259]
  We propose a simple yet general framework that transforms discrete distributions to equivalent piecewise continuous distributions. Our method outperforms traditional algorithms such as Gibbs sampling and discontinuous Hamiltonian Monte Carlo. We demonstrate that our method provides a promising tool for learning ensembles of binarized neural network (BNN) In addition, such transform can be straightforwardly employed in gradient-free kernelized Stein discrepancy to perform goodness-of-fit (GOF) test on discrete distributions.
  arXiv  Detail & Related papers  (2020-03-01T22:45:41Z)
• Distributed Sketching Methods for Privacy Preserving Regression [54.51566432934556]
  We leverage randomized sketches for reducing the problem dimensions as well as preserving privacy and improving straggler resilience in asynchronous distributed systems. We derive novel approximation guarantees for classical sketching methods and analyze the accuracy of parameter averaging for distributed sketches. We illustrate the performance of distributed sketches in a serverless computing platform with large scale experiments.
  arXiv  Detail & Related papers  (2020-02-16T08:35: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.