Estimating high-dimensional directed acyclic graphs with the PC-algorithm

Abstract

We consider the PC-algorithm Spirtes et. al. (2000) for estimating the skeleton of a very high-dimensional acyclic directed graph (DAG) with corresponding Gaussian distribution. The PC-algorithm is computationally feasible for sparse problems with many nodes, i.e. variables, and it has the attractive property to automatically achieve high computational efficiency as a function of sparseness of the true underlying DAG. We prove consistency of the algorithm for very high-dimensional, sparse DAGs where the number of nodes is allowed to quickly grow with sample size n, as fast as O(n^a) for any 0<a<infinity. The sparseness assumption is rather minimal requiring only that the neighborhoods in the DAG are of lower order than sample size n. We empirically demonstrate the PC-algorithm for simulated data and argue that the algorithm is rather insensitive to the choice of its single tuning parameter.

References in corpus (3)

• Causal Inference and Causal Explanation with Background Knowledge
• Strong Completeness and Faithfulness in Bayesian Networks
• Enumerating Markov Equivalence Classes of Acyclic Digraph Models

Cited by in corpus (117)

• The Gaussian Graphical Model in Cross-sectional and Time-series Data
• Detecting causal associations in large nonlinear time series datasets
• Sparse permutation invariant covariance estimation
• High-dimensional Ising model selection using ${\ell }_1$-regularized logistic regression
• Entropy inference and the James-Stein estimator, with application to nonlinear gene association networks
• Estimating high-dimensional intervention effects from observational data
• Learning high-dimensional directed acyclic graphs with latent and selection variables
• Characterization and Greedy Learning of Interventional Markov Equivalence Classes of Directed Acyclic Graphs
• Detecting crosstalk errors in quantum information processors
• Geometry of the faithfulness assumption in causal inference
• Causal Discovery with Continuous Additive Noise Models
• A fast PC algorithm for high dimensional causal discovery with multi-core PCs
• Variable selection in high-dimensional linear models: partially faithful distributions and the PC-simple algorithm
• ${\ell }_0$-penalized maximum likelihood for sparse directed acyclic graphs
• High-dimensional structure estimation in Ising models: Local separation criterion
• Learning Bayesian Networks with the bnlearn R Package
• High-dimensional variable selection via tilting
• A generalized back-door criterion
• Two Optimal Strategies for Active Learning of Causal Models from Interventional Data
• Scalable Multi-Output Label Prediction: From Classifier Chains to Classifier Trellises
• Stable Graphical Model Estimation with Random Forests for Discrete, Continuous, and Mixed Variables
• Treelets--An adaptive multi-scale basis for sparse unordered data
• Jointly interventional and observational data: estimation of interventional Markov equivalence classes of directed acyclic graphs
• High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion
• Causal Inference in Genetic Trio Studies
• Concave Penalized Estimation of Sparse Gaussian Bayesian Networks
• Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression
• Reversible MCMC on Markov equivalence classes of sparse directed acyclic graphs
• A Kernel Test for Three-Variable Interactions
• Causal Etiology of the Research of James M. Robins
• High dimensional sparse covariance estimation via directed acyclic graphs
• Uniform random generation of large acyclic digraphs
• Hypersurfaces and their singularities in partial correlation testing
• Non-Parametric Causality Detection: An Application to Social Media and Financial Data
• Nonlinear Causal Discovery with Confounders
• A Uniformly Consistent Estimator of Causal Effects under the $k$-Triangle-Faithfulness Assumption
• A Review on Algorithms for Constraint-based Causal Discovery
• A Distribution Free Conditional Independence Test with Applications to Causal Discovery
• Ancestral Causal Inference
• Mapping eQTL networks with mixed graphical Markov models
• Statistical Perspective on Functional and Causal Neural Connectomics: A Comparative Study
• Estimating causal structure using conditional DAG models
• A General Framework for Mixed Graphical Models
• Learning big Gaussian Bayesian networks: partition, estimation, and fusion
• Information-theoretic limits of selecting binary graphical models in high dimensions
• Statistical Perspective on Functional and Causal Neural Connectomics: The Time-Aware PC Algorithm
• Order-independent constraint-based causal structure learning
• A causal framework for discovering and removing direct and indirect discrimination
• The Reduced PC-Algorithm: Improved Causal Structure Learning in Large Random Networks
• Direct Estimation of Differences in Causal Graphs
• Calculation of Entailed Rank Constraints in Partially Non-Linear and Cyclic Models
• A review of Gaussian Markov models for conditional independence
• Inference for Individual Mediation Effects and Interventional Effects in Sparse High-Dimensional Causal Graphical Models
• Learning directed acyclic graphs based on sparsest permutations
• Does the Markov Decision Process Fit the Data: Testing for the Markov Property in Sequential Decision Making
• Active Learning Algorithms for Graphical Model Selection
• Minimal I-MAP MCMC for Scalable Structure Discovery in Causal DAG Models
• High-Dimensional Joint Estimation of Multiple Directed Gaussian Graphical Models
• Selective Greedy Equivalence Search: Finding Optimal Bayesian Networks Using a Polynomial Number of Score Evaluations
• SADA: A General Framework to Support Robust Causation Discovery with Theoretical Guarantee
• Learning linear structural equation models in polynomial time and sample complexity
• Determining full conditional independence by low-order conditioning
• Learning Bayesian networks: a copula approach for mixed-type data
• Dynamic Chain Graph Models for Ordinal Time Series Data
• On Discrimination Discovery and Removal in Ranked Data using Causal Graph
• Marginal integration for nonparametric causal inference
• Learning linear non-Gaussian directed acyclic graph with diverging number of nodes
• Complexity analysis of Bayesian learning of high-dimensional DAG models and their equivalence classes
• RSVP-graphs: Fast High-dimensional Covariance Matrix Estimation under Latent Confounding
• Learning directed acyclic graphs via bootstrap aggregating
• A Recursive Markov Boundary-Based Approach to Causal Structure Learning
• A review of some recent advances in causal inference
• A Junction Tree Framework for Undirected Graphical Model Selection
• Nonparametric causal structure learning in high dimensions
• Recovering Causal Structures from Low-Order Conditional Independencies
• Marginalizable Density Models
• Sage: Using Unsupervised Learning for Scalable Performance Debugging in Microservices
• High-Dimensional Covariance Decomposition into Sparse Markov and Independence Domains
• Joint estimation of linear non-Gaussian acyclic models
• Minimax Posterior Convergence Rates and Model Selection Consistency in High-dimensional DAG Models based on Sparse Cholesky Factors
• An Influence-based Approach for Root Cause Alarm Discovery in Telecom Networks
• Causal Structural Learning Via Local Graphs
• A Bregman Method for Structure Learning on Sparse Directed Acyclic Graphs
• Learning LWF Chain Graphs: an Order Independent Algorithm
• High-Dimensional Covariance Decomposition into Sparse Markov and Independence Models
• A Fast PC Algorithm with Reversed-order Pruning and A Parallelization Strategy
• Learning from Pairwise Marginal Independencies
• Nonparametric Causal Feature Selection for Spatiotemporal Risk Mapping of Malaria Incidence in Madagascar
• Learning LiNGAM based on data with more variables than observations
• Structure learning of undirected graphical models for count data
• MRPC: An R package for accurate inference of causal graphs
• PenPC: A Two-step Approach to Estimate the Skeletons of High Dimensional Directed Acyclic Graphs
• A Stepwise Approach for High-Dimensional Gaussian Graphical Models
• Identifiability of Gaussian Structural Equation Models with Homogeneous and Heterogeneous Error Variances
• A Bayesian incorporated linear non-Gaussian acyclic model for multiple directed graph estimation to study brain emotion circuit development in adolescence
• Kernel-based Approach to Handle Mixed Data for Inferring Causal Graphs
• Estimation of Gaussian directed acyclic graphs using partial ordering information with an application to dairy cattle data
• Penalized Likelihood Methods for Estimation of Sparse High Dimensional Directed Acyclic Graphs
• Learning Bayesian Networks through Birkhoff Polytope: A Relaxation Method
• A New Statistical Framework for Genetic Pleiotropic Analysis of High Dimensional Phenotype Data
• Definite Non-Ancestral Relations and Structure Learning
• Learning Bayesian Networks from Ordinal Data
• Causal inference of brain connectivity from fMRI with $\psi$-Learning Incorporated Linear non-Gaussian Acyclic Model ($\psi$-LiNGAM)
• Analysis of an interventional protein experiment using a vine copula based structural equation model
• Testing Mediation Effects Using Logic of Boolean Matrices
• Causality and Robust Optimization
• More investment in Research and Development for better Education in the future?
• A permutation-based Bayesian approach for inverse covariance estimation
• Estimation Rates for Sparse Linear Cyclic Causal Models
• Faithfulness and learning hypergraphs from discrete distributions
• Fully integrative data analysis of NMR metabolic fingerprints with comprehensive patient data: a case report based on the German Chronic Kidney Disease (GCKD) study
• Physical System for Non Time Sequence Data
• Renormalized Normalized Maximum Likelihood and Three-Part Code Criteria For Learning Gaussian Networks
• Joint estimation of causal effects from observational and intervention gene expression data
• Temporal Point Process Graphical Models
• Neuro-PC: Causal Functional Connectivity from Neural Dynamics
• Causality and Generalizability: Identifiability and Learning Methods