On the Completeness of Causal Discovery in the Presence of Latent Confounding with Tiered Background Knowledge

Bryan AndrewsAISTATS 2020 · OpenReview

Abstract

The discovery of causal relationships is a core part of scientific research. Accordingly, over the past several decades, algorithms have been developed to discover the causal structure for a system. This paper, presented at AISTATS 2020, provides a critical theoretical bridge in the field of causal discovery. It proves that a popular algorithm, Fast Causal Inference (FCI), is "complete" when given a specific, widely applicable type of prior knowledge.

Introduction

Causal discovery is often described as the "holy grail" of data science, as it seeks to move beyond mere correlation to understand the underlying mechanisms of a system. A significant challenge in this field is causal sufficiency: the assumption that there are no unmeasured common causes (latent confounders) for the variables we are studying. In the real world, this assumption is almost always violated.

The Fast Causal Inference (FCI) algorithm was designed to handle these hidden confounders by using a representation called Maximal Ancestral Graphs (MAGs). While FCI is known to be "complete" for purely observational data (meaning it finds all possible causal links), researchers often have background knowledge (e.g., knowing that a patient's age was determined before they took a medication). The gap this paper fills is a theoretical one: it was previously unknown if FCI remains complete when background knowledge is added.

The Completeness Gap

A key contribution of this work is identifying that FCI is not complete for arbitrary background knowledge. In fact, the authors demonstrate that for general background knowledge, FCI might miss some causal links that are logically implied by the combination of data and prior information.

FCI limitations with arbitrary background knowledge. Panel (a) shows the true graph, while (c) illustrates how specific knowledge (C → D) may fail to propagate further orientations in standard FCI.

As illustrated in Figure 1, providing specific causal information (such as $C \to D$ in panel c) does not always lead standard FCI to infer all logically forced relationships. For example, the algorithm may fail to realize that $C$ causes $B$, even though that relationship is logically necessitated. This gap highlights the need for a more structured approach to incorporating prior information.

Tiered Background Knowledge

To resolve this, the authors introduce and formalize Tiered Background Knowledge. In this framework, variables are partitioned into ordered tiers ($T_1, T_2, \dots, T_n$). A variable in an earlier tier can cause a variable in a later tier, but a variable in a later tier cannot cause one in an earlier tier. This structure is highly applicable to real-world scenarios:

  • Time-Series Data: Where variables at time $t$ naturally precede variables at time $t+1$.
  • Instrumental Variables: Where an instrument ($I$) is known to precede the treatment ($A$).
  • Experimental Contexts: Where we know which variables were manipulated by the researcher.

Main Results and Completeness

The authors prove Theorem 1, establishing that FCI with tiered background knowledge is both sound and complete. Given a "conditional independence oracle" (perfect data), the algorithm returns the maximally informative Partial Ancestral Graph (PAG).

The progression of causal discovery using tiered knowledge, leading to the identification of all logically forced relationships in panel (f).

The proof strategy involves a "Dummy Variable" approach, showing that orientations forced by tiered knowledge are mathematically equivalent to orientations FCI would find on a modified graph with specific auxiliary variables. This allows the authors to leverage existing completeness proofs for the standard FCI algorithm. The paper provides a concrete implementation via the FciTiers and FciExogenous algorithms.

Conclusion and Future Work

This research identifies a "sweet spot" for causal discovery: tiered knowledge is restrictive enough to allow for a proof of completeness but broad enough to cover most practical scenarios in science.

Future work remains in extending these proofs to handle selection bias, where the act of collecting data depends on the variables themselves. Additionally, the quest for an algorithm that is complete for any arbitrary background knowledge remains an open challenge in the field.

Summary updated

Abstract

The discovery of causal relationships is a core part of scientific research. Accordingly, over the past several decades, algorithms have been developed to discover the causal structure for a system...
BibTeX
@inproceedings{andrews2020completeness,
  author = {Bryan Andrews},
  title = {{On the Completeness of Causal Discovery in the Presence of Latent Confounding with Tiered Background Knowledge}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=SI5ZjUx8Hlq},
}
Figure