Learning Sparse Causal Models is not NP-hard

2013/09/26 by Claassen, Tom, Mooij, Joris, Heskes, Tom · 5 citations
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1309.6824

Abstract

This paper shows that causal model discovery is not an NP-hard problem, in the sense that for sparse graphs bounded by node degree k the sound and complete causal model can be obtained in worst case order N^2(k+2) independence tests, even when latent variables and selection bias may be present. We present a modification of the well-known FCI algorithm that implements the method for an independence oracle, and suggest improvements for sample/real-world data versions. It does not contradict any known hardness results, and does not solve an NP-hard problem: it just proves that sparse causal discovery is perhaps more complicated, but not as hard as learning minimal Bayesian networks.

Cited by

• Causal Structure and Representation Learning with Biomedical Applications
• Embracing Discrete Search: A Reasonable Approach to Causal Structure Learning
• Score-based Greedy Search for Structure Identification of Partially Observed Linear Causal Models
• Causal Structure Learning in Hawkes Processes with Complex Latent Confounder Networks
• Expert-aided causal discovery of ancestral graphs

Related

• Proof Supplement - Learning Sparse Causal Models is not NP-hard (UAI2013)
• Characterization and Learning of Causal Graphs with Small Conditioning Sets
• Ordering-Based Causal Structure Learning in the Presence of Latent Variables
• A Hybrid Anytime Algorithm for the Constructiion of Causal Models From Sparse Data
• Causal Structural Learning Via Local Graphs