Reversible MCMC on Markov equivalence classes of sparse directed acyclic graphs
This work addresses a bottleneck in statistical and causal inference for researchers analyzing complex systems, offering a scalable method for sampling equivalence classes, though it is incremental in improving existing algorithms.
The paper tackles the problem of sampling over Markov equivalence classes of sparse directed acyclic graphs (DAGs), which was previously limited to graphs with fewer than 20 vertices, by designing reversible irreducible Markov chains with a perfect set of operators, enabling efficient exploration of classes with thousands of vertices and revealing experimental findings such as most edges being directed and undirected subgraphs growing linearly with vertex count.
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