Day 46: Graph Basics & Directed Acyclic Graphs

Theory

Why graphs?

Phase 3 asked whether treatment is as good as random given $X$ (unconfoundedness). It never said which $X$ . Causal graphs answer that question by drawing the assumptions about how variables cause each other, then reading off which comparisons are valid. Phase 4 builds that machinery.

Directed graphs

A directed graph $G = (V, E)$ has a set of nodes $V$ (variables) and a set of directed edges $E$ , written $A \to B$ .

If $A \to B$ , then $A$ is a parent of $B$ and $B$ is a child of $A$ . We write $\operatorname{pa}(B)$ for the parents of $B$ .
A path is a sequence of distinct nodes, each adjacent to the next, ignoring arrow directions: $A \to B \leftarrow C$ is a path from $A$ to $C$ .
A directed (causal) path follows the arrows: $A \to B \to C$ .
$A$ is an ancestor of $B$ if there is a directed path from $A$ to $B$ ; then $B$ is a descendant of $A$ . By convention every node is its own ancestor and descendant.
A cycle is a directed path from a node back to itself: $A \to B \to C \to A$ .

DAGs

A directed acyclic graph (DAG) has no directed cycles. Equivalent characterisation:

G \text{ is acyclic} \iff \text{its nodes can be ordered } V_1, \dots, V_p \text{ so that every edge points forward } (V_i \to V_j \Rightarrow i < j).

Such an ordering is a topological order. In a causal DAG it is a possible time order: causes before effects.

Causal DAGs

In a causal DAG, an arrow $A \to B$ means " $A$ is a direct cause of $B$ relative to the variables in the graph". Two rules:

Missing arrows are the strong assumptions. Omitting $A \to B$ claims that $A$ has no direct effect on $B$ . Drawing an arrow only allows an effect; it may be zero.
Common causes must be included. If any variable (observed or not) causes two variables in the graph, it must appear, perhaps as an unobserved node $U$ .

Example (returns to schooling): ability $A$ affects schooling $S$ and wages $W$ ; family background $F$ affects $A$ and $S$ ; schooling affects wages directly and through occupation $O$ :

F \to A, \quad F \to S, \quad A \to S, \quad A \to W, \quad S \to O, \quad S \to W, \quad O \to W.

The adjacency matrix

Number the nodes $1, \dots, p$ . The adjacency matrix $A$ has $A_{ij} = 1$ if $i \to j$ , else 0. Then

(A^k)_{ij} = \text{number of directed paths (walks) of length } k \text{ from } i \text{ to } j.

A graph is acyclic exactly when $A$ is nilpotent: $A^p = 0$ . In a topological order, $A$ is strictly upper triangular.

Time and feedback

Real systems have feedback (health ↔ income). A DAG handles it by indexing time: $\text{Health}_{t} \to \text{Income}_{t+1} \to \text{Health}_{t+2}$ is acyclic even though the two variables affect each other.

Part 1 · Warm-up

Use this graph for Exercises 1–3: $A \to B$ , $A \to C$ , $B \to C$ , $B \to D$ , $C \to D$ , $E \to D$ .

Exercise 1 · Parents and children

List the parents and children of each node.

Show solution

Step 1. Read each arrow $X \to Y$ as "X is a parent of Y".

Step 2. Parents: $\operatorname{pa}(A) = \varnothing$ , $\operatorname{pa}(B) = \{A\}$ , $\operatorname{pa}(C) = \{A, B\}$ , $\operatorname{pa}(D) = \{B, C, E\}$ , $\operatorname{pa}(E) = \varnothing$ .

Step 3. Children: $\operatorname{ch}(A) = \{B, C\}$ , $\operatorname{ch}(B) = \{C, D\}$ , $\operatorname{ch}(C) = \{D\}$ , $\operatorname{ch}(D) = \varnothing$ , $\operatorname{ch}(E) = \{D\}$ .

Exercise 2 · Ancestors and descendants

Find the ancestors of $D$ and the descendants of $B$ .

Show solution

Step 1. Ancestors of $D$ : its parents $B, C, E$ , their parents $A$ (of $B$ and $C$ ), and $D$ itself.

Step 2. So $\operatorname{an}(D) = \{A, B, C, D, E\}$ .

Step 3. Descendants of $B$ : $B \to C$ , $B \to D$ , $C \to D$ .

Answer: $\operatorname{an}(D) = \{A, B, C, D, E\}$ and $\operatorname{de}(B) = \{B, C, D\}$ .

Exercise 3 · A topological order

Give two different topological orders.

Show solution

Step 1. Sources (no parents): $A$ and $E$ . Either can go first.

Step 2. After $A$ : $B$ (its only parent is placed), then $C$ (parents $A, B$ placed).

