Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexity

Abstract

Learning the directed acyclic graph (DAG) structure of a Bayesian network from observational data is a notoriously difficult problem for which many hardness results are known. In this paper we propose a provably polynomial-time 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, 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 show that our method out-performs existing state-of-the-art methods for learning Gaussian Bayesian networks in terms of recovering the true DAG structure while being comparable in speed to heuristic methods.

Cited by in corpus (11)

• Causality-based Feature Selection: Methods and Evaluations
• Learning Sparse Nonparametric DAGs
• Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy To Game
• A polynomial-time algorithm for learning nonparametric causal graphs
• Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families
• Identifiability of Gaussian Structural Equation Models with Homogeneous and Heterogeneous Error Variances
• The Effect of Noise Level on Causal Identification with Additive Noise Models
• Efficient Bayesian network structure learning via local Markov boundary search
• Learning Graphs from Linear Measurements: Fundamental Trade-offs and Applications
• Identifiability of AMP chain graph models
• Robust Identifiability in Linear Structural Equation Models of Causal Inference