Parallel globally optimal structure learning of Bayesian networks

• First parallel algorithm for learning optimal structure of Bayesian networks.
• Work optimal, with space complexity within a factor of 1.41 of the optimal.
• First investigation of Bayesian network learning with bounded node in-degree dd.
• Proof that d• Extensive experimental validation on Blue Gene/P and Opteron InfiniBand cluster.

Given nn random variables and a set of mm observations of each of the nn variables, the Bayesian network structure learning problem is to learn a directed acyclic graph (DAG) on the nn variables such that the implied joint probability distribution best explains the set of observations. Bayesian networks are widely used in many fields including data mining and computational biology. Globally optimal (exact) structure learning of Bayesian networks takes O(n2⋅2n)O(n2⋅2n) time plus the cost of O(n⋅2n)O(n⋅2n) evaluations of an application-specific scoring function whose run-time is at least linear in mm. In this paper, we present a parallel algorithm for exact structure learning of a Bayesian network that is communication-efficient and work-optimal up to O(1n⋅2n) processors. We further extend this algorithm to the important restricted case of structure learning with bounded node in-degree and investigate the performance gains achievable because of limiting node in-degree. We demonstrate the applicability of our method by implementation on an IBM Blue Gene/P system and an AMD Opteron InfiniBand cluster and present experimental results that characterize run-time behavior with respect to the number of variables, number of observations, and the bound on in-degree.