Causal Identification under Markov Equivalence

Amin Jaber, Jiji Zhang, Elias Bareinboim

Causal Identification under Markov Equivalence

This research bridges the gap between causal discovery and causal effect estimation by introducing a new algorithm, IDP (Identification in PAGs). The algorithm identifies cause-and-effect relationships even when the exact causal structure is unknown and only a "Markov equivalence class"—a set of possible graphs—is available. The authors demonstrate that IDP is strictly more powerful than existing state-of-the-art techniques like the generalized adjustment criterion.

The Problem: Uncertainty in Causal Structures

In the ideal scenario of causal inference, researchers start with a fully specified Directed Acyclic Graph (DAG). Tools like Pearl’s do-calculus can then determine if a causal effect is identifiable from observational data. However, real-world causal discovery algorithms often output a Markov equivalence class rather than a single DAG. This class is represented by a Partial Ancestral Graph (PAG), which uses "circle" marks to indicate uncertainty about edge directions or the presence of hidden confounders.

Comparison of causal structures: (a) represents a specific graph with hidden confounders (ADMG), while (b) represents a Markov equivalence class (PAG) where circle marks denote structural uncertainty.

The challenge addressed here is how to identify causal effects when provided with a PAG instead of a certain DAG. Previous methods were either computationally prohibitive or lacked the power to identify many valid effects.

The IDP Algorithm

The authors develop a systematic, recursive algorithm called IDP. Their approach involves several novel methodological steps:

  1. Composite C-Components: They adapt the concept of "c-components" (groups of variables linked by unobserved confounders) to PAGs, defining "possible c-components" (pc-components) to account for structural uncertainty.
  2. PAG Subgraph Properties: A major hurdle is that a subgraph of a PAG is not necessarily a PAG itself. The authors derive new graphical properties showing that these subgraphs still preserve enough ancestral information for valid causal identification.
  3. Recursive Decomposition: Similar to the ID algorithm for DAGs, IDP breaks complex causal queries into smaller, "atomic" pieces, checking if specific variables can be removed based on their local surroundings in the PAG.
  4. Partial Topological Ordering: Since PAGs lack a single fixed order, the authors use a "bucket-based" ordering system to handle groups of variables where the direction of influence is uncertain.
An example of a subgraph derived from a PAG. The paper proves that such subgraphs preserve necessary ancestral information for the IDP algorithm to function correctly.

Key Insights and Results

  • The Power of Circles: One of the most significant insights is that "circle" marks do not necessarily block identification. If the uncertainty is "downstream" or does not create a "hedge" (a specific problematic structure), the causal effect can still be uniquely determined.
  • Soundness and Superiority: The authors provide a formal proof that IDP is sound. They also demonstrate scenarios where a causal effect is identifiable via IDP but no "adjustment set" exists, proving their method is strictly more powerful than the current state-of-the-art adjustment methods.
  • Efficiency: By providing a systematic recursive procedure, IDP offers a practical alternative to the search-based applications of generalized do-calculus.

Limitations and Future Work

While IDP is more powerful than adjustment, the authors do not claim it is "complete" (finding every possible identifiable effect in a PAG). Establishing a complete algorithm remains a major goal in the field. Additionally, the current work assumes acyclic systems; extending these results to cyclic models or models with selection bias is a key path for future research.

Summary updated

Abstract

Assessing the magnitude of cause-and-effect relations is one of the central challenges found throughout the empirical sciences. The problem of identification of causal effects is concerned with determining whether a causal effect can be computed from a combination of observational data and substantive knowledge about the domain under investigation, which is formally expressed in the form of a causal graph. In many practical settings, however, the knowledge available for the researcher is not strong enough so as to specify a unique causal graph. Another line of investigation attempts to use observational data to learn a qualitative description of the domain called a Markov equivalence class, which is the collection of causal graphs that share the same set of observed features. In this paper, we marry both approaches and study the problem of causal identification from an equivalence class, represented by a partial ancestral graph (PAG). We start by deriving a set of graphical properties of PAGs that are carried over to its induced subgraphs. We then develop an algorithm to compute the effect of an arbitrary set of variables on an arbitrary outcome set. We show that the algorithm is strictly more powerful than the current state of the art found in the literature.
BibTeX
@inproceedings{jaber2018causal,
  author = {Amin Jaber and Jiji Zhang and Elias Bareinboim},
  title = {{Causal Identification under Markov Equivalence}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=lb7TqUcMFiI},
}
Figure