Causal Discovery and Causal Representation Learning

A discovery package prints one graph. It does not print how many other graphs fit the data exactly as well.

That count exists. A 2015 paper built the first method able to count the DAGs inside a large Markov equivalence class. It opens with the sentence no package prints alongside its output: “When learning a directed acyclic graph (DAG) model via observational data, one generally cannot identify the underlying DAG, but can potentially obtain a Markov equivalence class.” The counts are not reassuring. The paper reports that “the size of a Markov equivalence class with 50 vertices and 250 edges could be greater than 10^24”. That is how many distinct graphs a single sparse fifty-variable run may be picking one representative from.

The other end of the distribution is what makes the first end easy to miss. Every DAG on up to 10 vertices had already been walked, one by one, by Gillispie and Perlman. The average class size across all of them is about 3.7. On small problems the ambiguity really is a handful of candidates you could list on a whiteboard. Nothing on the printout tells you which regime you are in.

So a team points a package at its sensor logs. The graph that comes back goes into a design review as the causal map of the system. Where the tests could not tell which of two directions held, the package fell back on a default orientation rule and picked one. It printed the result with no mark separating the arrows it had earned from the arrows it had guessed. What it printed was one member of a set, chosen by convention. The review treated it as a finding.

The three families of discovery methods differ mainly in what they are willing to assume in exchange for an arrowhead.

Constraint-based methods test conditional independence and keep the graphs consistent with the results. So they inherit whatever those tests get wrong at the sample size you actually have.

Score-based methods pick whichever graph scores best under a chosen criterion. That search is not merely large. It is provably intractable. A 2004 proof showed that identifying high-scoring Bayesian-network structures is NP-hard even in the large-sample limit with a consistent scoring criterion. It stays NP-hard when the learner is handed an independence oracle, an inference oracle or an information oracle. It stays NP-hard when every node is restricted to at most k parents, for any k ≥ 3. The scope sentence is the one to carry into practice: “Our results therefore hold whenever the learning algorithm uses a consistent scoring criterion and is applied to a sufficiently large dataset.” More data does not rescue the search. What a score-based package returns is where its heuristic stopped, not the best graph. It prints the two in the same typeface.

Functional methods orient more edges than either, but only by assuming something specific about the equations. The canonical one states its price in its own abstract. LiNGAM, published in 2006, promises to “discover the complete causal structure of continuous-valued data, under the assumptions that (a) the data generating process is linear, (b) there are no unobserved confounders, and (c) disturbance variables have non-Gaussian distributions of non-zero variances.” A fully oriented graph out of purely observational data, bought with (a), (b) and (c). Those three conditions are doing the orienting, not the data. And (b) is exactly the condition an unmeasured common cause voids without announcing itself.

A road network inferred from which towns have correlated traffic behaves the same way. Many layouts produce the same flow patterns. They stay indistinguishable until somebody closes a road and watches, or a new kind of observation arrives. Causal systems add problems the road picture does not have: variables nobody recorded, feedback where cause runs both ways over time, and measurements that are transformations of the quantity you care about rather than the quantity itself.

Any one of those can put the true structure outside the space the search was allowed to consider. A search cannot report an answer it had no way to represent.

These four turn up in every argument about a discovery result, and they are easy to blur together. Two are conditions the search needs in order to be right. One is the thing that quietly breaks it. The last is what you were hoping to build on top — and it was only set out as a field's founding problem in 2021.

It helps to walk the workflow in order. Each stage is a place where an assumption gets in, and it can be written down before it hardens into a picture.

Define the variables and their timing first. An arrow between two quantities recorded at the same instant is rarely interpretable, whatever the algorithm says about it.

Choose the assumption family next, out loud, rather than inheriting it from whichever package was already installed. Out loud means writing down something as specific as LiNGAM's (a) linearity, (b) no unobserved confounders and (c) non-Gaussian disturbances of non-zero variance. Or naming the consistent scoring criterion whose optimum the 2004 hardness result put out of reach, even in the large-sample limit.

Then run several methods instead of one. Compare what they agree on, and how stable that agreement stays when the sample is resampled or perturbed. The stable agreements are the part you can defend in a room. Then validate causally, which always means going outside the data set that produced the graph.

