4  Graph Theory and Causal Patterns

Status: Draft

v0.5

4.1 Introduction

Chapter 2 took as its primary unit a directed dyad \(X \rightarrow Y\) with a local mechanism \(Y \coloneqq f(X, U)\). This chapter assembles those atoms into path patterns. Graph theory is the language of the Structural stratum for association under observation: which parents enter which assignments, which paths carry dependence, and which conditioning sets block or open those paths (Pearl 2009; Spirtes et al. 2000).

Nothing here invents a fourth kind of relation. A DAG \(G = (V, E)\) is a sparse collection of dyads; chains, forks, and colliders are overlapping edges with characteristic path geometry. What changes is how paths compose, and how d-separation translates that geometry into conditional independence. Executable mechanisms and the linear matrix form \(\mathbf{X} = B\mathbf{X} + \mathbf{U}\) belong to Chapter 4; here the edge set of \(G\) is enough.

NotePackages implement the examples

This book’s framing is general: structure, dynamics, and observation for complex dynamical systems. Executable examples use a Julia stack with four clear owners:

• CausalDynamics.jl — graphs, identify, SCM/CDM do
• CausalTargeted.jl — cross-fitted LMTP / MTP grids, factor recodes, Super Learner profiles
• CausalMediation.jl — TE / NDE / NIE and related mediation (incl. moc)
• DAGMakie.jl — DAG figures from the same graph objects

The book is not package documentation; manuals and changelogs live in the repositories.

Code keeps standard Pearl / targeted-learning names (Intervention, do_surgery, backdoor_adjustment_set, run_lmtp_grid, run_mediation, …). Prose may use a sparse process gloss where it helps: prehension (taking account of), shared \(U\) as creative advance (Introduction), L3 alternative concrescences, and Chapter 9’s organism / environment / Markov blanket / society vocabulary for CDM scope (\(\mu\), \(\eta\), \(s\), \(a\), \(G\), \(F\)), plus enduring / occasion for how temporal-DAG nodes are indexed (entity-level / time-indexed only as a one-time gloss; DAGMakie marks enduring nodes with rounded rectangles). Prefer ordinary words (observation, intervention, time step) elsewhere. Mapping: Concept Reference, Tables 4 and 8.

Package source as notation. Where the implementation is the explanation (graph surgery, path blocking, shared-\(U\) counterfactuals), chapters may show a short, syntax-highlighted excerpt from the owned packages in a “From …jl” callout, alongside executed API chunks. Those excerpts are curated under snippets/package-source/; they are not a substitute for the Documenter manuals.

4.2 Graphs as Structural Claims

Chapter 1 already stated the SCM as \(\mathcal{M} = (G, F, P_U)\) with mechanisms \(V_j \coloneqq f_j(\mathrm{pa}_G(V_j), U_j)\). This chapter stays with \(G\): the directed acyclic graph whose edges are Chapter 2’s dyads (Pearl 2009; Spirtes et al. 2000). Direction encodes parenthood; acyclicity rules out directed feedback in this static graph (cycles return in Chapter 9b); absent edges are part of the claim as much as present ones. Path criteria and \(do(\cdot)\) presuppose that stated edge set; the modelled system may still unfold in time (Introduction).

4.3 Three Fundamental Patterns

Chapter 2 listed three classical assemblies of dyads. Here they become the vocabulary for every nontrivial path (Pearl 2009).

Chain. \(A \rightarrow B \rightarrow C\): association flows along the directed path; conditioning on the mediator \(B\) blocks it.

Fork. \(A \leftarrow B \rightarrow C\): \(B\) is a common cause. Conditioning on \(B\) blocks the fork. When \(B\) is a confounder of treatment and outcome, this is the good-control triangle of Chapter 1 (\(C \rightarrow A\), \(C \rightarrow Y\), \(A \rightarrow Y\)) and of Cinelli, Forney, and Pearl (Cinelli et al. 2024).

