A Core-Guided Approach to Learning Optimal Causal Graphs

Antti Hyttinen, Paul Saikko, Matti JärvisaloIJCAI 2017 · DOI

TL;DR

This paper introduces "Dseptor," a novel approach to learning causal graphs that can handle complex relationships like feedback cycles and latent confounders. By integrating domain-specific knowledge into a powerful constraint satisfaction solver (MaxSAT), Dseptor significantly speeds up the discovery of optimal causal structures without sacrificing accuracy, outperforming existing methods on both simulated and real-world data.

What Problem Does This Paper Address?

Discovering causal relationships from observational data is a fundamental challenge in many scientific fields. While simpler causal discovery methods exist, they often struggle with complex scenarios involving feedback loops (where variables can influence each other cyclically) and latent confounders (unobserved common causes that create spurious correlations). Existing exact methods for these complex scenarios, while accurate, are computationally expensive. This paper aims to bridge this gap by developing a faster, yet still optimal, exact causal discovery algorithm for these challenging settings.

Methods

The core of this work is an enhancement of an existing MaxSAT-based causal discovery approach. The authors introduce several domain-specific techniques integrated into a MaxSAT solver:

  • Domain-Specific Cores: They identify and leverage common patterns of conflicting constraints (called "cores") that frequently arise in causal discovery problems. Finding these cores directly, rather than relying solely on the SAT solver, speeds up the search.
  • Incremental Core Extraction: Instead of feeding all constraints to the SAT solver at once, they incrementally add them. This allows for earlier detection of unsatisfiability and provides better upper bounds on the optimal solution cost, which helps prune the search space.
  • Dynamic Partial Encoding: The encoding of the causal discovery problem into a SAT solver is made more efficient by dynamically switching off parts of the encoding that are not relevant to the current set of constraints being considered. This reduces the complexity for the SAT solver.
  • Bounds-based Constraint Hardening: Using information from the solver's intermediate results (lower bounds on solution cost), they can "harden" certain constraints, effectively forcing them to be satisfied. This further prunes the search space and simplifies subsequent steps.

These techniques are integrated into a solver named "Dseptor."

Datasets

The paper evaluates Dseptor on:

  • Simulated Data: Generated from 7-node cyclic (possibly) linear Gaussian models with correlated disturbances.
  • Real-World Datasets: Subsets of variables from commonly used benchmarks for Bayesian network structure learning (e.g., Adult, Alarm, Autos, etc.). These datasets are often discrete.

Key Insights and Ideas

  • Domain Knowledge is Key for Speed: The most significant insight is that by encoding domain-specific knowledge (like common constraint patterns or the structure of the problem) directly into the solver, substantial performance gains can be achieved without sacrificing optimality.
  • Incrementalism Pays Off: Breaking down the problem into smaller, incremental steps (like incremental core extraction) not only helps find solutions faster but also provides valuable intermediate information (upper bounds) that further accelerates the overall search.
  • Pruning the Search Space: Techniques like constraint hardening and dynamic encoding are crucial for making complex optimization problems tractable. By effectively reducing the search space, these methods allow for finding optimal solutions in a more reasonable time.
  • MaxSAT as a Powerful Framework: The paper demonstrates the continued power of MaxSAT as a general framework for tackling complex AI problems like causal discovery, especially when augmented with domain-specific optimizations.

Key Results

Dseptor significantly outperforms existing state-of-the-art MaxSAT solvers and other causal discovery algorithms:

  • Synthetic Data: Dseptor solves 96% of instances within a 600-second timeout, outperforming competitors like Maxino (81%), LMHS (plain), and QMaxSAT.
  • Real-World Data: Dseptor shows a clear performance advantage on real-world benchmarks, often finding optimal solutions very quickly. The paper notes that the proof of optimality often dominates the running time, suggesting excellent "anytime" performance.
  • Component Contributions: The experiments show that each of the proposed techniques (domain-specific cores, incremental core extraction, dynamic partial encoding, and constraint hardening) contributes to Dseptor's improved performance.

Limitations and Future Work

  • Limitations: The paper acknowledges that while Dseptor is significantly faster, the problem of exact causal discovery for complex graphs remains computationally intensive. The performance is still dependent on the size and complexity of the input data and the number of constraints.
  • Future Work: The authors conjecture that enumerating additional, larger (but still relatively small) domain-specific minimal cores could further improve runtime performance. They also mention that their approach can be generalized to multiple experimental datasets, suggesting future work in incorporating such data.

Summary updated

BibTeX
@inproceedings{hyttinen2017core,
  author = {Antti Hyttinen and Paul Saikko and Matti Järvisalo},
  title = {{A Core-Guided Approach to Learning Optimal Causal Graphs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/90},
}
Figure