Identification for Tree-Shaped Structural Causal Models in Polynomial Time

Aaryan Gupta, Markus Bläser

Abstract

Linear structural causal models (SCMs) are used to express and analyze the relationships between random variables. Direct causal effects are represented as directed edges and confounding factors as bidirected edges. Identifying the causal parameters from correlations between the nodes is an open problem in artificial intelligence. In this paper, we study SCMs whose directed component forms a tree. Van der Zander et al. give a PSPACE-algorithm for the identification problem in this case, which is a significant improvement over the general Gröbner basis approach, which has doubly-exponential time complexity in the number of structural parameters. However, they do not show that their algorithm is complete. In this work, we present a randomized polynomial-time algorithm, which solves the identification problem for tree-shaped SCMs. For every structural parameter, our algorithms decides whether it is generically identifiable, generically 2-identifiable, or generically unidentifiable. (No other cases can occur.) In the first two cases, it provides one or two fractional affine square root terms of polynomials (FASTPs) for the corresponding parameter, respectively. In particular, our algorithm is not only polynomial time, but also complete for tree-shaped SCMs.

Introduction

In causal inference, identification is the process of determining whether a causal effect (the "strength" of a directed edge in a graph) can be uniquely calculated from observed correlations (the covariance matrix). For Linear Structural Causal Models (SCMs), this usually involves solving a system of complex polynomial equations. While general methods like Gröbner bases can solve this, they have a "doubly-exponential" time complexity, making them computationally infeasible for large models. Researchers have spent decades looking for faster, graph-based "criteria" (like Instrumental Variables), but these are often incomplete—they might fail to identify a parameter that is, in principle, identifiable.

Figure 1: A tree-shaped SCM where directed edges (λ) form a tree and bidirected edges (ω) represent confounding factors.

This paper focuses on tree-shaped SCMs, where the directed edges form a tree. While a previous algorithm (TreeID) existed for this class, it was computationally expensive (PSPACE) and its completeness was unknown. The authors present a randomized polynomial-time algorithm that is both efficient and complete for this model class.

Methodology

The authors treat the identification problem as a graph-theoretic search for specific types of equations. Their approach relies on several key technical pillars:

  1. Bilinear Equations from Missing Edges: Every "missing" bidirected edge (a lack of correlation between error terms) provides a bilinear equation involving the causal parameters.
  2. Matrix Composition (Möbius Transforms): They show that these equations can be composed along paths in the graph. This allows them to represent the relationship between parameters as a product of $2 \times 2$ matrices, similar to Möbius transforms.
  3. Polynomial Identity Testing (PIT): To avoid the "exponential explosion" of enumerating all possible cycles in the graph, the authors use the Schwartz-Zippel Lemma. By plugging in random numbers and checking if a polynomial evaluates to zero, they can determine if an identifying cycle exists in randomized polynomial time.
  4. Layered Graphs: To find these identifying cycles efficiently, they construct a layered version of the graph where every walk is a path, allowing them to use matrix multiplication to check for the existence of valid causal "instruments."
Figure 4: The layered graph construction enables efficient searching for identifying cycles using matrix multiplication and PIT.

Key Insights

  • The Power of Missing Edges: The paper reinforces the idea that what isn't in the graph (missing correlations) is just as important for identification as what is there.
  • Rank-Based Identification: They distinguish between "Rank-1" and "Rank-2" missing edges. Rank-1 edges act as simple instruments that identify one parameter directly, while Rank-2 edges act as "bridges" that transfer identifiability from one part of the tree to another.
  • Completeness: The authors prove their algorithm is complete for tree-shaped SCMs. This means if a parameter is identifiable (or 2-identifiable), their algorithm will find it.
  • Finite Solutions: They show that for tree-shaped models, a parameter can only have one solution (identifiable), two solutions (2-identifiable), or infinitely many (unidentifiable). No other cases (like 3-identifiable) can occur.

Key Results

  • Complexity Leap: The algorithm runs in randomized polynomial time (BPP), a massive improvement over the previous PSPACE and doubly-exponential methods.
  • Symbolic Output: For identifiable parameters, the algorithm provides a FASTP (Fractional Affine Square-root Term of Polynomials)—a symbolic expression that researchers can use to calculate the causal effect from data.
  • Algorithmic Completeness: The paper fills a theoretical gap by proving that the conditions they check are both necessary and sufficient for identification in this model class.

Conclusion

The most obvious limitation is the "tree-shaped" requirement for the directed component of the graph. While many real-world models are trees, many are not. Additionally, the algorithm is randomized; while PIT is highly reliable, a deterministic polynomial-time algorithm remains a theoretical goal. However, the techniques used here—specifically the matrix representation of bilinear equations and the use of resultants—could potentially be extended to more general classes of graphs beyond trees.

Summary updated

Abstract

Linear structural causal models (SCMs) are used to express and analyze the relationships between random variables. Direct causal effects are represented as directed edges and confounding factors as bidirected edges. Identifying the causal parameters from correlations between the nodes is an open problem in artificial intelligence. In this paper, we study SCMs whose directed component forms a tree. Van der Zander et al. give a PSPACE-algorithm for the identification problem in this case, which is a significant improvement over the general Gröbner basis approach, which has doubly-exponential time complexity in the number of structural parameters. However, they do not show that their algorithm is complete. In this work, we present a randomized polynomial-time algorithm, which solves the identification problem for tree-shaped SCMs. For every structural parameter, our algorithms decides whether it is generically identifiable, generically 2-identifiable, or generically unidentifiable. (No other cases can occur.) In the first two cases, it provides one or two fractional affine square root terms of polynomials (FASTPs) for the corresponding parameter, respectively. In particular, our algorithm is not only polynomial time, but also complete for for tree-shaped SCMs.
BibTeX
@inproceedings{gupta2024identification,
  author = {Aaryan Gupta and Markus Bläser},
  title = {{Identification for Tree-Shaped Structural Causal Models in Polynomial Time}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=IbPqlXnSRv},
}
Figure