Collider. \(A \rightarrow B \leftarrow C\): the collider blocks by default; conditioning on \(B\) (or a descendant of \(B\)) opens the path. Colliders are not good controls for the total effect of \(A\) on \(C\) along other routes (Cinelli et al. 2024).

Figure 4.1 draws the three motifs. The next section turns the blocking rules into d-separation; M-bias then applies the collider rule on a Cinelli-style bad-control path.

g_chain = SimpleDiGraph(3)
add_edge!(g_chain, 1, 2)  # A → B
add_edge!(g_chain, 2, 3)  # B → C

g_fork = SimpleDiGraph(3)
add_edge!(g_fork, 2, 1)  # B → A
add_edge!(g_fork, 2, 3)  # B → C

g_collider = SimpleDiGraph(3)
add_edge!(g_collider, 1, 2)  # A → B
add_edge!(g_collider, 3, 2)  # C → B

Figure 4.1: The three fundamental causal patterns as assemblies of dyads: chain, fork, and collider.

4.4 d-Separation

d-separation is the graph criterion that connects the three patterns to conditional independence (Pearl 2009). Two nodes \(X\) and \(Y\) are d-separated by a set \(Z\) when every path between them is blocked by \(Z\). Blocking follows the motifs above:

• Chain \(A \rightarrow B \rightarrow C\): blocked if \(B \in Z\)
• Fork \(A \leftarrow B \rightarrow C\): blocked if \(B \in Z\)
• Collider \(A \rightarrow B \leftarrow C\): blocked if \(B \notin Z\) and no descendant of \(B\) is in \(Z\)

If \(X\) and \(Y\) are d-separated by \(Z\) in \(G\), then \(X ⫫ Y \mid Z\) in every distribution compatible with \(G\) (under the usual Markov and faithfulness reading). That is why Structural claims constrain Observable association: the graph names which conditional independences the data ought to show if \(G\) is correctly specified. This chapter is therefore Seeing on the Structural stratum (Chapter 1); identification of interventional effects from those independences is Chapter 5.

Figure 4.2 is used for the checks below and again for the Markov boundary: \(Z \rightarrow X \rightarrow Y \leftarrow W\) with \(Z \rightarrow W\). Conditioning on \(X\) alone does not d-separate \(Z\) from \(Y\); the path \(Z \rightarrow W \rightarrow Y\) remains open.

g_zw = SimpleDiGraph(4)
add_edge!(g_zw, 1, 2)  # Z → X
add_edge!(g_zw, 2, 3)  # X → Y
add_edge!(g_zw, 4, 3)  # W → Y
add_edge!(g_zw, 1, 4)  # Z → W
labels_zw = ["Z", "X", "Y", "W"]

Figure 4.2: Composite DAG \(Z \rightarrow X \rightarrow Y \leftarrow W\) with \(Z \rightarrow W\), used for d-separation checks and for the Markov boundary of \(X\).

checks = [
    ("Chain A→B→C", "A ⫫ C | B", d_separated(g_chain, 1, 3, [2])),
    ("Chain A→B→C", "A ⫫ C", d_separated(g_chain, 1, 3, Int[])),
    ("Fork A←B→C", "A ⫫ C | B", d_separated(g_fork, 1, 3, [2])),
    ("Fork A←B→C", "A ⫫ C", d_separated(g_fork, 1, 3, Int[])),
    ("Collider A→B←C", "A ⫫ C", d_separated(g_collider, 1, 3, Int[])),
    ("Collider A→B←C", "A ⫫ C | B", d_separated(g_collider, 1, 3, [2])),
    ("Composite Z…W", "X ⫫ Y", d_separated(g_zw, 2, 3, Int[])),
    ("Composite Z…W", "X ⫫ Y | W", d_separated(g_zw, 2, 3, [4])),
    ("Composite Z…W", "Z ⫫ Y | X", d_separated(g_zw, 1, 3, [2])),
    ("Composite Z…W", "Z ⫫ Y | X,W", d_separated(g_zw, 1, 3, [2, 4])),
]

