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 analyse 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. (AISTATS'22) give a PSPACE-algorithm for the identification problem in this case, which is a significant improvement over the general Gr"obner basis approach, which has doubly-exponential time complexity in the number of structural parameters. 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.

Introduction

In causal inference, Structural Causal Models (SCMs) provide a formal framework for representing how variables influence one another. These models use directed edges ($X \to Y$) to denote direct causal effects and bidirected edges ($X \leftrightarrow Y$) to represent hidden common causes, or confounders. A fundamental challenge in this field is the identification problem: determining whether the strength of causal effects (parameters $\lambda$) can be uniquely calculated from the observed correlations (covariances) between variables, given the graph structure.

For general graphs, identification is computationally expensive. The standard approach involves solving systems of polynomial equations using Gröbner bases, a method with doubly-exponential time complexity. This paper focuses on a specific, hierarchical class of models known as tree-shaped SCMs.

Tree-Shaped Structural Causal Models

A tree-shaped SCM is one where the directed component of the graph forms a tree structure. While previous state-of-the-art algorithms for this class were in the complexity class PSPACE—implying potential exponential runtimes—this work introduces a randomized polynomial-time algorithm that is both efficient and complete.

A tree-shaped SCM with directed edges (causal effects $\lambda$) and bidirected edges (confounders $\omega$).

Methodology

The authors' approach moves away from exhaustive symbolic manipulation, instead utilizing several mathematical innovations to achieve polynomial-time complexity.

Bilinear Equations and Resultants

Identifying causal parameters often involves solving equations derived from the graph's structure. The authors demonstrate that "missing" bidirected edges (pairs of nodes without a common hidden cause) create bilinear equations. By applying the theory of resultants, they can eliminate variables and link these equations to solve for specific parameters.

The Matrix Product Trick for Cycle Detection

A core technical challenge in identification is finding specific "cycles" of missing edges that allow for parameter calculation. Enumerating every possible cycle is computationally infeasible, as the number of cycles can grow exponentially with the number of nodes.

To solve this, the authors represent paths in the graph as products of $2 \times 2$ matrices. By using weighted adjacency matrices and matrix powers, they can detect the existence of an identifying cycle without having to explicitly list them.

Representation of paths in the graph as products of $2 \times 2$ matrices to identify causal parameters.

Polynomial Identity Testing (PIT)

To avoid the "monomial explosion" associated with symbolic polynomials, the algorithm employs the Schwartz-Zippel lemma. Instead of manipulating complex symbolic expressions, the algorithm plugs in random numbers. If the resulting value is zero, the polynomial is almost certainly zero. This randomized approach allows the algorithm to function within the complexity class BPP (Bounded-error Probabilistic Polynomial time).

Key Results and Classification

The proposed algorithm runs in $O(e \cdot n^4)$ time, where $n$ is the number of nodes and $e$ is the number of edges. For every causal parameter in a tree-shaped SCM, the algorithm provides a definitive classification:

  1. Generically Identifiable: A unique solution exists.
  2. Generically 2-Identifiable: Exactly two solutions exist (typically involving a square root).
  3. Unidentifiable: Infinitely many solutions exist.

The algorithm provides solutions in the form of Fractional Affine Square-root Terms of Polynomials (FASTPs). Crucially, the authors prove that for tree-shaped models, no other cases (such as 3-identifiability) are possible, and their algorithm is guaranteed to find a solution if one exists.

Conclusion

By reducing the complexity of the identification problem from exponential to polynomial time for tree-shaped models, this research makes causal analysis computationally feasible for large-scale hierarchical systems. Future work may involve extending these matrix-based techniques to broader graph classes, such as forests or graphs with limited directed cycles.

Summary updated

Abstract

Linear structural causal models (SCMs) are used to express and analyse 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. (AISTATS'22, PLMR 151, pp. 6770--6792, 2022) give a PSPACE-algorithm for the identification problem in this case, which is a significant improvement over the general Gr\"obner basis approach, which has doubly-exponential time complexity in the number of structural parameters. 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.
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