Learning Sparse Causal Models is not NP-hard

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.

Appears in Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence (UAI2013)

References in corpus (2)

• Bayesian network learning with cutting planes
• A Logical Characterization of Constraint-Based Causal Discovery

Cited by in corpus (17)

• A Complete Generalized Adjustment Criterion
• Complete Graphical Characterization and Construction of Adjustment Sets in Markov Equivalence Classes of Ancestral Graphs
• Constraint-based Causal Discovery for Non-Linear Structural Causal Models with Cycles and Latent Confounders
• Distributional robustness of K-class estimators and the PULSE
• Constraint-Based Causal Discovery using Partial Ancestral Graphs in the presence of Cycles
• Switching Regression Models and Causal Inference in the Presence of Discrete Latent Variables
• A review of some recent advances in causal inference
• FRITL: A Hybrid Method for Causal Discovery in the Presence of Latent Confounders
• Causal Structural Learning Via Local Graphs
• Improving Efficiency and Accuracy of Causal Discovery Using a Hierarchical Wrapper
• A Single Iterative Step for Anytime Causal Discovery
• Iterative Causal Discovery in the Possible Presence of Latent Confounders and Selection Bias
• Causal Inference in medicine and in health policy, a summary
• Definite Non-Ancestral Relations and Structure Learning
• Identification of Latent Variables From Graphical Model Residuals
• Causality and Generalizability: Identifiability and Learning Methods
• Evaluation of Causal Structure Learning Algorithms via Risk Estimation