Efficient Symbolic Computations for Identifying Causal Effects
This work addresses a central problem in causal inference for researchers and practitioners by providing a more scalable method for identifying causal effects from observational data, though it is incremental as it builds on existing symbolic computation approaches.
The paper tackles the computational challenge of determining causal effect identifiability in linear structural causal models with latent confounding, presenting an efficient algorithm that finds the lowest degree identifying formulas in quasi-polynomial time, improving upon the doubly exponential complexity of standard Gröbner bases methods.
Determining identifiability of causal effects from observational data under latent confounding is a central challenge in causal inference. For linear structural causal models, identifiability of causal effects is decidable through symbolic computation. However, standard approaches based on Gröbner bases become computationally infeasible beyond small settings due to their doubly exponential complexity. In this work, we study how to practically use symbolic computation for deciding rational identifiability. In particular, we present an efficient algorithm that provably finds the lowest degree identifying formulas. For a causal effect of interest, if there exists an identification formula of a prespecified maximal degree, our algorithm returns such a formula in quasi-polynomial time.