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

Abstract

We consider the PC-algorithm ([13]) for estimating the skeleton of a very highdimensional 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(na) for any 0 < a < 1. 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.