Machine Learning · Lecture 20b

Lecture 20b
Learning Graphs from Data II: Causal Discovery

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

Cartoon: the rooster and the sunriseA rooster crows on a fence as the sun rises behind a hill. One stick figure says the rooster makes the sun rise; the other, holding a box, says to shut the rooster in tomorrow and see. Every morning it crows,and then the sun rises. Shut it in tomorrowand see what happens.
Observation shows what goes together; intervention shows which way the arrow points
In this lecture
  1. DAGs, d-separation and Markov equivalence
  2. Constraint-based discovery: the PC algorithm
  3. Score-based discovery: BIC and greedy equivalence search
  4. Continuous optimisation: NOTEARS, and its pitfalls
  5. Interventions and identifiability
  6. Summary, exercises, projects, reading

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.

1 — DAGs, d-separation and Markov equivalence

definition 20.5 — causal DAG and structural equation model

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.

definition 20.6 — d-separation

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.

theorem 20.3 — the global Markov property

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.

definition 20.7 — faithfulness

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.$$
code — d-separation on a five-variable DAG, checked against data
# 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.

The d-separation game

Pick two variables, then click other nodes to condition on them (amber). Open paths are drawn in red. Each conditioning set also shows the sample partial correlation from 5,000 simulated draws of this DAG: it should be near zero exactly when the pair is d-separated. Try B and C: condition on A, then on D, then on E instead.

theorem 20.4 — Markov equivalence (Verma and Pearl, 1990)

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.

spot check 20.3

Which DAG is not Markov equivalent to \(X\to M\to Y\)?

Compare skeletons and v-structures (Theorem 20.4).
The collider is a v-structure, since \(X\) and \(Y\) are not adjacent. In it \(X\perp Y\) holds marginally but fails given \(M\): the opposite of the chain.

2 — Constraint-based discovery: the PC algorithm

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.

  1. Skeleton. Start with every pair joined. For conditioning sets of size 0, 1, 2, …, test each remaining pair \(i,j\) for independence given subsets of the current neighbours of \(i\) or of \(j\). If a test accepts independence, remove the edge and record the conditioning set as the separating set \(S_{ij}\).
  2. V-structures. For every \(i-m-j\) with \(i\) and \(j\) not adjacent, orient \(i\to m\leftarrow j\) if \(m\notin S_{ij}\).
  3. Propagation. Orient further edges by Meek's rules, which forbid new v-structures and cycles. The first rule: if \(k\to i-j\) and \(k\), \(j\) are not adjacent, orient \(i\to j\).

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.

theorem 20.5 — the PC algorithm is sound and complete

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\)

The PC algorithm, step by step

The run of the code below on 2,000 samples from the five-variable DAG. Each step shows the test that removed an edge (conditioning variables in amber), or the orientation it made. Compare the final graph with the true DAG of the d-separation game.

data — Sachs et al. (2005): protein signalling in single cells

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.

code — the PC algorithm; a faithfulness failure; the Sachs data
# 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.

theorem 20.6 — unfaithful parameters have measure zero

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.

history — from path analysis to the Turing Award

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".

3 — Score-based discovery: BIC and greedy equivalence search

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.

definition 20.8 — the BIC score of a DAG

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.

code — BIC scores of competing DAGs; GES
# 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.

bayes — Bayesian networks and Bayesian structure learning

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.

4 — Continuous optimisation: NOTEARS, and its pitfalls

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.

theorem 20.7 — acyclicity as a smooth equation (Zheng et al., 2018)

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.

code — NOTEARS on raw and standardised data; the Sachs data
# 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).

consensus networkrafmekplcpip2pip3erkaktpkapkcp38jnkPCrafmekplcpip2pip3erkaktpkapkcp38jnkGESrafmekplcpip2pip3erkaktpkapkcp38jnkNOTEARSrafmekplcpip2pip3erkaktpkapkcp38jnkconsensus edge, right directionconsensus edge, reversed or undirectednot in the consensus
The Sachs data. Top left: the 20-edge consensus network. The other panels show the graphs learned from the 853 general-stimulation cells by PC, GES and NOTEARS, coloured by agreement with the consensus. Undirected edges are drawn without arrowheads.

Rescale a variable, change the answer

NOTEARS on the five-variable example, after multiplying one variable by a factor. A change of units (metres to centimetres, say) carries no causal information, yet the learned graph changes: green arrows are correct, amber reversed, red extra, dashed grey missing. PC uses partial correlations, which ignore units, and its answer does not change.

5 — Interventions and identifiability

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.

definition 20.9 — intervention

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).

code — what an intervention reveals
# 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.

spot check 20.4

The true graph is \(X\to Y\). You intervene on \(Y\), setting it at random. What happens to the correlation between \(X\) and \(Y\)?

An intervention on \(Y\) deletes the arrows into \(Y\) (Definition 20.9).
Setting \(Y\) externally cuts \(X\to Y\), so \(X\) and \(Y\) become independent. Had the truth been \(Y\to X\), the correlation would have survived. One experiment on \(Y\) therefore tells the two directions apart.
quantum — quantum causal models

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.

big picture — where causal discovery is used

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.

6 — Summary, exercises, projects, reading

summary
exercises
  1. In the collider \(X\to M\leftarrow Y\) with \(X,Y\) independent standard normals and \(M=X+Y+\varepsilon\), \(\varepsilon\sim\mathcal N(0,1)\), compute the correlation of \(X\) and \(Y\) given \(M\).

    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.

  2. List all DAGs in the Markov equivalence class of the five-variable example, and check the code's count. Which edge directions vary?

    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.

  3. Show that the BIC score of Definition 20.8 is the same for \(X\to Y\) and \(Y\to X\) when both variables are standardised.

    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\).

  4. Show that \(h(W)\) in Theorem 20.7 is zero for any strictly upper-triangular \(W\), and compute \(h\) for the two-cycle \(W=\begin{pmatrix}0&a\\b&0\end{pmatrix}\).

    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.

  5. Explain why the PC algorithm's output does not change when a variable is multiplied by a non-zero constant, while NOTEARS' output can.

    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.

  6. (Code.) Repeat the varsortability experiment with noise variances drawn at random from [0.5, 2] for each variable and edge weights in [0.2, 0.8]. How do varsortability and the SHDs of NOTEARS and of "sort by variance and regress" change?

    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.

student projects

Each project uses this lecture's methods and public data, and has a clear result.

1. Does standardising fix NOTEARS?

question
How much of NOTEARS' accuracy on simulated data and on the Sachs data comes from varsortability, and does any simple fix (standardising, random rescaling, a scale-invariant loss) restore it?
data
Simulated linear and nonlinear SEMs with controlled varsortability; the Sachs data, observational and with the intervention conditions (from cmu-phil/example-causal-datasets or the cdt package).
method
NOTEARS, PC, GES and sort-by-variance on raw, standardised and randomly rescaled data; structural Hamming distance and orientation accuracy against the truth; varsortability of each data set.
outcome
A replication of Reisach, Seiler and Weichwald (2021) on new simulations and a clear statement of when continuous structure learning can be trusted.

2. Causes of delays on the subway

question
Which factors (weather, ridership, signal problems, track work, incidents on other lines) cause delays on New York City subway lines, and which are merely correlated with them?
data
MTA performance and delay data from data.ny.gov; NOAA weather for Central Park; ridership counts; planned-work notices as natural interventions.
method
PC and GES on daily data with background knowledge (weather cannot be caused by delays); comparison of graphs across lines and years; planned work as an intervention to test learned arrows.
outcome
A causal graph with confidence for each edge, and a short list of arrows that the interventions confirm or refute.

Reading and sources

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)