Scores for Learning Discrete Causal Graphs with Unobserved Confounders

Alexis Bellot, Junzhe Zhang, Elias BareinboimAAAI 2024 · OpenReview

Abstract

Causal discovery in the presence of unobserved confounders is a fundamental challenge, as hidden variables induce complex constraints beyond simple conditional independence. This paper presents a novel scoring method for discrete causal graphs that leverages the Widely Applicable Bayesian Information Criterion (WBIC). By utilizing a singular asymptotic expansion of the marginal likelihood, the proposed score captures statistical signatures such as the Verma constraint and Instrumental Variable inequalities. We demonstrate that this approach effectively distinguishes between previously indistinguishable causal structures and outperforms existing state-of-the-art methods in structure recovery.

Introduction

Inferring causal relationships from observational data—causal discovery—traditionally relies on conditional independence (CI) tests. However, the presence of unobserved confounders (hidden variables affecting multiple observed ones) complicates this process. Hidden variables induce non-trivial constraints, such as the Verma constraint or the Instrumental Variable (IV) inequality, which are not captured by standard CI-based methods. Traditional scoring tools like the Bayesian Information Criterion (BIC) are ill-suited for these scenarios because they assume a smooth likelihood surface, whereas these constraints create mathematical "singularities."

Methodology: The WBIC Score

The authors propose a new scoring method based on Watanabe’s asymptotic expansion of the marginal likelihood, specifically the Widely Applicable Bayesian Information Criterion (WBIC). Unlike BIC, which approximates the log-marginal likelihood using the number of parameters, WBIC accounts for the "learning coefficient" ($\lambda_G$) that characterizes the complexity of singular models.

Key Technical Innovations

  1. Finite Parameterization: The authors prove that discrete Structural Causal Models (SCMs) with arbitrary hidden variables can be represented with a finite parameter set, provided hidden variable cardinality is appropriately bounded.
  2. Tempered Sampling: The score is estimated by sampling from a "tempered" posterior distribution with temperature $\beta = 1/\log n$. This effectively smooths the singular likelihood surface for integration.
  3. Decomposability: The score is shown to be decomposable into c-components (groups of variables linked by hidden confounders). This property is crucial for computational efficiency in structure search.
  4. Score Equivalence: The method ensures that graphs representing the same probability distributions receive identical scores, preventing bias toward specific graph representations.

Experimental Evaluation

The method was evaluated using synthetic SCMs (IV, Verma, Front-door, and Unconstrained graphs) and benchmark datasets (Sachs protein-signaling and Lung Cancer datasets). In benchmark tests, variables were intentionally omitted to simulate unobserved confounding.

Comparison of scoring methods in distinguishing the Instrumental Variable (IV) graph from an unconstrained model. The WBIC-based score (blue) consistently identifies the correct structure as sample size increases.

A critical test involved distinguishing the IV graph from an unconstrained model. As shown in Figure 2, the WBIC-based score achieves near-perfect identification as sample sizes reach $n=1000$, whereas BIC-based alternatives often fail to distinguish the two.

Structure Learning Results

The proposed score was integrated into a greedy search algorithm (GS-WBIC). The performance was compared against state-of-the-art Maximal Ancestral Graph (MAG) and Directed Acyclic Graph (DAG) learners.

Bayes factors for recovered structures across different causal models. The GS-WBIC approach generally achieves higher Bayes factors compared to state-of-the-art MAG and DAG learners.

As illustrated in Figure 6, GS-WBIC consistently recovers structures with higher Bayes factors across various models (IV, Verma, Frontdoor), indicating that the recovered graphs are more likely to have generated the observed data than those found by competing methods.

Discussion and Limitations

While the WBIC score provides a powerful tool for identifying complex causal signatures, it comes with computational trade-offs. The reliance on MCMC sampling for score calculation is slower than closed-form approximations. Furthermore, the current framework is restricted to discrete data. Future work may involve extending these principles to continuous variables and developing more advanced search heuristics to navigate the vast space of latent-variable graphs.

Conclusion

This work introduces the first scoring method capable of leveraging inequality and equality constraints for causal discovery with unobserved confounders in discrete data. By moving beyond simple conditional independence, the WBIC-based score opens new avenues for accurately mapping causal structures in complex, real-world systems.

Summary updated

BibTeX
@inproceedings{bellot2024scores,
  author = {Alexis Bellot and Junzhe Zhang and Elias Bareinboim},
  title = {{Scores for Learning Discrete Causal Graphs with Unobserved Confounders}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=j5gmjGPcT4},
}
Figure