Two numbers belong on the map itself, at the stage where the graph is handed to someone else. The first is the size of the equivalence class the run could not narrow. An average of about 3.7 members on problems of up to 10 vertices, more than 10^24 for a 50-vertex, 250-edge class: that distance is the whole story. The second is the count of edges oriented by a default rule rather than by evidence. Read the map as a list of decision points, not as a pipeline that runs itself.

The useful question about a discovery output is not whether it is true. It is what would settle it.

Sort the edges into three piles: the ones every method returned and every resample kept, the ones that flipped direction depending on the run, and the ones that exist only because a default rule had to break a tie. The first pile is the result. The second and third piles are the agenda.

For each disputed edge, write down what evidence would decide it and what that evidence costs. An intervention somebody has to authorise. A past period when the environment shifted. A variable someone could start recording tomorrow. That cost has a published ceiling. Among N variables it is N−1 experiments when each experiment randomizes at most one variable, or log2(N)+1 when any number of variables may be randomized at once. Both figures assume no latent variables, no sample selection bias and no feedback cycles. Whether your setting honours those three assumptions is itself worth writing down next to the budget.

Then filter by whether the dispute matters. If every graph in the class implies the same adjustment set for the decision actually in front of you, the ambiguity is free and you can move on without resolving it. If they imply different ones, you have just found where the next experiment goes.

Each family leans on a different assumption, so each breaks in a different way. The breakages are informative.

A constraint-based search is only as good as its independence tests. It degrades quietly rather than loudly when the data is thin or the dependence is nonlinear. A score-based search always returns something, with the same confidence whether or not the truth was inside the model class it searched — and, given the 2004 hardness result, whether or not the search came anywhere near the criterion's own optimum. A functional method will orient edges the other two leave undirected. That is a genuine gain and a genuine exposure, since the orientation rests entirely on its noise or shape assumption being right for these particular variables.

Both halves of that last sentence have been measured on real data. The CauseEffectPairs benchmark, published in 2016, is 100 cause-effect pairs drawn from 37 data sets with known ground-truth direction. On it, one of the best-performing methods overall reached an accuracy of 63 ± 10 % and an AUC of 0.74 ± 0.05. That was the additive-noise method of Hoyer and colleagues, from 2009. The benchmark authors' own summary is deliberately narrow: “Our empirical results on real-world data indicate that certain methods are indeed able to distinguish cause from effect using only purely observational data, although more benchmark data would be needed to obtain statistically significant conclusions.” That is a real signal on real pairs. It is also an error bar wide enough that one oriented edge from such a method is a lead worth chasing, not a mechanism you can build a decision on.

Where the families agree, you have evidence. Where they disagree, you have a specific question about which assumption is failing. That question is worth more than either graph on its own.

All of it converges on one point. Data collected while the system was left alone cannot separate the members of an equivalence class. Orientation has to come from evidence in which the data-generating process was itself different. Four kinds are usually within reach, in roughly descending order of what they cost to get.

One caution before the list. This ranking is about evidential strength, not about what a given method will manage to do with it. CausalBench was built out of more than 200,000 real single-cell samples under genetic perturbation, across two cell lines: K562, with 622 interventions, and RPE1, with 383. It appeared in 2022 and was peer-reviewed in Communications Biology in 2025. Its result: “Moreover, methods that use interventional information do not outperform those that only use observational data, contrary to what is observed on synthetic benchmarks.” The interventions were real and expensive. The methods could not convert them. Buying the evidence is one problem. Having a method that can use it is a second one.

Which leaves discovery in a smaller and far more defensible role than its name suggests.

It is good at organising hypotheses, at surfacing conditional structure nobody thought to look for, and at telling you which experiment would repay its cost. It is not a source of adjustment sets for a policy that will affect people. One run of one package should never be the whole argument behind a mechanism claim. A family of methods whose best real-world showing on 100 known pairs was an accuracy of 63 ± 10 % is a useful instrument and a poor witness.

The practical test is whether the ambiguity changes the answer. When every graph in the class implies the same estimand and the same adjustment set, say so in writing and proceed. Note, when the class could hold more than 10^24 members, that this is a claim about the class rather than a check you performed member by member. When they do not agree, report the alternatives instead of the most presentable one, and design the observation or intervention that would tell them apart.