Part V · Signals, senses, structure | directed acyclic graphs, d-separation and the Markov property, Markov equivalence, faithfulness, the PC algorithm, BIC scores and greedy equivalence search, NOTEARS and varsortability, interventions and identifiability, the Sachs protein-signalling data | reading: Spirtes, Glymour & Scheines (2000); Kalisch & Bühlmann (2007); Chickering (2002); Zheng et al. (2018); Reisach, Seiler & Weichwald (2021); Uhler et al. (2013) | undirected graphs are in Lecture 20a
Lecture 20a learned undirected graphs: which variables are related once the others are known. This lecture asks for arrows. A causal graph says which variables affect which, so that changing one changes those downstream and nothing upstream. Learning such a graph from data is causal discovery. It is possible, up to a limit that the lecture makes precise, because different causal structures leave different patterns of conditional independence.
By the end you should be able to read conditional independences off a DAG with d-separation; say which DAGs cannot be told apart from observational data; run and explain the PC algorithm; explain score-based search with BIC; prove the NOTEARS acyclicity characterisation and explain why rescaling variables breaks it; and say what interventions add.
A directed acyclic graph (DAG) has arrows between nodes and no directed cycles. In a structural equation model on a DAG, each variable is a function of its parents and its own independent noise:
$$X_j=f_j\big(X_{\mathrm{pa}(j)},\,\varepsilon_j\big),\qquad \varepsilon_1,\dots,\varepsilon_p\ \text{independent}.$$In the linear Gaussian case, \(X_j=\sum_{i\in\mathrm{pa}(j)}w_{ij}X_i+\varepsilon_j\) with Gaussian noise. The joint density then factorises as
$$p(x)=\prod_{j=1}^pp\big(x_j\mid x_{\mathrm{pa}(j)}\big).$$Which independences does such a model imply? Along any path between two variables, information can flow or be stopped, depending on what we condition on. There are three kinds of junction:
The collider is the surprising one. Talent and luck may be independent in the population, but among people who became famous (a common effect), the talented ones needed less luck: conditioning on the effect creates a dependence.
A path between \(X\) and \(Y\) is blocked by a set \(Z\) if it contains
\(X\) and \(Y\) are d-separated by \(Z\), written \(X\perp_G Y\mid Z\), if every path between them is blocked.
If the distribution of \(X\) factorises according to a DAG \(G\) as in Definition 20.5, then for all disjoint sets of variables,
$$X\perp_G Y\mid Z\quad\Longrightarrow\quad X\perp Y\mid Z.$$(Statement; see Lauritzen, 1996, or Koller and Friedman, 2009, ch. 3.)
The converse fails in special cases: parameters can conspire so that an independence holds that the graph does not imply. Causal discovery rules this out by assumption.
A distribution is faithful to \(G\) if it has no conditional independences other than those implied by d-separation:
$$X\perp Y\mid Z\quad\Longrightarrow\quad X\perp_G Y\mid Z.$$# DAGs and d-separation: a five-variable example, checked against simulated data import numpy as np, pandas as pd, itertools, warnings; warnings.filterwarnings('ignore') rng = np.random.default_rng(0) V = ['A', 'B', 'C', 'D', 'E']; d5 = 5 G = np.zeros((d5, d5), int) # G[i, j] = 1 means an arrow i -> j for a, b in [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D'), ('D', 'E')]: G[V.index(a), V.index(b)] = 1 def descendants(G, i): out, todo = set(), [i] while todo: for j in np.flatnonzero(G[todo.pop()]): if j not in out: out.add(j); todo.append(j) return out def d_separated(G, x, y, Z): """True if every path between x and y is blocked by the set Z (Definition 20.6).""" U = G + G.T; Z = set(Z) def paths(path): if path[-1] == y: yield path; return for k in np.flatnonzero(U[path[-1]]): if k not in path: yield from paths(path + [k]) for path in paths([x]): blocked = False for a, m, b in zip(path, path[1:], path[2:]): collider = G[a, m] and G[b, m] if collider and not ({m} | descendants(G, m)) & Z: blocked = True # closed collider if not collider and m in Z: blocked = True # chain or fork with conditioned middle if not blocked: return False return True def simulate_sem(G, n, w, rng, scale=None): """Linear Gaussian structural equation model X_j = sum_i w_ij X_i + noise, in a causal order of G.""" d = len(G); X = np.zeros((n, d)); done = [] while len(done) < d: for j in range(d): if j not in done and all(i in done for i in np.flatnonzero(G[:, j])): X[:, j] = X @ (w[:, j] * G[:, j]) + rng.standard_normal(n); done.append(j) return X if scale is None else X * scale def partial_corr(X, i, j, Z): if not Z: return np.corrcoef(X[:, i], X[:, j])[0, 1] Zm = np.column_stack([X[:, list(Z)], np.ones(len(X))]); r = lambda v: v - Zm @ np.linalg.lstsq(Zm, v, rcond=None)[0] return np.corrcoef(r(X[:, i]), r(X[:, j]))[0, 1] W5 = np.where(G, 0.8, 0.0); X5 = simulate_sem(G, 5000, W5, rng) print("query d-separated? sample partial correlation (n = 5,000)") for x, y, Z in [('B', 'C', []), ('B', 'C', ['A']), ('B', 'C', ['A', 'D']), ('B', 'C', ['A', 'E']), ('A', 'E', ['D']), ('A', 'D', [])]: i, j, zi = V.index(x), V.index(y), [V.index(z) for z in Z] print(f"{x} and {y} given {{{', '.join(Z)}}}".ljust(27) + f"{str(d_separated(G, i, j, zi)):14s} {partial_corr(X5, i, j, zi):+.3f}") # Markov equivalence: all DAGs with the same skeleton and the same v-structures def vstructs(G): return {(min(a, b), m, max(a, b)) for m in range(len(G)) for a, b in itertools.combinations(np.flatnonzero(G[:, m]), 2) if not (G[a, b] or G[b, a])} def is_acyclic(G): G = G.copy(); left = list(range(len(G))) while left: src = [j for j in left if not G[left][:, j].any()] if not src: return False left = [j for j in left if j not in src] return True skel = [(i, j) for i in range(d5) for j in range(i + 1, d5) if G[i, j] or G[j, i]] mec = [] for bits in itertools.product([0, 1], repeat=len(skel)): H = np.zeros_like(G) for (i, j), b_ in zip(skel, bits): H[(i, j) if b_ else (j, i)] = 1 if is_acyclic(H) and vstructs(H) == vstructs(G): mec.append(H) print(f"\n{2 ** len(skel)} ways to orient the {len(skel)} edges; {len(mec)} of them are acyclic with the same v-structures as G (its Markov equivalence class)") fixed = [f"{V[i]}->{V[j]}" for i in range(d5) for j in range(d5) if all(H[i, j] for H in mec)] print("edges with the same direction in every member:", ", ".join(fixed))
query d-separated? sample partial correlation (n = 5,000)
B and C given {} False +0.392
B and C given {A} True +0.013
B and C given {A, D} False -0.385
B and C given {A, E} False -0.186
A and E given {D} True +0.011
A and D given {} False +0.637
32 ways to orient the 5 edges; 3 of them are acyclic with the same v-structures as G (its Markov equivalence class)
edges with the same direction in every member: B->D, C->D, D->E
Every verdict of d-separation matches the data. B and C are correlated (+0.392) through their common cause A; given A they are d-separated and the partial correlation drops to +0.013. Conditioning on D as well opens the collider B → D ← C, and the correlation returns with the opposite sign (-0.385). Conditioning on E, a descendant of the collider, opens it partly (-0.186). Of the 32 ways to orient the five edges, 3 imply exactly the same independences: the arrows B→D, C→D and D→E are shared by all of them, while the two edges at A can point either way, as long as they do not both point into A.
Two DAGs imply the same d-separations exactly when they have
The set of all DAGs equivalent to \(G\) is its Markov equivalence class. It is drawn as a partially directed graph (a CPDAG) whose arrows are shared by every member and whose undirected edges vary.
Two facts carry the proof. First, \(X\) and \(Y\) are adjacent if and only if no set d-separates them; so the d-separations determine the skeleton.
Second, for a triple \(X-M-Y\) with \(X\) and \(Y\) not adjacent, \(M\) is a collider if and only if \(M\) is in no set that d-separates \(X\) and \(Y\) (conditioning on a collider opens the path, conditioning on a chain or fork closes it). So the d-separations also determine the v-structures.
The converse is the harder direction. One shows that if some path between \(X\) and \(Y\) is open given \(Z\) in one graph, then some (possibly different) path is open in the other, using only the shared skeleton and v-structures; see Verma and Pearl (1990) or Andersson, Madigan and Perlman (1997). We omit the details. \(\square\)
Theorem 20.4 is the fundamental limit of causal discovery from observational data. The chain \(X\to M\to Y\), the reverse chain and the fork all have the same skeleton and no v-structure, so no amount of observational data can tell them apart. The collider is different, which is why v-structures are the anchor of every discovery algorithm.
Which DAG is not Markov equivalent to \(X\to M\to Y\)?
Theorem 20.4 suggests a recipe: find the skeleton from independences, find the v-structures from the separating sets, then orient whatever else is forced. The PC algorithm (named after Peter Spirtes and Clark Glymour, 1991) does exactly this.
With Gaussian data, each test asks whether a partial correlation is zero, using Fisher's \(z\)-transform. Searching small conditioning sets first, and only among current neighbours, keeps the number of tests manageable for sparse graphs.
Suppose the distribution is Markov and faithful to a DAG \(G\), and every conditional-independence test answers correctly. Then the PC algorithm returns the CPDAG of \(G\): the correct skeleton, every arrow common to the Markov equivalence class, and nothing else.
Skeleton. If \(i\) and \(j\) are adjacent in \(G\), no set d-separates them, so by faithfulness no test accepts independence and the edge is never removed. If they are not adjacent, one of them (say \(i\)) is not a descendant of the other, and then \(\mathrm{pa}(j)\) d-separates them. Because true edges are never removed, \(\mathrm{pa}(j)\) is always contained in the current neighbours of \(j\), so the search eventually tests it and removes the edge.
V-structures. Take \(i-m-j\) with \(i\), \(j\) not adjacent and separating set \(S_{ij}\). If \(m\) were a collider and \(m\in S_{ij}\), the path \(i\to m\leftarrow j\) would be open given \(S_{ij}\). If \(m\) were a chain or fork node and \(m\notin S_{ij}\), the path through \(m\) would be open. Either way \(S_{ij}\) would not separate \(i\) and \(j\). So \(m\) is a collider exactly when \(m\notin S_{ij}\).
Propagation. Meek (1995) showed that his rules orient exactly the edges that have the same direction in every DAG of the class. \(\square\)
Karen Sachs and colleagues measured 11 phosphorylated proteins and phospholipids of the signalling network in thousands of individual human immune cells (naive CD4+ T cells) by multiparameter flow cytometry (Science 308, 523–529, 2005). Besides a general stimulation (antibodies to CD3 and CD28), they added drugs that activate or inhibit particular proteins: interventions. Their consensus network of known interactions is the usual benchmark for causal discovery. We use the combined file of 7,466 cells and the 20-edge ground truth from the GitHub repository cmu-phil/example-causal-datasets (the same data ship with the Causal Discovery Toolbox, cdt). The first 853 cells are the general-stimulation condition, the subset usually treated as observational; we analyse their logarithms.
# The PC algorithm with Fisher-z tests of partial correlation; then the Sachs protein data from scipy.stats import norm def fisher_z_indep(X, i, j, Z, alpha): r = np.clip(partial_corr(X, i, j, Z), -0.9999, 0.9999); stat = np.sqrt(len(X) - len(Z) - 3) * abs(np.arctanh(r)) return 2 * norm.sf(stat) > alpha # True means "independent": the test does not reject def pc_algorithm(X, alpha=0.01, trace=None): d = X.shape[1]; A = 1 - np.eye(d, dtype=int); sep = {} for size in range(d - 1): # step 1: remove edges, conditioning sets of growing size for i, j in [(i, j) for i in range(d) for j in range(d) if i < j]: if not A[i, j]: continue for cand in (np.flatnonzero(A[i]), np.flatnonzero(A[j])): for Z in itertools.combinations([k for k in cand if k not in (i, j)], size): if A[i, j] and fisher_z_indep(X, i, j, list(Z), alpha): A[i, j] = A[j, i] = 0; sep[(i, j)] = sep[(j, i)] = set(Z) if trace is not None: trace.append(('remove', i, j, list(Z))) P = A.copy() # P[i, j] = 1 and P[j, i] = 1: undirected; only P[i, j]: i -> j for m in range(d): # step 2: v-structures i -> m <- j for i, j in itertools.combinations(np.flatnonzero(A[m]), 2): if not A[i, j] and m not in sep.get((i, j), set()): P[m, i] = P[m, j] = 0 if trace is not None: trace.append(('collider', i, m, j)) changed = True # step 3: Meek's rule 1 (orient i - j away from an arrow k -> i) while changed: changed = False for k, i, j in itertools.permutations(range(d), 3): if P[k, i] and not P[i, k] and P[i, j] and P[j, i] and not (A[k, j]): P[j, i] = 0; changed = True if trace is not None: trace.append(('meek', k, i, j)) return P def show(P, names): s = [f"{names[i]}-{names[j]}" for i in range(len(P)) for j in range(i + 1, len(P)) if P[i, j] and P[j, i]] s += [f"{names[i]}->{names[j]}" for i in range(len(P)) for j in range(len(P)) if P[i, j] and not P[j, i]] return ", ".join(s) pc_trace = []; P5 = pc_algorithm(X5[:2000], 0.01, pc_trace) print(f"PC on 2,000 samples from the five-variable DAG: {show(P5, V)}") print(f" ({sum(t[0] == 'remove' for t in pc_trace)} edges removed by independence tests, " f"{sum(t[0] == 'collider' for t in pc_trace)} v-structure found, {sum(t[0] == 'meek' for t in pc_trace)} edge oriented by Meek's rule)") # faithfulness fails: a direct effect cancels an indirect one n_ = 5000; x = rng.standard_normal(n_); z = 0.8 * x + rng.standard_normal(n_); y = 0.5 * x - 0.625 * z + rng.standard_normal(n_) print(f"\nX -> Y with weight 0.5 and X -> Z -> Y with 0.8 x (-0.625) = -0.5: corr(X, Y) = {np.corrcoef(x, y)[0, 1]:+.3f}; " f"PC finds {show(pc_algorithm(np.column_stack([x, y, z]), 0.01), ['X', 'Y', 'Z'])}") # how often is a random triangle X -> Y, X -> Z -> Y nearly unfaithful? (exact population correlation of X and Y) a_, b_, c_ = rng.uniform(-1, 1, (3, 100000)); covxy = a_ + b_ * c_; vary = (a_ + b_ * c_) ** 2 + c_ ** 2 + 1; rxy = covxy / np.sqrt(vary) print(f"random weights in [-1, 1]: corr(X, Y) exactly 0 with probability 0; |corr(X, Y)| < 0.05 in {np.mean(np.abs(rxy) < 0.05):.1%} " f"and < 0.1 in {np.mean(np.abs(rxy) < 0.1):.1%} of 100,000 draws") # Sachs et al. (2005): 11 phosphorylated proteins and lipids in single human T cells, general stimulation (853 cells) sachs = pd.read_csv('data/sachs_cmu.txt', sep='\t').iloc[:853]; prot = list(sachs.columns) Xs = np.log(sachs.values); Xs = (Xs - Xs.mean(0)) / Xs.std(0) truth = np.zeros((11, 11), int) for line in open('data/sachs_truth.txt'): if '-->' in line: a, b = line.split('. ')[1].strip().split(' --> '); truth[prot.index(a), prot.index(b)] = 1 def score(P, T): sk = (P | P.T) > 0; skt = (T | T.T) > 0; iu_ = np.triu_indices(len(T), 1) tp = int((sk & skt)[iu_].sum()); right = int(sum(P[i, j] and not P[j, i] for i, j in zip(*np.nonzero(T)))) rev = int(sum(P[j, i] and not P[i, j] for i, j in zip(*np.nonzero(T)))) shd = int((sk ^ skt)[iu_].sum()) + int(sum(1 for i, j in zip(*np.nonzero(T)) if sk[i, j] and not (P[i, j] and not P[j, i]))) return f"{int(sk[iu_].sum())} edges, {tp} of the {int(skt[iu_].sum())} consensus edges found, {right} with the right direction, {rev} reversed; SHD {shd}" P_sachs = pc_algorithm(Xs, 0.01) print(f"\nSachs data, {Xs.shape[0]} cells x {Xs.shape[1]} proteins (log scale). PC (alpha = 0.01): {score(P_sachs, truth)}") from causallearn.search.ConstraintBased.PC import pc as cl_pc cg = cl_pc(Xs, 0.01, 'fisherz', show_progress=False).G.graph # causal-learn's PC, as a check on our implementation P_cl = ((cg == -1) & (cg.T == 1)).astype(int) + ((cg == -1) & (cg.T == -1)).astype(int) print(f"causal-learn's PC on the same data: {score(P_cl, truth)}")
PC on 2,000 samples from the five-variable DAG: A-B, A-C, B->D, C->D, D->E (5 edges removed by independence tests, 1 v-structure found, 1 edge oriented by Meek's rule) X -> Y with weight 0.5 and X -> Z -> Y with 0.8 x (-0.625) = -0.5: corr(X, Y) = -0.004; PC finds X->Z, Y->Z random weights in [-1, 1]: corr(X, Y) exactly 0 with probability 0; |corr(X, Y)| < 0.05 in 5.9% and < 0.1 in 11.7% of 100,000 draws Sachs data, 853 cells x 11 proteins (log scale). PC (alpha = 0.01): 6 edges, 6 of the 20 consensus edges found, 0 with the right direction, 2 reversed; SHD 20 causal-learn's PC on the same data: 6 edges, 6 of the 20 consensus edges found, 0 with the right direction, 2 reversed; SHD 20
On the simulated data PC returns A–B, A–C, B→D, C→D, D→E: exactly the CPDAG, with the two edges at A left undirected because the data cannot orient them. It needed 5 removals, one v-structure and one application of Meek's rule. The cancelling triangle shows what faithfulness buys. With the direct and indirect effects of X on Y cancelling, corr(X, Y) = -0.004, so PC removes the edge X – Y, orients X → Z and Y → Z, a v-structure that does not exist, and gets both the skeleton and an orientation wrong. Exact cancellation needs an exact equation between the weights, but near-cancellation is common: with random weights, 5.9% of triangles have |corr(X, Y)| below 0.05, too small to detect reliably with a few hundred samples. On the Sachs data PC finds only 6 edges, all in the consensus network but none oriented correctly (2 reversed, the rest undirected). Our implementation and causal-learn's agree exactly.
Fix a DAG \(G\) and parametrise linear Gaussian models on \(G\) by their edge weights and noise variances. The set of parameters whose distribution is not faithful to \(G\) has Lebesgue measure zero. (Statement; Spirtes, Glymour and Scheines, 2000; Meek, 1995.)
Each extra independence forces a polynomial in the parameters to vanish, such as
$$a+bc=0$$for the cancelling triangle in the code. The zero set of a non-zero polynomial is a lower-dimensional surface in parameter space, which has volume zero.
The theorem is reassuring and also misleading. A finite sample cannot distinguish an exact zero from a small value, so what matters is the volume of a thickened surface, the parameters for which some partial correlation is too small to detect. That volume is not small: it is the share of random triangles found in the code, and Uhler, Raskutti, Bühlmann and Yu (2013) show that for larger graphs it grows quickly, so strong faithfulness, the assumption that finite-sample guarantees actually need, often fails.
The geneticist Sewall Wright drew the first causal path diagrams in 1920–21, to separate the effects of heredity and environment on the coat patterns of guinea pigs, and showed how to read correlations off the arrows ("Correlation and causation", 1921). Economists and sociologists used such structural equation models for decades, but the arrows were assumed, not learned. In the 1980s and 1990s Peter Spirtes, Clark Glymour and Richard Scheines at Carnegie Mellon built the theory of learning them from data, with the PC algorithm and the Tetrad software, collected in Causation, Prediction, and Search (1993; 2nd ed. 2000). Judea Pearl developed d-separation, Bayesian networks and the do-calculus of interventions, and received the 2011 Turing Award "for fundamental contributions to artificial intelligence through the development of a calculus for probabilistic and causal reasoning".
Instead of testing independences one at a time, a score-based method gives every graph a number for how well it explains the data, with a penalty for complexity, and searches for the best graph.
For \(n\) observations and a linear Gaussian model on \(G\), regress each variable on its parents and let \(\hat\sigma_j^2\) be the residual variance. Up to a constant, the BIC score is
$$\mathrm{BIC}(G)=\sum_{j=1}^p\Big[-\frac n2\log\hat\sigma_j^2\;-\;\frac{|\mathrm{pa}(j)|+2}{2}\log n\Big].$$The first term is the maximised log-likelihood; the second penalises each parameter (the weights, an intercept and a variance per node). Higher is better.
Two properties make BIC suitable. It decomposes into one term per node, so changing one edge changes only one term. And it is score-equivalent: Markov-equivalent DAGs get exactly the same score, because they represent the same set of distributions. A score can therefore choose an equivalence class, never a DAG within it, which is Theorem 20.4 again.
Greedy equivalence search (GES; Chickering, 2002) moves between equivalence classes rather than DAGs. In a forward phase it adds the single edge that most improves the score, until no addition helps; in a backward phase it removes edges while removal helps. Chickering proved that with BIC and enough data, under faithfulness, GES finds the true equivalence class, although the space of graphs grows super-exponentially with the number of variables.
# Score-based discovery: the BIC score of a linear Gaussian DAG, and greedy equivalence search (GES) def bic(X, G): """BIC of a linear Gaussian DAG: sum over nodes of the Gaussian log-likelihood of regressing it on its parents, minus a penalty.""" n, d = X.shape; total = 0.0 for j in range(d): pa = np.flatnonzero(G[:, j]); M = np.column_stack([X[:, pa], np.ones(n)]) res = X[:, j] - M @ np.linalg.lstsq(M, X[:, j], rcond=None)[0] total += -0.5 * n * np.log(res @ res / n) - 0.5 * (len(pa) + 2) * np.log(n) return total X2k = X5[:2000]; Gnull = np.zeros_like(G) G_rev = G.copy(); G_rev[V.index('D'), V.index('E')], G_rev[V.index('E'), V.index('D')] = 0, 1 # reverse D -> E: new v-structures print("BIC score (higher is better) on 2,000 samples:") for label, H in [('the true DAG', G)] + [(f'equivalent DAG {k + 1}', H) for k, H in enumerate(mec) if not (H == G).all()] + \ [('true DAG with D -> E reversed', G_rev), ('no edges', Gnull)]: print(f" {label:30s} {bic(X2k, H):10.1f}") from causallearn.search.ScoreBased.GES import ges def ges_cpdag(X): Gg = ges(X, score_func='local_score_BIC')['G'].graph # causal-learn: -1 at [i, j] and 1 at [j, i] means i -> j return ((Gg == -1) & (Gg.T == 1)).astype(int) + ((Gg == -1) & (Gg.T == -1)).astype(int) print(f"\nGES on 2,000 samples from the five-variable DAG: {show(ges_cpdag(X2k), V)}") P_ges = ges_cpdag(Xs) print(f"GES on the Sachs data: {score(P_ges, truth)}")
BIC score (higher is better) on 2,000 samples: the true DAG -9.7 equivalent DAG 1 -9.7 equivalent DAG 2 -9.7 true DAG with D -> E reversed -789.3 no edges -3538.7 GES on 2,000 samples from the five-variable DAG: A-B, A-C, B->D, C->D, D->E GES on the Sachs data: 7 edges, 7 of the 20 consensus edges found, 0 with the right direction, 0 reversed; SHD 20
The three equivalent DAGs score exactly the same (-9.7), which is score equivalence: BIC cannot prefer one member of the class. Reversing D → E creates two new v-structures, implies independences the data do not have, and costs 780 points; the empty graph is far worse. GES recovers the same CPDAG as PC on the simulated data. On the Sachs data it finds 7 edges, all in the consensus network, with no direction resolved: the observational data support little more than which proteins move together.
A DAG with its conditional distributions is a Bayesian network (Pearl, 1988), the name used when the arrows are read as a factorisation rather than as causes. In Bayesian structure learning the graph itself is uncertain: put a prior on graphs and on parameters, and compute the posterior probability of each graph, \(p(G\mid\text{data})\propto p(\text{data}\mid G)\,p(G)\). For discrete data with Dirichlet priors the marginal likelihood has a closed form, the BDeu score (Heckerman, Geiger and Chickering, 1995); BIC is its large-sample approximation (Lecture 17a used BIC to choose the number of mixture components). Sachs et al. themselves learned their network this way, averaging over many high-scoring graphs and reporting each edge's posterior confidence instead of a single graph. Markov chain Monte Carlo over graphs, or over orderings of the variables (Friedman and Koller, 2003), makes this feasible for a few dozen variables.
Searching over graphs is a combinatorial problem. Zheng, Aragam, Ravikumar and Xing (2018) turned it into a smooth one. Represent a linear SEM by its weight matrix \(W\), with \(W_{ij}\neq0\) meaning \(i\to j\), and fit it by least squares. The only hard part is the constraint that \(W\) has no directed cycles. NOTEARS ("non-combinatorial optimisation via trace exponential and augmented Lagrangian for structure learning") writes acyclicity as a single smooth equation.
For a real \(d\times d\) matrix \(W\), let \(W\circ W\) be its entrywise square and define
$$h(W)=\operatorname{tr}\big(e^{W\circ W}\big)-d .$$Then \(h(W)\ge0\), and \(h(W)=0\) exactly when the graph of \(W\) is acyclic. Its gradient is
$$\nabla h(W)=\big(e^{W\circ W}\big)^{\!\top}\circ2W .$$Let \(B=W\circ W\), a matrix with non-negative entries, positive exactly where \(W\) has an edge. The matrix exponential is the power series
$$e^B=\sum_{k\ge0}\frac{B^k}{k!},\qquad\text{so}\qquad h(W)=\sum_{k\ge1}\frac{\operatorname{tr}(B^k)}{k!}.$$The diagonal entry \((B^k)_{ii}\) is a sum, over all closed walks of length \(k\) from \(i\) back to \(i\), of the products of the edge weights along the walk. Every such product is positive, so \((B^k)_{ii}>0\) exactly when there is a closed walk of length \(k\) through \(i\), and is zero otherwise.
Hence every term of the series is non-negative, and \(h(W)=0\) exactly when there is no closed walk of any length, that is, no directed cycle.
For the gradient, \(\partial\operatorname{tr}(e^B)/\partial B=(e^B)^\top\), and the chain rule through \(B_{ij}=W_{ij}^2\) multiplies each entry by \(2W_{ij}\). \(\square\)
NOTEARS then minimises the least-squares loss plus an \(\ell_1\) penalty subject to \(h(W)=0\), with an augmented Lagrangian method: a sequence of smooth, unconstrained problems whose penalty on \(h\) grows until the constraint holds. Small weights are set to zero at the end. On simulated data it often recovers the graph almost exactly, which made it very popular.
Reisach, Seiler and Weichwald (2021) asked why it works so well. In the usual simulations, with unit noise and weights of size 0.5 to 2, each variable adds its own noise to everything it inherits, so variance tends to grow along the causal order. They called the share of cause–effect pairs in which the effect has the larger variance varsortability. A least-squares method can exploit it: explaining a high-variance variable by low-variance ones reduces the loss more than the reverse. If the data's units are changed, the ordering changes.
# NOTEARS: structure learning as continuous optimisation, and how rescaling the variables changes its answer from scipy.optimize import minimize from scipy.linalg import expm def notears(X, lam=0.05, w_thresh=0.3, max_iter=30, h_tol=1e-8, rho_max=1e16): """Linear NOTEARS (Zheng et al., 2018): least squares + lam * |W|_1 subject to h(W) = tr(exp(W*W)) - d = 0.""" n, d = X.shape; w = np.zeros(2 * d * d); rho, alpha, h = 1.0, 0.0, np.inf def unpack(w): return (w[:d * d] - w[d * d:]).reshape(d, d) def obj(w): W = unpack(w); R = X - X @ W; E = expm(W * W); hW = np.trace(E) - d f = 0.5 / n * (R ** 2).sum() + 0.5 * rho * hW ** 2 + alpha * hW + lam * w.sum() gW = -X.T @ R / n + (rho * hW + alpha) * E.T * W * 2 return f, np.concatenate([gW.ravel() + lam, -gW.ravel() + lam]) bnds = [(0, 0) if i == j else (0, None) for _ in range(2) for i in range(d) for j in range(d)] for _ in range(max_iter): while rho < rho_max: w_new = minimize(obj, w, jac=True, method='L-BFGS-B', bounds=bnds).x; Wn = unpack(w_new) h_new = np.trace(expm(Wn * Wn)) - d if h_new > 0.25 * h: rho *= 10 else: break w, h = w_new, h_new; alpha += rho * h if h <= h_tol or rho >= rho_max: break W = unpack(w); W[np.abs(W) < w_thresh] = 0; return W def shd_dag(W, T): """Structural Hamming distance between two DAGs: missing + extra + reversed edges.""" A = (W != 0).astype(int); m = 0 for i, j in itertools.combinations(range(len(T)), 2): if (A[i, j], A[j, i]) != (T[i, j], T[j, i]): m += 1 return m def varsortability(X, T): """Share of causal pairs (i before j along a directed path) where Var(X_i) < Var(X_j) (Reisach et al., 2021).""" v = X.var(0); R = np.linalg.matrix_power(np.eye(len(T)) + T, len(T)) > 0; np.fill_diagonal(R, False) pairs = np.argwhere(R); return np.mean([v[i] < v[j] for i, j in pairs]) def sortnregress(X): """Order the variables by variance, then regress each on the ones before it with the lasso.""" from sklearn.linear_model import LassoLarsIC order = np.argsort(X.var(0)); W = np.zeros((X.shape[1],) * 2) for k in range(1, len(order)): j, pa = order[k], order[:k]; W[pa, j] = LassoLarsIC(criterion='bic').fit(X[:, pa], X[:, j]).coef_ W[np.abs(W) < 0.3] = 0; return W def random_dag(d, prob, g): perm = g.permutation(d); T = np.zeros((d, d), int) for a in range(d): for b in range(a + 1, d): if g.random() < prob: T[perm[a], perm[b]] = 1 return T, T * g.uniform(0.5, 2.0, (d, d)) * g.choice([-1, 1], (d, d)) res = [] # ten random DAGs on 10 variables: weights of size 0.5-2, random signs, unit noise for seed in range(10): g10 = np.random.default_rng(100 + seed); T10, Wt = random_dag(10, 0.3, g10) X10 = simulate_sem(T10, 1000, Wt, g10); X10 -= X10.mean(0); Z10 = X10 / X10.std(0) res.append([T10.sum(), varsortability(X10, T10), shd_dag(notears(X10), T10), shd_dag(sortnregress(X10), T10), shd_dag(notears(Z10), T10), shd_dag(sortnregress(Z10), T10), (pc_algorithm(X10) == pc_algorithm(Z10)).all()]) res = np.array(res, float) print(f"10 random DAGs, 10 variables each ({res[:, 0].mean():.1f} edges on average), 1,000 samples; mean varsortability {res[:, 1].mean():.2f}") print(f"mean structural Hamming distance (0 = perfect): NOTEARS sort by variance and regress") print(f" raw data {res[:, 2].mean():5.1f} {res[:, 3].mean():5.1f}") print(f" each variable standardised to variance 1 {res[:, 4].mean():5.1f} {res[:, 5].mean():5.1f}") print(f"PC returns the same graph on raw and standardised data in {int(res[:, 6].sum())} of 10 cases (partial correlations ignore units)") W_sachs = notears(Xs) print(f"NOTEARS on the standardised Sachs data: {score((W_sachs != 0).astype(int), truth)}")
10 random DAGs, 10 variables each (14.4 edges on average), 1,000 samples; mean varsortability 0.95 mean structural Hamming distance (0 = perfect): NOTEARS sort by variance and regress raw data 0.7 2.5 each variable standardised to variance 1 13.6 17.0 PC returns the same graph on raw and standardised data in 10 of 10 cases (partial correlations ignore units) NOTEARS on the standardised Sachs data: 5 edges, 5 of the 20 consensus edges found, 3 with the right direction, 2 reversed; SHD 17
On raw simulated data NOTEARS is nearly perfect: a mean structural Hamming distance (missing, extra and reversed edges) of 0.7 for graphs with 14.4 edges on average. But varsortability is 0.95: in almost every cause–effect pair the effect has the larger variance. The trivial method that sorts variables by variance and regresses each on those before it scores 2.5, nearly as well, without any causal reasoning. Standardise each variable, which changes nothing causal, and NOTEARS' error jumps to 13.6 (the sorting method's to 17.0). PC gives the same answer on raw and standardised data in 10 of 10 cases. On the Sachs data, where we standardised, NOTEARS finds 5 edges, 3 correctly oriented and 2 reversed, the best of the three methods here but still far from the consensus network (SHD 17 against 20 for PC).
Observational data identify at most the Markov equivalence class. To go further, we have to change the system. Sachs et al. did so with drugs that switch particular proteins on or off; the rooster in the cartoon is tested by shutting it in.
A (hard) intervention \(\mathrm{do}(X_k=\xi)\) replaces the structural equation of \(X_k\) by an externally set value or distribution \(\xi\), leaving every other equation unchanged. In the graph, it deletes all arrows into \(X_k\). The joint distribution becomes
$$p\big(x\mid\mathrm{do}(X_k=\xi)\big)=\xi(x_k)\prod_{j\neq k}p\big(x_j\mid x_{\mathrm{pa}(j)}\big).$$The key property is invariance: under an intervention on \(X_k\), the mechanisms of all other variables stay the same. If \(X\to Y\), intervening on \(X\) leaves the conditional distribution of \(Y\) given \(X\) unchanged, while the conditional distribution of \(X\) given \(Y\) shifts. That asymmetry reveals the direction. An intervention on \(X_k\) orients every edge at \(X_k\); with a few well-chosen interventions the whole graph can be identified (Hauser and Bühlmann, 2012).
# Interventions: what observational data cannot tell apart, an experiment can n_ = 5000; x = rng.standard_normal(n_); y = 0.8 * x + 0.6 * rng.standard_normal(n_) # truth: X -> Y Gxy, Gyx = np.array([[0, 1], [0, 0]]), np.array([[0, 0], [1, 0]]) obs = np.column_stack([x, y]) print(f"observational data: BIC of X -> Y {bic(obs, Gxy):.2f}, of Y -> X {bic(obs, Gyx):.2f} (equivalent: no way to choose)") xi = rng.normal(2.0, 2.0, n_); yi = 0.8 * xi + 0.6 * rng.standard_normal(n_) # do(X): set X by experiment slope = lambda a, b: np.polyfit(a, b, 1)[0] print(f"regression of Y on X: observational {slope(x, y):.2f}, under do(X) {slope(xi, yi):.2f} (the same: Y's mechanism is untouched)") print(f"regression of X on Y: observational {slope(y, x):.2f}, under do(X) {slope(yi, xi):.2f} (changes: this is not a causal mechanism)") # which interventions resolve the Markov equivalence class of the five-variable DAG? print(f"\nthe five-variable DAG has {len(mec)} Markov-equivalent DAGs. After an intervention on one variable they split into groups that can be told apart:") for k in range(d5): sig = [tuple(H[k] - H[:, k]) for H in mec] # orientation of every edge at the intervened node c = len(set(sig)); print(f" intervene on {V[k]}: {c} group{'s' if c > 1 else ''}" + (" (the true DAG is identified)" if c == len(mec) else "")) # the Sachs data again, now pooling all nine experimental conditions (several of them interventions on single proteins) allc = pd.read_csv('data/sachs_cmu.txt', sep='\t'); Xall = np.log(allc.values); Xall = (Xall - Xall.mean(0)) / Xall.std(0) print(f"\nPC on all {len(Xall):,} cells of the nine conditions pooled: {score(pc_algorithm(Xall, 0.01), truth)}")
observational data: BIC of X -> Y 2603.36, of Y -> X 2603.36 (equivalent: no way to choose) regression of Y on X: observational 0.80, under do(X) 0.80 (the same: Y's mechanism is untouched) regression of X on Y: observational 0.80, under do(X) 1.09 (changes: this is not a causal mechanism) the five-variable DAG has 3 Markov-equivalent DAGs. After an intervention on one variable they split into groups that can be told apart: intervene on A: 3 groups (the true DAG is identified) intervene on B: 2 groups intervene on C: 2 groups intervene on D: 1 group intervene on E: 1 group PC on all 7,466 cells of the nine conditions pooled: 12 edges, 7 of the 20 consensus edges found, 3 with the right direction, 4 reversed; SHD 22
From observation alone, X → Y and Y → X have identical BIC (2603.36). The intervention breaks the tie. The slope of Y on X is 0.80 before and 0.80 after, because the mechanism that produces Y was not touched. The slope of X on Y moves from 0.80 to 1.09: it was never a mechanism, only a by-product of how X happened to vary. On the five-variable example, one intervention on A splits the 3 equivalent DAGs into 3 distinguishable groups, so it identifies the graph; one on B or C leaves two candidates; one on D or E tells us nothing new, because every edge at D and E was already oriented. Pooling all nine Sachs conditions, several of them interventions, PC finds 7 consensus edges (against 6) and orients 3 correctly, but it also adds 5 edges outside the consensus, so its SHD is worse (22 against 20). Pooling experiments as if they were observational data mixes different distributions; the gain from experiments comes from modelling them as interventions, as Sachs et al. did, and as methods such as GIES (Hauser and Bühlmann, 2012) and invariant causal prediction (Peters, Bühlmann and Meinshausen, 2016) do.
The true graph is \(X\to Y\). You intervene on \(Y\), setting it at random. What happens to the correlation between \(X\) and \(Y\)?
Bell's theorem can be read as a result about causal discovery. Wood and Spekkens (2015) showed that the correlations between distant measurements on entangled particles can be reproduced by a classical DAG only if its parameters are fine-tuned, that is, only by an unfaithful model in the sense of Definition 20.7. Quantum causal models replace the classical common cause by a shared quantum system and conditional distributions by quantum channels, and recover versions of d-separation and the Markov property (Costa and Shrapnel, 2016; Barrett, Lorenz and Oreshkov, 2019). Quantum systems can even reveal their causal structure without interventions where classical ones cannot: Ried et al. (Nature Physics, 2015) distinguished, from passive measurements alone, whether two quantum systems were related as cause and effect or by a common cause, in a setting where classical observational data could not decide.
Gene-regulatory networks are inferred from expression data, increasingly from large CRISPR screens in which thousands of genes are knocked out one at a time: interventions at scale, exactly the setting of Section 5. In cloud computing, root-cause analysis learns causal graphs of services and their latency or error metrics, so that when an alert fires the system can trace it to the component that caused it. In neuroscience, effective connectivity asks which brain regions drive which, beyond the correlations of Lecture 20a. In macroeconomics and finance, structural vector autoregressions and causal discovery on time series are used to study how shocks propagate between markets and countries. In each case the methods of this lecture give hypotheses whose value depends on assumptions (no hidden confounders, faithfulness, correct units) that should be checked, ideally by experiment.
The covariance matrix of \((X,Y,M)\) has \(\operatorname{Var}M=3\) and \(\operatorname{Cov}(X,M)=\operatorname{Cov}(Y,M)=1\). Conditioning on \(M\),
$$\operatorname{Cov}(X,Y\mid M)=0-\frac{1\cdot1}{3}=-\frac13,\qquad\operatorname{Var}(X\mid M)=1-\frac13=\frac23,$$so the conditional correlation is \((-1/3)/(2/3)=-1/2\). Independent causes become negatively correlated once their common effect is known: if \(M\) is large and \(X\) is small, \(Y\) must be large.
The v-structure \(B\to D\leftarrow C\) and the edge \(D\to E\) are fixed (reversing \(D\to E\) would create new v-structures \(B\to D\leftarrow E\) and \(C\to D\leftarrow E\)). The edges \(A-B\) and \(A-C\) can be oriented in three ways without creating a v-structure at \(A\): \(A\to B,A\to C\); \(B\to A\to C\); \(C\to A\to B\). The fourth, \(B\to A\leftarrow C\), is a new v-structure. So the class has three members, as the code found.
For \(X\to Y\): \(\hat\sigma_X^2=1\) and \(\hat\sigma_{Y\mid X}^2=1-r^2\), with one parent in total. For \(Y\to X\): \(\hat\sigma_Y^2=1\) and \(\hat\sigma_{X\mid Y}^2=1-r^2\), also one parent. The log-likelihood terms and the penalties are identical. The same holds without standardising, because \(\hat\sigma_X^2\hat\sigma_{Y\mid X}^2=\hat\sigma_Y^2\hat\sigma_{X\mid Y}^2=\det\hat\Sigma\).
If \(W\) is strictly upper triangular, so is \(B=W\circ W\) and every power \(B^k\), \(k\ge1\); all have zero trace, so \(h=0\).
For the two-cycle, \(B\) has off-diagonal entries \(a^2,b^2\), so \(B^2=a^2b^2I\) and \(B^{2m}=(ab)^{2m}I\), while odd powers have zero diagonal. Hence
$$h(W)=2\sum_{m\ge1}\frac{(ab)^{2m}}{(2m)!}=2\big(\cosh(ab)-1\big),$$which is zero only if \(a=0\) or \(b=0\), and small when \(ab\) is small: the penalty pushes the product of the two weights towards zero.
PC uses only partial correlations, and these are unchanged when a variable is rescaled (the sign may flip, but the Fisher test uses the absolute value). NOTEARS minimises a sum of squared residuals in the original units. Multiplying \(X_k\) by a large constant makes its residuals dominate the loss, so the fit explains \(X_k\) by others at almost any cost; multiplying by a small constant makes \(X_k\) cheap to use as a cause. The minimiser changes, and so does the graph. Standardising every variable removes this dependence but also removes the variance ordering that NOTEARS relied on.
Change simulate_sem to scale each noise term by its own standard deviation, and random_dag to draw weights from uniform(0.2, 0.8). Smaller weights and unequal noise make variances grow less reliably along the causal order, so varsortability falls towards one half. Both methods then lose accuracy, and the gap between raw and standardised data shrinks. This is Reisach et al.'s recommendation: report varsortability for every benchmark, and compare against the trivial variance-sorting baseline.
Each project uses this lecture's methods and public data, and has a clear result.
cmu-phil/example-causal-datasets or the cdt package).Data. Sachs et al. (2005) flow-cytometry data (all nine conditions, 7,466 cells) and the 20-edge ground-truth graph from github.com/cmu-phil/example-causal-datasets (folder real/sachs); the same data are distributed with the Causal Discovery Toolbox (cdt, PyPI). GES and a check of our PC implementation use the causal-learn package (PyPI). All other data are simulated.
numbers in the text not printed by a code box are computed in verify_L20b.py, figures and widget data in figs_L20b.py; code-box outputs are pasted from actual runs (numpy, pandas, SciPy, scikit-learn and causal-learn on two CPU cores)