Linear-Time Algorithms for Front-Door Adjustment in Causal Graphs
Authors: Marcel Wienöbst, Benito van der Zander, Maciej Liśkiewicz
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We offer implementations of our algorithms in multiple programming languages to facilitate practical usage and empirically validate their feasibility, even for large graphs. [...] 5 Experiments We have shown that the run time of the algorithms proposed in this work scales linearly in the size of the graph. In this section, we empirically show that this translates to practical implementations |
| Researcher Affiliation | Academia | Institute of Theoretical Computer Science, University of L ubeck, Germany |
| Pseudocode | Yes | Algorithm 1: Finding the set Z(ii) in time O(n+m). [...] Algorithm 2: Finding an FD set Z relative to (X, Y) in time O(n + m). [...] Algorithm 3: Finding an I-inclusion minimal front-door adjustment set Z in linear time. |
| Open Source Code | Yes | The implementations and code to reproduce the experiments are available at https://github.com/mwien/frontdoor-adjustment. |
| Open Datasets | Yes | In the Appendix D, we also provide a run-time comparison for the real-life DAGs from the bnlearn repository (Scutari 2010), which further validate our findings, showing that FIND yields a sizeable improvement even for smaller graphs. |
| Dataset Splits | No | The paper describes the generation of graphs for experiments and runtime limits, but it does not provide traditional training, validation, and test dataset splits as typically found in machine learning papers. |
| Hardware Specification | Yes | We ran the experiments on a single core of the AMD Ryzen Threadripper 3970X 32-core processor on a 256GB RAM machine. |
| Software Dependencies | No | We implement our methods in Python, Julia, and Java Script to enable wide practical usage in the causal inference community. [...] To facilitate adoption, we base on the networkx Python package, which is the graph library used by causal inference packages such as Do Why (Sharma, Kiciman et al. 2019). Similarly, in Julia we allow for easy integration into Causal Inference.jl (Schauer, Keller, and Wien obst 2023) and in Javascript into the DAGitty environment (Textor et al. 2016). While software names are mentioned, specific version numbers for these dependencies are not provided. |
| Experiment Setup | Yes | Figure 4 shows the average run time in seconds. Per instance, each algorithm was given a time limit of 30 seconds (we only report results for parameter choices for which each instance was solved within the allocated time). The results confirm our theoretical findings as FIND (Algorithm 2) outperforms JTB by a factor of more than 104 on medium-sized instances (the gap widens with the number of variables). For each choice of n, we average over 50 graphs. [...] |E| = 1.5n; |R| = 0.5n [...] |E| = 5n; |R| = 0.5n [...] |X|, |Y| are random integers between 1 and 3; |I| = 0 and |R| = 0.5n. |