Discovering the causal structure of a system from data is fundamentally a search problem over the space of Directed Acyclic Graphs (DAGs). Because the number of possible graphs scales super-exponentially with the number of variables, finding the globally optimal network structure is an NP-hard problem. To make this tractable, traditional algorithms rely heavily on greedy local search heuristics—such as hill-climbing—that add, remove, or reverse one edge at a time.
However, these greedy strategies frequently fail because the structural optimization landscape is highly non-convex and rugged. A single myopic choice early in the search can trap the algorithm in a local optimum, preventing it from ever recovering the true causal graph.
The Myopia of Edge-by-Edge Search
Why does greedy search fail so reliably in large graph spaces? The core issue is that graph structural scores (such as the Bayesian Information Criterion) do not vary smoothly with individual edge modifications. A globally optimal graph structure might require the simultaneous rearrangement of multiple edges. A greedy algorithm, looking only one step ahead, will reject the first step of such a rearrangement if it temporarily lowers the score.
This phenomenon, often called the "horizon effect," means that local search operators lack the global perspective necessary to navigate complex dependencies. As noted by Yuhao Wang et al. in Permutation-based Causal Inference Algorithms with Interventions, operating directly on the discrete space of DAGs makes algorithms highly prone to getting stuck, destroying their statistical consistency even when provided with infinite data.
Furthermore, providing more data does not resolve this fundamental algorithmic limitation. Kun Zhang et al. in Improving Causal Discovery By Optimal Bayesian Network Learning document a "precision-saturation effect," where increasing sample sizes fails to improve accuracy or even causes a drop in precision. Because the greedy heuristic makes irreversible errors early on, additional data merely reinforces the sub-optimal local minimum rather than guiding the model out of it.
Similarly, in related domains like graph-based nearest neighbor retrieval, Jiafeng Guo et al. in Fast Approximate Nearest Neighbor Search via k-Diverse Nearest Neighbor Graph demonstrate that greedy routing processes get trapped when a graph structure focuses too heavily on local proximity, missing the broader global manifold.
Smoothing the Landscape via Continuous Relaxations
One of the most prominent modern solutions to this combinatorial nightmare is to transform the discrete search space into a continuous one. If the graph space can be made differentiable, we can replace myopic discrete edge swaps with global gradient descent.
This is the intuition behind frameworks like GraN-DAG, introduced by Sebastien Lachapelle et al. in Gradient-Based Neural DAG Learning. Instead of adding or removing edges one by one, the authors define a continuous, differentiable acyclicity constraint based on neural network weights. This allows the model to optimize the entire graph structure simultaneously via backpropagation. By avoiding discrete local steps, the algorithm maintains a global view of the graph structure and smoothly navigates around the local optima that derail traditional hill-climbing.
Bounding the Search via Exact Optimization
Another way to bypass the pitfalls of greedy heuristics is to eschew approximate search entirely in favor of exact mathematical optimization. While exhaustive search is computationally prohibitive, the problem can often be reformulated globally using mathematical programming.
For instance, Rui Chen et al. in Integer Programming for Causal Structure Learning in the Presence of Latent Variables address structure learning for Maximal Ancestral Graphs (MAGs)—which account for unobserved confounders. While greedy searches over MAGs frequently settle on sub-optimal solutions, the authors formulate the score maximization as an Integer Program (IP). By introducing global structural constraints (such as bicluster inequalities), they guarantee global optimality, bypassing local minima entirely.
Lookahead and Path Planning in Graph Space
If we must search a discrete graph space, we can mitigate myopia by looking multiple steps ahead. Rather than evaluating only immediate neighbors, algorithms can treat structure learning as a sequential decision-making problem.
Victor-Alexandru Darvariu et al. explore this in Tree search in DAG space with model-based reinforcement learning for causal discovery. By combining model-based reinforcement learning with Monte Carlo Tree Search (MCTS), their approach explicitly plans sequences of graph modifications. This deeper lookahead allows the algorithm to cross "valleys" of lower scores to reach higher global maxima, effectively overcoming the horizon effect that cripples standard greedy discovery.