论文标题
用于因果图中前门调整的线性时间算法
Linear-Time Algorithms for Front-Door Adjustment in Causal Graphs
论文作者
论文摘要
观察数据中的因果效应估计是经验科学的基本任务。当未观察到的混杂因素参与系统时，它变得尤其具有挑战性。本文着重于前门调整 - 一种经典技术，即即使在存在未观察到的混杂的情况下，使用观察到的介体也可以识别因果效应。尽管对前门估计的统计特性已经充分了解，但其算法方面长期以来尚未探索。 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(n^3(n+m))$ run time, where $n$ denotes the number of variables and $m$ the number of edges of the causal graph.在我们的工作中，我们给出了第一个线性时间，即$ o（n+m）$，该任务算法，因此达到了渐近的最佳时间复杂性。该结果意味着所有前门调整集的$ O（N（N+M））$延迟枚举算法，再次提高了先前的工作$ n^3 $。此外，我们提供了第一种线性时间算法，用于查找最小的前门调整集。我们在多种编程语言中提供算法的实现，以促进实际使用情况并在经验上验证其可行性，即使对于大图。
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(n^3(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 $n^3$. 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.
