Simple Algorithm
Artificial Intelligence · Deep Layer · 26 min

d-Separation & Independence

Reading independence off a graph.

Is AA independent of BB given CC and DD 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 O(∣V∣+∣E∣)\order{|V|+|E|} 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 NDi\mathrm{ND}_i for the non-descendants of XiX_i and An(S)\mathrm{An}(S) for the smallest ancestral set containing SS.

DerivationProof of (F) ⇒ (G) ⇒ (L) ⇒ (F)
  1. P(xA)=∏i∈AP(xi∣pai)P(x_A)=\prod_{i\in A}P(x_i\mid\mathrm{pa}_i)

    (F) ⇒ (G). Let A=An(X∪Y∪Z)A=\mathrm{An}(X\cup Y\cup Z). Summing out the nodes outside AA, childless ones first, removes their CPTs one by one (each sums to 1), and the parents of nodes in AA lie in AA:

  2. P(x′,y′,z)=f(x′,z) g(y′,z) ⟹ X′⊥ ⁣ ⁣ ⁣⊥Y′∣Z ⟹ X⊥ ⁣ ⁣ ⁣⊥Y∣Z  (decomposition)P(x',y',z)=f(x',z)\,g(y',z)\ \Longrightarrow\ X'\indep Y'\mid Z\ \Longrightarrow\ X\indep Y\mid Z\ \ (\text{decomposition})

    Each factor's scope {i}∪Pai\{i\}\cup\mathrm{Pa}_i is a clique of the moral graph (GA)m(G_A)^m. If ZZ separates XX from YY there, let X′X' be the nodes of A∖ZA\setminus Z connected to XX avoiding ZZ, and Y′Y' the rest. No clique meets both X′X' and Y′Y', so every factor belongs to one side:

  3. Pai d-separates Xi and NDi∖Pai\mathrm{Pa}_i\ \text{d-separates}\ X_i\ \text{and}\ \mathrm{ND}_i\setminus\mathrm{Pa}_i

    (G) ⇒ (L). Pai\mathrm{Pa}_i d-separates XiX_i from NDi\mathrm{ND}_i: 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 XiX_i, hence outside Pai\mathrm{Pa}_i and with no descendant in it.

  4. P(x)=∏iP(xi∣x1:i−1)=∏iP(xi∣pai)P(x)=\prod_iP(x_i\mid x_{1:i-1})=\prod_iP(x_i\mid\mathrm{pa}_i)

    (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 X→C←YX\to C\leftarrow Y with Z=∅Z=\varnothing.

Moralizing the whole graph marries XX and YY, the parents of CC, so they would look dependent. But CC is unobserved and is not an ancestor of anything in X∪Y∪ZX\cup Y\cup Z, so it is summed out first; then An({X,Y})={X,Y}\mathrm{An}(\{X,Y\})=\{X,Y\} 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

DerivationWhy unfaithful parameters have measure zero
  1. Fx,x′,y,y′,z(θ)=P(x,y,z) P(x′,y′,z)−P(x,y′,z) P(x′,y,z)=0for all valuesF_{x,x',y,y',z}(\theta)=P(x,y,z)\,P(x',y',z)-P(x,y',z)\,P(x',y,z)=0\quad\text{for all values}

    Fix a triple (X,Y,Z)(X,Y,Z) that is d-connected. Independence means that every cross-ratio of joint probabilities vanishes:

  2. P(x,y,z)=∑v ∏iθvi∣paiP(x,y,z)=\sum_{\mathbf v}\ \prod_i\theta_{v_i\mid\mathrm{pa}_i}

    Each P(x,y,z)P(x,y,z) is a sum, over the other variables, of products of CPT entries, so every FF is a polynomial in the parameters θ\theta.

  3. λ({θ: F(θ)=0})=0\lambda\big(\{\theta:\ F(\theta)=0\}\big)=0

    By completeness, some θ0\theta_0 makes XX and YY dependent given ZZ, so at least one FF 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).

  4. λ(⋃(X,Y,Z) d-connected{θ: X⊥ ⁣ ⁣ ⁣⊥PθY∣Z})=0\lambda\Big(\bigcup_{(X,Y,Z)\ \text{d-connected}}\{\theta:\ X\indep_{P_\theta}Y\mid Z\}\Big)=0

    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 X→YX\to Y (coefficient aa) and X→M→YX\to M\to Y (coefficients bb, cc), Cov⁡(X,Y)=(a+bc)Var⁡(X)\Cov(X,Y)=(a+bc)\Var(X), which vanishes when a=−bca=-bc. A drug that raises a risk directly and lowers it through a side effect can look inert.
  • Determinism. If Y=f(X)Y=f(X) exactly, then Y⊥ ⁣ ⁣ ⁣⊥W∣XY\indep W\mid X for every WW, even for YY's own children, which the graph connects to YY directly.
  • Context-specific independence. A CPT can make YY 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.

Check your understanding

In a linear model, X→MX\to M has coefficient b=2b=2, M→YM\to Y has coefficient c=0.5c=0.5, and there is also a direct edge X→YX\to Y with coefficient aa. Which value of aa makes XX and YY uncorrelated, a violation of faithfulness?

  1. a=1a=1
  2. a=−0.25a=-0.25
  3. a=0a=0
  4. a=−1a=-1
Show the answer