Step 3. $D$ needs $B, C, E$ placed, so it is last.

Answer: $A, B, C, E, D$ and $E, A, B, C, D$ (also $A, E, B, C, D$ , and others).

Exercise 4 · Counting paths with matrices

For $A \to B$ , $A \to C$ , $B \to C$ , $B \to D$ , $C \to D$ (order $A, B, C, D$ ), compute $A^2$ and $A^3$ and count the directed paths from $A$ to $D$ .

Show solution

Step 1. The adjacency matrix is

\mathbf A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix}.

Step 2. Row $A$ of $\mathbf A^2$ : $(\mathbf A^2)_{AD} = \sum_k \mathbf A_{Ak}\mathbf A_{kD} = \mathbf A_{AB}\mathbf A_{BD} + \mathbf A_{AC}\mathbf A_{CD} = 1 + 1 = 2$ (paths $A \to B \to D$ and $A \to C \to D$ ).

Step 3. Also $(\mathbf A^2)_{AC} = \mathbf A_{AB}\mathbf A_{BC} = 1$ and $(\mathbf A^2)_{BD} = \mathbf A_{BC}\mathbf A_{CD} = 1$ ; every other entry is 0.

Step 4. $(\mathbf A^3)_{AD} = \sum_k (\mathbf A^2)_{Ak}\mathbf A_{kD} = (\mathbf A^2)_{AC}\mathbf A_{CD} = 1$ (path $A \to B \to C \to D$ ). All other entries of $\mathbf A^3$ are 0, and $\mathbf A^4 = 0$ .

Answer: $2 + 1 = 3$ directed paths from $A$ to $D$ .

Exercise 5 · Spot the cycle

Is the graph $X \to Y$ , $Y \to Z$ , $Z \to W$ , $W \to Y$ a DAG? If not, give the cycle and fix it by adding time indices.

Show solution

Step 1. Follow the arrows from $Y$ : $Y \to Z \to W \to Y$ . That is a directed cycle.

Step 2. So the graph is not a DAG and has no topological order.

Step 3. With time indices the loop unrolls: $Y_t \to Z_t \to W_t \to Y_{t+1} \to Z_{t+1} \to \dots$ , with $X \to Y_t$ at each period.

Answer: not a DAG; the time-indexed graph is.

Part 2 · Proofs

Exercise 6 · Every DAG has a source

Prove that every finite DAG has at least one node with no parents.

Show solution

Step 1. Suppose not: every node has a parent.

Step 2. Start at any node $V_0$ and move to a parent $V_1$ , then to a parent of $V_1$ , and so on. This walk never stops, since every node has a parent.

Step 3. With $p$ nodes, after $p$ steps some node must repeat: $V_i = V_j$ with $i < j$ .

Step 4. Reversed, the walk $V_j \to V_{j-1} \to \dots \to V_i$ is a directed path from $V_i$ back to itself: a cycle.

Step 5. That contradicts acyclicity, so a node with no parents exists. $\blacksquare$

Exercise 7 · DAGs have topological orders

Prove by induction on the number of nodes that every DAG has a topological order.

Show solution

Step 1. Base case: one node, no edges; the single node is an order.

Step 2. Induction step: let $G$ have $p$ nodes. By Exercise 6 it has a source $S$ .

Step 3. Delete $S$ and its edges. The remaining graph has $p - 1$ nodes and is still acyclic (deleting edges cannot create cycles).

Step 4. By the induction hypothesis it has a topological order $V_1, \dots, V_{p-1}$ .

Step 5. Put $S$ first: $S, V_1, \dots, V_{p-1}$ . Edges out of $S$ point forward because $S$ is first; no edge points into $S$ ; all other edges point forward by the hypothesis. $\blacksquare$

Exercise 8 · Orders imply acyclicity

Prove the converse: if a topological order exists, the graph has no directed cycle.

Show solution

Step 1. Let $\pi(V)$ be the position of $V$ in the order. Every edge $V \to W$ has $\pi(V) < \pi(W)$ .

Step 2. Along a directed path $V_0 \to V_1 \to \dots \to V_k$ , positions strictly increase: $\pi(V_0) < \pi(V_1) < \dots < \pi(V_k)$ .

Step 3. A cycle would need $V_k = V_0$ , so $\pi(V_0) < \pi(V_0)$ : impossible. $\blacksquare$

Exercise 9 · Matrix powers count paths

Prove by induction that $(\mathbf A^k)_{ij}$ equals the number of directed walks of length $k$ from $i$ to $j$ .

Show solution

Step 1. Base case $k = 1$ : $\mathbf A_{ij} = 1$ exactly when the one-edge walk $i \to j$ exists.

Step 2. Assume the claim for $k$ . A walk of length $k + 1$ from $i$ to $j$ is a walk of length $k$ from $i$ to some node $m$ , followed by the edge $m \to j$ .

