Research map / Learning theory and algorithms / Combinatorial and search optimization
Linear-Time Algorithms for Front-Door Adjustment in Causal Graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first linear-time O(n+m) algorithm for finding front-door adjustment sets in a DAG, an O(n(n+m))-delay enumeration algorithm, and the first linear-time algorithm for finding an inclusion-minimal front-door set, with Python, Julia and JavaScript implementations.
Problem
Finding, enumerating, and minimizing front-door adjustment sets in causal DAGs with unobserved confounders; prior best algorithm for finding FD sets ran in O(n^3(n+m)) time.
Approach
Decomposes the existing FD search into Bayes-Ball-style graph searches: a forbidden-vertex labeling computed by a single linear-time search from Y, and a minimal-set construction via directed-path and back-door-way conditions, all realized as a general rule-table graph search.
Key results
- The linear-time FIND algorithm outperforms JTB by a factor of more than 10^4 on medium-sized instances, and JTB times out beyond 256 vertices on sparse graphs (expected degree 3).
- The minimal-set algorithm MIN has only slightly higher run time than FIND while returning much smaller FD sets, often of size zero or one.
- The algorithms scale to graphs with hundreds of thousands of variables.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the linear-time find algorithm instead of JTB | front-door adjustment set finding · Erdős-Rényi graphs | runtime speedup: more than $10^4$ | Helped |
| use the linear-time min algorithm instead of find | front-door adjustment set finding · Erdős-Rényi graphs | front-door set size | Helped |
| use min instead of find | front-door adjustment set finding · Erdős-Rényi graphs | runtime | Hurt |
| use JTB instead of find | front-door adjustment set finding · Erdős-Rényi graphs with expected degree 3 | maximum solved graph size within 30 seconds: more than 256 vertices | Hurt |
| use JTB instead of find | front-door adjustment set finding · Erdős-Rényi graphs with expected degree 10 | maximum solved graph size within 30 seconds: up to 64 vertices | Hurt |
Surprising findings
- Maximal FD sets returned by prior and linear-time FIND methods grow linearly with graph size, even when a minimal FD set has size zero or one.
Limitations
- Minimum-size FD sets are not computed; efficient algorithm for them is an open problem.
- Assumes the causal DAG is known and correctly specified.
- Classical FD criterion requires no back-door path from X to Z, which is restrictive.
Experimental setup
Datasets: Erdős-Rényi random DAGs bnlearn repository DAGs
Benchmarks: Erdős-Rényi random DAGs bnlearn DAGs
Metrics: average run time in seconds size of returned FD set
Baselines: JTB (Jeong, Tian, Bareinboim 2022)
Builds on: Bayes-Ball algorithm Jeong, Tian, Bareinboim front-door algorithm front-door criterion
Closest papers by meaning
- Identifying Macro Conditional Independencies and Macro Total Effects in Summary Causal Graphs with Latent Confounding (AAAI 2025 · similarity 0.88)
- Graph Distance Based on Cause-Effect Estimands with Latents (NeurIPS 2026 · similarity 0.87)
- Identifying Macro Causal Effects in C-DMGs over DMGs (NeurIPS 2025 · similarity 0.87)
- Causal Inference with Conditional Front-Door Adjustment and Identifiable Variational Autoencoder (ICLR 2024 · similarity 0.87)
- Unified Covariate Adjustment for Causal Inference (NeurIPS 2024 · similarity 0.87)
- Causal Effect Identification in LiNGAM Models with Latent Confounders (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.