Identification in Tree-shaped Linear Structural Causal Models

Benito van der Zander, Marcel Wienöbst, Markus Bläser, Maciej Liskiewicz

Presented at AISTATS 2022, this research addresses a fundamental challenge in causal inference: the identification of causal parameters from observational data. In linear Structural Causal Models (SCMs), identification involves finding a symbolic formula that expresses direct effects (edge weights) in terms of observed covariances. While various criteria exist, they often fail to identify parameters in complex graphs, leaving researchers to rely on computationally prohibitive methods like Gröbner bases.

What Problem Does This Paper Address?

In linear SCMs, direct causal influences are represented by directed edges ($X \to Y$), while unobserved confounding is denoted by bidirected edges ($X \leftrightarrow Y$). The goal is to identify the edge weights ($\lambda$) using the observed covariance matrix ($\Sigma$).

Examples of tree-shaped linear SCMs with various confounding patterns.

Existing methods like the Instrumental Variable (IV) method, ACID, or the Half-Trek Criterion (HTC) are "incomplete"—they cannot solve all theoretically identifiable models. The only known complete method uses Gröbner bases from algebraic geometry, but its doubly-exponential time complexity makes it impractical for large models. This paper introduces TreeID, a polynomial-time algorithm specifically designed for models where the directed edges form a tree.

Methods: The TreeID Algorithm

TreeID's efficiency stems from its focus on tree-shaped directed components and a novel exploitation of "missing cycles" in the confounding structure.

Notation for causal parameters (λ) and confounding (ω) in simple models.

The algorithm operates through several key steps:

  1. Preliminary Propagation: It uses the root of the tree as an initial instrument to identify its children. Identified edges then serve as auxiliary variables to identify subsequent edges down the path.
  2. Exploiting Missing Cycles: The core innovation is the use of "missing cycles" of confounding. If a specific cycle of bidirected edges is absent, it generates a system of quadratic equations.
  3. Recursive Solutions: Rather than using general solvers, the authors provide a recursive method to collapse these systems into a single quadratic equation for a target parameter. This can result in one or two valid solutions.
  4. Information Integration: By intersecting solution sets from multiple missing cycles, the algorithm can often pinpoint a unique, identifiable value.
  5. Randomized Testing: To maintain speed, the algorithm employs Randomized Polynomial Identity Testing (PIT) to verify algebraic equivalences without full symbolic expansion.

Key Insights and Results

  • Absence as Information: The paper demonstrates that the lack of confounding (missing bidirected cycles) provides critical mathematical constraints for solving causal effects.
  • Handling Multi-Identifiability: TreeID can manage "2-identifiable" cases—where two solutions are mathematically possible—and use additional graph information to select the correct one.
  • Algorithmic Superiority: The authors prove that TreeID can identify every edge that the ACID algorithm can, plus many cases where ACID and other state-of-the-art heuristics (HTC, TSID) fail.
  • Efficiency: Running in randomized polynomial time, TreeID is significantly faster than Gröbner basis methods, making it feasible for large-scale tree-shaped models.

Evaluation and Limitations

The authors validated TreeID using synthetic benchmarks and canonical path graphs. They successfully identified causal effects in "difficult" graphs known to be unidentifiable by previous methods. For path graphs with missing cycles of lengths 5 to 10, they categorized the models as consistently "2-identifiable."

Despite its strengths, the method is currently limited to tree-shaped directed components. While trees are common in many hierarchical modeling, many real-world systems are more complex Directed Acyclic Graphs (DAGs) with multiple parents per node. Future work aims to extend the "missing cycle" logic to these more general structures and investigate the numerical stability of the derived formulas on noisy empirical data.

Summary updated

Abstract

Linear structural equation models represent direct causal effects as directed edges and confounding factors as bidirected edges. An open problem is to identify the causal parameters from correlations between the nodes. We investigate models, whose directed component forms a tree, and show that there, besides classical instrumental variables, missing cycles of bidirected edges can be used to identify the model. They can yield systems of quadratic equations that we explicitly solve to obtain one or two solutions for the causal parameters of adjacent directed edges. We show how multiple missing cycles can be combined to obtain a unique solution. This results in an algorithm that can identify instances that previously required approaches based on Gröbner bases, which have doubly-exponential time complexity in the number of structural parameters.
BibTeX
@inproceedings{zander2022identification,
  author = {Benito van der Zander and Marcel Wienöbst and Markus Bläser and Maciej Liskiewicz},
  title = {{Identification in Tree-shaped Linear Structural Causal Models}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=2-4FGCOA1xN},
}
Figure