Score-based search#

Cover: two summits drawn in contour lines, one dotted trail ending on each, drawn in navy lines

Shu Wan · October 12, 2026 · Andrey 0.3.0

A score-based method searches for the graph that best explains the data according to a score. This release adds Tabu search and XGES. From 0.3.0, both are supported, as is hill climbing. Hill climbing also returns the same graphs in less time.

Below, we explain why a search can stop at the wrong graph. We run GES, hill climbing, Tabu search, and XGES on one small dataset, then report benchmark results.

Searching by a score#

Andrey’s score-based methods rate a graph by its BIC (Bayesian information criterion). For each variable, the BIC measures how much variance its parents in the graph leave unexplained. It adds a penalty for each parent. A lower score is better. This BIC assumes linear relations with Gaussian noise. The methods also assume no hidden common causes.

The number of graphs grows faster than exponentially with the number of variables, so a search cannot score them all. A greedy search starts from the empty graph. It takes the move that improves the score most, such as adding, removing, or reversing one edge. It stops when no move improves the score. That graph is a local optimum: no single move improves it. A better graph can lie a few moves away, past graphs that score worse. A search that stops there can miss edges or point them the wrong way.

The four methods handle local optima differently:

Hill climbing searches over DAGs (directed acyclic graphs) and stops at the first local optimum.
Tabu search takes the same moves. At a local optimum, it takes the best move even when the score gets worse, and keeps going. It never returns to a recently visited graph, so it cannot step straight back. It returns the best graph it visited, so with the same settings its score is never worse than hill climbing’s.
GES (greedy equivalence search) searches over equivalence classes: sets of graphs that fit any data equally well. It adds edges while the score improves, then removes edges while the score improves.
XGES (extremely greedy equivalence search) searches the same classes with GES’s moves and edge reversals, in a different order. Each step deletes an edge if that improves the score. Otherwise, it tries reversing an edge, then adding one. Its extended search then deletes each edge of the result in turn, forbids adding it back, and searches again. It keeps any result with a better score, which lets it leave a local optimum.

Methods#

Before each release, we benchmark each supported method against another package and check its results on known graphs. Tabu search and XGES are new in this release.

Method	Status	Searches over	Returns
GES	Supported	Equivalence classes	A CPDAG and its BIC score
XGES	Supported	Equivalence classes	A CPDAG and its BIC score
Hill climbing	Supported	DAGs	The CPDAG of the final DAG, and its score
Tabu search	Supported	DAGs	The CPDAG of the best DAG visited, and its score
GIES	Experimental	Equivalence classes	A CPDAG and its BIC score; without interventions, the same search as GES
Exact search	Experimental	Every DAG, so only a few variables	One DAG with the best BIC score
CALM	Experimental	A penalized likelihood, by continuous optimization	A weighted DAG, without a score

Choose a method for your data:

XGES for continuous data that roughly fit the BIC’s assumptions. In our benchmarks, its graphs scored better and had fewer errors than GES’s (see Benchmarks). Set extended_search=False for a faster fit that can stop at a local optimum.
GES for the same data, as a well-studied reference.
Hill climbing as a fast baseline over DAGs, and Tabu search when hill climbing may stop early. Both take max_iter, a move limit.
Exact search to find the best-scoring graph on a few variables.
CALM to try continuous optimization that returns edge weights. You need the torch extra.

BOSS and GRaSP also minimize the BIC but search over orders of the variables. These are Andrey’s permutation-based methods. When hidden common causes are plausible, use the methods in the 0.2.0 post.

Reading a CPDAG#

GES, XGES, hill climbing, Tabu search, and GIES all return a CPDAG (completed partially directed acyclic graph). You can find its BIC score in metadata["score"]. A CPDAG represents an equivalence class:

x -> y: every graph in the class has x causing y.
x -- y: the class has graphs with x -> y and graphs with x <- y. These fit the data equally well, so the data cannot orient this edge.

See Graph types for details.

Example#

Here x0 causes x1, and x0, x1, and x2 cause x3. The relations are linear. The noise is Gaussian. We chose this model because GES and hill climbing stop early on it.

example.py#

import numpy as np
import pandas as pd

import andrey

# x0 causes x1, and x0, x1, and x2 cause x3.
rng = np.random.default_rng(0)
e0, e1, e2, e3 = rng.standard_normal((4, 500))
x0, x2 = e0, e2
x1 = -0.8 * x0 + e1
x3 = 0.8 * x0 - x1 + x2 + e3
df = pd.DataFrame({"x0": x0, "x1": x1, "x2": x2, "x3": x3})

methods = (andrey.ges, andrey.hc, andrey.tabu, andrey.xges)
print(*(method(df) for method in methods), sep="\n\n")

# For comparison: XGES without its extended search.
print()
print(andrey.xges(df, extended_search=False))

What each search returns

True graphthe model behind the data

GESscore 18.22, a local optimum

Hill climbingscore 18.22, a local optimum

Tabu searchscore 15.11, the true graph

XGESscore 15.11, the true graph

Every node in the same place; lower scores are better. GES and hill climbing stop at the same graph: x2 -> x0 (cobalt) is not in the true graph, x3 -> x0 (cobalt) points the wrong way, and x0 -- x1 is missing. Tabu search and XGES return the true graph's equivalence class, which leaves x0 -- x1 (amber) undirected.

