GES, BOSS and GRaSP (score-based discovery)

Score-based causal discovery: how GES adds and removes links to improve a score, how BOSS and GRaSP search over orderings instead, what they assume and when to choose them.

In short

Score-based methods give every candidate graph a score for how well it explains the data, with a penalty for each extra link, and search for the graph with the best score. In UCMT Labs the score is BIC (the Bayesian information criterion), from the causal-learn library.

GES: add, then remove

GES (Greedy Equivalence Search) works in two passes over groups of graphs that the data cannot tell apart (equivalence classes):

  1. Forward: starting from an empty graph, add the single link that improves the score most. Repeat until no addition helps.
  2. Backward: remove the single link whose removal improves the score most. Repeat until no removal helps.

With enough data, and when its assumptions hold, this simple greedy search reaches the right equivalence class.

The two passes of GES

The two passes of GES

Hand-drawn sketch of GES: start from an empty graph, add the links that improve the score most one at a time, then remove the links whose removal improves it

BOSS and GRaSP: search over orderings

BOSS (best-order score search) and GRaSP (greedy relaxations of the sparsest permutation) search over orders of the variables rather than over graphs. For each order, the best graph consistent with it is easy to score; the method moves variables around the order to find the one whose graph is sparsest and scores best. On tables with more variables they can find good graphs where a greedy search over graphs gets stuck.

What they assume

  • No hidden common causes (for that, see FCI).
  • A score that fits the data: BIC suits linear relationships with bell-shaped noise.
  • No feedback loops.

How to read the output

Like PC, they return a partially directed graph: arrows where the data decides the direction, undirected links where it cannot. They report no confidence per link.

When to use them

  • A second opinion next to PC: a different strategy (scores instead of tests) with similar assumptions.
  • Tables of counts or categories coded as numbers, where independence tests are fragile; UCMT Labs' data check may suggest GES for such tables.
  • BOSS or GRaSP for larger tables.

Practical tips

  • Remove IDs and duplicate columns first: they distort the score.
  • If PC and GES disagree on a link, that link is sensitive to assumptions; check it before acting.
  • Results can change when you add a column, because the best-scoring graph is chosen for the whole table.