Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Bias
TL;DR.
L-MARVEL extends recursive causal discovery to latent variables and selection bias. We prove the method is sound and complete, derive a strong upper bound on its CI-test complexity together with a general lower bound, and show strong empirical gains on synthetic and real-world structures.
Why this matters.
Latent confounding and selection bias are exactly the settings in which causal discovery becomes much harder. The paper shows that recursive removal still works there and retains both correctness guarantees and near-optimal worst-case efficiency.
Abstract
We consider the problem of learning the causal MAG of a system from observational data in the presence of latent variables and selection bias. Constraint-based methods are one of the main approaches for solving this problem, but the existing methods are either computationally impractical when dealing with large graphs or lacking completeness guarantees. We propose a novel computationally efficient recursive constraint-based method that is sound and complete. The key idea of our approach is that at each iteration a specific type of variable is identified and removed. This allows us to learn the structure efficiently and recursively, as this technique reduces both the number of required conditional independence (CI) tests and the size of the conditioning sets. The former substantially reduces the computational complexity, while the latter results in more reliable CI tests. We provide an upper bound on the number of required CI tests in the worst case. To the best of our knowledge, this is the tightest bound in the literature. We further provide a lower bound on the number of CI tests required by any constraint-based method. The upper bound of our proposed approach and the lower bound at most differ by a factor equal to the number of variables in the worst case. We provide experimental results to compare the proposed approach with the state of the art on both synthetic and real-world structures.
The paper at a glance
An informal guide to the problem, the idea, and the main results.
1. The problem
Hidden variables and selection bias break many of the assumptions that make ordinary causal discovery straightforward. The resulting graph objects are more complicated, and search can become very expensive.
2. The key idea
We adapt the recursive removal strategy to mixed-graph structure. The point is to recover the same computational intuition as in simpler recursive methods while respecting the extra complexity of latent and selection effects.
3. L-MARVEL is sound and complete
We characterize removable variables in maximal ancestral graphs and use them to construct L-MARVEL, a recursive constraint-based algorithm that is sound and complete in the presence of latent variables and selection bias.
4. Near-matching complexity bounds
We derive an upper bound on the number of CI tests required by L-MARVEL and a lower bound for any constraint-based method. In the worst case, the two differ by at most a factor equal to the number of variables.
5. How it works
- Represent the observed structure with the appropriate mixed-graph object.
- Use local conditions to identify a variable or substructure that can be peeled away safely.
- Recurse on the smaller problem.
- Reconstruct the global structure from the recursive pieces.
What the experiments show
Where this helps
Good fit
- You want causal discovery in the presence of latent confounding or selection bias.
- You like recursive methods but need them in a more realistic non-DAG setting.
- You care about efficient structure learning under mixed-graph semantics.
Keep in mind
- The method handles both latent confounding and selection bias within one recursive mixed-graph framework.
- The theoretical guarantees pair with benchmark improvements in both the number of CI tests and structure-learning accuracy.
Cite this paper
@inproceedings{akbari2021recursive,
title = {Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Bias},
author = {Sina Akbari and Ehsan Mokhtarian and AmirEmad Ghassami and Negar Kiyavash},
booktitle = {Advances in Neural Information Processing Systems},
volume = {34},
pages = {10119--10130},
year = {2021},
url = {https://proceedings.neurips.cc/paper/2021/hash/53edebc543333dfbf7c5933af792c9c4-Abstract.html}
}