# Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexity

arXiv: https://arxiv.org/abs/1703.01196 · HTML: https://mlsanity.com/paper/1703.01196/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Mar 2017.

## Built on by (most cited first, 27 of 27)

- [Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy To Game](https://mlsanity.com/paper/2102.13647/) (2021)
- [DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization](https://mlsanity.com/paper/2209.08037/) (2022)
- [Causal Structure Learning: a Combinatorial Perspective](https://mlsanity.com/paper/2206.01152/) (2022)
- [Optimal estimation of Gaussian DAG models](https://mlsanity.com/paper/2201.10548/) (2022)
- [Optimizing NOTEARS Objectives via Topological Swaps](https://mlsanity.com/paper/2305.17277/) (2023)
- [Efficient Bayesian network structure learning via local Markov boundary search](https://mlsanity.com/paper/2110.06082/) (2021)
- [Causal Fourier Analysis on Directed Acyclic Graphs and Posets](https://mlsanity.com/paper/2209.07970/) (2022)
- [Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families](https://mlsanity.com/paper/2110.04719/) (2021)
- [Learning DAGs from Data with Few Root Causes](https://mlsanity.com/paper/2305.15936/) (2023)
- [Markov Equivalence and Consistency in Differentiable Structure Learning](https://mlsanity.com/paper/2410.06163/) (2024)
- [Learning bounded-degree polytrees with known skeleton](https://mlsanity.com/paper/2310.06333/) (2023)
- [BUILD with Precision: Bottom-Up Inference of Linear DAGs](https://mlsanity.com/paper/2512.16111/) (2025)
- [Sequentially learning the topological ordering of causal directed acyclic graphs with likelihood ratio scores](https://mlsanity.com/paper/2202.01748/) (2022)
- [Optimal estimation of Gaussian (poly)trees](https://mlsanity.com/paper/2402.06380/) (2024)
- [Learning Gaussian DAG Models without Condition Number Bounds](https://mlsanity.com/paper/2511.06164/) (2025)
- [Learning Sparse Fixed-Structure Gaussian Bayesian Networks](https://mlsanity.com/paper/2107.10450/) (2021)
- [Information Theoretically Optimal Sample Complexity of Learning Dynamical Directed Acyclic Graphs](https://mlsanity.com/paper/2308.16859/) (2023)
- [Causal Discovery in Equal Variance Linear Gaussian DAGs via SURE-Tuned Ridge Regression](https://mlsanity.com/paper/2608.17132/) (2026)
- [Recovering Linear Causal Models with Latent Variables via Cholesky Factorization of Covariance Matrix](https://mlsanity.com/paper/2311.00674/) (2023)
- [Generalized Criterion for Identifiability of Additive Noise Models Using Majorization](https://mlsanity.com/paper/2404.05148/) (2024)
- [Identifiability of AMP chain graph models](https://mlsanity.com/paper/2106.09350/) (2021)
- [The Effect of Noise Level on Causal Identification with Additive Noise Models](https://mlsanity.com/paper/2108.11320/) (2021)
- [A Density Evolution framework for Preferential Recovery of Covariance and Causal Graphs from Compressed Measurements](https://mlsanity.com/paper/2203.09636/) (2022)
- [Distributionally Robust Skeleton Learning of Discrete Bayesian Networks](https://mlsanity.com/paper/2311.06117/) (2023)
- [Bayesian Approach to Linear Bayesian Networks](https://mlsanity.com/paper/2311.15610/) (2023)
- [Inconsistency of cross-validation for structure learning in Gaussian graphical models](https://mlsanity.com/paper/2312.17047/) (2023)
- [On the Identifiability of Mixed Ordinal and Exponential Family Causal DAGs under Linear Parametric Models](https://mlsanity.com/paper/2609.17942/) (2026)

## Abstract (arXiv)

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(k4 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.