Abstract
The study of graphical causal models is fundamentally the study of separations and conditional independences. We provide linear time algorithms for two graphical primitives: to test if a given set $Z$ is a minimal d-separator of $X$ and $Y$, and to find a minimal d-separator of $X$ and $Y$. These algorithms operate in $O(n+m)$ time, where $n$ is the number of nodes and $m$ is the number of edges, bypassing the traditional, computationally expensive step of graph moralization.
Introduction
In causal inference, graphs represent the structural relationships between variables. A core concept is d-separation: if a set of variables $Z$ "d-separates" $X$ and $Y$, then $X$ and $Y$ are conditionally independent given $Z$. While finding any separator is relatively easy, finding a minimal one—where removing any variable from $Z$ breaks the separation—is much more valuable. Minimal sets are preferred because they require fewer variables to be measured and tested, reducing statistical noise and data collection costs.
The Computational Challenge: Bypassing Moralization
Previously, the best algorithms for finding minimal separators relied on a process called moralization, which transforms a directed graph into an undirected one. This step can explode the number of edges in the graph, leading to quadratic time complexity ($O(m^2)$) or worse. For large, complex models, this becomes a significant bottleneck.
The authors propose a direct approach that works on the original graph without moralization. Their method centers on three main algorithmic primitives:
- Modified Bayes-Ball: They adapt the classic "Bayes-Ball" algorithm to track reachability under specific constraints, identifying which nodes are "reachable" from $X$ or $Y$ through active paths.
TESTMINSEP: An algorithm that verifies if a given set $Z$ is a minimal separator by checking if every node in $Z$ is reachable from both $X$ and $Y$ via specific paths.FINDMINSEP: A constructive algorithm that finds a minimal separator by identifying a "nearest" separator and then pruning it.
Broad Applicability Across Graph Types
Crucially, these algorithms are designed to work across a hierarchy of graph types. The paper shows that many complex causal problems—like finding optimal covariate adjustment sets or identifying instrumental variables—can be reduced to the problem of finding a minimal d-separator in these various structures.
Key Results and Applications
- Linear Time Complexity: The primary result is achieving $O(n+m)$ time complexity. This is a substantial improvement over the previous $O(m^2)$ or $O(n^4)$ benchmarks.
- Optimization of Adjustment Sets: The authors show their algorithm can find "optimal" adjustment sets that minimize the asymptotic variance of causal effect estimators.
- Instrumental Variables: They provide a linear-time solution for finding "ancestral" conditional instrumental variables, a task previously thought to be more computationally demanding.
Conclusion
By defining new rules for how information passes through different types of nodes (colliders vs. non-colliders) in ancestral graphs, the authors prove that expensive undirected transformations are unnecessary. These algorithms are implemented in the open-source software dagitty, providing researchers with efficient tools for large-scale causal analysis.
Summary updated