Causal Discovery: Why Conditional Independence Can Recover a Graph - and When It Cannot

Correlation tells you that two variables move together. It does not tell you why. Causal discovery is the attempt to go one step further: given observational data alone, can we recover the causal graph that generated it?

Sometimes the answer is yes, up to an important qualification. Sometimes it is no, and the reason is instructive. This article explains the core idea, the assumptions it rests on, the most widely used algorithm, and the pitfalls that make practitioners overclaim.

The question, stated precisely

Assume the data come from a causal directed acyclic graph, a DAG. Each node is a variable. Each directed edge means a direct causal effect. The joint distribution factorises over the graph:

$$p(x_{1}, \dots, x_{n}) = \prod_{i=1}^{n} p(x_{i} \mid \text{pa}_{i})$$

Here $\text{pa}{i}$ denotes the parents of $x{i}$ . This is not a modelling convenience. It is the claim that each variable is generated from its direct causes plus independent noise.

Causal discovery asks the inverse question. We observe samples from $p$ . Can we recover the DAG? The short answer is: we can often recover its skeleton and some of its directions, but not always the full DAG. Understanding why is the whole subject.

Three small graphs that explain most of the intuition

Almost everything in causal discovery follows from three patterns involving three variables.

A chain: $X \rightarrow Y \rightarrow Z$ . Here $X$ and $Z$ are dependent marginally, but independent given $Y$ . Conditioning on the middle variable blocks the flow of association.

A fork: $X \leftarrow Y \rightarrow Z$ . Again $X$ and $Z$ are dependent marginally, because they share a common cause, but independent given $Y$ . This is confounding in its simplest form.

A collider: $X \rightarrow Y \leftarrow Z$ . Here $X$ and $Z$ are independent marginally, but dependent given $Y$ , or given any descendant of $Y$ . Conditioning on a common effect creates association where none existed. This is Berkson's paradox, and it is the reason naive conditioning is dangerous.

In symbols, the chain and fork give:

$$X \perp Z \mid Y$$

while the collider gives the opposite pattern: marginal independence, but conditional dependence. That contrast is what lets an algorithm orient some edges. If $X$ and $Z$ become dependent only after conditioning on $Y$ , then $Y$ is probably a collider, not a mediator or a confounder.

The general rule behind these examples is d-separation. A path between two variables is blocked by a conditioning set if the set contains a non-collider on the path, or if it contains neither a collider on the path nor any descendant of that collider. Two variables are d-separated by a set when every path between them is blocked. Under the assumptions below, d-separation in the graph corresponds exactly to conditional independence in the data.

The two assumptions you cannot skip

1. The causal Markov condition. Every variable is independent of its non-descendants given its parents. This follows from the factorisation above, and it is what connects graph structure to testable independence statements.

2. Faithfulness. Every conditional independence in the data is implied by d-separation in the true graph, not an accident of parameter values. Faithfulness rules out exact cancellations, for example two causal paths whose effects cancel perfectly so that a genuine dependence looks like independence.

Add a third, often implicit assumption:

3. Causal sufficiency. There are no unobserved common causes of the measured variables. If a hidden confounder exists, many standard algorithms will happily draw a wrong edge.

When these assumptions hold, conditional independence tests are informative about structure. When they fail, the output is still a graph, but it is no longer a reliable causal graph. That distinction matters more than the choice of algorithm.

The PC algorithm, step by step

The PC algorithm, named after its creators Peter Spirtes and Clark Glymour, is the classic constraint-based method. It works in three phases.

Phase 1: learn the skeleton. Start with a complete undirected graph. For each pair of variables, test whether they are independent given some subset of the other variables. Start with the empty set, then sets of size one, then size two, and so on. Remove the edge when an independence is found. The conditioning set that removed the edge is recorded as a separating set.

Phase 2: orient v-structures. For each triple $X - Y - Z$ where $X$ and $Z$ are not adjacent, check whether $Y$ is in the separating set for $X$ and $Z$ . If it is not, orient the triple as a collider: $X \rightarrow Y \leftarrow Z$ . This is the collider test from the previous section, applied systematically.

Phase 3: propagate orientations. Apply orientation rules that avoid creating new v-structures or cycles. For example, if $X \rightarrow Y$ and $Y - Z$ with $X$ and $Z$ non-adjacent, then orient $Y \rightarrow Z$ . Otherwise a new collider would appear that phase 2 did not find.

The output is not a single DAG. It is a completed partially directed acyclic graph, a CPDAG, which represents the whole Markov equivalence class: all DAGs that imply exactly the same conditional independencies. Chains and forks are Markov equivalent, because they imply the same independence pattern, so the algorithm cannot distinguish $X \rightarrow Y \rightarrow Z$ from $X \leftarrow Y \leftarrow Z$ from observational data alone. Colliders break the tie, which is why they are so valuable.

