High-dimensional learning of linear causal networks via inverse covariance estimation

Abstract

We establish a new framework for statistical estimation of directed acyclic graphs (DAGs) when data are generated from a linear, possibly non-Gaussian structural equation model. Our framework consists of two parts: (1) inferring the moralized graph from the support of the inverse covariance matrix; and (2) selecting the best-scoring graph amongst DAGs that are consistent with the moralized graph. We show that when the error variances are known or estimated to close enough precision, the true DAG is the unique minimizer of the score computed using the reweighted squared l_2-loss. Our population-level results have implications for the identifiability of linear SEMs when the error covariances are specified up to a constant multiple. On the statistical side, we establish rigorous conditions for high-dimensional consistency of our two-part algorithm, defined in terms of a "gap" between the true DAG and the next best candidate. Finally, we demonstrate that dynamic programming may be used to select the optimal DAG in linear time when the treewidth of the moralized graph is bounded.

41 pages, 7 figures

References in corpus (3)

• A Transformational Characterization of Equivalent Bayesian Network Structures
• A simple approach for finding the globally optimal Bayesian network structure
• Score-based Causal Learning in Additive Noise Models

Cited by in corpus (35)

• On Causal Discovery with Equal Variance Assumption
• Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression
• Causal Fourier Analysis on Directed Acyclic Graphs and Posets
• CASTLE: Regularization via Auxiliary Causal Graph Discovery
• Learning Sparse Nonparametric DAGs
• Identifying Best Interventions through Online Importance Sampling
• Gradient-Based Neural DAG Learning
• Estimating causal structure using conditional DAG models
• Learning Quadratic Variance Function (QVF) DAG models via OverDispersion Scoring (ODS)
• The Reduced PC-Algorithm: Improved Causal Structure Learning in Large Random Networks
• Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy To Game
• A review of Gaussian Markov models for conditional independence
• Causal Discovery with Unobserved Confounding and non-Gaussian Data
• High-Dimensional Joint Estimation of Multiple Directed Gaussian Graphical Models
• Unsuitability of NOTEARS for Causal Graph Discovery
• Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks
• Marginal integration for nonparametric causal inference
• Efficient Intervention Design for Causal Discovery with Latents
• A polynomial-time algorithm for learning nonparametric causal graphs
• Nonparametric causal structure learning in high dimensions
• Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families
• A Bregman Method for Structure Learning on Sparse Directed Acyclic Graphs
• Intervention Efficient Algorithms for Approximate Learning of Causal Graphs
• Mixed Graphical Models for Causal Analysis of Multi-modal Variables
• Identifiability of Gaussian Structural Equation Models with Homogeneous and Heterogeneous Error Variances
• Causal Structure Learning: a Bayesian approach based on random graphs
• The Effect of Noise Level on Causal Identification with Additive Noise Models
• The neighborhood lattice for encoding partial correlations in a Hilbert space
• Deconfounded Score Method: Scoring DAGs with Dense Unobserved Confounding
• Inference of Causal Effects when Control Variables are Unknown
• Estimation Rates for Sparse Linear Cyclic Causal Models
• Learning Functional Dependencies with Sparse Regression
• Learning Bayesian Networks through Birkhoff Polytope: A Relaxation Method
• Graphical Fermat's Principle and Triangle-Free Graph Estimation
• A New Statistical Framework for Genetic Pleiotropic Analysis of High Dimensional Phenotype Data