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

• URL: http://arxiv.org/abs/2510.17714v2
• Date: Mon, 27 Oct 2025 16:20:43 GMT
• Title: The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions
• Authors: Atticus McWhorter, Daryl DeFord,
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Novel Markov Chain Monte Carlo (MCMC) methods have enabled the generation of large ensembles of redistricting plans through graph partitioning. However, existing algorithms such as Reversible Recombination (RevReCom) and Metropolized Forest Recombination (MFR) are constrained to sampling from distributions related to spanning trees. We introduce the marked edge walk (MEW), a novel MCMC algorithm for sampling from the space of graph partitions under a tunable distribution. 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 target distributions unrelated to spanning trees. For this reason, MEW represents an advancement in flexible ensemble generation.

Related papers

• Thinking with Images as Continuous Actions: Numerical Visual Chain-of-Thought [55.65577137924979]
  We propose a framework that enables MLLMs to reason over images using continuous numerical coordinates.<n> NV-CoT expands the MLLM action space from discrete vocabulary tokens to a continuous Euclidean space.<n>Experiments on three benchmarks demonstrate that NV-CoT significantly improves localization precision and final answer accuracy.
  arXiv  Detail & Related papers  (2026-02-27T12:04:07Z)
• Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs [7.434126318858966]
  We propose a history-driven target (HDT) framework in Markov Chain Monte Carlo (MCMC) to improve any random walk algorithm on discrete state spaces.<n>We show that HDT preserves lightweight implementation by requiring only local information between the current and proposed states.<n>Experiments in graph sampling demonstrate consistent performance gains, and a memory-efficient Least Recently Used (LRU) cache ensures scalability to large general graphs.
  arXiv  Detail & Related papers  (2025-05-23T18:46:10Z)
• Scaling up Dynamic Edge Partition Models via Stochastic Gradient MCMC [33.08344607564694]
  The edge partition model (EPM) is a generative model for extracting an overlapping community structure from static graph-structured data. Despite having many attractive properties, inference in the EPM is typically performed using Markov chain Monte Carlo (MCMC) methods that prevent it from being applied to massive network data.
  arXiv  Detail & Related papers  (2024-02-29T15:19:35Z)
• M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning of Mixture Graph Matching and Clustering [57.947071423091415]
  We introduce Minorize-Maximization Matching and Clustering (M3C), a learning-free algorithm that guarantees theoretical convergence. We develop UM3C, an unsupervised model that incorporates novel edge-wise affinity learning and pseudo label selection. Our method outperforms state-of-the-art graph matching and mixture graph matching and clustering approaches in both accuracy and efficiency.
  arXiv  Detail & Related papers  (2023-10-27T19:40:34Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• 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)
• Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
  This paper focuses on creating a small graph to represent the original graph, so that GNNs trained on the size-reduced graph can make accurate predictions. We view the original graph as a distribution of receptive fields and aim to synthesize a small graph whose receptive fields share a similar distribution.
  arXiv  Detail & Related papers  (2022-06-28T02:10:05Z)
• A new perspective on probabilistic image modeling [92.89846887298852]
  We present a new probabilistic approach for image modeling capable of density estimation, sampling and tractable inference. DCGMMs can be trained end-to-end by SGD from random initial conditions, much like CNNs. We show that DCGMMs compare favorably to several recent PC and SPN models in terms of inference, classification and sampling.
  arXiv  Detail & Related papers  (2022-03-21T14:53:57Z)
• Bayesian Structure Learning with Generative Flow Networks [85.84396514570373]
  In Bayesian structure learning, we are interested in inferring a distribution over the directed acyclic graph (DAG) from data. Recently, a class of probabilistic models, called Generative Flow Networks (GFlowNets), have been introduced as a general framework for generative modeling. We show that our approach, called DAG-GFlowNet, provides an accurate approximation of the posterior over DAGs.
  arXiv  Detail & Related papers  (2022-02-28T15:53:10Z)
• 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)
• Bayesian structure learning and sampling of Bayesian networks with the R package BiDAG [0.0]
  BiDAG implements Markov chain Monte Carlo (MCMC) methods for structure learning and sampling of Bayesian networks. The package includes tools to search for a maximum a posteriori (MAP) graph and to sample graphs from the posterior distribution given the data.
  arXiv  Detail & Related papers  (2021-05-02T14:42:32Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  Hybrid Monte Carlo is a powerful Markov Chain Monte Carlo method for sampling from complex continuous distributions. We introduce a new approach based on augmenting Monte Carlo methods with SurVAE Flows to sample from discrete distributions. We demonstrate the efficacy of our algorithm on a range of examples from statistics, computational physics and machine learning, and observe improvements compared to alternative algorithms.
  arXiv  Detail & Related papers  (2021-02-04T02:21:08Z)

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.