Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexity

Learning the directed acyclic graph (DAG) structure of a Bayesian network from observational data is a notoriously difficult problem for which many non-identifiability and hardness results are known. In this paper we propose a provably polynomialtime algorithm for learning sparse Gaussian Bayesian networks with equal noise variance -- a class of Bayesian networks for which the DAG structure can be uniquely identified from observational data -- under high-dimensional settings.