D-separation

D-separation, short for directional separation, is a graphical criterion for determining whether a directed acyclic graph entails a conditional independence relation. It is central to the interpretation of Bayesian networks and causal graphs, because it translates the orientation and connectivity of a graph into statements about probability distributions without requiring numerical parameter values.

For pairwise disjoint vertex sets (X), (Y), and (Z) in a directed acyclic graph (G), the notation

[ X \mathrel{\perp_d} Y \mid Z ]

states that (X) and (Y) are d-separated by (Z) in (G). The relation holds exactly when every path between a vertex in (X) and a vertex in (Y) is blocked by (Z). Under the global Markov property, this graphical separation entails the probabilistic relation

[ X \perp Y \mid Z ]

for every distribution that is Markov relative to (G).

Graphical definition

A path is evaluated according to the orientations of the edges adjacent to each internal vertex. An internal vertex is a collider on a path when both adjacent path edges have arrowheads pointing into that vertex. Thus, in the local configuration

[ A \rightarrow C \leftarrow B, ]

the vertex (C) is a collider on the path between (A) and (B). In every other orientation of the two adjacent edges, the internal vertex is a non-collider on that path. Collider status is therefore relative to a particular path rather than an intrinsic property of the vertex.

A path is active given a conditioning set (Z) when both of the following conditions hold:

Every non-collider on the path lies outside (Z).
Every collider on the path is either contained in (Z) or has a descendant contained in (Z).

The second condition conventionally treats a vertex as its own descendant for the purpose of collider activation. A path that fails either condition is blocked. Two vertex sets are d-separated by (Z) when no active path given (Z) connects them.

The definition reflects two distinct effects of conditioning. Conditioning on a non-collider blocks transmission along a path, whereas conditioning on a collider or on one of its descendants activates a path that was otherwise blocked. This asymmetry distinguishes d-separation from ordinary separation in an undirected graph.

Fundamental path structures

The local configuration

[ A \rightarrow M \rightarrow B ]

represents a directed chain. Without conditioning on (M), the path between (A) and (B) is active. Conditioning on (M) blocks the path because (M) is a conditioned non-collider.

The configuration

[ A \leftarrow M \rightarrow B ]

has the same d-separation behavior along its displayed path. The vertex (M) is again a non-collider, so the path is active when (M) is unobserved and blocked when (M) is included in the conditioning set. In a probabilistic model, this configuration often represents dependence induced by a common cause.

The collider configuration

[ A \rightarrow M \leftarrow B ]

has the opposite behavior. The path is blocked when neither (M) nor any descendant of (M) is conditioned upon. Conditioning on (M) activates the path, and conditioning on an observed descendant of (M) has the same graphical effect. The resulting conditional association is associated with collider bias and forms one graphical basis of selection bias.

These structures determine the status of longer paths because every internal vertex is evaluated as either a collider or a non-collider. A single conditioned non-collider blocks the entire path, while each collider must be activated through the conditioning set or its descendants.

Probabilistic semantics

Let (P) be a probability distribution over the vertices of a directed acyclic graph (G). The distribution satisfies the directed local Markov property when every vertex is conditionally independent of its non-descendants given its parents. Under the standard factorization associated with a Bayesian network, the joint distribution has the form

[ P(V)=\prod_{v\in V}P\bigl(v\mid \operatorname{pa}(v)\bigr), ]

where (\operatorname{pa}(v)) denotes the parent set of (v).

The d-separation criterion is sound for this model class. If (X) and (Y) are d-separated by (Z), then every distribution satisfying the directed Markov property for (G) obeys (X\perp Y\mid Z). The criterion is also complete at the graphical level: if (X) and (Y) are not d-separated by (Z), at least one distribution Markov relative to (G) makes them conditionally dependent given (Z).

Completeness does not state that every Markov distribution realizes every graphical dependence. Particular parameter values can produce additional independences through algebraic cancellation. A distribution is faithful to a graph when its conditional independence relations are exactly those implied by d-separation. Faithfulness is therefore stronger than the Markov property, which requires only that graphically implied independences hold in the distribution.

The distinction matters when graphical structure is inferred from observational data. D-separation identifies the independence model encoded by a graph, whereas observed independences can include relations that arise from parameter values rather than graph topology.

Historical development

