Learning Sparse Causal Models is not NP-hard

By Tom Claassen, Joris M. Mooij, Tom M. Heskes. 2013

132 citations recorded by the source corpus.

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 N2(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.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Invariant Causal Prediction for Nonlinear Models (2017, methodology): “rtial ancestral graph (PAG), i.e. it estimates the Markov equivalence class of the underlying maximal ancestral graph (MAG). Faster versions, RFCI and FCI+, were proposed by Colombo et al. (2012) and Claassen et al. (2013), respectively. The PC, FCI, RFCI and FCI+ algorithms are formulated such that”
Order-independent constraint-based causal structure learning (2012, methodology): “We start by discussing several prominent examples of such algorithms, designed for diﬀerent settings.”
Structural Intervention Distance (SID) for Evaluating Causal Graphs (2013, background): “, 2000) and its successors (Colombo et al., 2012; Claassen et al., 2013) output an equivalence class of MAGs that are called partial ancestral graphs (PAGs) (Richardson and Spirtes, 2002).”
Causal Structure Learning (2017, background): “Since the additional tests can slow down the algorithm considerably, faster adaptations have been developed, such as RFCI (Colombo et al., 2012) and FCI+ (Claassen et al., 2013).”
Joint Causal Inference from Multiple Contexts (2016, methodology): “Also, alternatives for the skeleton search phase such as FCI+ (Claassen et al., 2013) could be employed to gain further speedups.”
A survey of Bayesian Network structure learning (2021, background): “Fast Causal Inference Plus (FCI+) centers around another approach to speeding up the adjacency phase of FCI (Claassen et al., 2013).”
Structure Learning in Graphical Modeling (2016, background): “While certain forms of feedback can be represented in the paradigm of linear structural equation modeling (Spirtes et al., 2000; Mooij & Heskes, 2013) and conditional independence can then be exploited in structure learning (Richardson, 1996), these models can generally not be described using…”
Structural Intervention Distance for Evaluating Causal Graphs (2015, methodology): “Furthermore, methods like FCI (Spirtes et al., 2000) and its successors (Colombo, Maathuis, Kalisch, & Richardson, 2012; Claassen, Mooij, & Heskes, 2013) output an equivalence class of MAGs that are called partial ancestral graphs (PAGs) (Richardson & Spirtes, 2002).”
Causal Learning for Partially Observed Stochastic Dynamical Systems (2018, background): “candidate separator sets may be chosen in more-or-less efficient ways, but we will not discuss this aspect of the algorithm (Colombo et al., 2012; Claassen et al., 2013).”
Learning Optimal Causal Graphs with Exact Search (2018, methodology): “We can also enforce sparsity constraints, such as a bound on the maximum degree of nodes (as used by Claassen et al. (2013)), in a straightforward way.”
Differentiable Causal Discovery Under Latent Interventions (2022, background): “There are many works that do causal discovery with latent confounders (Spirtes et al., 1993; Colombo et al., 2012; Claassen et al., 2013; Ogarrio et al., 2016).”
Estimating the effect of joint interventions from observational data in sparse high-dimensional settings (2014, background): “, [4, 7, 33]) and the adjustment criteria developed in [18, 26, 37].”
Discovery of Causal Models that Contain Latent Variables through Bayesian Scoring of Independence Constraints (2017, methodology): “In addition, a modification of FCI can be implemented to run in polynomial time, if a maximum number of causes (parents) per node is specified [9].”
A Complete Generalized Adjustment Criterion (2015, background): “…criterion for DAGs, MAGs, CPDAGs and PAGs, where CPDAGs andPAGs represent Markov equivalence classes of DAGs or MAGs, respectively, and can be inferred directly from data (see, e.g., Spirtes et al., 2000; Chickering, 2003; Colombo et al., 2012; Claassen et al., 2013; Colombo and Maathuis, 2014).”