for (pattern, claim, ok) in checks
    println(rpad(pattern, 18), "  ", rpad(claim, 14), "  ", ok)
end

Chain A→B→C         A ⫫ C | B       true
Chain A→B→C         A ⫫ C           false
Fork A←B→C          A ⫫ C | B       true
Fork A←B→C          A ⫫ C           false
Collider A→B←C      A ⫫ C           true
Collider A→B←C      A ⫫ C | B       false
Composite Z…W       X ⫫ Y           false
Composite Z…W       X ⫫ Y | W       false
Composite Z…W       Z ⫫ Y | X       false
Composite Z…W       Z ⫫ Y | X,W     true

4.4.1 Simulation: association blocked by \(\{X,W\}\)

Under a faithful linear Gaussian SEM for Figure 4.2,

\[ \begin{aligned} Z &\coloneqq U_Z, \\ X &\coloneqq \beta_{ZX} Z + U_X, \\ W &\coloneqq \beta_{ZW} Z + U_W, \\ Y &\coloneqq \beta_{XY} X + \beta_{WY} W + U_Y, \end{aligned} \]

\(Y\) does not have \(Z\) as a parent, yet open chains leave a clear \(Z\)–\(Y\) association. Raw scatter cannot show conditioning; under linear Gaussian assumptions the Frisch–Waugh–Lovell residual plot does. Residualise both \(Z\) and \(Y\) on \(\{X,W\}\): the slope in that residual–residual scatter is exactly coef(Z) in \(Y \sim Z + X + W\), and under \(Z ⫫ Y \mid X,W\) the cloud is noise (Figure 4.3).

rng = StableRNG(7)
n = 800

Z = randn(rng, n)
X = 0.9 .* Z .+ 0.5 .* randn(rng, n)
W = 0.8 .* Z .+ 0.5 .* randn(rng, n)
Y = 1.1 .* X .+ 0.9 .* W .+ 0.5 .* randn(rng, n)

"""OLS residuals of `y` after regression on columns of `X` (with intercept)."""
function ols_residuals(y, X)
    X₁ = hcat(ones(length(y)), X)
    return y .- X₁ * (X₁ \ y)
end

β_marg = hcat(ones(n), Z) \ Y
Z_res = ols_residuals(Z, hcat(X, W))
Y_res = ols_residuals(Y, hcat(X, W))
β_res = hcat(ones(n), Z_res) \ Y_res  # equals coef(Z) in Y ~ Z + X + W

2-element Vector{Float64}:
 2.7476618026966062e-17
 0.06971147229718273

Figure 4.3: Left: raw \(Z\) vs \(Y\) (open paths). Right: residuals after regressing both on \(\{X,W\}\); the fitted slope is coef(Z) in \(Y \sim Z+X+W\) and is near zero under \(Z ⫫ Y \mid X,W\).

4.4.2 M-bias

When each parent of a collider is tied to an unobserved common cause of an exposure or an outcome, the structure is often called M-bias (Pearl 2009; Cinelli et al. 2024). The five-node graph below has latents \(U_1\) and \(U_2\) and collider \(M\):

\[ X \leftarrow U_1 \rightarrow M \leftarrow U_2 \rightarrow Y. \]

\(X\) and \(Y\) are independent unconditionally. Conditioning on \(M\) opens the path through the collider and induces a spurious association. Do not adjust for a collider (or its descendant) when estimating the effect of \(X\) on \(Y\): the same good/bad-control discipline as Chapter 1, now on a path that looks “pre-treatment” yet still spoils identification.

Figure 4.4: Classic M-bias with explicit latents: \(X \leftarrow U_1 \rightarrow M \leftarrow U_2 \rightarrow Y\). Conditioning on the collider \(M\) opens a non-causal path between \(X\) and \(Y\) (dagplot_m_bias; Cinelli et al. (Cinelli et al. 2024)).

