2022/11/29 by Marcel Wienöbst, Wienöbst, Marcel, Benito van der Zander +3 · 3 citations
Computer Science · Mathematics · #Advanced Causal Inference Techniques #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Methodology (stat.ME) #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.2211.16468
openalex publication_date 2022/11/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Causal effect estimation from observational data is a fundamental task in empirical sciences. It becomes particularly challenging when unobserved confounders are involved in a system. This paper focuses on front-door adjustment -- a classic technique which, using observed mediators allows to identify causal effects even in the presence of unobserved confounding. While the statistical properties of the front-door estimation are quite well understood, its algorithmic aspects remained unexplored for a long time. In 2022, Jeong, Tian, and Bareinboim presented the first polynomial-time algorithm for finding sets satisfying the front-door criterion in a given directed acyclic graph (DAG), with an O(n3(n+m)) run time, where n denotes the number of variables and m the number of edges of the causal graph. In our work, we give the first linear-time, i.e., O(n+m), algorithm for this task, which thus reaches the asymptotically optimal time complexity. This result implies an O(n(n+m)) delay enumeration algorithm of all front-door adjustment sets, again improving previous work by a factor of n3. Moreover, we provide the first linear-time algorithm for finding a minimal front-door adjustment set. We offer implementations of our algorithms in multiple programming languages to facilitate practical usage and empirically validate their feasibility, even for large graphs.