The Reduced PC-Algorithm: Improved Causal Structure Learning in Large Random Networks

• Activity Number: 338 - BIOP Student Paper Awards
• Type: Topic Contributed
• Date/Time: Tuesday, July 31, 2018 : 10:30 AM to 12:20 PM
• Sponsor: Biopharmaceutical Section
• Author(s): Arjun Sondhi* and Ali Shojaie
• Companies: University of Washington and University of Washington
• Keywords: causal discovery; directed acyclic graphs; faithfulness; high dimensions; random graphs

Abstract

We consider estimation of a high-dimensional directed acyclic graph, given observations from a linear structural equation model with arbitrary noise distribution. By exploiting properties of random graphs, we develop a new algorithm that requires conditioning only on small sets of variables. The proposed algorithm, a modified version of the PC-Algorithm, both reduces computational complexity and improves 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 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.