Generalizing Metropolis-Hastings for DAG Sampling
Abstract
A fundamental challenge in Bayesian network structure learning lies in efficiently approximating the posterior distribution of directed acyclic graphs (DAGs). For large, high-dimensional datasets, the task remains beyond the capabilities of current methods. This work advances Markov chain Monte Carlo algorithms by introducing novel moves that simultaneously resample the parents for multiple nodes of the DAG. At the core of these moves is duet sampling, a new generalization of the Metropolis-Hastings algorithm that selects two proposal distributions from a pool at each iteration. One is used for generating a candidate state of the Markov chain and another for evaluating the return to the current state; both are ingredients of an appropriately crafted acceptance criterion. Pairing different proposal distributions provides additional freedom and enables constructing Markov chains that mix more efficiently than their basic Metropolis-Hastings counterparts, at no additional computational cost. Experiments show that our new moves, both individually and in combination, outperform the previous state of the art, which relies on a more restrictive pool of moves. This advantage persists even when letting the previous methods leverage duet sampling to enhance their performance.
Related
- Convergence of Independence Metropolis-Hastings Algorithms in High Dimensions: Iteration Lengths, Cutoff Profiles, and Diagnostic Unreliability
- Spectral Gap Inheritance for Metropolis-Hastings with Reversible Proposals
- When Metropolis and Hastings Meet Bradley and Terry: Exact MCMC From Preference Voting
- Fixed-Horizon Error Rates for Array-RQMC Metropolis-Hastings
- Generalizing the AA Problem for Finite Ordered Sets
BibTeX
@misc{nikzad2026generalizing,
title = {{Generalizing Metropolis-Hastings for DAG Sampling}},
author = {Daniele Nikzad and Mikko Koivisto},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.30291},
eprint = {2610.30291},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.30291},
}
RIS
TY - UNPB
TI - Generalizing Metropolis-Hastings for DAG Sampling
AU - Daniele Nikzad
AU - Mikko Koivisto
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.30291
UR - https://arxiv.org/abs/2610.30291
AB - A fundamental challenge in Bayesian network structure learning lies in efficiently approximating the posterior distribution of directed acyclic graphs (DAGs). For large, high-dimensional datasets, the task remains beyond the capabilities of current methods. This work advances Markov chain Monte Carlo algorithms by introducing novel moves that simultaneously resample the parents for multiple nodes of the DAG. At the core of these moves is duet sampling, a new generalization of the Metropolis-Hastings algorithm that selects two proposal distributions from a pool at each iteration. One is used for generating a candidate state of the Markov chain and another for evaluating the return to the current state; both are ingredients of an appropriately crafted acceptance criterion. Pairing different proposal distributions provides additional freedom and enables constructing Markov chains that mix more efficiently than their basic Metropolis-Hastings counterparts, at no additional computational cost. Experiments show that our new moves, both individually and in combination, outperform the previous state of the art, which relies on a more restrictive pool of moves. This advantage persists even when letting the previous methods leverage duet sampling to enhance their performance.
ER -