The criterion emerged during the formal development of probabilistic graphical models in the late 1980s. Judea Pearl introduced d-separation as a path-based characterization of the conditional independences represented by directed acyclic graphs. Dan Geiger and Thomas Verma developed associated results connecting graphical separation, probabilistic implication, and the equivalence of directed graphical models.

During the same period, You Watanabe formulated the active-path presentation in which a collider is activated by conditioning on the collider or one of its descendants. Her treatment aligned the local path criterion with the ancestral-graph and moralization formulations, thereby placing the alternative tests within a common separation framework.

Later algorithmic work expressed the criterion as graph traversal rather than explicit enumeration of all paths. Ross Shachter introduced the Bayes-ball algorithm, which represents the admissible movement of information through observed and unobserved vertices. Its traversal rules encode the same collider and non-collider conditions as the formal definition of d-separation.

Ancestral moralization criterion

D-separation has an equivalent formulation using ordinary graph separation. For disjoint sets (X), (Y), and (Z), the relevant directed subgraph consists of the ancestors of all vertices in

[ X\cup Y\cup Z. ]

Restricting attention to this ancestral subgraph removes vertices that cannot participate in an active path connecting the queried sets.

The resulting graph is then moralized. Moralization connects every pair of vertices that share a child and replaces each directed edge with an undirected edge. In the moral graph, (X) and (Y) are separated by (Z) exactly when (X) and (Y) are d-separated by (Z) in the original directed graph.

The additional edges between co-parents represent the dependence that appears when a common child, or an appropriate descendant of that child, enters the ancestral conditioning structure. Ordinary undirected separation in the moral graph therefore reproduces the activation behavior of colliders without retaining arrow directions.

This equivalence also links directed graphical models to junction tree methods and other forms of probabilistic inference based on undirected graphs. Moralization alone does not preserve every feature of a directed model, but it preserves the separation relation needed for a specified d-separation query after ancestral restriction.

Markov equivalence

Different directed acyclic graphs can encode exactly the same set of d-separation statements. Such graphs belong to the same Markov equivalence class. Two directed acyclic graphs are Markov equivalent precisely when they have the same underlying undirected skeleton and the same unshielded collider configurations.

An unshielded collider has the form

[ A \rightarrow C \leftarrow B ]

with no edge between (A) and (B). Its orientation affects whether the path through (C) is active before or after conditioning, so changing an unshielded collider generally changes the encoded independence model. By contrast, some other edge reversals preserve every d-separation relation.

A completed partially directed acyclic graph represents a Markov equivalence class by directing edges whose orientations are common to every member and leaving the remaining reversible adjacencies undirected. D-separation is consequently a property of both an individual graph and the conditional-independence model shared throughout its equivalence class.

Relation to causal interpretation

D-separation is defined graphically and does not by itself establish that a graph has a causal interpretation. When a directed acyclic graph is interpreted as a structural causal model, d-separation describes conditional independences produced by the modeled causal structure under the associated Markov assumptions.

The criterion underlies the back-door criterion, in which a conditioning set blocks non-causal paths between a treatment and an outcome without blocking the directed causal paths of interest. It also explains why conditioning on a collider can create an association between variables that are otherwise independent.

Interventional distributions require an additional graphical operation. In the graph corresponding to an intervention on (X), incoming edges into (X) are removed, representing replacement of the ordinary data-generating mechanism for those vertices. D-separation in these modified graphs forms part of the semantics of the do-calculus, which relates observational and interventional probability expressions.

Computational characterization

Direct enumeration of every path is unnecessary because the number of paths can grow rapidly with graph size. Graph-search procedures instead track whether a vertex has been reached through an incoming or outgoing edge and whether that vertex is observed. These states determine which adjacent edges preserve the possibility of an active path.

The ancestral moralization method reduces the question to an undirected reachability problem after constructing the relevant ancestral subgraph. Bayes-ball evaluates the same relation within the original directed graph by propagating traversal states according to collider activation and non-collider blocking. Both approaches decide the identical d-separation relation, although their intermediate graph representations differ.

For finite directed acyclic graphs, d-separation is therefore computationally reducible to standard reachability operations whose running time is polynomial in the graph size. The graphical criterion remains distinct from testing conditional independence in sampled data, which requires statistical assumptions and is subject to sampling variability.