This card maps, for each supported method, the problems it can handle: those it finishes within
the cap and solves with fewer errors than the empty graph. It measures Andrey alone, on the 0.9.0
code, with no other package. Each boundary is a reference for the measured conditions, not a hard
limit; it depends on the data, settings, and hardware.
How far each method goes. At 2,000 samples and a mean degree of 2, every size up to these
finished and beat the empty graph: BOSS 1,600 variables; GRaSP 800; PC, CALM, and DirectLiNGAM 400;
GES, GIES, and XGES 200 (400 with 10,000 samples); CD-NOD, tabu search, and hill climbing 100;
ICA-LiNGAM 50; exact search 22. The post’s table gives 500
and 10,000 samples, and the maps below every size.
What stops them. Most score-based searches stop on accuracy, and reach further with more
samples. The permutation-based searches, exact search, and CALM stop on time. PC stops on accuracy.
Inside the boundary. A size, a number of variables with a number of samples and a mean degree,
is inside a method’s boundary when it is through, fewer than 3 of its fits cut by the time cap, the
memory cap, or an error, and the median errors of its finished fits are fewer than the empty
graph’s. A fit that did not finish never counts as an empty graph. A ladder’s boundary is the
largest size up to which every size is inside.
How a ladder ends. A ladder steps the number of variables on one setting until it stops: on
time, memory, or an error (3 fits of a size cut), past the accuracy boundary (two sizes in a row
that do not beat the empty graph), or at its last planned size. Larger sizes past the accuracy
boundary cost compute and tell you nothing more. Seven ladders ran past it before the rule, and
keep those sizes, marked.
What a boundary is not. Each boundary is a reference measured under the conditions below: our
graph and data generators, the listed sizes and densities, each method’s settings as listed under
Reproduce, and the listed machines. Other graphs, data, settings, or hardware move
it. It is not a guarantee that a method fails past it, or succeeds before it.
Data. Each method runs on the data its release card used: Erdos-Renyi graphs with linear
relations and Gaussian noise for the Gaussian searches, with non-Gaussian noise for the LiNGAM
methods; for RCD and BottomUpParceLiNGAM, one node in five is hidden (at least one), the number of
variables counts the hidden ones, and the errors are against the true PAG of the observed nodes; for
GIES, 40% of the variables get single-variable interventions, with the samples split evenly between
observation and each intervention, so the samples per setting shrink as the variables grow. Each
ladder’s label names its setting.
Two maps. The size map: variables from 20, doubling, by 500, 2,000, and 10,000 samples, with a
mean degree of 2. The density map: the same variables by a mean degree of 1, 2, 4, and 8, with
2,000 samples. Exact search runs from 10 variables.
Datasets. 5 datasets per size, one per seed, 10 where the median errors were within 10% of the
empty graph’s, and 20 per size for the pairwise methods. A size stops after 3 fits that did not
finish (on time, memory, or an error), so a cut size lists 3 or 4 datasets. For RCD and
BottomUpParceLiNGAM, a seed whose graph has too few nodes with two or more children to hide is
skipped, so a size can have fewer datasets.
Errors. The structural Hamming distance against the true graph in the form each method
returns: the CPDAG for the constraint-based, score-based, permutation-based, and LiNGAM searches,
with a DAG estimate (from CALM, exact search, hill climbing, and tabu search) scored against its
equivalence class; the PAG, marks included, for FCI and GFCI; the true PAG of the observed nodes,
endpoint by endpoint, for RCD and BottomUpParceLiNGAM; and the time-series graph for PCMCI, PCMCI+,
and LPCMCI. F1 for VARMA-LiNGAM and LongitudinalLiNGAM, the share of pairs with the right direction
for ANM and PNL, and the adjusted Rand index of the indicator clusters for GIN. The empty graph’s
errors are the number of true edges.
Limits. A one-hour wall cap and a 28,000 MB memory cap per fit, on 4 CPUs: almost all on an AMD
EPYC 7713, some on an AMD EPYC 9534 or an Intel Xeon Gold 6542Y. Nine sizes ran on two CPU models;
their errors are the median over every finished fit, and they quote no time.
Columns: the number of variables. Color: errors as a share of the empty graph's, the stronger the fewer; gray does no better than the empty graph. × stopped at the time cap, ■ at the memory cap, ! failed, ○ past the accuracy boundary. The outline is the boundary: in each row, the sizes before the first that does not finish or does not beat the empty graph. A cell's tip gives its errors as a share of the empty graph's: on a denser graph the empty graph makes more errors, so beating it says less.
Columns: the number of variables. Color: errors as a share of the empty graph's, the stronger the fewer; gray does no better than the empty graph. × stopped at the time cap, ■ at the memory cap, ! failed, ○ past the accuracy boundary. The outline is the boundary: in each row, the sizes before the first that does not finish or does not beat the empty graph. A cell's tip gives its errors as a share of the empty graph's: on a denser graph the empty graph makes more errors, so beating it says less.
Columns: the number of variables. Color: errors as a share of the empty graph's, the stronger the fewer; gray does no better than the empty graph. × stopped at the time cap, ■ at the memory cap, ! failed, ○ past the accuracy boundary. The outline is the boundary: in each row, the sizes before the first that does not finish or does not beat the empty graph. A cell's tip gives its errors as a share of the empty graph's: on a denser graph the empty graph makes more errors, so beating it says less.
Columns: the number of variables. Color: errors as a share of the empty graph's, the stronger the fewer; gray does no better than the empty graph. × stopped at the time cap, ■ at the memory cap, ! failed, ○ past the accuracy boundary. The outline is the boundary: in each row, the sizes before the first that does not finish or does not beat the empty graph. A cell's tip gives its errors as a share of the empty graph's: on a denser graph the empty graph makes more errors, so beating it says less.
FCI and GFCI run with the samples growing with the variables (10 or 50 samples per variable). The
latent-variable, time-series, and pairwise methods run on their own axes. Granger is not measured in
this release: its data grow denser as the variables grow, so its sizes are not comparable. PCMCI+’s
ladders end at 320 variables, where the campaign’s generator found no stationary series; 0.10.0’s
generator draws one.
The other methods' boundaries
Max size
Ended
Constraint-based
FCImean degree 2, 10 samples per variable
200 variables
past the accuracy boundary, 800 variables
FCImean degree 2, 50 samples per variable
200 variables
past the accuracy boundary, 800 variables
FCImean degree 4, 10 samples per variable
1,600 variables
time cap, 3,200 variables
FCImean degree 4, 50 samples per variable
1,600 variables
time cap, 3,200 variables
GFCImean degree 2, 10 samples per variable
1,600 variables
time cap, 3,200 variables
GFCImean degree 2, 50 samples per variable
3,200 variables
largest size measured, 3,200 variables
GFCImean degree 4, 10 samples per variable
1,600 variables
time cap, 3,200 variables
GFCImean degree 4, 50 samples per variable
3,200 variables
largest size measured, 3,200 variables
Latent variables
BottomUpParceLiNGAMmean degree 2, 10,000 samples
10 variables
past the accuracy boundary, 20 variables
BottomUpParceLiNGAMmean degree 2, 2,000 samples
10 variables
past the accuracy boundary, 20 variables
BottomUpParceLiNGAMmean degree 4, 10,000 samples
-
time cap, 30 variables
BottomUpParceLiNGAMmean degree 4, 2,000 samples
-
past the accuracy boundary, 20 variables
GIN1,000 samples, 3 observed indicators per latent variable
16 latent variables
largest size measured, 16 latent variables
GIN5,000 samples, 3 observed indicators per latent variable
8 latent variables
time cap, 12 latent variables
RCDmean degree 2, 10,000 samples
30 variables
memory cap, 60 variables
RCDmean degree 2, 2,000 samples
-
past the accuracy boundary, 60 variables
RCDmean degree 4, 10,000 samples
-
time cap, 30 variables
RCDmean degree 4, 2,000 samples
-
past the accuracy boundary, 10 variables
Time series
LongitudinalLiNGAM2,000 units, each observed at 20 time points
40 variables
largest size measured, 40 variables
LongitudinalLiNGAM500 units, each observed at 20 time points
40 variables
largest size measured, 40 variables
LPCMCIseries of max(1,000, 4·τ·(d+1)) time steps, τ = 3
40 variables
time cap, 80 variables
LPCMCIseries of 5·max(1,000, 4·τ·(d+1)) time steps (five times as long), τ = 3
40 variables
time cap, 80 variables
PCMCIseries of max(1,000, 4·τ·(d+1)) time steps, τ = 2
20 variables
past the accuracy boundary, 80 variables
PCMCIseries of 5·max(1,000, 4·τ·(d+1)) time steps (five times as long), τ = 2
20 variables
past the accuracy boundary, 80 variables
PCMCI+series of max(1,000, 4·τ·(d+1)) time steps, τ = 5
160 variables
no data could be generated at 320 variables
PCMCI+series of 5·max(1,000, 4·τ·(d+1)) time steps (five times as long), τ = 5
160 variables
no data could be generated at 320 variables
VARMA-LiNGAMseries of max(1,000, 4·τ·(d+1)) time steps, τ = 1
40 variables
time cap, 80 variables
VARMA-LiNGAMseries of 5·max(1,000, 4·τ·(d+1)) time steps (five times as long), τ = 1
20 variables
time cap, 40 variables
Pairwise
ANM2 variables, samples doubling from 1,000
16,000 samples
memory cap, 32,000 samples
PNL2 variables, samples doubling from 1,000
32,000 samples
memory cap, 64,000 samples
Max size: the largest size up to which every size finished and beat the empty graph. For the latent-variable and LPCMCI ladders, the variables include the hidden ones.
Each table answers one question: on the same datasets, how fast and how accurate is Andrey’s PC,
GES, BOSS, GRaSP, and FCI against Tetrad 7.6.10’s? Both run with the same score or test, penalty,
and depth, on the same node, with one worker; Tetrad’s time is its search inside the Java virtual
machine, without its start or the data loading. Each time is the median over 5 datasets. The errors
are the mean SHD over every dataset of the matched rerun (Datasets), and for FCI the median over its
5.
PC against Tetrad's PC
Variables
Andrey (s)
Tetrad (s)
Faster
Andrey errors
Tetrad errors
Datasets
20200 samples
0.00390
0.0248
6.28x
8.9
10.2
20
50500 samples
0.0243
0.0958
3.95x
17.9
21.2
30
1001,000 samples
0.0313
0.328
10.5x
39.4
47.6
20
2002,000 samples
0.108
1.62
15.0x
98.9
111.1
10
GES against Tetrad's FGES
Variables
Andrey (s)
Tetrad (s)
Faster
Andrey errors
Tetrad errors
Datasets
20200 samples
0.0286
0.0944
3.31x
10.2
9.9
20
50500 samples
0.128
0.300
2.35x
36.9
35.8
20
1001,000 samples
0.253
1.23
4.88x
80.6
78.2
20
2002,000 samples
0.964
10.9
11.4x
203.8
198.7
10
BOSS against Tetrad's BOSS
Variables
Andrey (s)
Tetrad (s)
Faster
Andrey errors
Tetrad errors
Datasets
20200 samples
0.0260
0.0591
2.27x
3.0
4.0
20
50500 samples
0.134
0.248
1.85x
4.2
4.7
20
1001,000 samples
0.437
0.869
1.99x
6.7
7.5
20
2002,000 samples
1.66
4.03
2.42x
8.8
3.0
10
GRaSP against Tetrad's GRaSP
Variables
Andrey (s)
Tetrad (s)
Faster
Andrey errors
Tetrad errors
Datasets
20200 samples
0.0236
0.0268
1.13x
5.3
4.3
20
50500 samples
0.138
0.182
1.32x
5.2
1.6
20
1001,000 samples
0.619
2.98
4.82x
7.8
2.6
20
2002,000 samples
5.13
170
33.2x
12.2
3.5
10
FCI against Tetrad's FCI
Variables
Andrey (s)
Tetrad (s)
Faster
Andrey errors
Tetrad errors
Datasets
20200 samples
0.00440
0.0388
8.80x
14
15
5
50500 samples
0.0231
0.102
4.43x
28
32
5
1001,000 samples
0.115
0.321
2.80x
70
77
5
2002,000 samples
0.577
1.45
2.51x
218
227
5
Where the errors differ, the cause, from a matched rerun on more datasets:
PC. The two find the same skeleton on every dataset and differ only in how they orient
colliders: Tetrad keeps the first separating set it finds, and Andrey the union of the sets of
that size. Andrey makes fewer errors at every size.
GES. At the BIC penalty both packages use by default, both searches return graphs denser than
the truth on these data, and Andrey’s single pass and FGES’s three passes stop in different local
optima. With a penalty of 2 on both sides, the errors are equal within the run-to-run spread.
BOSS. Each package runs one start of a local search: Tetrad from the data’s column order,
Andrey from a seeded order, and each reaches the true graph on some datasets and not others. Up
to 100 variables the errors are equal within the run-to-run spread. At 200 variables Tetrad’s
start from the column order has fewer errors (3.0 against 8.8); started from random orders, as
Andrey’s search is, Tetrad’s mean is 7.5, within the spread of Andrey’s.
GRaSP. A difference in search quality, not in the depth or the score. At 100 variables,
Andrey’s search ends at a worse BIC than the true graph’s in 58% to 75% of fits, and Tetrad’s in
45% to 55%, so Andrey makes more errors; the gap sits in the fits that go furthest wrong.
Every method’s docstring gives its measured boundary in its Limitations paragraph: how far
it beat the empty graph and how far it finished, on each setting measured here.
With several workers, the worker pool starts when TMPDIR is on a file system that rejects the
forkserver’s socket, such as a cluster’s parallel file system, where ges, gfci, and the
skeleton search raised OSError. Results do not change.
categorical=[] is accepted by every test and score, and every score search takes both names of
the linear-Gaussian BIC, "local_score_BIC" and "local_score_BIC_from_cov".
andrey.data.storage and the data extra are removed.
A reference, not a hard limit. The boundaries depend on the graph and data generators, the
densities, each method’s settings, and the machine; see What a boundary is not.
Settings. Most methods run at their defaults, but not all: BOSS and GRaSP run with a BIC
penalty of 4, GES with a limit of 4 parents, hill climbing and tabu search with up to 100,000
iterations, and the time-series methods with their own lag window; Reproduce lists
every setting. A smaller alpha, a max_depth, or another score can move a boundary either way.
The cap. A longer cap moves a time boundary to the right; it does not move an accuracy
boundary.
Every size can be rerun from the protocol on this card. Each fit is one call of the method on one
dataset, with a 3,600 s wall cap, a 28,000 MB memory cap, and 4 cores. The datasets per size and the
stop rules are under Method and The boundary. Each method runs with the
settings below, passed as keyword arguments, and every setting not listed is at its default; each
dataset is drawn by the call below, from Andrey or the repository’s benchmarks/ folder, with its
variables, samples, density, and seed.
Each method's settings
Method
Settings
PC
defaults
FCI
defaults
GFCI
defaults
CD-NOD
defaults
GES
max_parents=4, score_func='local_score_BIC'max_parents as the measured build (8a134cd) applied it: a node holding 4 parents gains no new parent in the forward phase, and one move can still give a node more; on 0.10.0, andrey.ges(max_parents=4) caps every DAG of the returned class at 4 parents, a stricter rule.
