Structure Learning and the Limits of Markov Equivalence

Everything in the preceding articles takes the graph as given. The next question is where it comes from: given a table of observations, which graph should be asserted? Two families of answers exist, and they agree on one thing — the most that observational data can identify is not a graph but a set of graphs. Understanding why that ceiling exists is more useful than any particular search procedure, because every procedure is measured against it.

The equivalence class is the observable unit

Two directed acyclic graphs are indistinguishable from observational data when they imply exactly the same set of conditional independencies. The characterization is structural: two DAGs are Markov equivalent precisely when they have the same skeleton — the same undirected edges, ignoring orientation — and the same set of unshielded colliders, where an unshielded collider is a triple $X \rightarrow Z \leftarrow Y$ in which $X$ and $Y$ are not adjacent. The proof obligation runs from the d-separation criterion described in Directed Graphical Models: D-Separation and the Markov Blanket: only colliders create independence statements that flipping an edge would destroy, so any orientation-preserving transformation that avoids creating or destroying an unshielded collider leaves the set of independencies unchanged.

The consequence is immediate. A chain $a \rightarrow b \rightarrow c$ and a fork $a \leftarrow b \rightarrow c$ imply the same independencies and cannot be told apart, while a collider $a \rightarrow b \leftarrow c$ differs from both because it implies that $a$ and $c$ are independent until $b$ or a descendant of $b$ is observed. Orientation information in observational data lives entirely in the unshielded colliders; every other edge direction is a convention. A search procedure that reports a fully oriented graph from observational data has reported more than the data support, and the honest output is a partially directed graph — a completed partially directed acyclic graph, or CPDAG — in which the directed edges are those common to every member of the class and the undirected ones mark the genuine ambiguity.

Independence tests as a search criterion

Constraint-based learning reads the class off test results directly. The skeleton is recovered by testing pairs of variables for independence given subsets of their neighbours, deleting an edge when some subset renders the pair independent and remembering the set that did it. Orientation then proceeds on unshielded triples: if $X$ and $Y$ are non-adjacent and both adjacent to $Z$, the triple is oriented as a collider exactly when $Z$ was not in the separating set of $X$ and $Y$; a set of further rules propagates forced orientations to avoid creating new colliders or cycles. The work is dominated by the tests: with the conditioning set allowed to grow, the number of subsets to examine is exponential in the degree of a node, so the usual implementation fixes a maximum conditioning size $k$, which makes the test count polynomial in the number of variables but also makes the procedure unable to detect an independence that requires conditioning on more than $k$ variables. That limitation is a modelling choice, not a numerical one, and it fails in a specific direction: too few conditioning variables leaves an edge in place, so the recovered graph is denser than the truth rather than sparser.

The assumptions are the delicate part. Correctness requires that the tests be reliable and that the distribution be faithful to some graph in the search space — that every independence the distribution satisfies be implied by the graph. Faithfulness is violated by near-deterministic dependencies, where one variable is almost a function of another and the pair behaves like a single variable, producing independencies, and hence missing edges, that no graph in the search space generates. A second assumption is causal sufficiency: no unmeasured variable influences two of the observed ones. When it fails, an orientation produced by the collider rule can be an artifact of a common cause that was never measured, which is why the extended procedure for that case replaces single directed edges with bidirected ones and reports a different kind of object whose directed edges are still identifiable.

Scoring functions and the search that maximizes them

Score-based learning replaces tests with a single objective over graphs. A decomposable score is a sum over nodes of a term depending only on that node and its parents, which is what makes local search affordable: adding an edge to a node’s parent set changes only that node’s term and, if the score is score-equivalent, leaves the terms of Markov-equivalent structures identical. The two standard choices are a penalized likelihood, in which each node contributes its maximum log likelihood minus half its free-parameter count times the logarithm of the sample size, and a Bayesian score obtained by integrating the parameters against a Dirichlet prior. Both penalize the parameters, and because Markov-equivalent structures have the same number of free parameters, both assign equal scores within an equivalence class — so searching over DAGs with either score is effectively searching over classes, with the tie broken arbitrarily.

Search itself is where the difficulty moves. Adding and deleting single edges until no change improves the score terminates at a local maximum, and the space of graphs contains many of them, so greedy hill climbing from a random start is not expected to find the highest-scoring structure. A hybrid reduces the search space before scoring: first recover each node’s candidate neighbourhood from independence tests with a bounded conditioning set, then run the greedy search restricted to those candidates, which is cheaper than unrestricted search and less sensitive to an early wrong orientation than the constraint-based procedure alone.

Exact search and its price

Finding the highest-scoring structure is not an approximation problem with an unknown optimum; the optimum can be computed exactly for moderate numbers of variables. The standard formulation is a dynamic program over subsets: a graph induces a topological order, the best structure consistent with the order decomposes into a best parent set per node, and the best order can be built by considering subsets in increasing size. The recurrence needs the best score for each subset, giving memory proportional to $2^n$ and time proportional to $n^2 2^n$ with the straightforward formulation, and fewer operations with a matrix-permanent-style evaluation. That exponent is not an implementation artifact. The count of labelled acyclic digraphs is 25 on three nodes and 543 on four, and it grows faster than exponentially from there, so enumeration is hopeless at any size where a graph is worth learning; the dynamic program is what makes exactness reachable anyway, and even it gives up somewhere in the twenties on current hardware.

What the numbers do not support

Structure learning algorithms are asymptotic statements operating on finite samples, and most of their practical failures are failures of that gap. A conditional independence test with a fixed significance level is applied many times during skeleton recovery, so the family-wise error rate grows with the number of tests, and each mistaken verdict either deletes a real edge or retains a spurious one. Penalized scores have their own bias: the penalty is a function of the sample size alone, so at small samples either sparser or denser structures can be preferred depending on which score is used, which means that the difference between two algorithms’ outputs at a few hundred observations is frequently a difference of penalty rather than evidence.

Two further limits are structural rather than statistical. Even with a correct equivalence class, the parameters must be estimated, and for a fixed structure that estimation is the likelihood maximization of Expectation-Maximization as Inference with Latent Variables whenever the model contains hidden variables; the score and the parameters are then not independent choices. And the score of a graph is not itself a probability that the graph is correct: scores across different structures are comparable as objective values, not as posterior probabilities, and differences of a few points of penalized log likelihood at a given sample size do not correspond to any calibrated degree of belief. The most defensible summary of a structure-learning run is the equivalence class plus the edges that were forced by definite structure, with the undirected edges treated as exactly what they are.