GES and hill climbing stop at the same graph, with a score of 18.22. It has x2 -> x0, an edge absent from the true graph. It also has x3 -> x0, which points the wrong way. It misses x0 -- x1.
Tabu search and XGES return the true graph’s equivalence class, with a lower score of 15.11. The edge x0 -- x1 stays undirected. The true graph and the same graph with x1 -> x0 are equivalent, so they fit any data equally well.
XGES without its extended search returns GES’s graph (the last result below). Here, the extended search finds the better graph.

The script prints each result in full:

example.py#

GES  cpdag  |  4 nodes  |  4 edges (4 directed)

  x2 -> x0
  x3 -> x0
  x1 -> x3
  x2 -> x3

  score: 18.22

HC  cpdag  |  4 nodes  |  4 edges (4 directed)

  x2 -> x0
  x3 -> x0
  x1 -> x3
  x2 -> x3

  score: 18.22

Tabu  cpdag  |  4 nodes  |  4 edges (1 undirected, 3 directed)

  x0 -- x1
  x0 -> x3
  x1 -> x3
  x2 -> x3

  score: 15.11

XGES  cpdag  |  4 nodes  |  4 edges (1 undirected, 3 directed)

  x0 -- x1
  x0 -> x3
  x1 -> x3
  x2 -> x3

  score: 15.11

XGES  cpdag  |  4 nodes  |  4 edges (4 directed)

  x2 -> x0
  x3 -> x0
  x1 -> x3
  x2 -> x3

  score: 18.22

Benchmarks#

We compared XGES with xges, a Python package that implements it, and Tabu search and hill climbing with bnlearn, an R package. The data are linear-Gaussian, simulated from random graphs with ten rows per variable.

Method	Compared with	Andrey’s speedup	Same graph
XGES	xges	up to 140x	on every dataset
Tabu search	bnlearn	up to 561x	on most datasets
Hill climbing	bnlearn	up to 906x	on most datasets

The 0.3.0 release card reports every measurement, with the sizes, machines, and settings. Hill climbing ran to a local optimum and Tabu search until it stopped on its own, both with no move limit. Without the extended search, XGES still returns the same graph as xges on every dataset, and runs faster at every size.

Speedup over xges and bnlearnRelease card

XGESTabu searchHill climbing

25 variables3.95x

50 variables10.9x

100 variables43.2x

200 variables140x

10 variables2.54x

20 variables2.38x

50 variables5.63x

100 variables16.6x

200 variables55.3x

400 variables176x

800 variables561x

10 variables5.27x

20 variables3.60x

50 variables6.13x

100 variables19.3x

200 variables70.6x

400 variables231x

800 variables906x

Each bar is the other package's time divided by Andrey's on the same dataset, the median over five datasets: xges for XGES, on 1 core per fit, and bnlearn for Tabu search and hill climbing, on 4 cores. Every graph has a mean degree of 2. The bars are on a log scale, so equal steps are equal factors; each method's bars share its own scale.

On these data, XGES’s graphs scored better than GES’s and had fewer errors, at every size. On the denser graphs, the extended search cut XGES’s errors at every size, nearly by half at 50 variables.

Agreement between packages does not establish accuracy. From 50 variables on, Tabu search’s and hill climbing’s graphs have more errors than the empty graph, in both packages. Tabu search finds better-scoring graphs than hill climbing at every size, yet at 400 variables its graphs have more errors. A better score is not always a better graph.

On the sparser graphs, XGES’s graphs score better than the true graph at every size. With ten rows per variable, the best-scoring graph is not the true one. A larger lambda_value penalizes each parent more and favors sparser graphs.

Errors against the true graph

XGESMean degree 4: the fewest errors at every size

XGESWithout extended searchGESEmpty graph

Tabu search and hill climbingMean degree 2: more errors than the empty graph from 50 variables

Tabu searchHill climbingEmpty graphMore errors than the empty graph

The median over five datasets per size of the structural Hamming distance (SHD) to the true graph's equivalence class: the edges added, missed, or misoriented. Lower is better. XGES returns the same graphs as xges, with and without the extended search, so each shares one line. Tabu search and hill climbing are Andrey's; bnlearn's medians are within one error of them at every size.

Andrey alone also ran XGES at up to 1,000 variables, and Tabu search and hill climbing at up to 3,200. On the sparser graphs, their graphs at these sizes have more errors than the empty graph.

Speed and accuracy depend on your data, settings, and hardware.

Other highlights#

Faster hill climbing. Hill climbing caches the score change for each candidate move between steps. It recomputes only the moves a step changes. It returns the same graphs as before in less time.
Hill climbing runs in one process. Its worker processes were slower at every measured size. We removed them, along with ANDREY_HC_PARALLEL_MIN_WORK and andrey calibrate --method hc. This change breaks scripts that set either one. ANDREY_NUM_WORKERS still sets the workers for GES, GIES, and GFCI.
XGES without the extended search. andrey.xges(data, extended_search=False) returns the graph where the first search stops. On the sparser graphs at 200 variables, it took a tenth of the time of the full search.
Shorter summaries. Since 0.2.1, a result’s summary shows the length of a long metadata list instead of printing it in full.

For more details, read the changelog.

Try it#

pip install -U andrey-core

The GES quickstart notebook fits GES on a small chain. You can open it in Colab and replace andrey.ges with andrey.xges, andrey.tabu, or andrey.hc. Then try the methods on your own data.

Help us build it#

Andrey is in alpha, and the API may change between releases. When you try it on your own data, tell us what breaks or which method you need. We also welcome pull requests. The contributing guide explains how you can set up.

Hidden common causes Pairwise direction