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

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

TL;DR

This paper introduces a general, SAT-based procedure for discovering causal models that can include directed cycles and unmeasured latent variables. It leverages a novel logical encoding of d-separation constraints and a SAT solver to determine the presence, absence, or unknown status of causal edges, offering a more comprehensive approach than many existing methods.

What Problem Does This Paper Address?

Identifying causal relationships is a fundamental goal across many scientific disciplines. Traditionally, causal discovery has relied on frameworks like causal Bayes networks, which often assume acyclic structures and the absence of unmeasured common causes (causal sufficiency). However, real-world systems frequently exhibit feedback loops (cyclic causality) and unmeasured confounders (latent variables). Existing algorithms often struggle to handle these complexities simultaneously, either by making restrictive assumptions or by being incomplete in their discovery capabilities. This paper aims to bridge this gap by providing a general procedure that can discover cyclic causal models with latent variables from observational and experimental data, while also allowing for the integration of background knowledge.

Methods

The core of this paper's contribution lies in its novel approach to encoding causal discovery problems as a Boolean satisfiability (SAT) problem.

  • Logical Encoding of D-Separation: The authors develop a propositional logic encoding that translates d-separation and d-connection constraints into Boolean variables representing the presence or absence of edges ([x→y], [x↔y]) and relationships between nodes. This encoding is designed to handle cyclic graphs and latent variables, extending the concept of d-separation to these more general settings.
  • SAT Solver for Backbone Computation: The problem of determining which causal edges are definitively present or absent is framed as finding the "backbone" of a SAT formula. A backbone variable is one whose truth value is fixed across all satisfying assignments of the formula. By using a SAT solver, the algorithm can efficiently identify these fixed edges.
  • Incremental Approach: The algorithm iteratively builds a SAT formula by adding constraints derived from d-separation/connection tests. This incremental approach, combined with a pruning heuristic and the use of an incremental SAT solver, helps manage the complexity of the problem.
  • Handling Experiments and Overlapping Data: The framework is extended to incorporate experimental interventions (where certain variables are manipulated) and to handle data from multiple, potentially overlapping, studies.

Datasets

Not discussed in the paper. The paper focuses on a general algorithmic framework and uses simulated data for evaluation.

Key Insights and Ideas

  • Unifying Framework for Complex Causal Structures: The most significant insight is the development of a single, general framework that can handle both cyclic causal structures and latent variables, a combination that is challenging for many existing methods.
  • SAT as a Powerful Inference Engine: Demonstrating that a SAT solver can be effectively used to compute the "backbone" of causal relationships provides a powerful and flexible inference mechanism for causal discovery.
  • Completeness in a General Sense: The procedure is described as "query-complete," meaning that for any propositional query about the causal graph (e.g., "is edge X present?"), the SAT solver can determine if the query is true for all possible underlying graphs, false for all, or unknown.
  • Flexibility in Incorporating Background Knowledge: The SAT-based encoding allows for the straightforward inclusion of various forms of background knowledge, such as known edge presences/absences or restrictions on acyclicity, making it highly adaptable.

Key Results

  • Scalability for Small Graphs: Simulations show that the algorithm can solve problems with up to 10-12 nodes within minutes or seconds, which is notable given the complexity of the model space it handles.
  • Limited Loss of Identifiability with Generalization: Experiments suggest that allowing for cycles and latent variables in the model space does not drastically reduce the identifiability of direct edge presences and absences compared to assuming more restricted models (e.g., acyclic or causally sufficient).
  • Efficiency Gains with Conditioning Set Pruning: Limiting the size of conditioning sets considered in d-separation tests significantly speeds up computation, with minimal loss in the proportion of identified edges.

Limitations and Future Work

  • Scalability for Larger Graphs: The authors acknowledge that the current implementation does not scale well to much larger numbers of variables. Future work could focus on developing more efficient search strategies for unknown d-separations in Step 1 of the algorithm.
  • Statistical Inference Integration: The current framework assumes error-free d-separation/connection relations. Integrating statistical inference to handle noisy independence tests and potential contradictions is identified as a crucial area for future research. Techniques like using p-value thresholds or MaxSAT solvers are suggested.
  • Interpretable Representations: For very general model spaces, easily interpretable graphical representations of the solution space are still lacking.
  • Test Schedule Optimization: While the algorithm is d-separation complete, further optimization of the test selection process, potentially by adapting schedules from more restricted algorithms, is an open challenge.

Summary updated

Abstract

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.
BibTeX
@inproceedings{hyttinen2013discovering,
  author = {Antti Hyttinen and Patrik O. Hoyer and Frederick Eberhardt and Matti Järvisalo},
  title = {{Discovering Cyclic Causal Models with Latent Variables: A General SAT-Based Procedure}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2013},
}
Figure