Step 3. Summing over the last intermediate node $m$ :

\#\{\text{walks of length } k + 1\} = \sum_m (\mathbf A^k)_{im}\,\mathbf A_{mj} = (\mathbf A^{k+1})_{ij}.

Step 4. In a DAG every walk is a path (a repeated node would create a cycle), so the entries count directed paths. $\blacksquare$

Exercise 10 · Acyclic means nilpotent

Prove that a graph with $p$ nodes is acyclic if and only if $\mathbf A^p = 0$ .

Show solution

Step 1. (⇒) In a DAG a directed path visits distinct nodes, so it has at most $p - 1$ edges.

Step 2. Hence there are no walks of length $p$ , and by Exercise 9 every entry of $\mathbf A^p$ is 0.

Step 3. (⇐) If there is a cycle through node $i$ of length $c \le p$ , then going around it repeatedly gives walks from $i$ to $i$ of every length that is a multiple of $c$ .

Step 4. Going around and then stopping partway gives walks of length exactly $p$ from $i$ to some node, so $\mathbf A^p \ne 0$ . $\blacksquare$

Part 3 · Applied

Exercise 11 · Returns to schooling

Use the schooling DAG from the theory: $F \to A$ , $F \to S$ , $A \to S$ , $A \to W$ , $S \to O$ , $S \to W$ , $O \to W$ (family background, ability, schooling, occupation, wage). (a) List all directed paths from $S$ to $W$ . (b) List all other paths from $S$ to $W$ . (c) Which variables are descendants of schooling?

Show solution

Step 1. (a) Directed paths: $S \to W$ and $S \to O \to W$ . These carry the causal effect of schooling.

Step 2. (b) Paths that start with an arrow into $S$ : $S \leftarrow A \to W$ and $S \leftarrow F \to A \to W$ .

Step 3. Both run through ability, a common cause of schooling and wages; they generate correlation that is not causal (Day 52 calls them back-door paths).

Step 4. (c) Descendants of $S$ : $S$ , $O$ , $W$ .

Answer: occupation is a descendant (a mediator), so controlling for it would remove part of the effect of schooling (Day 53).

Exercise 12 · Assumptions hidden in missing arrows

A cardiology team draws: age $\to$ obesity, age $\to$ heart disease, obesity $\to$ diabetes, diabetes $\to$ heart disease, smoking $\to$ heart disease. List three missing arrows and the substantive claim each makes. Which is the least plausible?

Show solution

Step 1. No arrow obesity $\to$ heart disease: obesity affects heart disease only through diabetes.

Step 2. No arrow age $\to$ diabetes: age affects diabetes only through obesity.

Step 3. No arrow between age and smoking, and no common cause of them: smoking is unrelated to age (and to income, education...).

Step 4. The obesity claim is the least plausible: obesity raises blood pressure and cholesterol, which affect heart disease without diabetes.

Answer: every missing arrow is a testable or debatable claim; arguing about the graph means arguing about these claims.

Exercise 13 · Insurance and health spending

An analyst writes: health insurance $\to$ health spending $\to$ health $\to$ insurance (sicker people buy coverage). Explain the problem and redraw the graph for annual panel data.

Show solution

Step 1. Insurance $\to$ spending $\to$ health $\to$ insurance is a directed cycle, so it is not a DAG and the causal question "effect of insurance" is ill-posed in this graph.

Step 2. In reality the arrows act at different times: this year's health affects next year's insurance choice.

Step 3. Time-indexed DAG:

\text{Health}_{t-1} \to \text{Ins}_t \to \text{Spend}_t \to \text{Health}_t \to \text{Ins}_{t+1}, \quad \text{Health}_{t-1} \to \text{Health}_t.

Answer: the unrolled graph is acyclic, and it shows that $\text{Health}_{t-1}$ is a common cause of insurance and later health, which must be accounted for.

Exercise 14 · Paths from the minimum wage to poverty

A labour economist draws: minimum wage $W$ $\to$ employment $E$ , $W \to$ hours $H$ , $W \to$ earnings $R$ , $E \to R$ , $H \to R$ , $R \to$ poverty $P$ , $E \to P$ . Count the directed paths from $W$ to $P$ by length using the adjacency matrix, and list them.

Show solution

Step 1. Order the nodes $W, E, H, R, P$ . Arrows out of each: $W: E, H, R$ ; $E: R, P$ ; $H: R$ ; $R: P$ .

Step 2. Length 2: $(\mathbf A^2)_{WP} = \sum_k \mathbf A_{Wk}\mathbf A_{kP} = \mathbf A_{WE}\mathbf A_{EP} + \mathbf A_{WR}\mathbf A_{RP} = 2$ : paths $W \to E \to P$ and $W \to R \to P$ .

