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

Markus Kalisch, Peter Bühlmann.

Year: 2007, Volume: 8, Issue: 22, Pages: 613−636

#### 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 ^{a}*) for any
0 <

*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.