A Hybrid Markov Chain Monte Carlo Approach for Structural Learning in Bayesian Networks Based on Variable Blocking

Bayesian networks are models to represent dependence structures among variables through a directed acyclic graph (DAG). Structural learning refers to the statistical estimation of the DAG configuration. A challenge in structural learning is that the number of possible DAG grows super-exponentially as the number of variables increases. Most existing works discover structures over either the DAG space or the topological order space. We propose a hybrid approach that uses Markov chain Monte Carlo (MCMC) to learn Bayesian networks from data, making use of both the DAG space and the topological order space. A key feature of the proposed method is to partition the variables of similar topological orders into blocks. We introduce a hybrid MCMC approach where the structure search is conducted over the DAG space within each block to promote more targeted edge moves, and the across-block search is done to ensure the ergodicity of the Markov chain. A main innovation in our hybrid MCMC with blocking is to make use of the topological order in Bayesian networks to mimic natural time sequence in time series. Both simulation and empirical results suggest that the propose blocking idea with the hybrid MCMC enhances the efficiency in structural learning.