4.5 Markov Boundary

The Markov boundary of a node \(X\) is a minimal set that d-separates \(X\) from all other nodes in the graph (Pearl 2009): parents of \(X\), children of \(X\), and other parents of those children (spouses). It is read from \(G\), not from a fitted regression. Nodes outside that set are screened off once the boundary is known for the stated local predictive factorisation; the boundary is not thereby a causal adjustment or counterfactual-sufficiency set.

Figure 4.5 uses an eight-node DAG with letter labels. The focus is \(M\); its boundary is \(\{A, G, I, N, R, S\}\). A parent of \(A\) alone (\(O\rightarrow A\), and the \(G\rightarrow A\) leg of a fork) stays screened off by \(A\), but \(G\rightarrow I\) also makes \(G\) a co-parent of the child \(I\), so \(G\) enters the boundary as a spouse. The sole muted node outside the boundary is \(O\).

# Focus M = node 5
g_mb = SimpleDiGraph(8)
for (s, d) in (
    (1, 2),   # O → A  (ancestor of parent; outside MB)
    (2, 5),   # A → M
    (3, 5),   # N → M
    (4, 2),   # G → A  (screened by A as ancestor path)
    (4, 6),   # G → I  (spouse of M via child I)
    (5, 6),   # M → I
    (5, 7),   # M → S
    (8, 7),   # R → S  (spouse)
)
    add_edge!(g_mb, s, d)
end
# Node order: O,A,N,G,M,I,S,R
labels_mb = ["O", "A", "N", "G", "M", "I", "S", "R"]

layout_mb = Point2f[
    Point2f(0.0, 5.0),   # O (parent of A; outside MB)
    Point2f(0.0, 3.8),   # A (parent of M)
    Point2f(2.0, 3.8),   # N (parent of M)
    Point2f(3.5, 3.8),   # G (spouse via G→I; also →A)
    Point2f(1.0, 2.6),   # M (focus)
    Point2f(2.2, 1.4),   # I (child)
    Point2f(0.0, 1.4),   # S (child)
    Point2f(-1.5, 1.4),  # R (spouse)
]

focus = 5  # M
parents_mb = get_parents(g_mb, focus)
children_mb = get_children(g_mb, focus)
mb = markov_boundary(g_mb, focus)
spouses_mb = setdiff(mb, union(parents_mb, children_mb))
outside_mb = setdiff(Set(1:nv(g_mb)), union(mb, Set([focus])))

col_outside = RGBf(0.60, 0.60, 0.60)
col_parent = RGBf(0.85, 0.65, 0.05)
col_focus = RGBf(0.20, 0.55, 0.45)
col_child = RGBf(0.30, 0.55, 0.70)
col_spouse = RGBf(0.80, 0.40, 0.35)
node_colors_mb = fill(col_outside, nv(g_mb))
for i in parents_mb
    node_colors_mb[i] = col_parent
end
for i in children_mb
    node_colors_mb[i] = col_child
end
for i in spouses_mb
    node_colors_mb[i] = col_spouse
end
node_colors_mb[focus] = col_focus

println("Markov boundary of M")
println("  Parents:  ", join(labels_mb[sort(collect(parents_mb))], ", "))
println("  Children: ", join(labels_mb[sort(collect(children_mb))], ", "))
println("  Spouses:  ", join(labels_mb[sort(collect(spouses_mb))], ", "))
println("  Boundary: ", join(labels_mb[sort(collect(mb))], ", "))
println("  Outside:  ", join(labels_mb[sort(collect(outside_mb))], ", "))

Markov boundary of M
  Parents:  A, N
  Children: I, S
  Spouses:  G, R
  Boundary: A, N, G, I, S, R
  Outside:  O

Figure 4.5: Markov boundary of \(M\) (teal): parents \(A\), \(N\) (gold); children \(I\), \(S\) (blue); spouses \(G\), \(R\) (coral). \(O\rightarrow A\) remains outside (muted); \(G\) enters via \(G\rightarrow I\), not via \(G\rightarrow A\).

