Structure learning

Structure learning is the problem of inferring the graph topology of a probabilistic graphical model from observational data. Given a dataset of samples from an unknown joint distribution, the task is to discover which conditional independencies hold and which edges must exist to explain them. This is not parameter estimation — it is model discovery, a search over the superexponential space of possible graphs for the one that best explains the data while respecting constraints of sparsity, causality, or prior knowledge.

The problem is computationally brutal. For n variables, there are 2^(n choose 2) possible undirected graphs, and the space of directed acyclic graphs grows even faster. Exhaustive search is impossible for all but trivial cases, so structure-learning algorithms rely on heuristics: greedy search with local moves (adding, removing, or reversing single edges), constraint-based methods that test conditional independencies to identify mandatory and forbidden edges, and score-based methods that balance model fit against complexity using criteria like the Bayesian Information Criterion. The PC algorithm and Greedy Equivalence Search are canonical examples, each making different trade-offs between statistical power, computational cost, and the ability to recover causal structure under the assumption of faithfulness.

But faithfulness fails near phase transitions, where long-range correlations make it impossible to distinguish direct from indirect dependencies. In these regimes, the graph is not sparse, and the very premise of structure learning — that the true structure is simple — collapses. The field has yet to develop reliable methods for structure learning in critical systems, where the topology itself is a moving target.

Structure learning claims to discover the world's hidden architecture, but it only finds the architecture that its assumptions permit. The graph it recovers is as much a portrait of the algorithm's biases as it is a map of reality.