Paper Info
Title
Parallel Exact Dynamic Bayesian Network Structure Learning with Application to Gene Networks
Abstract
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(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> .2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n(M+1)</sup> ) 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 = 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sup> processors, the parallel algorithm runs in O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> .2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> M.(2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n-k</sup> + k)) time and achieves optimal parallel efficiency when 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n-k</sup> > 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.
Year
DOI
Venue
2017
10.1109/HiPC.2017.00015
2017 IEEE 24th International Conference on High Performance Computing (HiPC)
Keywords
Field
DocType
Dynamic Bayesian networks,Machine learning,Gene regulatory networks,Parallel algorithms
Dynamic programming,Heuristic,InfiniBand,Parallel algorithm,Computer science,Parallel computing,Parallel programming model,Bayesian network,Xeon,Dynamic Bayesian network
Conference
ISSN
ISBN
Citations 
1094-7256
978-1-5386-2294-0
0
PageRank 
References 
Authors
0.34
13
2
Name
Order
Citations
PageRank
Md. Vasimuddin161.82
Aluru, Srinivas21166122.83