Efficient causal structure learning in high dimensions

• Activity Number: 120 - SPEED: Variable Selection and Networks
• Type: Contributed
• Date/Time: Monday, July 31, 2017 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Learning and Data Science
• Author(s): Arjun Sondhi* and Ali Shojaie
• Companies: University of Washington and University of Washington
• Keywords: causal discovery ; high dimensions ; directed acyclic graphs ; networks ; structural equation models

Abstract

Directed acyclic graphs (DAGs) are commonly used to represent causal networks over a large number of random variables. We consider the task of estimating the equivalence class of a potentially high-dimensional DAG representing a general linear structural equation model. By exploiting properties of common random graph families, we develop a new algorithm that requires conditioning only on small sets of variables. This is useful for high-dimensional settings, and requires significantly less computation than current methods. In extending previous theoretical results for undirected graphs to the setting of DAGs, we prove the consistency of our algorithm, and generalize to a broader class of models than current methods. In low and high-dimensional simulation settings, we demonstrate improvements over the state-of-the-art alternative and conclude by applying our proposed algorithm on a real gene expression data set.