4.6 Looking ahead: edges as coefficient support

Chapter 2 counted how few of the \(n(n-1)\) possible directed dyads a sparse scientific DAG retains. Those present edges are exactly the non-zeros of a linear structural matrix \(B\) once mechanisms are linear: \(B_{ij}\neq 0\) means \(X_j \rightarrow X_i\) (Peters et al. 2017).

Figure 4.6 redraws Chapter 1’s good-control triangle with labels \(C\), \(A\), \(Y\). Adjustment colouring marks \(C\) as the good control for the total effect of \(A\) on \(Y\) (Cinelli et al. 2024); that colouring is a reminder of the fork already seen, not yet a full identification argument (Chapter 5). Path coefficients on the edges preview the executable linear SCM of Chapter 4, where the same support becomes \(B\), adjacency conventions, and simulation.

# Same motif as Chapter 1: C → A → Y, C → Y (nodes 1,2,3)
g_cay = SimpleDiGraph(3)
add_edge!(g_cay, 1, 2)  # C → A
add_edge!(g_cay, 2, 3)  # A → Y
add_edge!(g_cay, 1, 3)  # C → Y
labels_cay = ["C", "A", "Y"]
elabels_cay = structural_edge_labels(
    g_cay,
    ["\\beta_{CA}", "\\beta_{CY}", "\\beta_{AY}"];
    latex = true,
)

Figure 4.6: Chapter 1’s good-control triangle \(C \rightarrow A \rightarrow Y\), \(C \rightarrow Y\), with structural path coefficients on the edges. Colouring marks \(C\) as the adjustment set for \(A \rightarrow Y\) (Cinelli et al. 2024); the matrix form of this graph is developed in Chapter 4.

4.7 Summary

Graph theory supplies the Structural language for assembling Chapter 2’s dyads. Chains, forks, and colliders organise paths; d-separation links those patterns to conditional independence under observation; M-bias shows how conditioning on a collider can invent dependence; and the Markov boundary names a minimal sufficient set for local reasoning about a node. Good controls block backdoors; mediators and colliders on causal paths are not good controls for total effects (Cinelli et al. 2024).

Chapter 4 attaches executable mechanisms and the linear matrix \(B\) to the same skeletons. Chapter 5 turns path criteria into identification strategies.

4.8 Further Reading

• Pearl (2009): Causality: Graph theory and d-separation
• Spirtes et al. (2000): Causation, Prediction, and Search: Graph-theoretic causal discovery
• Cinelli et al. (2024): Crash course in good and bad controls (forks, colliders, M-bias)
• Chernozhukov et al. (2024): Applied Causal Inference Powered by ML and AI, Chapters 6–7 and 11 (SEMs to DAGs, d-separation and backdoor, good and bad controls)
• Structural Causal Models as Executable Mechanisms: Linear \(B\), adjacency conventions, and simulation
• Identification: When Can We Learn from Data?

Chernozhukov, Victor, Christian Hansen, Nathan Kallus, Martin Spindler, and Vasilis Syrgkanis. 2024. Applied Causal Inference Powered by ML and AI. https://doi.org/10.48550/arXiv.2403.02467.

Cinelli, Carlos, Andrew Forney, and Judea Pearl. 2024. “A Crash Course in Good and Bad Controls.” Sociological Methods & Research 53 (3): 1071–104. https://doi.org/10.1177/00491241221099552.

Pearl, Judea. 2009. Causality: Models, Reasoning, and Inference. 2nd ed. Cambridge University Press.

Peters, Jonas, Dominik Janzing, and Bernhard Schölkopf. 2017. Elements of Causal Inference: Foundations and Learning Algorithms. MIT Press.

Spirtes, Peter, Clark Glymour, and Richard Scheines. 2000. Causation, Prediction, and Search. 2nd ed. MIT Press.