## Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm

** Markus Kalisch, Peter Bühlmann**; 8(Mar):613--636, 2007.

### Abstract

We consider the PC-algorithm (Spirtes et al., 2000) for estimating the skeleton and equivalence class of a very high-dimensional directed acyclic graph (DAG) with corresponding Gaussian distribution. The PC-algorithm is computationally feasible and often very fast for sparse problems with many nodes (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 uniform 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*) for any 0 <

^{a}*a*< ∞. The sparseness assumption is rather minimal requiring only that the neighborhoods in the DAG are of lower order than sample size

*n*. We also demonstrate the PC-algorithm for simulated data.

[abs][pdf]