Finding Minimal d-separators in Linear Time and Applications

Benito van der Zander, Maciej LiskiewiczUAI 2019 · OpenReview

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:

  1. 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.
  2. 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.
  3. FINDMINSEP: A constructive algorithm that finds a minimal separator by identifying a "nearest" separator and then pruning it.
Illustration of the modified Bayes-Ball rules for how information (the "ball") passes through a node $V$ depending on edge directions and node membership in the separator set.

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.

Hierarchy of graphical causal models, showing the relationships between Ancestral Graphs (AG), Maximal Ancestral Graphs (MAG), Directed Acyclic Graphs (DAG), and others.

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

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...
BibTeX
@inproceedings{zander2019finding,
  author = {Benito van der Zander and Maciej Liskiewicz},
  title = {{Finding Minimal d-separators in Linear Time and Applications}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=WR3Oc5irmcd},
}
Figure