d-separation · Tae Hyun Kim (Lowell)

Definition

d-separation (directional separation)은 DAG에서 두 변수 집합이 세 번째 집합에 조건부로 독립인지 판단하는 graphical criterion.

Formal Definition:

DAG $G$ 에서, $Z$ 가 $X$ 와 $Y$ 를 d-separate 한다면:

$X \perp_G Y \mid Z$

$X$ 와 $Y$ 사이의 모든 path가 $Z$ 에 의해 blocked.

Path Blocking Rules

Three Elementary Structures

Structure	Name	Blocked by $Z$ ?
$A \rightarrow B \rightarrow C$	Chain	$B \in Z$ 이면 blocked
$A \leftarrow B \rightarrow C$	Fork	$B \in Z$ 이면 blocked
$A \rightarrow B \leftarrow C$	Collider	$B \notin Z$ and $De(B) \cap Z = \emptyset$ 이면 blocked

Blocking Rule Summary

Path $\pi$ 가 $Z$ 에 의해 blocked 되려면:

Non-collider (chain or fork)의 중간 node가 $Z$ 에 포함
Collider의 중간 node와 그 descendants가 $Z$ 에 미포함

Intuitive Understanding

핵심 아이디어:

d-separation = “정보 흐름의 차단”

Fork (Common Cause):
    A ← B → C

    - B가 주어지면: A, C 독립 (confounding 제거)
    - B가 주어지지 않으면: A, C 연관 (via B)

Chain (Mediation):
    A → B → C

    - B가 주어지면: A, C 독립 (mediator blocked)
    - B가 주어지지 않으면: A, C 연관 (causal path)

Collider (Common Effect):
    A → B ← C

    - B가 주어지지 않으면: A, C 독립 (default blocked)
    - B가 주어지면: A, C 연관! (collider bias)

d-separation Algorithm

Input

DAG $G$
Sets $X$ , $Y$ , $Z$

Procedure

For each path π between X and Y:
    blocked = False
    For each node B on path π (excluding endpoints):
        If B is a non-collider on π:
            If B ∈ Z:
                blocked = True
                break
        Else (B is a collider on π):
            If B ∉ Z and De(B) ∩ Z = ∅:
                blocked = True
                break

    If not blocked:
        return "X and Y are NOT d-separated by Z"

return "X and Y are d-separated by Z"

Faithfulness Assumption

Markov Property

$P$ 가 DAG $G$ 에 대해 Markov: $X \perp_G Y \mid Z \implies X \perp_P Y \mid Z$

그래프의 d-separation → 확률적 독립

Faithfulness

$P$ 가 DAG $G$ 에 faithful: $X \perp_P Y \mid Z \implies X \perp_G Y \mid Z$

확률적 독립 → 그래프의 d-separation

Combined (Perfect Map): $X \perp_P Y \mid Z \iff X \perp_G Y \mid Z$

Examples

Example 1: Simple Chain

X → Y → Z

$X \perp_G Z \mid Y$ ? Yes (Y blocks the chain)
$X \perp_G Z$ ? No (path open)

Example 2: Fork (Confounding)

    C
   ↙ ↘
  X   Y

$X \perp_G Y \mid C$ ? Yes (C blocks the fork)
$X \perp_G Y$ ? No (confounding path open)

Example 3: Collider

X → C ← Y

$X \perp_G Y$ ? Yes (collider blocks by default)
$X \perp_G Y \mid C$ ? No (conditioning opens collider)

Example 4: Complex Graph

    A
   ↙ ↘
  B   C
   ↘ ↗
    D

$A \perp_G D$ ? Check all paths:
- $A \rightarrow B \rightarrow D$ : Open
- Not d-separated
$A \perp_G D \mid B$ ?
- $A \rightarrow B \rightarrow D$ : Blocked (B ∈ Z)
- $A \rightarrow C \rightarrow D$ : Open
- Not d-separated
$A \perp_G D \mid \{B, C\}$ ?
- $A \rightarrow B \rightarrow D$ : Blocked
- $A \rightarrow C \rightarrow D$ : Blocked
- d-separated!