GES

Greedy Equivalence Search (GES) is a score-based algorithm for learning the structure of a Bayesian network from observational data. Unlike constraint-based methods such as the PC algorithm, which rely on conditional independence tests to build and orient a graph, GES searches directly over the space of possible graph structures, scoring each candidate with a penalized likelihood criterion such as the Bayesian Information Criterion (BIC) or a Bayesian Dirichlet equivalent uniform (BDeu) score. It was introduced by David Chickering in 2002 as a computationally tractable alternative to exhaustive search, which is impossible for all but the smallest variable sets.

The central insight of GES is that searching over individual directed acyclic graphs (DAGs) is wasteful. Many DAGs encode the exact same set of conditional independencies and are therefore statistically indistinguishable from observational data alone. These DAGs form a Markov equivalence class, represented compactly as a completed partially directed acyclic graph (CPDAG) in which directed edges indicate causal arrows that are identifiable from the data, and undirected edges indicate arrows whose direction cannot be determined without additional assumptions or experiments. By searching over equivalence classes rather than individual DAGs, GES avoids the local optima that trap greedy searches in DAG space.

The GES Search Procedure

GES operates in two phases, each a greedy hill-climbing search over CPDAGs. In the forward phase, the algorithm starts with an empty graph and iteratively adds the single edge that most improves the score, continuing until no addition improves the score. In the backward phase, the algorithm iteratively removes the single edge whose removal most improves the score, again continuing until no removal helps. The combination of forward and backward phases allows GES to escape some local optima: an edge added early may become unnecessary once other edges are in place, and the backward phase cleans these up.

The search operators — edge addition, deletion, and (in some variants) reversal — are applied to the CPDAG representation, not to a single DAG. This means that when GES adds an undirected edge to a CPDAG, it is effectively committing to the existence of some causal relationship between two variables without yet committing to its direction. The direction is resolved only when the data, through the scoring criterion, prefers one orientation over all others in the equivalence class. This delayed commitment is what distinguishes GES from naive greedy search in DAG space, where an early orientation choice can lock the search into a suboptimal branch.

Score-Based vs. Constraint-Based Discovery

The divide between score-based methods like GES and constraint-based methods like the PC algorithm is deeper than a difference in optimization strategy. It is a difference in epistemological framing. The PC algorithm treats causal discovery as a logical inference problem: it asks which conditional independencies hold in the data, and from those logical facts it derives a graph. GES treats causal discovery as a statistical model selection problem: it asks which graph provides the best trade-off between fit and complexity, and it searches for that graph directly. The PC algorithm's output is determined by the outcome of independence tests; GES's output is determined by the choice of scoring criterion and the path taken through the search space.

Each approach has characteristic failure modes. The PC algorithm is sensitive to the order in which conditional independence tests are performed, and its output can change dramatically when the significance threshold for the tests is adjusted. GES is sensitive to the scoring criterion: BIC penalizes complexity more aggressively than BDeu, and the difference can lead to different graph structures, especially in small samples. More fundamentally, GES assumes that the true graph is identifiable by score optimization — that the scoring landscape has a clear global optimum that corresponds to the true causal structure. When the Faithfulness assumption fails, when hidden confounders are present, or when the data come from a distribution near a phase transition, the scoring landscape becomes flat or multi-modal, and GES has no way to know that it has converged to the wrong structure.

Extensions and Limitations

The original GES algorithm is computationally expensive for high-dimensional problems, and several extensions have been developed to improve scalability. FGES (Fast Greedy Equivalence Search) parallelizes the scoring of candidate edges and uses caching to avoid recomputing scores for structures that have already been evaluated. MMPC (Max-Min Parents and Children) is a hybrid approach that first uses constraint-based methods to identify the local neighborhood of each variable, then applies score-based search within those neighborhoods, reducing the search space dramatically.

Despite these improvements, all score-based methods share a fundamental limitation: they optimize a criterion that measures how well the graph explains the observed data, not how well it predicts the effects of interventions. A graph that scores well under BIC may still make systematically wrong predictions about what happens when a variable is manipulated. The gap between observational fit and interventional validity is the central unsolved problem in causal discovery, and no scoring criterion currently closes it. GES finds the graph that best describes the data. It does not — and cannot — find the graph that best describes the world's causal mechanisms.

The assumption that the best-fitting graph is the true causal graph is not merely optimistic; it is a category error that conflates statistical explanation with causal mechanism. GES optimizes a score, but the score knows nothing about interventions, manipulations, or counterfactuals. The graph it returns is a statistical artifact dressed in causal clothing — useful for prediction, dangerous for policy, and silent on the question that matters most: what would happen if we changed something?