D. a=−1a=-1

The total effect is a+bc=a+1a+bc=a+1, so a=−1a=-1 cancels the indirect path exactly. XX and YY 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 WW from a child (moving up), the path may continue to WW's parents and children unless W∈ZW\in Z. Arriving from a parent (moving down), it may continue down if W∉ZW\notin Z, and bounce back up to WW's other parents only if WW is a collider that is active, that is, WW is an ancestor of ZZ (Shachter, 1998; Geiger, Verma & Pearl, 1990).

text
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 R

The reachability algorithm of Koller & Friedman (2009, chapter 3). Each of the 2∣V∣2|V| states is visited once and each edge is scanned a constant number of times, so the cost is O(∣V∣+∣E∣)\order{|V|+|E|}. YY is d-separated from XX by ZZ exactly when Y∉RY\notin R. The same pass tells inference which nodes, and which CPTs, a query can depend on at all.

Markov equivalence

DerivationProof sketch
  1. X,Y adjacent  ⟺  ∄S: X⊥ ⁣ ⁣ ⁣⊥GY∣SX,Y\ \text{adjacent}\iff\nexists S:\ X\indep_GY\mid S

    Same independences ⇒ same skeleton. Adjacent nodes are d-connected by every set. Non-adjacent nodes are d-separated by some set: by PaX\mathrm{Pa}_X if YY is not a descendant of XX (local Markov), otherwise by PaY\mathrm{Pa}_Y.

  2. Z is a collider on X→Z←Y  ⟺  Z∉S for every S with X⊥ ⁣ ⁣ ⁣⊥GY∣SZ\ \text{is a collider on}\ X\to Z\leftarrow Y\iff Z\notin S\ \text{for every}\ S\ \text{with}\ X\indep_GY\mid S

    ⇒ same v-structures. For an unshielded triple X−Z−YX-Z-Y, if ZZ is a collider then no separating set of XX and YY contains ZZ (it would open the path), and if ZZ is not a collider then every separating set contains ZZ (otherwise the path through ZZ is open). The independences therefore reveal which unshielded triples are colliders.

  3. P(x∣paX) P(y∣paX,x)=P(x,y∣paX)=P(y∣paX) P(x∣paX,y)P(x\mid\mathrm{pa}_X)\,P(y\mid\mathrm{pa}_X,x)=P(x,y\mid\mathrm{pa}_X)=P(y\mid\mathrm{pa}_X)\,P(x\mid\mathrm{pa}_X,y)

    ⇐. Call X→YX\to Y covered if PaY=PaX∪{X}\mathrm{Pa}_Y=\mathrm{Pa}_X\cup\{X\}. 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:

  4. G=G0→G1→⋯→Gk=G′,k=#{edges oriented differently}G=G_0\to G_1\to\cdots\to G_k=G',\qquad k=\#\{\text{edges oriented differently}\}

    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 A→B−CA\to B-C with AA and CC not adjacent, orient B→CB\to C, since B←CB\leftarrow C 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 O(∣V∣+∣E∣)\order{|V|+|E|} 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.

Question 1

d-separation is complete. Which statement follows?

  1. Every distribution that factorizes over GG has exactly the independences that d-separation lists
  2. Every independence that holds for all distributions factorizing over GG is a d-separation, although particular distributions can have extra independences
  3. Two variables that are d-connected are dependent in every distribution that factorizes over GG
  4. 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 GG 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.

Question 2

To test whether ZZ d-separates XX and YY with the moralization criterion, which graph do you moralize?

  1. The whole DAG
  2. The subgraph induced by X∪Y∪ZX\cup Y\cup Z
  3. The subgraph induced by the ancestors of X∪Y∪ZX\cup Y\cup Z, these sets included
  4. The subgraph induced by the descendants of ZZ
Show the answer

C. The subgraph induced by the ancestors of X∪Y∪ZX\cup Y\cup Z, these sets included

Non-ancestors can be summed out without changing the marginal on An(X∪Y∪Z)\mathrm{An}(X\cup Y\cup Z). Moralizing more than that marries the parents of unobserved colliders and hides true independences.

Question 3

Which DAG is Markov equivalent to A→B→C→DA\to B\to C\to D?

  1. A→B←C→DA\to B\leftarrow C\to D
  2. A←B←C←DA\leftarrow B\leftarrow C\leftarrow D
  3. A→B→C←DA\to B\to C\leftarrow D
  4. A←B→C←DA\leftarrow B\to C\leftarrow D
Show the answer

B. A←B←C←DA\leftarrow B\leftarrow C\leftarrow D

It has the same skeleton and, like the original, no v-structures: a chain read backwards encodes the same independences, such as A⊥ ⁣ ⁣ ⁣⊥D∣BA\indep D\mid B and A⊥ ⁣ ⁣ ⁣⊥D∣CA\indep D\mid C.

Question 4

In Bayes-ball, a path arrives at node WW from one of its parents. WW is not in ZZ, but one of its descendants is. Where can the path continue?

  1. Only down, to WW's children
  2. Only up, to WW's other parents
  3. Nowhere: the path is blocked at WW
  4. Down to WW's children, and up to its other parents
Show the answer

D. Down to WW's children, and up to its other parents

W∉ZW\notin Z, so the chain through WW to its children stays open. WW is an ancestor of ZZ, 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.