MCMC for Directed Acyclic Graphs via Birth-and-Death Processes

Music City Center 

Inferring a directed acyclic graph (DAG) given data is computationally challenging. Current state-of-the-art MCMC methods for graph inference efficiently scan the space by first considering a restricted search space and iteratively expanding it until a stopping criterion is met. We estimate the error introduced from current methods that use restricted spaces compared to the full space, and develop a novel MCMC method that reduces this error. Our method is an adaptive algorithm which allows for either expansion or contraction of the search space at any iteration. Both expansion and contraction are determined by a birth-and-death process. Extensive simulations demonstrate the efficiency of the new algorithm, compare its performance with existing methods, and consider applications in the field of imaging proteomics.

directed acyclic graph

Markov chain Monte Carlo

birth and death process

skeleton graph