Abstract 

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. We show that O(k 4 log p) number of samples suffices for our method to recover the true DAG structure with high probability, where p is the number of variables and k is the maximum Markov blanket size. We obtain our theoretical guarantees under a condition called restricted strong adjacency faithfulness (RSAF), which is strictly weaker than strong faithfulness — a condition that other methods based on conditional independence testing need for their success. The sample complexity of our method matches the information-theoretic limits in terms of the dependence on p. We validate our theoretical findings through synthetic experiments.