  We consider the task of estimating a high-dimensional directed acyclic graph,
given observations from a linear structural equation model with arbitrary noise
distribution. By exploiting properties of common random graphs, we develop a
new algorithm that requires conditioning only on small sets of variables. The
proposed algorithm, which is essentially a modified version of the
PC-Algorithm, offers significant gains in both computational complexity and
estimation accuracy. In particular, it results in more efficient and accurate
estimation in large networks containing hub nodes, which are common in
biological systems. We prove the consistency of the proposed algorithm, and
show that it also requires a less stringent faithfulness assumption than the
PC-Algorithm. Simulations in low and high-dimensional settings are used to
illustrate these findings. An application to gene expression data suggests that
the proposed algorithm can identify a greater number of clinically relevant
genes than current methods.
