Parallel globally optimal structure learning of Bayesian networks

Olga Nikolova, Jaroslaw Zola, Srinivas Aluru

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


Given n random variables and a set of m observations of each of the n variables, the Bayesian network structure learning problem is to learn a directed acyclic graph (DAG) on the n 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) time plus the cost of O(n · 2n) evaluations of an applicationspecific scoring function whose run-time is at least linear in m. In this paper, we present a parallel algorithm for exact structure learning of a Bayesian network that is communication- efficient and workoptimal up to O(1/n · 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.

Original languageEnglish (US)
Pages (from-to)1039-1048
Number of pages10
JournalJournal of Parallel and Distributed Computing
Issue number8
StatePublished - 2013
Externally publishedYes


  • Bayesian networks
  • Graphical models
  • Machine learning
  • Parallel algorithm
  • Structure learning

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'Parallel globally optimal structure learning of Bayesian networks'. Together they form a unique fingerprint.

Cite this