Reversible MCMC on Markov equivalence classes of sparse directed acyclic graphs
arXiv:1209.5860 · doi:10.1214/13-AOS1125
Abstract
Graphical models are popular statistical tools which are used to represent dependent or causal complex systems. Statistically equivalent causal or directed graphical models are said to belong to a Markov equivalent class. It is of great interest to describe and understand the space of such classes. However, with currently known algorithms, sampling over such classes is only feasible for graphs with fewer than approximately 20 vertices. In this paper, we design reversible irreducible Markov chains on the space of Markov equivalent classes by proposing a perfect set of operators that determine the transitions of the Markov chain. The stationary distribution of a proposed Markov chain has a closed form and can be computed easily. Specifically, we construct a concrete perfect set of operators on sparse Markov equivalence classes by introducing appropriate conditions on each possible operator. Algorithms and their accelerated versions are provided to efficiently generate Markov chains and to explore properties of Markov equivalence classes of sparse directed acyclic graphs (DAGs) with thousands of vertices. We find experimentally that in most Markov equivalence classes of sparse DAGs, (1) most edges are directed, (2) most undirected subgraphs are small and (3) the number of these undirected subgraphs grows approximately linearly with the number of vertices. The article contains supplement arXiv:1303.0632, http://dx.doi.org/10.1214/13-AOS1125SUPP
Published in at http://dx.doi.org/10.1214/13-AOS1125 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)
References in corpus (7)
- Causal Inference and Causal Explanation with Background Knowledge
- Estimating high-dimensional intervention effects from observational data
- A Transformational Characterization of Equivalent Bayesian Network Structures
- Causal Discovery from a Mixture of Experimental and Observational Data
- Robust graphical modeling of gene networks using classical and alternative T-distributions
- Supplement to "Reversible MCMC on Markov equivalence classes of sparse directed acyclic graphs"
- Approximate Counting of Graphical Models Via MCMC Revisited
Cited by in corpus (7)
- Partition MCMC for inference on acyclic digraphs
- Structural Markov graph laws for Bayesian model uncertainty
- On sampling graphical Markov models
- Complexity analysis of Bayesian learning of high-dimensional DAG models and their equivalence classes
- Towards a Multi-Subject Analysis of Neural Connectivity
- Supplement to "Reversible MCMC on Markov equivalence classes of sparse directed acyclic graphs"
- Approximate Counting of Graphical Models Via MCMC Revisited