Discovering Cyclic Causal Models with Latent Variables: A General SAT-Based Procedure

By Antti Hyttinen, Patrik O. Hoyer, Frederick Eberhardt, Matti Järvisalo. 2013

97 citations recorded by the source corpus.

We present a very general approach to learning the structure of causal models based on d-separation constraints, obtained from any given set of overlapping passive observational or experimental data sets. The procedure allows for both directed cycles (feedback loops) and the presence of latent variables. Our approach is based on a logical representation of causal pathways, which permits the integration of quite general background knowledge, and inference is performed using a Boolean satisfiability (SAT) solver. The procedure is complete in that it exhausts the available information on whether any given edge can be determined to be present or absent, and returns "unknown" otherwise. Many existing constraint-based causal discovery algorithms can be seen as special cases, tailored to circumstances in which one or more restricting assumptions apply. Simulations illustrate the effect of these assumptions on discovery and how the present algorithm scales.

Subfields: Artificial Intelligence, Software

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 Software

Citations in the corpus

Causal Models for Dynamical Systems (2020, neutral): “Diﬀerent causal methodology and several extensions of SCMs have been proposed [Wiener, 1956, Granger, 1969, Schreiber, 2000, White and Lu, 2010, Hyttinen et al., 2013, Peters et al., 2013, Pﬁster et al., 2018b], mostly considering discrete time models such as vector autoregressive models…”
Do-calculus when the True Graph Is Unknown (2015, background): “Figure 1: Overall structure of the system. of causal structures (Hyttinen et al., 2013, 2014).”
Constraint-based Causal Discovery: Conflict Resolution with Answer Set Programming (2014, background): “Hyttinen et al. (2013) extend these approaches to include experimental data sets where a subset of the variables has been subject to an intervention.”
Constraint-based causal discovery from multiple interventions over overlapping variable sets (2014, methodology): “Such variables are called backbone variables of Φ ∧ F ′ (Hyttinen et al., 2013).”
D’ya Like DAGs? A Survey on Structure Learning and Causal Discovery (2021, unknown): “PC [228] 1993 constraint yes yes yes no CPDAG FCI [229, 275] 1995 constraint no yes yes no POIPG CCD [200] 1996 constraint yes yes both no PAG TPDA [31] 2002 constraint yes yes yes no CPDAG CPC [193] 2006 constraint yes relaxed yes no CPDAG KCL [233] 2007 constraint yes yes yes no CPDAG ION [241] 20”