|
Abstract:
|
We consider the task of estimating high-dimensional directed acyclic graph possibly containing hidden nodes, given observations from a linear structural equation model with arbitrary noise distribution. By exploiting properties of common random graphs, we develop new algorithms that require conditioning only on small sets of variables. The proposed algorithms offer significant gains in both computational and sample complexities. In particular, they 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 algorithms, and show that they require a less stringent faithfulness assumption than existing constraint-based algorithms. 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. Time permitting, we will discuss the extension of the algorithm for causal structure learning in the presence of confounders and selection variables.
|