Step 3. Length 3: $(\mathbf A^2)_{WR} = \mathbf A_{WE}\mathbf A_{ER} + \mathbf A_{WH}\mathbf A_{HR} = 2$ , so $(\mathbf A^3)_{WP} = (\mathbf A^2)_{WR}\,\mathbf A_{RP} = 2$ : paths $W \to E \to R \to P$ and $W \to H \to R \to P$ .

Step 4. Length 4: $(\mathbf A^4)_{WP} = 0$ , since no path from $W$ has four edges.

Answer: 4 causal channels. The total effect of the minimum wage on poverty adds them up; a positive hourly wage effect can be offset by negative employment and hours effects.

Exercise 15 · Pre-treatment variables

In a job-training evaluation the DAG is: age $\to$ training $T$ , age $\to$ earnings $Y$ , prior earnings $P \to T$ , $P \to Y$ , $T \to$ certificate $C \to Y$ , $T \to Y$ , $T \to$ job-search effort $J$ , $Y \to$ savings $S$ . Which variables are descendants of $T$ , and which are not?

Show solution

Step 1. Follow arrows out of $T$ : $T \to C$ , $T \to J$ , $T \to Y$ , and then $C \to Y$ , $Y \to S$ .

Step 2. Descendants: $\{T, C, J, Y, S\}$ .

Step 3. Non-descendants: age and $P$ .

Answer: age and prior earnings are pre-treatment variables, the natural candidates for adjustment. Certificate, job-search effort and savings are affected by training; Day 53 shows why adjusting for them is a mistake.

Verify in Python

import numpy as np
import networkx as nx

G = nx.DiGraph([("A", "B"), ("A", "C"), ("B", "C"), ("B", "D"), ("C", "D"), ("E", "D")])
print("acyclic:", nx.is_directed_acyclic_graph(G))
print("parents of D:", sorted(G.predecessors("D")), " ancestors of D:", sorted(nx.ancestors(G, "D")))
print("descendants of B:", sorted(nx.descendants(G, "B")))
print("all topological orders:", ["".join(o) for o in nx.all_topological_sorts(G)])

# Exercise 4: counting paths with matrix powers
H = nx.DiGraph([("A", "B"), ("A", "C"), ("B", "C"), ("B", "D"), ("C", "D")])
nodes = ["A", "B", "C", "D"]
M = nx.to_numpy_array(H, nodelist=nodes, dtype=int)
for k in (1, 2, 3, 4):
    print(f"A^{k}[A,D] =", np.linalg.matrix_power(M, k)[0, 3])

# Exercise 14: minimum wage -> poverty
W = nx.DiGraph([("W", "E"), ("W", "H"), ("W", "R"), ("E", "R"), ("H", "R"), ("R", "P"), ("E", "P")])
print([" -> ".join(p) for p in nx.all_simple_paths(W, "W", "P")])
M = nx.to_numpy_array(W, nodelist=list("WEHRP"), dtype=int)
print("paths by length:", [np.linalg.matrix_power(M, k)[0, 4] for k in (1, 2, 3, 4)])
print("nilpotent (A^5 = 0):", not np.linalg.matrix_power(M, 5).any())

# Exercise 5: a cycle
C = nx.DiGraph([("X", "Y"), ("Y", "Z"), ("Z", "W"), ("W", "Y")])
print("cycle:", nx.find_cycle(C))

Key takeaways

A causal DAG is a set of claims: each arrow allows a direct effect, each missing arrow rules one out, and every common cause must be drawn.
Acyclic ⇔ topological order exists ⇔ the adjacency matrix is nilpotent. Feedback is handled by indexing time.
Directed paths carry causal effects; other paths (through common causes) carry non-causal association. The next days make this precise.

Day 46. Graph Basics & Directed Acyclic Graphs

Theory

Why graphs?

Directed graphs

DAGs

Causal DAGs

The adjacency matrix

Time and feedback

Part 1 · Warm-up

Exercise 1 · Parents and children

Exercise 2 · Ancestors and descendants

Exercise 3 · A topological order

Exercise 4 · Counting paths with matrices

Exercise 5 · Spot the cycle

Part 2 · Proofs

Exercise 6 · Every DAG has a source

Exercise 7 · DAGs have topological orders

Exercise 8 · Orders imply acyclicity

Exercise 9 · Matrix powers count paths

Exercise 10 · Acyclic means nilpotent

Part 3 · Applied

Exercise 11 · Returns to schooling

Exercise 12 · Assumptions hidden in missing arrows

Exercise 13 · Insurance and health spending

Exercise 14 · Paths from the minimum wage to poverty

Exercise 15 · Pre-treatment variables

Verify in Python

Key takeaways

Simulation Lab: Build a Causal DAG