Causal Discovery: Learning the Graph

The previous two lessons assumed you had a causal graph and asked what could be computed from it. That assumption is doing enormous work, and it invites the obvious question: where does the graph come from?

Usually from domain knowledge. A clinician knows severity affects both treatment choice and outcome. An economist knows education precedes earnings.

But domain knowledge is often incomplete, contested, or simply absent, particularly in settings like genomics where the number of variables is large and the mechanisms are what you are trying to discover.

Causal discovery attempts to learn causal structure from data. Stated baldly it sounds impossible, since the first lesson established that correlation does not determine causation.

The resolution is that while a single correlation says nothing about direction, a pattern of conditional independencies across many variables constrains which graphs could have produced it. Not always to a unique answer, but to a restricted set, and sometimes that set is small enough to be useful.

This is Negar Kiyavash's area. She holds the Chair of Business Analytics at EPFL, working on statistical learning theory applied to network inference, developing models and algorithms to infer causal dynamics in complex networks rather than correlation-only relationships.

Causal discovery rests on two assumptions linking graph structure to observable independencies, and everything depends on them.

The causal Markov condition says that a graph implies independencies: variables that are d-separated in the graph are statistically independent in the data. This is the direction that follows from the model, and it is relatively uncontroversial.

The faithfulness condition says the converse: every independence observed in the data corresponds to a d-separation in the graph. Nothing is independent by numerical accident.

Faithfulness is the strong one, and it can fail. If two causal paths between variables have effects that exactly cancel, you observe independence without d-separation, and the algorithm will infer a missing edge. Exact cancellation is measure-zero in a technical sense and near-cancellation is entirely realistic, which makes faithfulness violations a practical concern rather than a theoretical curiosity.

With both assumptions, independence patterns become readable as structural information, and discovery becomes possible in principle.

A third assumption, causal sufficiency, is required by the basic algorithms: that there are no unmeasured common causes. That one is almost never true, and relaxing it is the subject of the second half of this lesson.

The canonical constraint-based method is the PC algorithm, named for its developers Peter Spirtes and Clark Glymour.

It proceeds in two phases.

Skeleton discovery. Begin with a fully connected undirected graph. For each pair of variables, search for a conditioning set that renders them independent. If one exists, remove the edge, and record the separating set. The search starts with the empty set, then all single variables, then pairs, and so on, which keeps the number of tests manageable on sparse graphs.

Orientation. Now use colliders. For any structure X to Z to Y where X and Y are non-adjacent, check whether Z is in the set that separated them. If Z is not in that set, the only consistent explanation is that Z is a collider, so orient both edges into Z. Remaining edges are oriented by rules that avoid creating new colliders or cycles.

The second phase is where direction genuinely comes from data. A chain and a fork imply the same independence, so they are indistinguishable. A collider implies a different pattern: X and Y independent unconditionally, dependent given Z.

That asymmetry is the only source of directional information available from observational independencies, and it is the entire basis for orienting any edge.

PC does not return a single graph. It returns a Markov equivalence class: the set of all graphs implying exactly the same conditional independencies.

The reason is the asymmetry just described. Consider three graphs on the same variables:

X -> Z -> Y     chain
X <- Z <- Y     reversed chain
X <- Z -> Y     fork

All three imply: X and Y dependent,
                 X and Y independent given Z.

X -> Z <- Y     collider

Implies:         X and Y independent,
                 X and Y dependent given Z.

The first three are indistinguishable from observational data, because they entail identical independence patterns. Only the collider is separable.

So the output is a partially directed graph: some edges oriented, others left ambiguous because the data cannot determine them.

This is not a weakness of the PC algorithm. It is an information-theoretic limit. No algorithm using only conditional independencies can do better, because the graphs are observationally identical.

The practical consequence matters for the previous lesson. If your effect of interest runs along an edge the data cannot orient, discovery has not given you the graph you needed, and it has told you precisely what additional assumption or experiment would settle it.

The single distinguishable pattern is the collider, and everything the algorithms can orient traces back to it. Where that asymmetry is absent, the data is genuinely silent and only assumptions or interventions resolve the direction.

PC assumes causal sufficiency: every common cause of any two measured variables is itself measured. In real data this is almost never true, and the consequence is severe. Under a hidden confounder, PC will infer a direct edge between two variables that have no direct relationship at all.

The FCI algorithm, for Fast Causal Inference, relaxes it. FCI begins with PC's adjacency search, then performs additional conditional independence tests required by the presence of latent variables, then orients what it can.

Its output is a different object: a partial ancestral graph, which uses a richer edge vocabulary to express uncertainty about mechanism rather than only about direction. An edge can record that one variable causes another, or that they share an unmeasured common cause, or that the data cannot distinguish these.

The critical property is that FCI is sound and complete even under latent confounding and selection bias, which means it returns everything the data supports and nothing more.

The cost is inevitable: with hidden variables permitted, more structures become observationally equivalent, so the output is correspondingly less determinate.

An edge annotated as "causal or confounded, cannot tell" is not a failure. It is an honest report, and far more useful than a confident arrow that the data never justified.

The equivalence class is a limit on what conditional independencies determine. Additional information can break it, and each source is a distinct research direction.

Interventions. Even a few experiments resolve a great deal. Intervening on X and observing whether Y changes settles that edge's direction directly. Work on optimal experiment design asks which minimal set of interventions identifies the whole graph.

Multiple environments. Data collected under different conditions constrains structure, because causal mechanisms are expected to remain invariant across environments while spurious associations shift. Kiyavash's work uses exactly this: causal effects can be identifiable in the presence of a latent confounder when data is available from multiple environments, provided the target effect is invariant across them.

Functional form assumptions. Restricting the class of relationships can break the symmetry. If effects are generated by additive non-Gaussian noise, the direction becomes identifiable: fitting the wrong direction leaves residuals dependent on the input in a detectable way.

Time. Temporal order excludes any arrow pointing backwards, which is a substantial constraint at no cost.

Domain knowledge. Forbidding or requiring specific edges is legitimate and usually available.

The common thread: every route out of the equivalence class adds information the observational distribution does not contain.

What to check before believing a learned graph.

Two gotchas dominate practice.

Errors cascade. These algorithms are sequential: a wrong independence decision early removes an edge, which changes the conditioning sets used later, which changes subsequent decisions. A single early error can restructure the output. This is why discovery results are far less stable on finite samples than the theory suggests.

A drawn arrow is not a discovered cause. Software will render a directed graph whether or not the data supported that orientation. Treat causal discovery as hypothesis generation: it proposes structures worth testing, ideally by intervention, and does not deliver a graph you should immediately feed into the identification machinery of the previous lesson.