# Partition MCMC for inference on acyclic digraphs

arXiv: https://arxiv.org/abs/1504.05006 · HTML: https://mlsanity.com/paper/1504.05006/

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Apr 2015.

## Built on by (most cited first, 30 of 33)

- [Bayesian Structure Learning with Generative Flow Networks](https://mlsanity.com/paper/2202.13903/) (2022)
- [DiBS: Differentiable Bayesian Structure Learning](https://mlsanity.com/paper/2105.11839/) (2021)
- [A survey of Bayesian Network structure learning](https://mlsanity.com/paper/2109.11415/) (2021)
- [Differentiable DAG Sampling](https://mlsanity.com/paper/2203.08509/) (2022)
- [Causal Structure Learning: a Combinatorial Perspective](https://mlsanity.com/paper/2206.01152/) (2022)
- [Variational Causal Networks: Approximate Bayesian Inference over Causal Structures](https://mlsanity.com/paper/2106.07635/) (2021)
- [BayesDAG: Gradient-Based Posterior Inference for Causal Discovery](https://mlsanity.com/paper/2307.13917/) (2023)
- [Bayesian structure learning and sampling of Bayesian networks with the R package BiDAG](https://mlsanity.com/paper/2105.00488/) (2021)
- [Tractable Uncertainty for Structure Learning](https://mlsanity.com/paper/2204.14170/) (2022)
- [Causal Entropy Optimization](https://mlsanity.com/paper/2208.10981/) (2022)
- [Computably Continuous Reinforcement-Learning Objectives are PAC-learnable](https://mlsanity.com/paper/2303.05518/) (2023)
- [Estimating Interventional Distributions with Uncertain Causal Graphs through Meta-Learning](https://mlsanity.com/paper/2507.05526/) (2025)
- [Benchpress: A Scalable and Versatile Workflow for Benchmarking Structure Learning Algorithms](https://mlsanity.com/paper/2107.03863/) (2021)
- [Effective Bayesian Causal Inference via Structural Marginalisation and Autoregressive Orders](https://mlsanity.com/paper/2402.14781/) (2024)
- [The interventional Bayesian Gaussian equivalent score for Bayesian causal inference with unknown soft interventions](https://mlsanity.com/paper/2205.02602/) (2022)
- [A Bayesian Take on Gaussian Process Networks](https://mlsanity.com/paper/2306.11380/) (2023)
- [Structure Learning with Adaptive Random Neighborhood Informed MCMC](https://mlsanity.com/paper/2311.00599/) (2023)
- [Bayesian Causal Inference with Gaussian Process Networks](https://mlsanity.com/paper/2402.00623/) (2024)
- [Possible Principles for Aligned Structure Learning Agents](https://mlsanity.com/paper/2410.00258/) (2024)
- [Causal structure learning with momentum: Sampling distributions over Markov Equivalence Classes of DAGs](https://mlsanity.com/paper/2310.05655/) (2023)
- [Greedy equivalence search for nonparametric graphical models](https://mlsanity.com/paper/2406.17228/) (2024)
- [Test-Time Learning of Causal Structure from Interventional Data](https://mlsanity.com/paper/2602.19131/) (2026)
- [Optimal Particle-based Approximation of Discrete Distributions (OPAD)](https://mlsanity.com/paper/2412.00545/) (2024)
- [Covariate Dependent Mixture of Bayesian Networks](https://mlsanity.com/paper/2501.05745/) (2025)
- [Lower Bounds on the Size of Markov Equivalence Classes](https://mlsanity.com/paper/2506.20933/) (2025)
- [Consistent Bayesian causal discovery for structural equation models with equal error variances](https://mlsanity.com/paper/2509.15197/) (2025)
- [Reinforcement Causal Structure Learning on Order Graph](https://mlsanity.com/paper/2211.12151/) (2022)
- [Scalable Structure Learning for Sparse Context-Specific Systems](https://mlsanity.com/paper/2402.07762/) (2024)
- [Exact discovery is polynomial for certain sparse causal Bayesian networks](https://mlsanity.com/paper/2406.15012/) (2024)
- [Enhancing Solution Efficiency in Reinforcement Learning: Leveraging Sub-GFlowNet and Entropy Integration](https://mlsanity.com/paper/2410.00461/) (2024)

## Abstract (arXiv)

Acyclic digraphs are the underlying representation of Bayesian networks, a widely used class of probabilistic graphical models. Learning the underlying graph from data is a way of gaining insights about the structural properties of a domain. Structure learning forms one of the inference challenges of statistical graphical models. MCMC methods, notably structure MCMC, to sample graphs from the posterior distribution given the data are probably the only viable option for Bayesian model averaging. Score modularity and restrictions on the number of parents of each node allow the graphs to be grouped into larger collections, which can be scored as a whole to improve the chain's convergence. Current examples of algorithms taking advantage of grouping are the biased order MCMC, which acts on the alternative space of permuted triangular matrices, and non ergodic edge reversal moves. Here we propose a novel algorithm, which employs the underlying combinatorial structure of DAGs to define a new grouping. As a result convergence is improved compared to structure MCMC, while still retaining the property of producing an unbiased sample. Finally the method can be combined with edge reversal moves to improve the sampler further.