Causal Structural Learning via Local Graphs

We consider the problem of learning causal structures in sparse high-dimensional settings that may be subject to the presence of (potentially many) unmeasured confounders, as well as selection bias. Based on structure found in common families of large random networks, we propose a new local notion of sparsity for structure learning in the presence of latent and selection variables, and develop a new version of the Fast Causal Inference (FCI) algorithm, which we refer to as local FCI (lFCI). Under the new sparsity condition and an additional assumption that ensures that conditional dependencies can be determined locally, lFCI is consistent and offers reduced computational and sample complexity when compared to standard FCI algorithms. The new notion of sparsity allows the presence of highly connected hub nodes, which are common in real-world networks, but problematic for existing methods. Our numerical experiments indicate that the lFCI algorithm achieves state-of-the-art performance across many classes of large random networks, and its performance is superior to that of existing methods for networks containing hub nodes.