The Graph Is an Equivalence Class

A causal arrow is easy to draw.

It is harder to earn.

Suppose observational data tells you that three variables form this undirected skeleton:

A - B - C

and suppose no conditional-independence test finds a collider witness at B. There are then several causal stories with the same independence shadow:

A -> B -> C
A <- B -> C
A <- B <- C

They disagree causally. They agree observationally.

That is not a bug in a causal-discovery algorithm. It is a theorem-shaped limit.

The Part the Data Can See

For directed acyclic graphs, Verma and Pearl’s Markov-equivalence criterion is the sentence to keep taped to the monitor:

same skeleton + same unshielded colliders = same conditional independences

More formally, two DAGs are Markov equivalent when they imply the same d-separation statements. The classical characterization says this happens exactly when they have the same undirected skeleton and the same v-structures, also called unshielded colliders.¹²

A v-structure is the local pattern:

A -> B <- C      with A and C not adjacent

The “not adjacent” clause matters. If A and C are connected, the collider is shielded by an extra edge, and the same conditional-independence witness no longer appears.

So the observational target is usually not a single DAG. It is a Markov equivalence class:

[G] = every DAG with the same skeleton and v-structures as G

The clean representation is the essential graph, or CPDAG. Its directed edges are the arrows shared by every DAG in the class. Its undirected edges are the arrows the observational data has not oriented.³

The lab below enumerates that class exactly for small graphs.

A Small Exact Enumerator

The code does not estimate from samples. It starts after the idealized conditional-independence oracle has already done its job. For each small skeleton, it:

enumerates every acyclic orientation
keeps only orientations with the same v-structures as the drawn DAG
cross-checks that class with an exact d-separation oracle
marks an edge as compelled only if every surviving DAG agrees on its direction
optionally adds one perfect intervention and recomputes the class

This is deliberately brute force. That is the point. The picture is not a metaphor for the theorem; it is a tiny verifier for it. The audit does not merely restate the skeleton/v-structure rule. It enumerates conditional-independence statements over the shown variables and checks that the two views pick the same surviving DAGs.

Graph:

three-node chain

three-node chain unshielded collider shielded triangle diamond with sink four-node corridor Extra data:

observed only

observed only do(A) do(B) do(C)

drawn DAG compelled arrow reversible link v-structure collider witness

Exact finite enumeration for small DAGs. Its 22-case audit checks acyclicity, d-separation equivalence, CPDAG edge unanimity, scorecard class sizes, and monotone refinement under the displayed perfect-intervention model.

Start with three-node chain and observed only. The class has three DAGs. The CPDAG has two gray links because the conditional independences do not decide whether B is a cause, a mediator, or an effect.

Now switch to unshielded collider. The class collapses to one DAG. The collider is not a vague visual cue; it is an independence fingerprint. Marginally A and C can be independent, but conditioning on B opens the path. That pattern singles out the arrowheads into B.

Then try shielded triangle. A complete three-node skeleton has six acyclic orientations and no unshielded colliders. The lab shows the annoying truth: every topological ordering gives a different DAG, and observational conditional-independence structure alone has nothing local to grab.

Interventions Shrink the Class

The intervention selector uses a simple ideal model: a perfect intervention on node X cuts incoming arrows into X in the intervention graph, while leaving the rest of the system’s arrows intact.

This is the graphical intuition behind interventional Markov equivalence. Hauser and Buehlmann formalize how observational plus interventional distributions define a finer equivalence class, represented by an interventional essential graph.⁴

In the three-node chain:

A -> B -> C

observational data leaves three DAGs. But do(A) or do(B) identifies the drawn chain in this toy. Why? If B caused A, intervening on A would cut the incoming B -> A edge and change the intervention graph’s independence fingerprint. If A causes B, there is no incoming edge to cut.

This is why experiments are not decorative causal labels. They change the graph whose independences you get to observe.

The Algorithmic Consequence

Once the target is an equivalence class, it is wasteful to search only over individual DAGs as if each orientation were separately identifiable.

Chickering’s Greedy Equivalence Search works over equivalence-class states rather than raw DAG states, using local operators on CPDAG-like representations.² Modern constraint-based algorithms such as PC also end in partially directed graphs, with finite-sample complications layered on top of the population theorem.⁵

The population theorem says:

with the right assumptions and infinite data, observational discovery reaches [G]

It does not say:

finite noisy tests recover the right class
hidden confounding is harmless
faithfulness always holds
the CPDAG is the causal graph

Those are separate contracts.

Reproducibility Notes

The executable artifact is assets/js/markov-equivalence-lab.js.

Its self-test runs 22 scenario/intervention cases and performs 687 local checks:

all displayed orientations are acyclic DAGs
the skeleton/v-structure criterion matches an independent d-separation oracle
every accepted orientation has the same observational/interventional CI signature
every rejected orientation differs from that CI signature
directed CPDAG edges are unanimous across the surviving class
undirected CPDAG edges occur in both directions across the surviving class
single-node interventions refine, rather than enlarge, the observational class
displayed class sizes match fixed regression anchors for all graph/target pairs

A Useful Reporting Habit

When a causal-discovery result prints a graph, ask:

Which edges are compelled across the equivalence class?
Which edges are merely one chosen representative?
What assumptions made this a DAG instead of a PAG or other object?
Were interventions used, or only observational independences?
How stable is the class under finite-sample uncertainty?
Does the downstream effect estimate average over the class or pretend it is a singleton?

The last question is where many analyses quietly change subject. A model can draw a single DAG because a plotting function needs arrowheads. But the scientific claim may only justify a CPDAG.

The honest object is not always:

the graph

Sometimes it is:

the set of graphs still alive

1. Thomas S. Verma and Judea Pearl, “Equivalence and Synthesis of Causal Models”, UAI, 1990. See also the arXiv-hosted version, “On the Equivalence of Causal Models”. ↩

2. David M. Chickering, “Optimal Structure Identification With Greedy Search”, Journal of Machine Learning Research 3:507-554, 2002. ↩ ↩²

3. Steen A. Andersson, David Madigan, and Michael D. Perlman, “A Characterization of Markov Equivalence Classes for Acyclic Digraphs”, The Annals of Statistics 25(2):505-541, 1997. ↩

4. Alain Hauser and Peter Buehlmann, “Characterization and Greedy Learning of Interventional Markov Equivalence Classes of Directed Acyclic Graphs”, Journal of Machine Learning Research 13:2409-2464, 2012. ↩

5. Diego Colombo and Marloes H. Maathuis, “Order-Independent Constraint-Based Causal Structure Learning”, Journal of Machine Learning Research 15:3741-3782, 2014. ↩