Exact Distributed Structure-Learning for Bayesian Networks

Learning the structure of a Bayesian network is currently practical for only a limited number of variables. Existing distributed learning approaches approximate the true structure. We present an exact distributed structure-learning algorithm to find a P-map for a set of random variables. First, by using conditional independence, the variables are divided into sets $X_1,\dots ,X_I$ such that for each $X_i$, the presence and absence of edges that are adjacent with any interior node (a node that is not in any other $X_j,j\ne i$) can be correctly identified by learning the structure of $X_i$ separately without using the information of the variables other than $X_i$. Second, constraint or score-based structure learners are employed to learn the P-map of $X_i$, in a decentralized way. Finally, the separately learned structures are appended by checking a conditional independence test on the boundary nodes (those that are in at least two $X_i$'s). The result is proven to be a P-map. This approach allows for a significant reduction in computation time, and opens the door for structure learning for a “giant” number of variables.