d-Separation & Independence
Reading independence off a graph.
Is independent of given and in a hundred-node network? You never need to look at a probability: a linear-time search of the graph answers the question, and the answer is right for every distribution the graph can represent. This lesson proves why. The directed Markov properties are equivalent, d-separation is sound and complete, and the independences of a DAG pin it down only up to its skeleton and v-structures.
What you’ll learn
- State the directed Markov properties and prove that they are equivalent for every distribution, using the moralization criterion.
- Prove that the parameters of an unfaithful distribution form a set of measure zero, and construct faithfulness violations.
- Implement the Bayes-ball reachability algorithm, which decides d-separation in time.
- Prove the Verma–Pearl characterization of Markov equivalence, and describe essential graphs and covered edge reversals.
The directed Markov properties
d-separation satisfies all five axioms and more, but no finite list of axioms characterizes probabilistic independence completely (Studený, 1992). A graph is therefore best seen as a compact certificate for a family of independences. Write for the non-descendants of and for the smallest ancestral set containing .
(F) ⇒ (G). Let . Summing out the nodes outside , childless ones first, removes their CPTs one by one (each sums to 1), and the parents of nodes in lie in :
Each factor's scope is a clique of the moral graph . If separates from there, let be the nodes of connected to avoiding , and the rest. No clique meets both and , so every factor belongs to one side:
(G) ⇒ (L). d-separates from : a path that leaves through a parent is blocked at that parent, and a path that leaves through a child must turn around at a collider that is a descendant of , hence outside and with no descendant in it.
(L) ⇒ (F) is the chain rule in a topological order, as in the Hidden Layer lesson. Combined with the moralization criterion, the first step is the soundness of d-separation. ∎
Think first Why restrict to the ancestral set before moralizing? Try with .
Moralizing the whole graph marries and , the parents of , so they would look dependent. But is unobserved and is not an ancestor of anything in , so it is summed out first; then has no edge and they are correctly separated. Moral edges should be added only for colliders that are ancestors of the evidence, which are exactly the colliders that d-separation treats as open.
Completeness and faithfulness
Fix a triple that is d-connected. Independence means that every cross-ratio of joint probabilities vanishes:
Each is a sum, over the other variables, of products of CPT entries, so every is a polynomial in the parameters .
By completeness, some makes and dependent given , so at least one is not the zero polynomial. The zero set of a nonzero polynomial has measure zero (induction on the number of variables and Fubini's theorem).
There are finitely many d-connected triples, and a finite union of null sets is null. The same argument works for linear-Gaussian networks, with edge coefficients and noise variances as parameters. ∎
Measure zero is not the same as harmless. Three mechanisms produce unfaithful distributions:
- Path cancellation. In a linear model with (coefficient ) and (coefficients , ), , which vanishes when . A drug that raises a risk directly and lowers it through a side effect can look inert.
- Determinism. If exactly, then for every , even for 's own children, which the graph connects to directly.
- Context-specific independence. A CPT can make independent of one parent when another parent takes a particular value, a structure no DAG can express.
Near-cancellations are the practical problem: for linear-Gaussian models the parameters that come close to an independence occupy a non-negligible volume (Uhler, Raskutti, Bühlmann & Yu, 2013), and finite-sample causal discovery cannot tell them from exact ones.
In a linear model, has coefficient , has coefficient , and there is also a direct edge with coefficient . Which value of makes and uncorrelated, a violation of faithfulness?
Show the answer
D.
The total effect is , so cancels the indirect path exactly. and are d-connected along both paths, yet uncorrelated, and with Gaussian noise independent.
Bayes-ball: d-separation in linear time
A DAG can have exponentially many paths between two nodes, so checking them one by one is hopeless. But "is there an active path?" is a reachability question over states (node, direction of arrival), and breadth-first search answers it. Arriving at from a child (moving up), the path may continue to 's parents and children unless . Arriving from a parent (moving down), it may continue down if , and bounce back up to 's other parents only if is a collider that is active, that is, is an ancestor of (Shachter, 1998; Geiger, Verma & Pearl, 1990).
function REACHABLE(G, X, Z): # nodes d-connected to X given Z
A ← Z together with all ancestors of Z # phase 1: active colliders
L ← {(X, ↑)}; visited ← ∅; R ← ∅ # ↑: arrived from a child
while L is not empty:
(W, d) ← remove an element of L
if (W, d) ∈ visited: continue
visited ← visited ∪ {(W, d)}
if W ∉ Z: R ← R ∪ {W}
if d = ↑ and W ∉ Z: # chain or fork through W
add (P, ↑) for each parent P of W, and (C, ↓) for each child C of W
if d = ↓: # arrived from a parent
if W ∉ Z: add (C, ↓) for each child C of W
if W ∈ A: add (P, ↑) for each parent P of W # active collider
return RThe reachability algorithm of Koller & Friedman (2009, chapter 3). Each of the states is visited once and each edge is scanned a constant number of times, so the cost is . is d-separated from by exactly when . The same pass tells inference which nodes, and which CPTs, a query can depend on at all.
Markov equivalence
Same independences ⇒ same skeleton. Adjacent nodes are d-connected by every set. Non-adjacent nodes are d-separated by some set: by if is not a descendant of (local Markov), otherwise by .
⇒ same v-structures. For an unshielded triple , if is a collider then no separating set of and contains (it would open the path), and if is not a collider then every separating set contains (otherwise the path through is open). The independences therefore reveal which unshielded triples are colliders.
⇐. Call covered if . Reversing a covered edge preserves the family of factorizing distributions, because the two CPTs combine into one conditional over the shared parents, which Bayes' rule can factor either way:
Chickering (1995) showed that two DAGs with the same skeleton and v-structures are connected by a sequence of covered edge reversals, one per edge on which they differ, each step staying in the class. ∎
A class is summarized by its essential graph (or CPDAG): an edge is directed if every member orients it the same way (it is compelled), and undirected otherwise. Its undirected parts are chordal (Andersson, Madigan & Perlman, 1997), and given the skeleton and the v-structures, four orientation rules of Meek (1995) recover every compelled edge, for example: if with and not adjacent, orient , since would create a new v-structure.
Classes are often small. The three-node chain, the reversed chain and the fork form one class, while the collider is alone in its own. Exhaustive enumeration for up to ten nodes found about 3.7 DAGs per equivalence class on average (Gillispie & Perlman, 2001).
Key takeaways
- For DAGs, factorization, the global Markov property (d-separation implies independence) and the local Markov property are equivalent for every distribution. The proof goes through the moral graph of the ancestral set.
- d-separation is sound and complete: its statements are exactly the independences shared by all distributions on the graph. Unfaithful parameters have measure zero because each independence is a polynomial equation, but near-cancellations matter in finite samples.
- Bayes-ball decides d-separation, and finds every node d-connected to a query, in time by searching over (node, direction) states.
- DAGs are Markov equivalent if and only if they have the same skeleton and v-structures. Equivalent DAGs are linked by covered edge reversals, and a class is summarized by its essential graph.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
d-separation is complete. Which statement follows?
- Every distribution that factorizes over has exactly the independences that d-separation lists
- Every independence that holds for all distributions factorizing over is a d-separation, although particular distributions can have extra independences
- Two variables that are d-connected are dependent in every distribution that factorizes over
- A DAG can be recovered uniquely from the independences of a faithful distribution
Show the answer
B. Every independence that holds for all distributions factorizing over is a d-separation, although particular distributions can have extra independences
Completeness quantifies over all parameterizations: for each d-connected triple, some distribution is dependent, and Meek showed that almost all are. Special parameters, such as path cancellation or deterministic CPTs, add independences.
To test whether d-separates and with the moralization criterion, which graph do you moralize?
- The whole DAG
- The subgraph induced by
- The subgraph induced by the ancestors of , these sets included
- The subgraph induced by the descendants of
Show the answer
C. The subgraph induced by the ancestors of , these sets included
Non-ancestors can be summed out without changing the marginal on . Moralizing more than that marries the parents of unobserved colliders and hides true independences.
Which DAG is Markov equivalent to ?
Show the answer
B.
It has the same skeleton and, like the original, no v-structures: a chain read backwards encodes the same independences, such as and .
In Bayes-ball, a path arrives at node from one of its parents. is not in , but one of its descendants is. Where can the path continue?
- Only down, to 's children
- Only up, to 's other parents
- Nowhere: the path is blocked at
- Down to 's children, and up to its other parents
Show the answer
D. Down to 's children, and up to its other parents
, so the chain through to its children stays open. is an ancestor of , so as a collider it is active and the path can also turn up to its other parents.
Further reading
- D. Geiger, T. Verma & J. Pearl, "Identifying independence in Bayesian networks," Networks 20(5), 507–534 (1990).
- S. L. Lauritzen, A. P. Dawid, B. N. Larsen & H.-G. Leimer, "Independence properties of directed Markov fields," Networks 20(5), 491–505 (1990).
- T. Verma & J. Pearl, "Equivalence and synthesis of causal models," Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence (1990).
- C. Meek, "Strong completeness and faithfulness in Bayesian networks," Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence (1995).
- D. Koller & N. Friedman, Probabilistic Graphical Models: Principles and Techniques (MIT Press, 2009), chapter 3.