Score-based alternatives, such as greedy equivalence search, take a different route: they search over equivalence classes scoring each by fit plus a complexity penalty. They can be more stable in small samples, but they rest on the same assumptions. No search strategy escapes a violated assumption.

A concrete example you can run

Consider a chain where sleep affects focus, and focus affects exam performance. In code, generate it, then check the key pattern: marginal dependence between sleep and score, but independence given focus.

import numpy as np

rng = np.random.default_rng(0)
n = 5000
sleep = rng.normal(0, 1, n)          # hours relative to average
focus = 0.8 * sleep + rng.normal(0, 1, n)
score = 0.8 * focus + rng.normal(0, 1, n)

def partial_corr(x, y, z):
    # Residualise x and y on z, then correlate the residuals.
    bx = np.polyfit(z, x, 1)
    by = np.polyfit(z, y, 1)
    rx = x - np.polyval(bx, z)
    ry = y - np.polyval(by, z)
    return np.corrcoef(rx, ry)[0, 1]

print("corr(sleep, score):", round(np.corrcoef(sleep, score)[0, 1], 3))
print("partial corr given focus:", round(partial_corr(sleep, score, focus), 3))

The marginal correlation is clearly positive, while the partial correlation given focus is close to zero. That is exactly the signature the PC algorithm looks for in phase 1: an edge between sleep and score that disappears once focus is conditioned on. The algorithm would keep the edges sleep-focus and focus-score, and remove sleep-score.

Note what this example does not show. It does not prove that the chain runs in this direction. The reversed chain implies the same independencies. Direction here comes from background knowledge, from time order, or from an intervention, not from the correlation pattern alone.

Limitations and common pitfalls

Latent confounding breaks causal sufficiency. If an unmeasured variable causes two measured ones, the algorithm may draw a direct edge between them. The FCI algorithm relaxes sufficiency and can mark such edges as possibly confounded, but at the cost of leaving more edges unoriented. A graph with an ambiguous edge is more honest than a confident wrong one.

Selection bias creates colliders. If your sample is selected on a variable that is a common effect of two others, conditioning on selection induces dependence between them. Hospital samples, survey respondents, and users who passed a filter are all selected samples. Discovery on selected data can invent edges that do not exist in the population.

Finite samples make tests noisy. Conditional independence testing is hard, especially with many variables, nonlinear relationships, or small samples. A single wrong test early in the PC algorithm can remove a true edge or keep a false one, and errors propagate through the orientation rules. Stability checks, such as bootstrapping the procedure and reporting how often each edge appears, are not optional polish. They are the main defence against overinterpretation.

Faithfulness can fail quietly. Near-cancellations are common in real systems: a direct effect and an indirect effect of opposite signs can nearly cancel, making a genuine dependence look weak. The algorithm then removes an edge that is causally real. Weak edges deserve suspicion in both directions.

Markov equivalence is a hard limit, not a technicality. Without interventions, experiments, time order, or parametric assumptions such as non-Gaussian noise or additive noise models, observational data alone cannot distinguish members of the same equivalence class. Any report that claims a unique causal direction from observational independencies alone should be asked which extra assumption did the work.

Variables must be the right variables. Discovery assumes the measured variables correspond to the causal variables. Aggregated measures, proxies, and variables measured with error can all distort the graph. If two distinct mechanisms are collapsed into one variable, no algorithm can recover the distinction.

When to use it, and when not to

Use causal discovery as an exploratory tool: to generate candidate graphs, to challenge an assumed structure, to find colliders worth investigating, and to make the assumptions behind a causal claim explicit. It is most useful when combined with domain knowledge that can orient edges the data cannot, and with a follow-up intervention or experiment that can test a specific edge.

Do not use it as an automatic oracle that outputs "the causal graph" from a spreadsheet. The output is only as good as the Markov condition, faithfulness, causal sufficiency, and the independence tests, and in real data at least one of those is usually shaky.

Takeaway

Causal discovery works because graph structure leaves a fingerprint in conditional independence patterns, and colliders leave a distinctive one. The PC algorithm reads that fingerprint in three phases: skeleton, v-structures, then propagation. Its limit is equally clear: it recovers an equivalence class, not a unique DAG, and it trusts assumptions that real data often violate. Treat its output as a hypothesis graph, check its stability, name the assumptions, and test the edges that matter with something stronger than observation.

---

Connect with me on LinkedIn: linkedin.com/in/umeshtharukaofficial