D-separation

D-separation is a criterion in graph theory for determining which conditional independence relations are implied by a directed acyclic graph (DAG). It is fundamental to Bayesian networks and other probabilistic graphical models, where vertices represent random variables. The criterion uses the arrangement and orientation of edges, rather than numerical probabilities, to identify independences that hold for every distribution factorizing according to the graph. The “d” denotes directional: arrow orientations affect whether a path is blocked. (bayes.cs.ucla.edu)

Graphical definition

Let $G=(V,E)$ be a DAG, and let $A,B,S\subseteq V$ be pairwise disjoint sets of vertices. A path between vertices in $A$ and $B$ is considered without requiring its traversal to follow arrow directions. However, the directions determine the status of each internal vertex. An internal vertex is a collider on the path when both adjacent edges point toward it:

Otherwise, it is a non-collider. These classifications are relative to a particular path, not permanent properties of a vertex. (cs.cmu.edu)

A path is active, or open, given $S$ precisely when:

1. Every internal non-collider lies outside $S$.
2. Every internal collider either belongs to $S$ or has a descendant in $S$.

A descendant is reachable by following one or more directed edges. If no active path connects any vertex in $A$ to any vertex in $B$, then $A$ and $B$ are d-separated by $S$, written

Otherwise, they are d-connected. Establishing separation requires blocking every connecting path; finding one blocked path is insufficient. (bayes.cs.ucla.edu)

Chains, forks, and colliders

Three elementary configurations explain the criterion:

• Chain: $X\rightarrow M\rightarrow Y$, or its reversal. The path is open without conditioning on $M$, but conditioning on $M$ blocks it.
• Fork: $X\leftarrow C\rightarrow Y$. The common-parent path is likewise blocked by conditioning on $C$.
• Collider: $X\rightarrow C\leftarrow Y$. This path is blocked unless $C$, or one of its descendants, is conditioned on.

For an isolated chain or fork, $X\perp Y\mid M$ or $X\perp Y\mid C$ follows. For an isolated collider, $X\perp Y$ follows before conditioning, whereas conditioning on the common effect can introduce dependence. (bayes.cs.ucla.edu)

Consequently, adding conditioning variables does not necessarily preserve d-separation. A larger conditioning set may block a non-collider while simultaneously opening a collider elsewhere. This distinguishes d-separation from ordinary vertex separation in an undirected graph and explains why indiscriminately conditioning on additional variables can change independence relations. (bayes.cs.ucla.edu)

Probabilistic interpretation

Suppose a joint probability distribution factorizes over $G$:

where $\operatorname{pa}(i)$ denotes the parents of vertex $i$. The factors describe conditional probabilities. D-separation then entails

This is the global Markov property of the DAG. With an empty conditioning set, it yields ordinary statistical independence. (ftp.cs.ucla.edu)

The criterion is sound because every independence it identifies holds in all distributions factorizing over the graph. It is also complete for graph-implied independences: if two sets are d-connected, there exists a compatible distribution in which they are conditionally dependent. Completeness does not assert dependence in every compatible distribution. Particular parameter choices may generate additional independences not encoded by the graph. (ftp.cs.ucla.edu)

Faithfulness and causal interpretation

A distribution is faithful to a DAG when its conditional independences coincide exactly with the graph’s d-separation relations. Under faithfulness, d-connection implies dependence in that distribution. Without it, independence can arise through parameter cancellations or other special choices. Faithfulness is therefore an additional assumption, not part of the graphical definition. (cs.cmu.edu)

D-separation alone does not establish causation. A Bayesian network can represent probabilistic relationships without its arrows being causal. In causal inference, causal interpretations require additional assumptions about the mechanisms represented by the graph. Independence-based discovery can also leave several candidate graphs indistinguishable: graphs in the same Markov equivalence class encode the same independence relations. (cs.cmu.edu)

Computational methods

Explicitly enumerating connecting paths is unnecessary. The Bayes-ball algorithm explores the graph using traversal rules determined by whether a vertex is observed and whether it is approached from a parent or child. By recording traversal states, it avoids repeated work. Its time complexity is linear in the graph’s size, $O(|V|+|E|)$, and it can identify variables irrelevant to an inference query. (web.stanford.edu)

An alternative uses a moralized ancestral graph. First retain $A\cup B\cup S$ and all their ancestors. Next connect every pair of parents sharing a child, and replace directed edges with undirected edges. D-separation holds exactly when removing $S$ from this graph leaves no connection between $A$ and $B$. Restricting to the ancestral subgraph before moralization is essential. (cs.cmu.edu)

Role in causal adjustment

Within a structural causal model, blocking rules help distinguish causal paths from paths producing confounding. The back-door criterion requires an adjustment set containing no descendants of the exposure and blocking every path that enters the exposure through an incoming arrow. Collider activation matters here: conditioning can create an unwanted association rather than remove one. (cs.cmu.edu)

D-separation also supplies graphical implications used by constraint-based causal-discovery procedures. Such procedures compare conditional independences in data with those predicted by candidate graphs, typically assuming the causal Markov condition and faithfulness. Their output need not identify a unique causal DAG. (cs.cmu.edu)

References

1. d-Separation Without Tearsbayes.cs.ucla.edu
2. d-Separation: From Theorems to Algorithmsftp.cs.ucla.edu
3. Bayes-Ball: The Rational Pastimeweb.stanford.edu
4. 10-708 PGM: Lecture 2—Bayesian Networkscs.cmu.edu
5. 10-708 PGM: Lecture 8—Causal Discovery and Inferencecs.cmu.edu
6. The Intuition Behind the Back-Door Criterionbayes.cs.ucla.edu