Parallel Exact Dynamic Bayesian Network Structure Learning with Application to Gene Networks

摘要

Learning the structure of Bayesian networks, even in the static case, is NP-hard, compelling much of the research to focus on heuristic-based approaches. However, there are instances where exact solutions are desirable especially for small network sizes. In this work, we present a dynamic programming based exact solution to learn dynamic Bayesian network structure. Our method simultaneously learns intra- as well as higher order inter-time-slice interactions in the network. For n variables, our exact solution requires O(nn²n.2n^n(M+1)n) computations to learn M-th order network. To handle such high computational requirements, we present a parallel exact solution to push the limit on the size of the networks that can be learned. Given p = 2n^knprocessors, the parallel algorithm runs in O(nn²n.2nⁿnM.(2n^n-kn+ k)) time and achieves optimal parallel efficiency when 2n^n-kn> k. Using MPI+X parallel programming model, the parallel algorithm linearly scales to 1,024 cores of a 64-node Intel Xeon InfiniBand cluster, sustaining >99% of parallel efficiency. We also show that the learned networks on gene network datasets are of high fidelity compared to heuristic-based techniques.