Mapping and Advancing the Scalability-Accuracy Frontier of Nonlinear Causal Discovery

Hendrik Suhr; Sascha Xu; Jilles Vreeken

cs.LGOct 2, 2026

Mapping and Advancing the Scalability-Accuracy Frontier of Nonlinear Causal Discovery

Authors: Hendrik Suhr, Sascha Xu, Jilles Vreeken

Organizations: CISPA Helmholtz Center for Information Security

Abstract

Scalable nonlinear causal discovery requires methods that combine flexible mechanism estimators with efficient search over large graph spaces. Several algorithmic families have been proposed to address this challenge, yet their accuracy-runtime trade-offs remain poorly understood. We empirically compare the four major approaches: differentiable structure learning, amortized structure learning, score-matching, and combinatorial search. Our results reveal complementary bottlenecks: differentiable and amortized methods scale well but exhibit an accuracy gap, score-matching methods can be accurate in low dimensions but degrade quickly for increasing feature sizes, and combinatorial methods remain accurate but are slowed by repeated and redundant local scoring. Motivated by this bottleneck, we develop SPADE, a spline-based score-evaluation scheme that compiles sufficient statistics once and reuses them throughout combinatorial search. Under bounded indegree, its Gaussian variant reduces algorithmic complexity from O(nd^3) to O(nd^2+d^3). Empirically, SPADE shifts the observed scalability-accuracy frontier by orders of magnitude: it solves 100-variable problems with 160K samples in seconds and 1600-variable problems with 2.5K samples in minutes, while retaining high structural accuracy across synthetic and real-world benchmarks. These results reveal a substantial shift in the practical scale of combinatorial search and highlight the importance of evaluating scalable causal-discovery methods along the full accuracy-runtime frontier.

Figures & tables

Panel of Figure 1 — Figure 1: Scalability–accuracy Pareto comparison on the synthetic qualitative benchmark, with F1 scores and runtimes averaged over 480 datasets (left), and on the real-world Causal Chamber benchmark (right).

Panel of Figure 2 — Figure 2: Scalability–accuracy trade-offs. Runtime and F1 score are shown in separate panels with matched dimensions. Dotted lines indicate the 24h timeout. Results are averaged across 5 seeds, shaded regions correspond to standard errors.

Panel of Figure 3 — Figure 3: Scalability in features and samples on clean data. Runtime and F1 score of the obtained DAG are shown in separate panels with matched dimensions. Results are averaged across 5 seeds, shaded regions correspond to standard errors.

Figure 4: Qualitative performance on synthetic datasets with

n=1000

in F1 score. Each spoke isolates the respective condition while marginalizing over remaining conditions.

Appendix figures & tables46 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 5 — Figure 5: Scalability in features and samples on heterogeneous data. Runtime and F1 score of the obtained DAG are shown in separate panels with matched dimensions. Results are averaged across 5 seeds, shaded regions correspond to standard errors.

Figure 6: The mechanisms learned by differentiable structure learning methods do not rank the true DAG the highest reliably.

Panel of Figure 7 — Figure 7: Runtime ablation of the cached sufficient-statistics implementation. Each cached variant is compared to an otherwise identical variant that refits the additive-spline score from scratch. Results are averaged across 5 seeds, and shaded regions show standard errors.

Figure 8: Qualitative performance on synthetic datasets with

n=2000

in F1 score. Each spoke isolates the respective condition while marginalizing over remaining conditions.

method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
Spade-Hist	5	0.785 $\pm$ 0.023	0.993 $\pm$ 0.007	0.653 $\pm$ 0.033	0.761 $\pm$ 0.015	0.964 $\pm$ 0.019	0.632 $\pm$ 0.025	14.2 $\pm$ 0.9	0.068 $\pm$ 0.018	1.95 $\pm$ 0.06	25.0 $\pm$ 1.4
Spade-Gauss	5	0.785 $\pm$ 0.020	1.000	0.647 $\pm$ 0.027	0.785 $\pm$ 0.020	1.000	0.647 $\pm$ 0.027	13.4 $\pm$ 1.0	0.047 $\pm$ 0.015	0.16 $\pm$ 0.01	24.6 $\pm$ 1.0
Spade-Hist-NoCache	5	0.785 $\pm$ 0.023	0.993 $\pm$ 0.007	0.653 $\pm$ 0.033	0.761 $\pm$ 0.015	0.964 $\pm$ 0.019	0.632 $\pm$ 0.025	14.2 $\pm$ 0.9	0.068 $\pm$ 0.018	3.54 $\pm$ 0.22	25.0 $\pm$ 1.4
Spade-Gauss-NoCache	5	0.785 $\pm$ 0.020	1.000	0.647 $\pm$ 0.027	0.785 $\pm$ 0.020	1.000	0.647 $\pm$ 0.027	13.4 $\pm$ 1.0	0.047 $\pm$ 0.015	3.75 $\pm$ 0.15	24.6 $\pm$ 1.0
Topic	5	0.791 $\pm$ 0.024	0.864 $\pm$ 0.023	0.732 $\pm$ 0.028	0.729 $\pm$ 0.027	0.795 $\pm$ 0.024	0.674 $\pm$ 0.031	16.8 $\pm$ 1.6	0.174 $\pm$ 0.040	39.21 $\pm$ 1.81	32.2 $\pm$ 1.0
Cam	5	0.809 $\pm$ 0.017	0.698 $\pm$ 0.021	0.963 $\pm$ 0.016	0.791 $\pm$ 0.023	0.682 $\pm$ 0.023	0.942 $\pm$ 0.027	18.2 $\pm$ 2.0	0.021 $\pm$ 0.015	918.03 $\pm$ 3.79	52.6 $\pm$ 1.5

Appendix

Table 1: Controlled scalability feature-size experiment. Graph metrics are computed from stored DAG outputs where available; plot-only aggregate rows retain only reported metrics (n_features=25).

method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
Spade-Hist	5	0.796 $\pm$ 0.022	0.992 $\pm$ 0.008	0.667 $\pm$ 0.029	0.777 $\pm$ 0.032	0.966 $\pm$ 0.023	0.651 $\pm$ 0.036	26.6 $\pm$ 3.0	0.080 $\pm$ 0.025	3.24 $\pm$ 0.10	50.4 $\pm$ 2.0
Spade-Gauss	5	0.810 $\pm$ 0.024	0.996 $\pm$ 0.004	0.685 $\pm$ 0.033	0.807 $\pm$ 0.026	0.991 $\pm$ 0.009	0.683 $\pm$ 0.034	24.0 $\pm$ 2.7	0.021 $\pm$ 0.008	0.55 $\pm$ 0.01	51.6 $\pm$ 2.4
Spade-Hist-NoCache	5	0.797 $\pm$ 0.021	0.996 $\pm$ 0.004	0.667 $\pm$ 0.029	0.778 $\pm$ 0.026	0.971 $\pm$ 0.011	0.651 $\pm$ 0.033	26.4 $\pm$ 2.5	0.072 $\pm$ 0.015	10.42 $\pm$ 0.45	50.2 $\pm$ 2.1
Spade-Gauss-NoCache	5	0.810 $\pm$ 0.024	0.996 $\pm$ 0.004	0.685 $\pm$ 0.033	0.807 $\pm$ 0.026	0.991 $\pm$ 0.009	0.683 $\pm$ 0.034	24.0 $\pm$ 2.7	0.021 $\pm$ 0.008	12.52 $\pm$ 0.40	51.6 $\pm$ 2.4
Topic	5	0.771 $\pm$ 0.021	0.824 $\pm$ 0.018	0.725 $\pm$ 0.028	0.740 $\pm$ 0.017	0.792 $\pm$ 0.018	0.696 $\pm$ 0.023	34.4 $\pm$ 2.5	0.072 $\pm$ 0.018	162.32 $\pm$ 4.47	66.0 $\pm$ 2.1
Cam	5	0.682 $\pm$ 0.022	0.533 $\pm$ 0.025	0.949 $\pm$ 0.011	0.661 $\pm$ 0.025	0.517 $\pm$ 0.027	0.920 $\pm$ 0.019	69.4 $\pm$ 6.5	0.045 $\pm$ 0.013	14909.67 $\pm$ 175.55	134.6 $\pm$ 5.6

Appendix

Table 2: Controlled scalability feature-size experiment. Graph metrics are computed from stored DAG outputs where available; plot-only aggregate rows retain only reported metrics (n_features=50).

method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
Spade-Hist	5	0.786 $\pm$ 0.011	0.988 $\pm$ 0.004	0.653 $\pm$ 0.016	0.746 $\pm$ 0.012	0.939 $\pm$ 0.017	0.620 $\pm$ 0.014	58.2 $\pm$ 1.9	0.140 $\pm$ 0.013	8.56 $\pm$ 0.28	99.2 $\pm$ 2.6
Spade-Gauss	5	0.783 $\pm$ 0.014	0.996 $\pm$ 0.003	0.645 $\pm$ 0.019	0.776 $\pm$ 0.012	0.988 $\pm$ 0.002	0.640 $\pm$ 0.017	54.4 $\pm$ 2.7	0.052 $\pm$ 0.011	1.90 $\pm$ 0.06	97.2 $\pm$ 2.7
Spade-Hist-NoCache	5	0.788 $\pm$ 0.013	0.990 $\pm$ 0.003	0.656 $\pm$ 0.019	0.755 $\pm$ 0.014	0.948 $\pm$ 0.012	0.628 $\pm$ 0.018	56.8 $\pm$ 2.6	0.132 $\pm$ 0.010	35.79 $\pm$ 1.24	99.4 $\pm$ 2.9
Spade-Gauss-NoCache	5	0.786 $\pm$ 0.010	0.996 $\pm$ 0.003	0.649 $\pm$ 0.013	0.776 $\pm$ 0.011	0.984 $\pm$ 0.005	0.641 $\pm$ 0.013	54.2 $\pm$ 2.2	0.065 $\pm$ 0.011	54.82 $\pm$ 1.61	97.8 $\pm$ 1.8
Topic	5	0.757 $\pm$ 0.010	0.811 $\pm$ 0.009	0.709 $\pm$ 0.013	0.728 $\pm$ 0.010	0.780 $\pm$ 0.008	0.683 $\pm$ 0.012	72.4 $\pm$ 2.5	0.088 $\pm$ 0.021	630.21 $\pm$ 16.82	131.2 $\pm$ 1.9
CauScale	5	0.860 $\pm$ 0.007	0.949 $\pm$ 0.007	0.787 $\pm$ 0.014	0.657 $\pm$ 0.018	0.726 $\pm$ 0.021	0.601 $\pm$ 0.018	66.2 $\pm$ 2.7	0.253 $\pm$ 0.013	6.99 $\pm$ 0.01	124.4 $\pm$ 2.9

Appendix

Table 3: Controlled scalability feature-size experiment. Graph metrics are computed from stored DAG outputs where available; plot-only aggregate rows retain only reported metrics (n_features=100).

method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
Spade-Hist	5	0.776 $\pm$ 0.011	0.988 $\pm$ 0.004	0.639 $\pm$ 0.014	0.742 $\pm$ 0.015	0.946 $\pm$ 0.012	0.611 $\pm$ 0.016	118.8 $\pm$ 5.5	0.151 $\pm$ 0.010	27.85 $\pm$ 0.38	193.8 $\pm$ 3.7
Spade-Gauss	5	0.787 $\pm$ 0.010	1.000	0.649 $\pm$ 0.014	0.779 $\pm$ 0.009	0.990 $\pm$ 0.006	0.642 $\pm$ 0.013	107.4 $\pm$ 3.8	0.089 $\pm$ 0.015	7.25 $\pm$ 0.08	194.6 $\pm$ 4.2
Spade-Hist-NoCache	5	0.775 $\pm$ 0.010	0.989 $\pm$ 0.004	0.637 $\pm$ 0.013	0.740 $\pm$ 0.013	0.944 $\pm$ 0.012	0.609 $\pm$ 0.015	119.6 $\pm$ 4.9	0.152 $\pm$ 0.008	136.26 $\pm$ 1.99	193.4 $\pm$ 3.8
Spade-Gauss-NoCache	5	0.787 $\pm$ 0.010	1.000	0.649 $\pm$ 0.014	0.779 $\pm$ 0.009	0.990 $\pm$ 0.006	0.642 $\pm$ 0.013	107.4 $\pm$ 3.8	0.089 $\pm$ 0.015	297.55 $\pm$ 4.22	194.6 $\pm$ 4.2
Topic	5	0.728 $\pm$ 0.007	0.776 $\pm$ 0.009	0.685 $\pm$ 0.007	0.699 $\pm$ 0.008	0.746 $\pm$ 0.011	0.658 $\pm$ 0.006	161.8 $\pm$ 4.5	0.105 $\pm$ 0.012	2615.19 $\pm$ 26.09	264.6 $\pm$ 2.7
CauScale	5	0.841 $\pm$ 0.013	0.951 $\pm$ 0.013	0.755 $\pm$ 0.016	0.640 $\pm$ 0.018	0.723 $\pm$ 0.015	0.575 $\pm$ 0.019	139.4 $\pm$ 7.5	0.295 $\pm$ 0.019	10.46 $\pm$ 1.61	238.2 $\pm$ 4.9

Appendix

Table 4: Controlled scalability feature-size experiment. Graph metrics are computed from stored DAG outputs where available; plot-only aggregate rows retain only reported metrics (n_features=200).

method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
Spade-Hist	5	0.782 $\pm$ 0.008	0.989 $\pm$ 0.001	0.646 $\pm$ 0.011	0.739 $\pm$ 0.007	0.936 $\pm$ 0.002	0.611 $\pm$ 0.010	237.4 $\pm$ 5.5	0.166 $\pm$ 0.010	105.26 $\pm$ 1.40	392.0 $\pm$ 6.7
Spade-Gauss	5	0.793 $\pm$ 0.006	0.997 $\pm$ 0.001	0.658 $\pm$ 0.008	0.787 $\pm$ 0.005	0.989 $\pm$ 0.001	0.653 $\pm$ 0.008	209.2 $\pm$ 4.4	0.073 $\pm$ 0.006	26.62 $\pm$ 0.29	396.0 $\pm$ 4.8
Spade-Hist-NoCache	5	0.780 $\pm$ 0.007	0.990 $\pm$ 0.001	0.644 $\pm$ 0.009	0.738 $\pm$ 0.007	0.936 $\pm$ 0.003	0.609 $\pm$ 0.009	238.4 $\pm$ 5.6	0.161 $\pm$ 0.009	533.05 $\pm$ 12.78	390.2 $\pm$ 5.6
Spade-Gauss-NoCache	5	0.793 $\pm$ 0.006	0.997 $\pm$ 0.001	0.658 $\pm$ 0.008	0.787 $\pm$ 0.005	0.989 $\pm$ 0.001	0.653 $\pm$ 0.008	209.2 $\pm$ 4.4	0.073 $\pm$ 0.006	1838.97 $\pm$ 19.86	396.0 $\pm$ 4.8
Topic	5	0.728 $\pm$ 0.008	0.769 $\pm$ 0.009	0.691 $\pm$ 0.010	0.714 $\pm$ 0.007	0.755 $\pm$ 0.008	0.678 $\pm$ 0.009	317.8 $\pm$ 7.7	0.083 $\pm$ 0.005	10821.17 $\pm$ 248.61	539.0 $\pm$ 8.4
CauScale	5	0.840 $\pm$ 0.014	0.986 $\pm$ 0.002	0.732 $\pm$ 0.020	0.639 $\pm$ 0.014	0.751 $\pm$ 0.013	0.557 $\pm$ 0.016	271.8 $\pm$ 9.9	0.302 $\pm$ 0.015	10.23 $\pm$ 1.01	445.4 $\pm$ 11.7

Appendix

Table 5: Controlled scalability feature-size experiment. Graph metrics are computed from stored DAG outputs where available; plot-only aggregate rows retain only reported metrics (n_features=400).

method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
Spade-Hist	5	0.760 $\pm$ 0.004	0.989 $\pm$ 0.002	0.618 $\pm$ 0.006	0.718 $\pm$ 0.006	0.934 $\pm$ 0.004	0.584 $\pm$ 0.007	508.0 $\pm$ 8.1	0.174 $\pm$ 0.009	386.91 $\pm$ 5.20	749.8 $\pm$ 7.1
Spade-Gauss	5	0.770 $\pm$ 0.005	0.998 $\pm$ 0.001	0.626 $\pm$ 0.007	0.761 $\pm$ 0.004	0.988 $\pm$ 0.002	0.620 $\pm$ 0.006	457.8 $\pm$ 7.2	0.089 $\pm$ 0.004	99.31 $\pm$ 1.38	753.0 $\pm$ 8.9
Spade-Hist-NoCache	5	0.761 $\pm$ 0.003	0.990 $\pm$ 0.002	0.618 $\pm$ 0.005	0.721 $\pm$ 0.004	0.938 $\pm$ 0.005	0.586 $\pm$ 0.005	504.6 $\pm$ 5.3	0.169 $\pm$ 0.007	2089.16 $\pm$ 42.92	749.8 $\pm$ 6.9
Spade-Gauss-NoCache	5	0.770 $\pm$ 0.005	0.998 $\pm$ 0.001	0.626 $\pm$ 0.007	0.761 $\pm$ 0.004	0.988 $\pm$ 0.002	0.620 $\pm$ 0.006	457.8 $\pm$ 7.2	0.089 $\pm$ 0.004	12680.18 $\pm$ 136.39	753.0 $\pm$ 8.9
Topic	5	0.701 $\pm$ 0.006	0.748 $\pm$ 0.007	0.659 $\pm$ 0.005	0.687 $\pm$ 0.005	0.733 $\pm$ 0.006	0.646 $\pm$ 0.005	691.4 $\pm$ 12.6	0.100 $\pm$ 0.005	45302.69 $\pm$ 534.96	1056.8 $\pm$ 3.4
CauScale	5	0.696 $\pm$ 0.009	0.875 $\pm$ 0.035	0.581 $\pm$ 0.013	0.479 $\pm$ 0.008	0.602 $\pm$ 0.026	0.400 $\pm$ 0.009	827.4 $\pm$ 30.2	0.391 $\pm$ 0.008	11.75 $\pm$ 0.33	804.6 $\pm$ 47.9

Appendix

Table 6: Controlled scalability feature-size experiment. Graph metrics are computed from stored DAG outputs where available; plot-only aggregate rows retain only reported metrics (n_features=800).

method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
Spade-Hist	5	0.762 $\pm$ 0.004	0.990 $\pm$ 0.002	0.620 $\pm$ 0.005	0.722 $\pm$ 0.007	0.939 $\pm$ 0.004	0.587 $\pm$ 0.007	1005.2 $\pm$ 17.1	0.174 $\pm$ 0.009	1587.04 $\pm$ 24.79	1501.8 $\pm$ 13.3
Spade-Gauss	5	0.769 $\pm$ 0.004	0.998 $\pm$ 0.001	0.625 $\pm$ 0.005	0.760 $\pm$ 0.005	0.986 $\pm$ 0.002	0.618 $\pm$ 0.006	919.6 $\pm$ 13.7	0.094 $\pm$ 0.005	427.20 $\pm$ 7.73	1503.6 $\pm$ 11.0
Spade-Hist-NoCache	5	0.760 $\pm$ 0.003	0.989 $\pm$ 0.002	0.618 $\pm$ 0.005	0.721 $\pm$ 0.006	0.938 $\pm$ 0.004	0.586 $\pm$ 0.007	1011.0 $\pm$ 15.7	0.176 $\pm$ 0.007	8415.97 $\pm$ 105.52	1498.6 $\pm$ 11.9
CauScale	5	0.611 $\pm$ 0.016	0.684 $\pm$ 0.049	0.560 $\pm$ 0.010	0.399 $\pm$ 0.014	0.447 $\pm$ 0.036	0.365 $\pm$ 0.006	2193.4 $\pm$ 149.0	0.438 $\pm$ 0.005	25.79 $\pm$ 0.98	2012.6 $\pm$ 170.4
SDCD	5	0.691 $\pm$ 0.003	0.827 $\pm$ 0.002	0.594 $\pm$ 0.005	0.588 $\pm$ 0.005	0.704 $\pm$ 0.004	0.505 $\pm$ 0.006	1485.8 $\pm$ 12.4	0.282 $\pm$ 0.008	231.34 $\pm$ 3.21	1721.6 $\pm$ 12.7
Avici	2	0.000 $\pm$ 0.000	0.500 $\pm$ 0.500	0.000 $\pm$ 0.000	0.000 $\pm$ 0.000	0.500 $\pm$ 0.500	0.000 $\pm$ 0.000	2399.5 $\pm$ 0.5	0.492 $\pm$ 0.007	2016.08 $\pm$ 34.10	0.5 $\pm$ 0.5

Appendix

Table 7: Controlled scalability feature-size experiment. Graph metrics are computed from stored DAG outputs where available; plot-only aggregate rows retain only reported metrics (n_features=1600).

method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
Spade-Hist	5	0.786 $\pm$ 0.011	0.988 $\pm$ 0.004	0.653 $\pm$ 0.016	0.746 $\pm$ 0.012	0.939 $\pm$ 0.017	0.620 $\pm$ 0.014	58.2 $\pm$ 1.9	0.140 $\pm$ 0.013	8.56 $\pm$ 0.28	99.2 $\pm$ 2.6
Spade-Gauss	5	0.783 $\pm$ 0.014	0.996 $\pm$ 0.003	0.645 $\pm$ 0.019	0.776 $\pm$ 0.012	0.988 $\pm$ 0.002	0.640 $\pm$ 0.017	54.4 $\pm$ 2.7	0.052 $\pm$ 0.011	1.90 $\pm$ 0.06	97.2 $\pm$ 2.7
Spade-Hist-NoCache	5	0.788 $\pm$ 0.013	0.990 $\pm$ 0.003	0.656 $\pm$ 0.019	0.755 $\pm$ 0.014	0.948 $\pm$ 0.012	0.628 $\pm$ 0.018	56.8 $\pm$ 2.6	0.132 $\pm$ 0.010	35.79 $\pm$ 1.24	99.4 $\pm$ 2.9
Spade-Gauss-NoCache	5	0.786 $\pm$ 0.010	0.996 $\pm$ 0.003	0.649 $\pm$ 0.013	0.776 $\pm$ 0.011	0.984 $\pm$ 0.005	0.641 $\pm$ 0.013	54.2 $\pm$ 2.2	0.065 $\pm$ 0.011	54.82 $\pm$ 1.61	97.8 $\pm$ 1.8
Topic	5	0.757 $\pm$ 0.010	0.811 $\pm$ 0.009	0.709 $\pm$ 0.013	0.728 $\pm$ 0.010	0.780 $\pm$ 0.008	0.683 $\pm$ 0.012	72.4 $\pm$ 2.5	0.088 $\pm$ 0.021	630.21 $\pm$ 16.82	131.2 $\pm$ 1.9
CauScale	5	0.860 $\pm$ 0.007	0.949 $\pm$ 0.007	0.787 $\pm$ 0.014	0.657 $\pm$ 0.018	0.726 $\pm$ 0.021	0.601 $\pm$ 0.018	66.2 $\pm$ 2.7	0.253 $\pm$ 0.013	6.99 $\pm$ 0.01	124.4 $\pm$ 2.9

Appendix

Table 8: Controlled scalability sample-size experiment. Graph metrics are computed from stored DAG outputs where available; plot-only aggregate rows retain only reported metrics (n_samples=2500).

method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
Spade-Hist	5	0.862 $\pm$ 0.010	0.993 $\pm$ 0.003	0.761 $\pm$ 0.015	0.828 $\pm$ 0.013	0.955 $\pm$ 0.010	0.732 $\pm$ 0.016	41.0 $\pm$ 2.6	0.088 $\pm$ 0.010	11.45 $\pm$ 0.17	115.0 $\pm$ 2.1
Spade-Gauss	5	0.858 $\pm$ 0.008	0.996 $\pm$ 0.002	0.753 $\pm$ 0.012	0.846 $\pm$ 0.008	0.982 $\pm$ 0.004	0.743 $\pm$ 0.011	39.0 $\pm$ 1.8	0.057 $\pm$ 0.013	2.67 $\pm$ 0.09	113.4 $\pm$ 1.7
Spade-Hist-NoCache	5	0.859 $\pm$ 0.009	0.993 $\pm$ 0.003	0.757 $\pm$ 0.013	0.827 $\pm$ 0.013	0.956 $\pm$ 0.011	0.729 $\pm$ 0.016	41.4 $\pm$ 2.6	0.088 $\pm$ 0.010	63.87 $\pm$ 2.41	114.4 $\pm$ 1.9
Spade-Gauss-NoCache	5	0.858 $\pm$ 0.008	0.996 $\pm$ 0.002	0.753 $\pm$ 0.012	0.846 $\pm$ 0.008	0.982 $\pm$ 0.004	0.743 $\pm$ 0.011	39.0 $\pm$ 1.8	0.057 $\pm$ 0.013	81.01 $\pm$ 2.65	113.4 $\pm$ 1.7
Topic	5	0.811 $\pm$ 0.010	0.816 $\pm$ 0.009	0.807 $\pm$ 0.014	0.783 $\pm$ 0.014	0.788 $\pm$ 0.014	0.779 $\pm$ 0.016	60.4 $\pm$ 3.5	0.071 $\pm$ 0.009	1199.87 $\pm$ 23.24	148.2 $\pm$ 2.1
CauScale	5	0.831 $\pm$ 0.007	0.874 $\pm$ 0.007	0.792 $\pm$ 0.015	0.586 $\pm$ 0.021	0.616 $\pm$ 0.020	0.559 $\pm$ 0.023	83.4 $\pm$ 2.9	0.332 $\pm$ 0.022	7.36 $\pm$ 0.10	136.0 $\pm$ 3.3

Appendix

Table 9: Controlled scalability sample-size experiment. Graph metrics are computed from stored DAG outputs where available; plot-only aggregate rows retain only reported metrics (n_samples=5000).

method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
Spade-Hist	5	0.910 $\pm$ 0.007	0.992 $\pm$ 0.002	0.840 $\pm$ 0.013	0.881 $\pm$ 0.008	0.961 $\pm$ 0.009	0.813 $\pm$ 0.012	29.0 $\pm$ 1.7	0.069 $\pm$ 0.006	19.30 $\pm$ 0.39	127.0 $\pm$ 2.3
Spade-Gauss	5	0.914 $\pm$ 0.009	0.995 $\pm$ 0.003	0.845 $\pm$ 0.017	0.892 $\pm$ 0.014	0.972 $\pm$ 0.010	0.825 $\pm$ 0.020	26.8 $\pm$ 2.8	0.049 $\pm$ 0.009	4.21 $\pm$ 0.50	127.4 $\pm$ 2.7
Spade-Hist-NoCache	5	0.908 $\pm$ 0.008	0.991 $\pm$ 0.003	0.839 $\pm$ 0.014	0.876 $\pm$ 0.011	0.956 $\pm$ 0.011	0.809 $\pm$ 0.014	29.8 $\pm$ 2.2	0.072 $\pm$ 0.004	117.39 $\pm$ 1.72	127.0 $\pm$ 2.3
Spade-Gauss-NoCache	5	0.914 $\pm$ 0.009	0.995 $\pm$ 0.003	0.845 $\pm$ 0.017	0.892 $\pm$ 0.014	0.972 $\pm$ 0.010	0.825 $\pm$ 0.020	26.8 $\pm$ 2.8	0.049 $\pm$ 0.009	130.96 $\pm$ 3.57	127.4 $\pm$ 2.7
Topic	5	0.847 $\pm$ 0.008	0.810 $\pm$ 0.007	0.888 $\pm$ 0.013	0.819 $\pm$ 0.010	0.784 $\pm$ 0.010	0.859 $\pm$ 0.011	52.4 $\pm$ 2.5	0.064 $\pm$ 0.011	2769.23 $\pm$ 108.37	164.4 $\pm$ 2.0
CauScale	5	0.812 $\pm$ 0.011	0.827 $\pm$ 0.015	0.800 $\pm$ 0.018	0.567 $\pm$ 0.016	0.577 $\pm$ 0.015	0.559 $\pm$ 0.020	91.6 $\pm$ 3.2	0.319 $\pm$ 0.022	11.78 $\pm$ 1.29	145.4 $\pm$ 4.5

Appendix

Table 10: Controlled scalability sample-size experiment. Graph metrics are computed from stored DAG outputs where available; plot-only aggregate rows retain only reported metrics (n_samples=10000).

method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
Spade-Hist	5	0.935 $\pm$ 0.009	0.986 $\pm$ 0.006	0.889 $\pm$ 0.017	0.897 $\pm$ 0.008	0.946 $\pm$ 0.010	0.853 $\pm$ 0.015	24.0 $\pm$ 2.1	0.071 $\pm$ 0.008	34.66 $\pm$ 0.67	135.4 $\pm$ 3.1
Spade-Gauss	5	0.942 $\pm$ 0.009	0.990 $\pm$ 0.005	0.900 $\pm$ 0.016	0.916 $\pm$ 0.013	0.962 $\pm$ 0.010	0.875 $\pm$ 0.018	20.2 $\pm$ 2.8	0.051 $\pm$ 0.010	5.66 $\pm$ 0.15	136.4 $\pm$ 2.7
Spade-Hist-NoCache	5	0.934 $\pm$ 0.009	0.986 $\pm$ 0.006	0.888 $\pm$ 0.017	0.896 $\pm$ 0.008	0.946 $\pm$ 0.010	0.852 $\pm$ 0.015	24.2 $\pm$ 2.1	0.072 $\pm$ 0.009	278.99 $\pm$ 7.07	135.2 $\pm$ 3.0
Spade-Gauss-NoCache	5	0.942 $\pm$ 0.009	0.990 $\pm$ 0.005	0.900 $\pm$ 0.016	0.916 $\pm$ 0.013	0.962 $\pm$ 0.010	0.875 $\pm$ 0.018	20.2 $\pm$ 2.8	0.051 $\pm$ 0.010	259.90 $\pm$ 8.44	136.4 $\pm$ 2.7
Topic	5	0.845 $\pm$ 0.009	0.778 $\pm$ 0.009	0.927 $\pm$ 0.018	0.814 $\pm$ 0.012	0.749 $\pm$ 0.015	0.892 $\pm$ 0.016	56.0 $\pm$ 3.4	0.059 $\pm$ 0.008	6428.36 $\pm$ 432.32	178.8 $\pm$ 4.1
SDCD	5	0.749 $\pm$ 0.015	0.942 $\pm$ 0.013	0.623 $\pm$ 0.019	0.663 $\pm$ 0.013	0.833 $\pm$ 0.014	0.551 $\pm$ 0.016	73.2 $\pm$ 2.8	0.288 $\pm$ 0.021	1175.25 $\pm$ 37.55	99.2 $\pm$ 3.1

Appendix

Table 11: Controlled scalability sample-size experiment. Graph metrics are computed from stored DAG outputs where available; plot-only aggregate rows retain only reported metrics (n_samples=20000).

method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
Spade-Hist	5	0.950 $\pm$ 0.008	0.977 $\pm$ 0.007	0.927 $\pm$ 0.017	0.915 $\pm$ 0.007	0.941 $\pm$ 0.012	0.892 $\pm$ 0.013	19.6 $\pm$ 1.9	0.067 $\pm$ 0.009	64.16 $\pm$ 1.68	142.4 $\pm$ 3.2
Spade-Gauss	5	0.952 $\pm$ 0.009	0.978 $\pm$ 0.006	0.929 $\pm$ 0.018	0.924 $\pm$ 0.013	0.949 $\pm$ 0.016	0.901 $\pm$ 0.018	18.0 $\pm$ 2.9	0.052 $\pm$ 0.013	8.04 $\pm$ 0.15	142.6 $\pm$ 3.3
Spade-Hist-NoCache	5	0.950 $\pm$ 0.008	0.977 $\pm$ 0.007	0.925 $\pm$ 0.017	0.913 $\pm$ 0.007	0.939 $\pm$ 0.011	0.889 $\pm$ 0.014	20.0 $\pm$ 2.0	0.068 $\pm$ 0.010	572.68 $\pm$ 14.92	142.2 $\pm$ 3.2
Spade-Gauss-NoCache	5	0.952 $\pm$ 0.009	0.978 $\pm$ 0.006	0.929 $\pm$ 0.018	0.924 $\pm$ 0.013	0.949 $\pm$ 0.016	0.901 $\pm$ 0.018	18.0 $\pm$ 2.9	0.052 $\pm$ 0.013	546.27 $\pm$ 26.11	142.6 $\pm$ 3.3
Topic	5	0.845 $\pm$ 0.012	0.763 $\pm$ 0.012	0.947 $\pm$ 0.016	0.814 $\pm$ 0.015	0.735 $\pm$ 0.016	0.912 $\pm$ 0.015	57.4 $\pm$ 4.6	0.057 $\pm$ 0.010	15747.31 $\pm$ 973.76	186.2 $\pm$ 3.0
SDCD	5	0.751 $\pm$ 0.012	0.943 $\pm$ 0.009	0.625 $\pm$ 0.019	0.660 $\pm$ 0.008	0.829 $\pm$ 0.017	0.549 $\pm$ 0.011	73.4 $\pm$ 1.8	0.295 $\pm$ 0.023	2164.41 $\pm$ 13.30	99.6 $\pm$ 3.5

Appendix

Table 12: Controlled scalability sample-size experiment. Graph metrics are computed from stored DAG outputs where available; plot-only aggregate rows retain only reported metrics (n_samples=40000).

method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
Spade-Hist	5	0.958 $\pm$ 0.007	0.973 $\pm$ 0.010	0.945 $\pm$ 0.018	0.915 $\pm$ 0.004	0.930 $\pm$ 0.013	0.903 $\pm$ 0.013	18.6 $\pm$ 1.3	0.067 $\pm$ 0.008	148.94 $\pm$ 6.08	145.8 $\pm$ 3.9
Spade-Gauss	5	0.958 $\pm$ 0.008	0.967 $\pm$ 0.009	0.951 $\pm$ 0.015	0.926 $\pm$ 0.014	0.935 $\pm$ 0.019	0.919 $\pm$ 0.015	17.2 $\pm$ 2.9	0.048 $\pm$ 0.010	16.02 $\pm$ 2.78	147.6 $\pm$ 3.1
Spade-Hist-NoCache	5	0.958 $\pm$ 0.007	0.973 $\pm$ 0.010	0.945 $\pm$ 0.018	0.915 $\pm$ 0.004	0.930 $\pm$ 0.013	0.903 $\pm$ 0.013	18.6 $\pm$ 1.3	0.067 $\pm$ 0.008	1353.85 $\pm$ 140.56	145.8 $\pm$ 3.9
Spade-Gauss-NoCache	5	0.958 $\pm$ 0.008	0.967 $\pm$ 0.009	0.951 $\pm$ 0.015	0.926 $\pm$ 0.014	0.935 $\pm$ 0.019	0.919 $\pm$ 0.015	17.2 $\pm$ 2.9	0.048 $\pm$ 0.010	1328.62 $\pm$ 68.57	147.6 $\pm$ 3.1
Topic	5	0.825 $\pm$ 0.014	0.723 $\pm$ 0.016	0.963 $\pm$ 0.016	0.797 $\pm$ 0.016	0.698 $\pm$ 0.019	0.929 $\pm$ 0.014	66.2 $\pm$ 5.7	0.049 $\pm$ 0.007	43376.76 $\pm$ 2382.63	200.0 $\pm$ 4.5
SDCD	5	0.751 $\pm$ 0.014	0.948 $\pm$ 0.009	0.623 $\pm$ 0.019	0.669 $\pm$ 0.014	0.844 $\pm$ 0.015	0.555 $\pm$ 0.017	72.0 $\pm$ 2.8	0.283 $\pm$ 0.025	4163.32 $\pm$ 67.10	98.6 $\pm$ 3.2

Appendix

Table 13: Controlled scalability sample-size experiment. Graph metrics are computed from stored DAG outputs where available; plot-only aggregate rows retain only reported metrics (n_samples=80000).

method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
Spade-Hist	5	0.958 $\pm$ 0.007	0.956 $\pm$ 0.010	0.961 $\pm$ 0.019	0.912 $\pm$ 0.005	0.910 $\pm$ 0.015	0.915 $\pm$ 0.012	19.6 $\pm$ 1.5	0.067 $\pm$ 0.006	575.00 $\pm$ 42.56	151.0 $\pm$ 4.2
Spade-Gauss	5	0.964 $\pm$ 0.007	0.958 $\pm$ 0.009	0.971 $\pm$ 0.015	0.925 $\pm$ 0.013	0.920 $\pm$ 0.019	0.931 $\pm$ 0.013	16.8 $\pm$ 2.8	0.049 $\pm$ 0.009	25.72 $\pm$ 0.86	152.0 $\pm$ 3.2
Spade-Hist-NoCache	5	0.959 $\pm$ 0.008	0.956 $\pm$ 0.010	0.963 $\pm$ 0.019	0.911 $\pm$ 0.005	0.909 $\pm$ 0.015	0.915 $\pm$ 0.012	19.6 $\pm$ 1.5	0.067 $\pm$ 0.006	3639.34 $\pm$ 267.12	151.2 $\pm$ 4.2
Spade-Gauss-NoCache	5	0.964 $\pm$ 0.007	0.958 $\pm$ 0.009	0.971 $\pm$ 0.015	0.925 $\pm$ 0.013	0.920 $\pm$ 0.019	0.931 $\pm$ 0.013	16.8 $\pm$ 2.8	0.049 $\pm$ 0.009	3274.59 $\pm$ 236.83	152.0 $\pm$ 3.2
SDCD	5	0.759 $\pm$ 0.014	0.950 $\pm$ 0.009	0.632 $\pm$ 0.017	0.679 $\pm$ 0.015	0.850 $\pm$ 0.014	0.565 $\pm$ 0.016	70.2 $\pm$ 3.0	0.280 $\pm$ 0.016	8078.58 $\pm$ 132.57	99.8 $\pm$ 2.5

Appendix

Table 14: Controlled scalability sample-size experiment. Graph metrics are computed from stored DAG outputs where available; plot-only aggregate rows retain only reported metrics (n_samples=160000).

n_features	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
25	Spade-Hist	5	0.775 $\pm$ 0.034	0.912 $\pm$ 0.036	0.676 $\pm$ 0.035	0.746 $\pm$ 0.052	0.876 $\pm$ 0.057	0.651 $\pm$ 0.051	14.8 $\pm$ 3.7	0.103 $\pm$ 0.057	0.97 $\pm$ 0.06	25.0 $\pm$ 2.1
25	Spade-Gauss	5	0.787 $\pm$ 0.028	0.860 $\pm$ 0.025	0.731 $\pm$ 0.042	0.658 $\pm$ 0.033	0.720 $\pm$ 0.039	0.611 $\pm$ 0.041	17.8 $\pm$ 3.1	0.161 $\pm$ 0.019	0.23 $\pm$ 0.03	28.6 $\pm$ 2.5
25	Topic	5	0.732 $\pm$ 0.018	0.705 $\pm$ 0.027	0.771 $\pm$ 0.043	0.559 $\pm$ 0.029	0.540 $\pm$ 0.041	0.587 $\pm$ 0.033	25.4 $\pm$ 3.3	0.224 $\pm$ 0.013	54.38 $\pm$ 8.34	36.8 $\pm$ 3.0
25	CauScale	5	0.733 $\pm$ 0.049	0.796 $\pm$ 0.041	0.689 $\pm$ 0.066	0.475 $\pm$ 0.060	0.512 $\pm$ 0.058	0.450 $\pm$ 0.065	25.4 $\pm$ 4.6	0.359 $\pm$ 0.029	5.99 $\pm$ 0.13	29.0 $\pm$ 3.0
25	SDCD	5	0.693 $\pm$ 0.046	0.766 $\pm$ 0.048	0.646 $\pm$ 0.064	0.479 $\pm$ 0.078	0.528 $\pm$ 0.086	0.447 $\pm$ 0.078	25.4 $\pm$ 4.1	0.355 $\pm$ 0.036	159.94 $\pm$ 2.69	29.2 $\pm$ 4.3
25	Das	5	0.601 $\pm$ 0.039	0.528 $\pm$ 0.043	0.716 $\pm$ 0.055	0.456 $\pm$ 0.029	0.397 $\pm$ 0.020	0.551 $\pm$ 0.058	39.0 $\pm$ 6.4	0.270 $\pm$ 0.045	133.03 $\pm$ 1.28	47.2 $\pm$ 7.3

Appendix

Table 15: Heterogeneous scalability feature-size experiment. Entries are means with standard errors over successful seeds.

n_samples	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
2500	Spade-Hist	5	0.809 $\pm$ 0.006	0.938 $\pm$ 0.012	0.712 $\pm$ 0.004	0.784 $\pm$ 0.016	0.910 $\pm$ 0.023	0.690 $\pm$ 0.012	53.6 $\pm$ 2.0	0.125 $\pm$ 0.019	10.06 $\pm$ 0.69	114.4 $\pm$ 3.8
2500	Spade-Gauss	5	0.808 $\pm$ 0.014	0.893 $\pm$ 0.023	0.737 $\pm$ 0.009	0.689 $\pm$ 0.027	0.763 $\pm$ 0.036	0.629 $\pm$ 0.021	69.0 $\pm$ 5.4	0.172 $\pm$ 0.017	3.66 $\pm$ 0.31	124.4 $\pm$ 3.3
2500	Topic	5	0.700 $\pm$ 0.008	0.653 $\pm$ 0.014	0.756 $\pm$ 0.006	0.579 $\pm$ 0.011	0.540 $\pm$ 0.014	0.626 $\pm$ 0.011	117.2 $\pm$ 4.3	0.188 $\pm$ 0.009	1035.38 $\pm$ 77.52	174.8 $\pm$ 5.7
2500	CauScale	5	0.845 $\pm$ 0.003	0.908 $\pm$ 0.017	0.792 $\pm$ 0.010	0.667 $\pm$ 0.012	0.716 $\pm$ 0.014	0.625 $\pm$ 0.016	68.8 $\pm$ 2.4	0.219 $\pm$ 0.011	6.39 $\pm$ 0.13	131.2 $\pm$ 1.8
2500	SDCD	5	0.675 $\pm$ 0.015	0.667 $\pm$ 0.024	0.685 $\pm$ 0.014	0.406 $\pm$ 0.026	0.402 $\pm$ 0.031	0.411 $\pm$ 0.023	141.6 $\pm$ 11.9	0.408 $\pm$ 0.016	151.59 $\pm$ 4.29	155.4 $\pm$ 8.0
2500	Das	5	0.518 $\pm$ 0.012	0.442 $\pm$ 0.019	0.630 $\pm$ 0.007	0.317 $\pm$ 0.020	0.271 $\pm$ 0.023	0.384 $\pm$ 0.017	215.2 $\pm$ 15.8	0.363 $\pm$ 0.019	818.49 $\pm$ 9.20	217.0 $\pm$ 13.9

Appendix

Table 16: Heterogeneous scalability sample-size experiment. Entries are means with standard errors over successful seeds.

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.843 $\pm$ 0.035	0.986 $\pm$ 0.014	0.745 $\pm$ 0.052	0.749 $\pm$ 0.039	0.880 $\pm$ 0.052	0.659 $\pm$ 0.046	6.0 $\pm$ 0.9	0.118 $\pm$ 0.047	0.69 $\pm$ 0.06	12.6 $\pm$ 1.1
gaussian	Spade-Gauss	5	0.867 $\pm$ 0.033	0.986 $\pm$ 0.014	0.780 $\pm$ 0.051	0.835 $\pm$ 0.024	0.951 $\pm$ 0.020	0.750 $\pm$ 0.041	4.6 $\pm$ 1.0	0.052 $\pm$ 0.026	0.08 $\pm$ 0.00	13.2 $\pm$ 1.1
gaussian	Topic	5	0.763 $\pm$ 0.028	0.709 $\pm$ 0.060	0.849 $\pm$ 0.042	0.651 $\pm$ 0.044	0.604 $\pm$ 0.057	0.725 $\pm$ 0.052	10.8 $\pm$ 1.1	0.213 $\pm$ 0.048	12.14 $\pm$ 0.71	20.2 $\pm$ 1.1
gaussian	Cam	5	0.725 $\pm$ 0.016	0.588 $\pm$ 0.018	0.946 $\pm$ 0.015	0.718 $\pm$ 0.020	0.583 $\pm$ 0.020	0.937 $\pm$ 0.022	12.4 $\pm$ 1.6	0.018 $\pm$ 0.018	235.86 $\pm$ 1.13	27.2 $\pm$ 2.5
gaussian	CauScale	5	0.816 $\pm$ 0.037	0.965 $\pm$ 0.021	0.714 $\pm$ 0.053	0.504 $\pm$ 0.042	0.592 $\pm$ 0.029	0.443 $\pm$ 0.050	10.2 $\pm$ 1.8	0.390 $\pm$ 0.029	5.95 $\pm$ 0.07	12.2 $\pm$ 0.5
gaussian	SDCD	5	0.762 $\pm$ 0.047	0.848 $\pm$ 0.051	0.704 $\pm$ 0.061	0.494 $\pm$ 0.054	0.554 $\pm$ 0.067	0.454 $\pm$ 0.052	12.0 $\pm$ 2.6	0.358 $\pm$ 0.042	75.33 $\pm$ 1.56	14.0 $\pm$ 1.6

Appendix

Table 17: Qualitative comparison without marginalization (

n=1000

d=20

, degree 2, mechanism additive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.726 $\pm$ 0.070	1.000	0.587 $\pm$ 0.083	0.636 $\pm$ 0.045	0.893 $\pm$ 0.056	0.509 $\pm$ 0.052	8.4 $\pm$ 1.2	0.310 $\pm$ 0.061	0.48 $\pm$ 0.01	9.8 $\pm$ 1.4
gaussian	Spade-Gauss	5	0.736 $\pm$ 0.067	0.935 $\pm$ 0.048	0.613 $\pm$ 0.074	0.718 $\pm$ 0.057	0.915 $\pm$ 0.046	0.597 $\pm$ 0.062	7.6 $\pm$ 1.6	0.112 $\pm$ 0.027	0.08 $\pm$ 0.00	10.8 $\pm$ 1.0
gaussian	Topic	5	0.608 $\pm$ 0.028	0.582 $\pm$ 0.042	0.650 $\pm$ 0.046	0.546 $\pm$ 0.042	0.527 $\pm$ 0.061	0.579 $\pm$ 0.038	15.0 $\pm$ 1.2	0.183 $\pm$ 0.065	11.03 $\pm$ 0.37	18.6 $\pm$ 0.5
gaussian	Cam	5	0.650 $\pm$ 0.021	0.534 $\pm$ 0.033	0.850 $\pm$ 0.041	0.600 $\pm$ 0.029	0.493 $\pm$ 0.040	0.782 $\pm$ 0.039	16.2 $\pm$ 0.7	0.096 $\pm$ 0.024	242.98 $\pm$ 1.97	26.6 $\pm$ 1.0
gaussian	CauScale	5	0.702 $\pm$ 0.038	0.905 $\pm$ 0.046	0.582 $\pm$ 0.051	0.473 $\pm$ 0.038	0.610 $\pm$ 0.053	0.392 $\pm$ 0.040	11.4 $\pm$ 1.2	0.365 $\pm$ 0.064	5.93 $\pm$ 0.04	10.8 $\pm$ 1.1
gaussian	SDCD	5	0.765 $\pm$ 0.050	0.882 $\pm$ 0.040	0.682 $\pm$ 0.059	0.551 $\pm$ 0.045	0.631 $\pm$ 0.031	0.492 $\pm$ 0.051	10.2 $\pm$ 1.4	0.334 $\pm$ 0.039	73.22 $\pm$ 6.59	13.2 $\pm$ 1.8

Appendix

Table 18: Qualitative comparison without marginalization (

n=1000

d=20

, degree 2, mechanism neveradditive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.834 $\pm$ 0.041	0.971 $\pm$ 0.018	0.738 $\pm$ 0.057	0.808 $\pm$ 0.042	0.940 $\pm$ 0.019	0.715 $\pm$ 0.059	8.0 $\pm$ 1.9	0.056 $\pm$ 0.022	0.63 $\pm$ 0.05	19.2 $\pm$ 1.7
gaussian	Spade-Gauss	5	0.802 $\pm$ 0.044	0.948 $\pm$ 0.015	0.705 $\pm$ 0.066	0.791 $\pm$ 0.053	0.932 $\pm$ 0.025	0.696 $\pm$ 0.072	8.8 $\pm$ 1.9	0.026 $\pm$ 0.026	0.11 $\pm$ 0.01	18.8 $\pm$ 1.9
gaussian	Topic	5	0.737 $\pm$ 0.035	0.780 $\pm$ 0.030	0.708 $\pm$ 0.058	0.711 $\pm$ 0.024	0.755 $\pm$ 0.032	0.681 $\pm$ 0.045	13.2 $\pm$ 1.2	0.095 $\pm$ 0.034	14.52 $\pm$ 0.93	22.8 $\pm$ 1.6
gaussian	Cam	5	0.735 $\pm$ 0.042	0.621 $\pm$ 0.050	0.913 $\pm$ 0.027	0.718 $\pm$ 0.057	0.608 $\pm$ 0.062	0.887 $\pm$ 0.037	17.4 $\pm$ 3.5	0.026 $\pm$ 0.026	237.08 $\pm$ 1.95	37.8 $\pm$ 2.6
gaussian	CauScale	5	0.733 $\pm$ 0.037	0.863 $\pm$ 0.036	0.650 $\pm$ 0.059	0.535 $\pm$ 0.050	0.626 $\pm$ 0.044	0.478 $\pm$ 0.064	16.0 $\pm$ 1.5	0.264 $\pm$ 0.034	5.96 $\pm$ 0.15	19.0 $\pm$ 1.7
gaussian	SDCD	5	0.688 $\pm$ 0.041	0.740 $\pm$ 0.015	0.655 $\pm$ 0.063	0.479 $\pm$ 0.022	0.517 $\pm$ 0.016	0.455 $\pm$ 0.038	19.8 $\pm$ 1.9	0.304 $\pm$ 0.045	76.22 $\pm$ 1.38	22.2 $\pm$ 2.0

Appendix

Table 19: Qualitative comparison without marginalization (

n=1000

d=20

, degree 3, mechanism additive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.681 $\pm$ 0.023	0.931 $\pm$ 0.023	0.541 $\pm$ 0.030	0.594 $\pm$ 0.056	0.813 $\pm$ 0.080	0.471 $\pm$ 0.049	14.4 $\pm$ 1.3	0.302 $\pm$ 0.081	0.53 $\pm$ 0.02	14.6 $\pm$ 0.7
gaussian	Spade-Gauss	5	0.734 $\pm$ 0.035	0.973 $\pm$ 0.016	0.593 $\pm$ 0.039	0.702 $\pm$ 0.037	0.931 $\pm$ 0.031	0.566 $\pm$ 0.039	11.6 $\pm$ 1.9	0.146 $\pm$ 0.029	0.09 $\pm$ 0.00	15.2 $\pm$ 0.5
gaussian	Topic	5	0.741 $\pm$ 0.016	0.813 $\pm$ 0.014	0.682 $\pm$ 0.019	0.673 $\pm$ 0.024	0.738 $\pm$ 0.024	0.619 $\pm$ 0.024	13.8 $\pm$ 1.7	0.148 $\pm$ 0.014	13.49 $\pm$ 0.95	21.2 $\pm$ 1.2
gaussian	Cam	5	0.726 $\pm$ 0.008	0.599 $\pm$ 0.004	0.923 $\pm$ 0.019	0.675 $\pm$ 0.018	0.557 $\pm$ 0.015	0.857 $\pm$ 0.026	19.4 $\pm$ 1.9	0.097 $\pm$ 0.028	238.63 $\pm$ 2.68	39.0 $\pm$ 2.6
gaussian	CauScale	5	0.745 $\pm$ 0.048	0.950 $\pm$ 0.013	0.621 $\pm$ 0.057	0.488 $\pm$ 0.058	0.620 $\pm$ 0.056	0.407 $\pm$ 0.056	16.0 $\pm$ 2.3	0.385 $\pm$ 0.044	5.83 $\pm$ 0.07	16.2 $\pm$ 0.9
gaussian	SDCD	5	0.741 $\pm$ 0.029	0.897 $\pm$ 0.035	0.641 $\pm$ 0.048	0.634 $\pm$ 0.052	0.761 $\pm$ 0.042	0.551 $\pm$ 0.063	13.8 $\pm$ 2.4	0.291 $\pm$ 0.062	76.18 $\pm$ 3.53	18.0 $\pm$ 1.2

Appendix

Table 20: Qualitative comparison without marginalization (

n=1000

d=20

, degree 3, mechanism neveradditive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.780 $\pm$ 0.034	0.967 $\pm$ 0.016	0.659 $\pm$ 0.047	0.759 $\pm$ 0.038	0.941 $\pm$ 0.033	0.641 $\pm$ 0.048	13.8 $\pm$ 2.5	0.052 $\pm$ 0.021	0.59 $\pm$ 0.01	23.6 $\pm$ 0.8
gaussian	Spade-Gauss	5	0.785 $\pm$ 0.035	0.983 $\pm$ 0.011	0.660 $\pm$ 0.051	0.785 $\pm$ 0.035	0.983 $\pm$ 0.011	0.660 $\pm$ 0.051	12.8 $\pm$ 2.4	0.027 $\pm$ 0.018	0.11 $\pm$ 0.01	23.2 $\pm$ 0.7
gaussian	Topic	5	0.726 $\pm$ 0.024	0.859 $\pm$ 0.045	0.640 $\pm$ 0.046	0.699 $\pm$ 0.031	0.826 $\pm$ 0.045	0.618 $\pm$ 0.052	17.6 $\pm$ 1.7	0.092 $\pm$ 0.030	17.30 $\pm$ 1.32	26.0 $\pm$ 1.2
gaussian	Cam	5	0.815 $\pm$ 0.014	0.734 $\pm$ 0.023	0.922 $\pm$ 0.033	0.815 $\pm$ 0.014	0.734 $\pm$ 0.023	0.922 $\pm$ 0.033	14.6 $\pm$ 1.2	0.006 $\pm$ 0.006	242.91 $\pm$ 1.35	43.8 $\pm$ 1.1
gaussian	CauScale	5	0.693 $\pm$ 0.043	0.915 $\pm$ 0.028	0.564 $\pm$ 0.052	0.501 $\pm$ 0.036	0.660 $\pm$ 0.019	0.408 $\pm$ 0.042	23.0 $\pm$ 2.9	0.377 $\pm$ 0.025	6.19 $\pm$ 0.26	21.2 $\pm$ 0.4
gaussian	SDCD	5	0.654 $\pm$ 0.037	0.746 $\pm$ 0.029	0.584 $\pm$ 0.043	0.403 $\pm$ 0.065	0.456 $\pm$ 0.067	0.362 $\pm$ 0.062	29.8 $\pm$ 3.9	0.476 $\pm$ 0.068	77.22 $\pm$ 2.55	27.2 $\pm$ 1.4

Appendix

Table 21: Qualitative comparison without marginalization (

n=1000

d=20

, degree 4, mechanism additive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.593 $\pm$ 0.029	0.960 $\pm$ 0.027	0.432 $\pm$ 0.029	0.549 $\pm$ 0.033	0.895 $\pm$ 0.062	0.399 $\pm$ 0.027	21.8 $\pm$ 1.9	0.349 $\pm$ 0.021	0.53 $\pm$ 0.01	15.6 $\pm$ 0.4
gaussian	Spade-Gauss	5	0.684 $\pm$ 0.044	0.951 $\pm$ 0.023	0.539 $\pm$ 0.048	0.663 $\pm$ 0.042	0.921 $\pm$ 0.025	0.522 $\pm$ 0.047	18.2 $\pm$ 3.1	0.075 $\pm$ 0.022	0.10 $\pm$ 0.00	19.6 $\pm$ 1.2
gaussian	Topic	5	0.708 $\pm$ 0.027	0.855 $\pm$ 0.037	0.610 $\pm$ 0.035	0.654 $\pm$ 0.020	0.791 $\pm$ 0.034	0.563 $\pm$ 0.029	19.2 $\pm$ 1.7	0.136 $\pm$ 0.028	15.26 $\pm$ 0.54	24.8 $\pm$ 0.4
gaussian	Cam	5	0.690 $\pm$ 0.021	0.570 $\pm$ 0.022	0.881 $\pm$ 0.039	0.637 $\pm$ 0.019	0.526 $\pm$ 0.019	0.814 $\pm$ 0.042	30.6 $\pm$ 3.6	0.084 $\pm$ 0.016	249.86 $\pm$ 1.41	54.6 $\pm$ 4.5
gaussian	CauScale	5	0.538 $\pm$ 0.016	0.879 $\pm$ 0.035	0.388 $\pm$ 0.012	0.332 $\pm$ 0.021	0.541 $\pm$ 0.032	0.240 $\pm$ 0.017	28.8 $\pm$ 2.5	0.456 $\pm$ 0.058	7.12 $\pm$ 1.09	15.6 $\pm$ 1.2
gaussian	SDCD	5	0.657 $\pm$ 0.010	0.839 $\pm$ 0.030	0.542 $\pm$ 0.014	0.561 $\pm$ 0.014	0.718 $\pm$ 0.033	0.463 $\pm$ 0.013	22.8 $\pm$ 2.0	0.261 $\pm$ 0.020	75.47 $\pm$ 3.23	22.8 $\pm$ 1.7

Appendix

Table 22: Qualitative comparison without marginalization (

n=1000

d=20

, degree 4, mechanism neveradditive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.885 $\pm$ 0.016	0.990 $\pm$ 0.006	0.802 $\pm$ 0.022	0.876 $\pm$ 0.013	0.979 $\pm$ 0.005	0.793 $\pm$ 0.019	10.2 $\pm$ 1.7	0.036 $\pm$ 0.014	1.50 $\pm$ 0.05	37.4 $\pm$ 2.2
gaussian	Spade-Gauss	5	0.884 $\pm$ 0.020	0.995 $\pm$ 0.005	0.797 $\pm$ 0.028	0.884 $\pm$ 0.020	0.995 $\pm$ 0.005	0.797 $\pm$ 0.028	10.0 $\pm$ 2.4	0.029 $\pm$ 0.008	0.40 $\pm$ 0.03	36.8 $\pm$ 1.5
gaussian	Topic	5	0.763 $\pm$ 0.019	0.713 $\pm$ 0.020	0.822 $\pm$ 0.026	0.730 $\pm$ 0.027	0.683 $\pm$ 0.028	0.786 $\pm$ 0.031	25.6 $\pm$ 3.5	0.076 $\pm$ 0.012	82.75 $\pm$ 4.35	53.2 $\pm$ 3.1
gaussian	Cam	5	0.153 $\pm$ 0.009	0.084 $\pm$ 0.006	0.948 $\pm$ 0.015	0.150 $\pm$ 0.009	0.082 $\pm$ 0.005	0.930 $\pm$ 0.013	490.0 $\pm$ 33.0	0.035 $\pm$ 0.011	30345.19 $\pm$ 310.65	530.4 $\pm$ 34.3
gaussian	CauScale	5	0.879 $\pm$ 0.021	0.919 $\pm$ 0.012	0.846 $\pm$ 0.035	0.604 $\pm$ 0.028	0.631 $\pm$ 0.023	0.581 $\pm$ 0.035	23.2 $\pm$ 3.1	0.325 $\pm$ 0.024	12.59 $\pm$ 1.50	42.2 $\pm$ 1.5
gaussian	SDCD	5	0.743 $\pm$ 0.025	0.737 $\pm$ 0.016	0.750 $\pm$ 0.035	0.550 $\pm$ 0.012	0.546 $\pm$ 0.013	0.555 $\pm$ 0.016	33.2 $\pm$ 3.2	0.259 $\pm$ 0.033	76.03 $\pm$ 1.83	46.8 $\pm$ 2.3

Appendix

Table 23: Qualitative comparison without marginalization (

n=1000

d=50

, degree 2, mechanism additive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.731 $\pm$ 0.042	0.966 $\pm$ 0.019	0.600 $\pm$ 0.058	0.666 $\pm$ 0.034	0.881 $\pm$ 0.027	0.545 $\pm$ 0.050	22.6 $\pm$ 3.4	0.259 $\pm$ 0.024	1.37 $\pm$ 0.05	28.2 $\pm$ 1.8
gaussian	Spade-Gauss	5	0.745 $\pm$ 0.044	0.951 $\pm$ 0.021	0.621 $\pm$ 0.057	0.735 $\pm$ 0.047	0.937 $\pm$ 0.028	0.612 $\pm$ 0.060	20.0 $\pm$ 4.0	0.083 $\pm$ 0.017	0.37 $\pm$ 0.01	29.6 $\pm$ 1.2
gaussian	Topic	5	0.651 $\pm$ 0.028	0.629 $\pm$ 0.021	0.677 $\pm$ 0.041	0.591 $\pm$ 0.028	0.571 $\pm$ 0.018	0.616 $\pm$ 0.042	36.6 $\pm$ 4.0	0.177 $\pm$ 0.026	73.34 $\pm$ 3.67	49.4 $\pm$ 2.2
gaussian	Cam	5	0.172 $\pm$ 0.012	0.095 $\pm$ 0.007	0.951 $\pm$ 0.023	0.160 $\pm$ 0.010	0.088 $\pm$ 0.006	0.888 $\pm$ 0.036	431.8 $\pm$ 34.6	0.070 $\pm$ 0.019	29545.85 $\pm$ 174.38	470.8 $\pm$ 37.1
gaussian	CauScale	5	0.811 $\pm$ 0.025	0.895 $\pm$ 0.019	0.743 $\pm$ 0.035	0.559 $\pm$ 0.074	0.613 $\pm$ 0.070	0.516 $\pm$ 0.077	26.6 $\pm$ 4.3	0.319 $\pm$ 0.051	5.79 $\pm$ 0.07	38.4 $\pm$ 2.7
gaussian	SDCD	5	0.654 $\pm$ 0.038	0.694 $\pm$ 0.026	0.631 $\pm$ 0.061	0.464 $\pm$ 0.038	0.489 $\pm$ 0.019	0.450 $\pm$ 0.055	38.4 $\pm$ 2.8	0.364 $\pm$ 0.031	75.13 $\pm$ 1.78	42.0 $\pm$ 4.5

Appendix

Table 24: Qualitative comparison without marginalization (

n=1000

d=50

, degree 2, mechanism neveradditive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.759 $\pm$ 0.033	0.953 $\pm$ 0.007	0.635 $\pm$ 0.045	0.743 $\pm$ 0.033	0.933 $\pm$ 0.010	0.621 $\pm$ 0.044	29.8 $\pm$ 4.6	0.111 $\pm$ 0.024	1.64 $\pm$ 0.08	47.4 $\pm$ 2.8
gaussian	Spade-Gauss	5	0.773 $\pm$ 0.023	0.966 $\pm$ 0.011	0.647 $\pm$ 0.033	0.766 $\pm$ 0.022	0.958 $\pm$ 0.013	0.641 $\pm$ 0.031	27.6 $\pm$ 3.1	0.046 $\pm$ 0.010	0.51 $\pm$ 0.04	47.8 $\pm$ 2.8
gaussian	Topic	5	0.700 $\pm$ 0.019	0.748 $\pm$ 0.018	0.662 $\pm$ 0.033	0.665 $\pm$ 0.032	0.711 $\pm$ 0.036	0.628 $\pm$ 0.040	42.6 $\pm$ 3.0	0.118 $\pm$ 0.032	102.20 $\pm$ 6.57	63.0 $\pm$ 2.3
gaussian	Cam	5	0.191 $\pm$ 0.010	0.107 $\pm$ 0.007	0.941 $\pm$ 0.023	0.189 $\pm$ 0.011	0.105 $\pm$ 0.007	0.926 $\pm$ 0.022	573.4 $\pm$ 30.4	0.039 $\pm$ 0.011	27844.70 $\pm$ 114.38	635.0 $\pm$ 31.3
gaussian	CauScale	5	0.791 $\pm$ 0.015	0.922 $\pm$ 0.025	0.695 $\pm$ 0.021	0.627 $\pm$ 0.014	0.731 $\pm$ 0.018	0.552 $\pm$ 0.020	36.8 $\pm$ 3.3	0.237 $\pm$ 0.016	5.91 $\pm$ 0.12	54.0 $\pm$ 2.7
gaussian	SDCD	5	0.662 $\pm$ 0.017	0.674 $\pm$ 0.025	0.658 $\pm$ 0.032	0.502 $\pm$ 0.028	0.510 $\pm$ 0.028	0.499 $\pm$ 0.038	59.4 $\pm$ 4.6	0.276 $\pm$ 0.027	78.46 $\pm$ 1.66	69.8 $\pm$ 3.6

Appendix

Table 25: Qualitative comparison without marginalization (

n=1000

d=50

, degree 3, mechanism additive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.628 $\pm$ 0.043	0.960 $\pm$ 0.007	0.472 $\pm$ 0.048	0.575 $\pm$ 0.040	0.880 $\pm$ 0.015	0.433 $\pm$ 0.044	42.8 $\pm$ 5.8	0.290 $\pm$ 0.044	1.42 $\pm$ 0.04	34.6 $\pm$ 2.0
gaussian	Spade-Gauss	5	0.664 $\pm$ 0.028	0.958 $\pm$ 0.010	0.511 $\pm$ 0.033	0.639 $\pm$ 0.029	0.922 $\pm$ 0.018	0.492 $\pm$ 0.033	38.6 $\pm$ 4.7	0.110 $\pm$ 0.023	0.43 $\pm$ 0.02	37.8 $\pm$ 1.0
gaussian	Topic	5	0.621 $\pm$ 0.029	0.702 $\pm$ 0.018	0.561 $\pm$ 0.040	0.565 $\pm$ 0.024	0.639 $\pm$ 0.015	0.509 $\pm$ 0.033	52.6 $\pm$ 5.2	0.157 $\pm$ 0.023	84.96 $\pm$ 4.81	56.4 $\pm$ 0.7
gaussian	Cam	5	0.210 $\pm$ 0.006	0.118 $\pm$ 0.004	0.935 $\pm$ 0.012	0.191 $\pm$ 0.007	0.108 $\pm$ 0.004	0.850 $\pm$ 0.026	511.2 $\pm$ 28.6	0.107 $\pm$ 0.023	26618.99 $\pm$ 346.44	567.2 $\pm$ 30.6
gaussian	CauScale	5	0.734 $\pm$ 0.034	0.891 $\pm$ 0.020	0.627 $\pm$ 0.042	0.512 $\pm$ 0.046	0.620 $\pm$ 0.044	0.438 $\pm$ 0.047	46.2 $\pm$ 5.8	0.317 $\pm$ 0.033	5.73 $\pm$ 0.04	49.8 $\pm$ 1.1
gaussian	SDCD	5	0.631 $\pm$ 0.040	0.716 $\pm$ 0.053	0.565 $\pm$ 0.035	0.491 $\pm$ 0.051	0.559 $\pm$ 0.066	0.439 $\pm$ 0.043	57.4 $\pm$ 8.1	0.318 $\pm$ 0.040	72.92 $\pm$ 1.21	57.0 $\pm$ 4.3

Appendix

Table 26: Qualitative comparison without marginalization (

n=1000

d=50

, degree 3, mechanism neveradditive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.718 $\pm$ 0.030	0.946 $\pm$ 0.011	0.582 $\pm$ 0.040	0.702 $\pm$ 0.029	0.926 $\pm$ 0.016	0.569 $\pm$ 0.038	45.4 $\pm$ 6.1	0.097 $\pm$ 0.024	1.99 $\pm$ 0.11	58.4 $\pm$ 2.1
gaussian	Spade-Gauss	5	0.735 $\pm$ 0.025	0.963 $\pm$ 0.011	0.596 $\pm$ 0.030	0.735 $\pm$ 0.025	0.963 $\pm$ 0.011	0.596 $\pm$ 0.030	41.6 $\pm$ 5.3	0.047 $\pm$ 0.012	0.64 $\pm$ 0.04	59.0 $\pm$ 2.4
gaussian	Topic	5	0.714 $\pm$ 0.023	0.833 $\pm$ 0.021	0.627 $\pm$ 0.026	0.687 $\pm$ 0.027	0.802 $\pm$ 0.031	0.603 $\pm$ 0.028	50.6 $\pm$ 5.3	0.105 $\pm$ 0.014	114.17 $\pm$ 4.14	71.8 $\pm$ 2.1
gaussian	Cam	5	0.233 $\pm$ 0.016	0.133 $\pm$ 0.010	0.939 $\pm$ 0.014	0.226 $\pm$ 0.018	0.129 $\pm$ 0.012	0.910 $\pm$ 0.022	598.4 $\pm$ 13.1	0.043 $\pm$ 0.016	30816.27 $\pm$ 99.34	680.8 $\pm$ 10.0
gaussian	CauScale	5	0.783 $\pm$ 0.020	0.923 $\pm$ 0.008	0.682 $\pm$ 0.030	0.634 $\pm$ 0.018	0.747 $\pm$ 0.017	0.552 $\pm$ 0.023	49.0 $\pm$ 4.9	0.264 $\pm$ 0.021	5.83 $\pm$ 0.05	70.6 $\pm$ 3.3
gaussian	SDCD	5	0.635 $\pm$ 0.022	0.687 $\pm$ 0.028	0.593 $\pm$ 0.026	0.490 $\pm$ 0.022	0.530 $\pm$ 0.027	0.458 $\pm$ 0.022	78.6 $\pm$ 5.8	0.292 $\pm$ 0.033	77.32 $\pm$ 0.96	82.8 $\pm$ 3.8

Appendix

Table 27: Qualitative comparison without marginalization (

n=1000

d=50

, degree 4, mechanism additive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.559 $\pm$ 0.013	0.910 $\pm$ 0.011	0.404 $\pm$ 0.014	0.494 $\pm$ 0.019	0.804 $\pm$ 0.021	0.357 $\pm$ 0.017	65.6 $\pm$ 4.2	0.341 $\pm$ 0.030	1.53 $\pm$ 0.04	42.6 $\pm$ 2.5
gaussian	Spade-Gauss	5	0.628 $\pm$ 0.012	0.919 $\pm$ 0.010	0.477 $\pm$ 0.015	0.612 $\pm$ 0.020	0.895 $\pm$ 0.020	0.466 $\pm$ 0.020	55.4 $\pm$ 3.6	0.130 $\pm$ 0.019	0.48 $\pm$ 0.03	49.8 $\pm$ 2.6
gaussian	Topic	5	0.606 $\pm$ 0.014	0.755 $\pm$ 0.014	0.507 $\pm$ 0.020	0.555 $\pm$ 0.015	0.693 $\pm$ 0.013	0.465 $\pm$ 0.020	67.2 $\pm$ 3.9	0.184 $\pm$ 0.016	98.07 $\pm$ 7.86	64.2 $\pm$ 3.2
gaussian	Cam	5	0.230 $\pm$ 0.012	0.132 $\pm$ 0.008	0.893 $\pm$ 0.015	0.204 $\pm$ 0.015	0.117 $\pm$ 0.010	0.788 $\pm$ 0.013	583.4 $\pm$ 8.6	0.142 $\pm$ 0.022	28380.95 $\pm$ 50.48	649.0 $\pm$ 6.5
gaussian	CauScale	5	0.703 $\pm$ 0.012	0.913 $\pm$ 0.013	0.573 $\pm$ 0.017	0.539 $\pm$ 0.013	0.701 $\pm$ 0.026	0.439 $\pm$ 0.012	59.2 $\pm$ 3.2	0.299 $\pm$ 0.017	5.86 $\pm$ 0.06	60.2 $\pm$ 3.5
gaussian	SDCD	5	0.611 $\pm$ 0.015	0.699 $\pm$ 0.027	0.546 $\pm$ 0.019	0.493 $\pm$ 0.013	0.565 $\pm$ 0.025	0.440 $\pm$ 0.014	76.8 $\pm$ 5.5	0.314 $\pm$ 0.014	73.21 $\pm$ 2.44	75.2 $\pm$ 5.2

Appendix

Table 28: Qualitative comparison without marginalization (

n=1000

d=50

, degree 4, mechanism neveradditive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.887 $\pm$ 0.030	0.947 $\pm$ 0.024	0.851 $\pm$ 0.066	0.830 $\pm$ 0.029	0.890 $\pm$ 0.043	0.794 $\pm$ 0.055	4.6 $\pm$ 1.0	0.067 $\pm$ 0.032	0.58 $\pm$ 0.01	14.8 $\pm$ 0.6
gaussian	Spade-Gauss	5	0.907 $\pm$ 0.033	0.974 $\pm$ 0.016	0.860 $\pm$ 0.061	0.907 $\pm$ 0.033	0.974 $\pm$ 0.016	0.860 $\pm$ 0.061	3.2 $\pm$ 1.2	0.009 $\pm$ 0.009	0.10 $\pm$ 0.00	14.6 $\pm$ 0.7
gaussian	Topic	5	0.762 $\pm$ 0.022	0.697 $\pm$ 0.029	0.860 $\pm$ 0.061	0.762 $\pm$ 0.022	0.697 $\pm$ 0.029	0.860 $\pm$ 0.061	9.0 $\pm$ 1.2	0.047 $\pm$ 0.030	17.80 $\pm$ 0.97	20.4 $\pm$ 0.7
gaussian	Cam	5	0.685 $\pm$ 0.037	0.542 $\pm$ 0.040	0.943 $\pm$ 0.035	0.678 $\pm$ 0.040	0.536 $\pm$ 0.042	0.934 $\pm$ 0.041	15.2 $\pm$ 2.8	0.009 $\pm$ 0.009	333.86 $\pm$ 6.53	29.6 $\pm$ 2.6
gaussian	CauScale	5	0.810 $\pm$ 0.045	0.882 $\pm$ 0.037	0.768 $\pm$ 0.076	0.438 $\pm$ 0.043	0.472 $\pm$ 0.024	0.419 $\pm$ 0.063	12.0 $\pm$ 1.9	0.467 $\pm$ 0.054	5.91 $\pm$ 0.07	14.4 $\pm$ 1.1
gaussian	SDCD	5	0.741 $\pm$ 0.021	0.902 $\pm$ 0.043	0.634 $\pm$ 0.030	0.548 $\pm$ 0.025	0.666 $\pm$ 0.036	0.469 $\pm$ 0.029	10.2 $\pm$ 1.0	0.336 $\pm$ 0.065	132.10 $\pm$ 3.87	12.0 $\pm$ 1.4

Appendix

Table 29: Qualitative comparison without marginalization (

n=2000

d=20

, degree 2, mechanism additive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.805 $\pm$ 0.031	0.957 $\pm$ 0.043	0.715 $\pm$ 0.065	0.707 $\pm$ 0.074	0.836 $\pm$ 0.082	0.629 $\pm$ 0.080	7.2 $\pm$ 1.6	0.278 $\pm$ 0.036	0.56 $\pm$ 0.01	12.4 $\pm$ 0.9
gaussian	Spade-Gauss	5	0.829 $\pm$ 0.033	0.969 $\pm$ 0.031	0.740 $\pm$ 0.061	0.813 $\pm$ 0.030	0.954 $\pm$ 0.046	0.723 $\pm$ 0.050	5.4 $\pm$ 1.1	0.101 $\pm$ 0.021	0.09 $\pm$ 0.01	12.6 $\pm$ 0.7
gaussian	Topic	5	0.724 $\pm$ 0.038	0.674 $\pm$ 0.028	0.800 $\pm$ 0.074	0.664 $\pm$ 0.034	0.619 $\pm$ 0.028	0.731 $\pm$ 0.059	11.2 $\pm$ 1.5	0.167 $\pm$ 0.042	16.83 $\pm$ 2.01	19.6 $\pm$ 1.4
gaussian	Cam	5	0.697 $\pm$ 0.032	0.561 $\pm$ 0.038	0.934 $\pm$ 0.032	0.673 $\pm$ 0.041	0.540 $\pm$ 0.040	0.904 $\pm$ 0.057	14.6 $\pm$ 2.5	0.063 $\pm$ 0.048	322.19 $\pm$ 3.28	28.6 $\pm$ 3.5
gaussian	CauScale	5	0.737 $\pm$ 0.052	0.812 $\pm$ 0.065	0.697 $\pm$ 0.080	0.430 $\pm$ 0.060	0.466 $\pm$ 0.052	0.411 $\pm$ 0.070	13.2 $\pm$ 2.1	0.422 $\pm$ 0.052	6.14 $\pm$ 0.22	14.4 $\pm$ 1.6
gaussian	SDCD	5	0.683 $\pm$ 0.072	0.827 $\pm$ 0.056	0.602 $\pm$ 0.083	0.499 $\pm$ 0.082	0.595 $\pm$ 0.073	0.443 $\pm$ 0.084	12.2 $\pm$ 2.6	0.435 $\pm$ 0.057	139.74 $\pm$ 3.88	12.8 $\pm$ 2.7

Appendix

Table 30: Qualitative comparison without marginalization (

n=2000

d=20

, degree 2, mechanism neveradditive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.851 $\pm$ 0.028	0.969 $\pm$ 0.022	0.762 $\pm$ 0.039	0.833 $\pm$ 0.034	0.949 $\pm$ 0.034	0.746 $\pm$ 0.041	7.2 $\pm$ 1.5	0.083 $\pm$ 0.025	0.64 $\pm$ 0.02	19.8 $\pm$ 1.1
gaussian	Spade-Gauss	5	0.853 $\pm$ 0.030	0.976 $\pm$ 0.014	0.760 $\pm$ 0.043	0.853 $\pm$ 0.030	0.976 $\pm$ 0.014	0.760 $\pm$ 0.043	6.6 $\pm$ 1.4	0.033 $\pm$ 0.017	0.12 $\pm$ 0.01	19.6 $\pm$ 1.2
gaussian	Topic	5	0.778 $\pm$ 0.030	0.800 $\pm$ 0.029	0.762 $\pm$ 0.039	0.770 $\pm$ 0.021	0.791 $\pm$ 0.025	0.753 $\pm$ 0.031	11.2 $\pm$ 1.5	0.087 $\pm$ 0.023	22.19 $\pm$ 1.21	24.0 $\pm$ 1.1
gaussian	Cam	5	0.780 $\pm$ 0.034	0.692 $\pm$ 0.039	0.896 $\pm$ 0.028	0.780 $\pm$ 0.034	0.692 $\pm$ 0.039	0.896 $\pm$ 0.028	12.6 $\pm$ 1.7	0.009 $\pm$ 0.009	324.27 $\pm$ 1.43	32.8 $\pm$ 1.2
gaussian	CauScale	5	0.782 $\pm$ 0.042	0.894 $\pm$ 0.048	0.703 $\pm$ 0.050	0.488 $\pm$ 0.032	0.563 $\pm$ 0.052	0.435 $\pm$ 0.027	16.6 $\pm$ 1.9	0.338 $\pm$ 0.028	5.96 $\pm$ 0.07	19.8 $\pm$ 1.2
gaussian	SDCD	5	0.728 $\pm$ 0.039	0.843 $\pm$ 0.033	0.648 $\pm$ 0.054	0.521 $\pm$ 0.051	0.602 $\pm$ 0.051	0.465 $\pm$ 0.055	17.0 $\pm$ 2.8	0.316 $\pm$ 0.053	137.57 $\pm$ 4.04	19.4 $\pm$ 1.6

Appendix

Table 31: Qualitative comparison without marginalization (

n=2000

d=20

, degree 3, mechanism additive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.757 $\pm$ 0.043	0.987 $\pm$ 0.013	0.619 $\pm$ 0.049	0.691 $\pm$ 0.051	0.901 $\pm$ 0.050	0.564 $\pm$ 0.050	11.6 $\pm$ 2.4	0.257 $\pm$ 0.048	0.65 $\pm$ 0.03	15.6 $\pm$ 0.6
gaussian	Spade-Gauss	5	0.785 $\pm$ 0.034	0.965 $\pm$ 0.014	0.666 $\pm$ 0.043	0.767 $\pm$ 0.042	0.941 $\pm$ 0.026	0.651 $\pm$ 0.049	9.8 $\pm$ 2.1	0.103 $\pm$ 0.047	0.11 $\pm$ 0.00	17.2 $\pm$ 0.2
gaussian	Topic	5	0.742 $\pm$ 0.018	0.784 $\pm$ 0.047	0.713 $\pm$ 0.026	0.696 $\pm$ 0.020	0.731 $\pm$ 0.022	0.672 $\pm$ 0.041	13.6 $\pm$ 0.7	0.126 $\pm$ 0.038	19.50 $\pm$ 0.55	23.0 $\pm$ 0.5
gaussian	Cam	5	0.701 $\pm$ 0.021	0.562 $\pm$ 0.027	0.938 $\pm$ 0.008	0.669 $\pm$ 0.033	0.536 $\pm$ 0.036	0.893 $\pm$ 0.025	21.6 $\pm$ 2.8	0.054 $\pm$ 0.026	323.28 $\pm$ 2.87	42.6 $\pm$ 3.2
gaussian	CauScale	5	0.719 $\pm$ 0.047	0.874 $\pm$ 0.012	0.621 $\pm$ 0.065	0.496 $\pm$ 0.054	0.610 $\pm$ 0.070	0.426 $\pm$ 0.054	16.8 $\pm$ 1.7	0.376 $\pm$ 0.073	6.07 $\pm$ 0.08	17.6 $\pm$ 1.0
gaussian	SDCD	5	0.724 $\pm$ 0.025	0.813 $\pm$ 0.012	0.655 $\pm$ 0.033	0.563 $\pm$ 0.037	0.632 $\pm$ 0.036	0.508 $\pm$ 0.039	16.4 $\pm$ 1.9	0.324 $\pm$ 0.061	136.11 $\pm$ 1.61	20.2 $\pm$ 0.8

Appendix

Table 32: Qualitative comparison without marginalization (

n=2000

d=20

, degree 3, mechanism neveradditive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.789 $\pm$ 0.034	0.925 $\pm$ 0.048	0.689 $\pm$ 0.030	0.718 $\pm$ 0.058	0.844 $\pm$ 0.073	0.627 $\pm$ 0.050	16.0 $\pm$ 4.3	0.139 $\pm$ 0.058	0.73 $\pm$ 0.04	26.4 $\pm$ 2.4
gaussian	Spade-Gauss	5	0.830 $\pm$ 0.018	0.992 $\pm$ 0.008	0.716 $\pm$ 0.025	0.830 $\pm$ 0.018	0.992 $\pm$ 0.008	0.716 $\pm$ 0.025	10.2 $\pm$ 1.2	0.032 $\pm$ 0.013	0.17 $\pm$ 0.03	25.4 $\pm$ 2.0
gaussian	Topic	5	0.783 $\pm$ 0.029	0.850 $\pm$ 0.018	0.728 $\pm$ 0.038	0.777 $\pm$ 0.030	0.843 $\pm$ 0.018	0.722 $\pm$ 0.040	14.2 $\pm$ 1.8	0.032 $\pm$ 0.020	32.39 $\pm$ 6.13	30.0 $\pm$ 2.2
gaussian	Cam	5	0.808 $\pm$ 0.037	0.729 $\pm$ 0.039	0.910 $\pm$ 0.041	0.798 $\pm$ 0.040	0.719 $\pm$ 0.039	0.899 $\pm$ 0.046	15.8 $\pm$ 3.5	0.017 $\pm$ 0.012	335.82 $\pm$ 3.59	44.2 $\pm$ 3.7
gaussian	CauScale	5	0.719 $\pm$ 0.041	0.856 $\pm$ 0.047	0.623 $\pm$ 0.042	0.493 $\pm$ 0.042	0.586 $\pm$ 0.047	0.428 $\pm$ 0.040	24.2 $\pm$ 3.2	0.306 $\pm$ 0.043	5.97 $\pm$ 0.12	25.4 $\pm$ 1.1
gaussian	SDCD	5	0.729 $\pm$ 0.029	0.890 $\pm$ 0.040	0.622 $\pm$ 0.033	0.612 $\pm$ 0.041	0.748 $\pm$ 0.051	0.522 $\pm$ 0.039	20.2 $\pm$ 3.3	0.301 $\pm$ 0.018	142.69 $\pm$ 3.02	25.0 $\pm$ 3.1

Appendix

Table 33: Qualitative comparison without marginalization (

n=2000

d=20

, degree 4, mechanism additive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.738 $\pm$ 0.024	0.919 $\pm$ 0.026	0.624 $\pm$ 0.040	0.594 $\pm$ 0.019	0.741 $\pm$ 0.030	0.502 $\pm$ 0.029	19.6 $\pm$ 1.4	0.339 $\pm$ 0.016	0.66 $\pm$ 0.03	24.2 $\pm$ 2.7
gaussian	Spade-Gauss	5	0.762 $\pm$ 0.040	0.912 $\pm$ 0.017	0.659 $\pm$ 0.050	0.736 $\pm$ 0.045	0.880 $\pm$ 0.028	0.636 $\pm$ 0.053	14.8 $\pm$ 2.1	0.096 $\pm$ 0.025	0.14 $\pm$ 0.02	25.6 $\pm$ 2.8
gaussian	Topic	5	0.763 $\pm$ 0.042	0.819 $\pm$ 0.034	0.719 $\pm$ 0.056	0.682 $\pm$ 0.054	0.730 $\pm$ 0.046	0.644 $\pm$ 0.065	17.6 $\pm$ 1.9	0.154 $\pm$ 0.032	30.30 $\pm$ 4.87	31.0 $\pm$ 3.2
gaussian	Cam	5	0.714 $\pm$ 0.032	0.581 $\pm$ 0.039	0.935 $\pm$ 0.019	0.646 $\pm$ 0.036	0.526 $\pm$ 0.040	0.845 $\pm$ 0.028	29.4 $\pm$ 2.9	0.116 $\pm$ 0.036	335.78 $\pm$ 6.66	57.2 $\pm$ 4.2
gaussian	CauScale	5	0.686 $\pm$ 0.014	0.864 $\pm$ 0.035	0.572 $\pm$ 0.021	0.514 $\pm$ 0.024	0.644 $\pm$ 0.016	0.430 $\pm$ 0.029	23.4 $\pm$ 1.8	0.296 $\pm$ 0.032	6.07 $\pm$ 0.16	23.6 $\pm$ 2.4
gaussian	SDCD	5	0.722 $\pm$ 0.029	0.904 $\pm$ 0.029	0.611 $\pm$ 0.047	0.597 $\pm$ 0.032	0.747 $\pm$ 0.039	0.505 $\pm$ 0.043	20.0 $\pm$ 1.9	0.275 $\pm$ 0.022	139.60 $\pm$ 3.47	24.6 $\pm$ 4.2

Appendix

Table 34: Qualitative comparison without marginalization (

n=2000

d=20

, degree 4, mechanism neveradditive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.908 $\pm$ 0.016	0.982 $\pm$ 0.014	0.846 $\pm$ 0.024	0.891 $\pm$ 0.020	0.963 $\pm$ 0.021	0.830 $\pm$ 0.025	9.0 $\pm$ 2.2	0.055 $\pm$ 0.011	1.83 $\pm$ 0.05	39.8 $\pm$ 2.3
gaussian	Spade-Gauss	5	0.900 $\pm$ 0.016	0.975 $\pm$ 0.013	0.837 $\pm$ 0.023	0.895 $\pm$ 0.016	0.969 $\pm$ 0.015	0.832 $\pm$ 0.022	9.0 $\pm$ 1.8	0.030 $\pm$ 0.009	0.51 $\pm$ 0.02	39.6 $\pm$ 2.2
gaussian	Topic	5	0.733 $\pm$ 0.025	0.656 $\pm$ 0.034	0.837 $\pm$ 0.026	0.725 $\pm$ 0.025	0.648 $\pm$ 0.033	0.828 $\pm$ 0.025	28.6 $\pm$ 3.0	0.039 $\pm$ 0.011	129.93 $\pm$ 6.79	59.0 $\pm$ 2.3
gaussian	Cam	5	0.546 $\pm$ 0.030	0.385 $\pm$ 0.031	0.957 $\pm$ 0.005	0.544 $\pm$ 0.032	0.383 $\pm$ 0.032	0.952 $\pm$ 0.009	73.4 $\pm$ 4.4	0.005 $\pm$ 0.005	13046.86 $\pm$ 25.11	115.6 $\pm$ 2.4
gaussian	CauScale	5	0.852 $\pm$ 0.016	0.890 $\pm$ 0.015	0.820 $\pm$ 0.026	0.591 $\pm$ 0.027	0.616 $\pm$ 0.023	0.569 $\pm$ 0.033	24.8 $\pm$ 2.7	0.355 $\pm$ 0.039	6.01 $\pm$ 0.17	42.4 $\pm$ 1.9
gaussian	SDCD	5	0.767 $\pm$ 0.013	0.827 $\pm$ 0.016	0.717 $\pm$ 0.023	0.570 $\pm$ 0.027	0.616 $\pm$ 0.037	0.532 $\pm$ 0.024	28.8 $\pm$ 2.7	0.322 $\pm$ 0.033	137.50 $\pm$ 3.78	40.0 $\pm$ 2.2

Appendix

Table 35: Qualitative comparison without marginalization (

n=2000

d=50

, degree 2, mechanism additive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.772 $\pm$ 0.028	0.939 $\pm$ 0.032	0.658 $\pm$ 0.029	0.685 $\pm$ 0.038	0.833 $\pm$ 0.047	0.583 $\pm$ 0.035	21.6 $\pm$ 3.0	0.238 $\pm$ 0.015	1.71 $\pm$ 0.04	32.2 $\pm$ 1.2
gaussian	Spade-Gauss	5	0.829 $\pm$ 0.029	0.965 $\pm$ 0.017	0.729 $\pm$ 0.038	0.820 $\pm$ 0.035	0.954 $\pm$ 0.027	0.720 $\pm$ 0.042	14.4 $\pm$ 2.9	0.035 $\pm$ 0.013	0.48 $\pm$ 0.02	34.8 $\pm$ 2.2
gaussian	Topic	5	0.687 $\pm$ 0.021	0.621 $\pm$ 0.029	0.776 $\pm$ 0.028	0.665 $\pm$ 0.029	0.600 $\pm$ 0.033	0.751 $\pm$ 0.039	33.6 $\pm$ 2.6	0.085 $\pm$ 0.032	122.11 $\pm$ 6.90	57.6 $\pm$ 2.0
gaussian	Cam	5	0.529 $\pm$ 0.022	0.368 $\pm$ 0.023	0.959 $\pm$ 0.013	0.509 $\pm$ 0.021	0.354 $\pm$ 0.022	0.922 $\pm$ 0.015	80.4 $\pm$ 4.5	0.049 $\pm$ 0.012	13382.61 $\pm$ 218.57	121.0 $\pm$ 5.0
gaussian	CauScale	5	0.806 $\pm$ 0.021	0.853 $\pm$ 0.025	0.766 $\pm$ 0.024	0.587 $\pm$ 0.029	0.621 $\pm$ 0.030	0.558 $\pm$ 0.030	26.8 $\pm$ 3.0	0.285 $\pm$ 0.029	6.17 $\pm$ 0.16	41.4 $\pm$ 2.2
gaussian	SDCD	5	0.722 $\pm$ 0.027	0.811 $\pm$ 0.038	0.652 $\pm$ 0.026	0.552 $\pm$ 0.031	0.622 $\pm$ 0.046	0.497 $\pm$ 0.023	30.6 $\pm$ 3.5	0.321 $\pm$ 0.017	139.53 $\pm$ 0.83	37.2 $\pm$ 2.2

Appendix

Table 36: Qualitative comparison without marginalization (

n=2000

d=50

, degree 2, mechanism neveradditive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.827 $\pm$ 0.032	0.966 $\pm$ 0.020	0.725 $\pm$ 0.042	0.807 $\pm$ 0.036	0.943 $\pm$ 0.028	0.708 $\pm$ 0.044	23.0 $\pm$ 4.4	0.086 $\pm$ 0.028	2.24 $\pm$ 0.15	53.6 $\pm$ 3.3
gaussian	Spade-Gauss	5	0.839 $\pm$ 0.022	0.993 $\pm$ 0.004	0.729 $\pm$ 0.035	0.836 $\pm$ 0.023	0.990 $\pm$ 0.007	0.727 $\pm$ 0.036	20.2 $\pm$ 3.0	0.026 $\pm$ 0.011	0.71 $\pm$ 0.08	52.6 $\pm$ 3.6
gaussian	Topic	5	0.765 $\pm$ 0.020	0.769 $\pm$ 0.019	0.763 $\pm$ 0.031	0.746 $\pm$ 0.022	0.750 $\pm$ 0.018	0.744 $\pm$ 0.035	34.8 $\pm$ 3.0	0.058 $\pm$ 0.004	177.65 $\pm$ 17.15	70.8 $\pm$ 3.0
gaussian	Cam	5	0.610 $\pm$ 0.025	0.467 $\pm$ 0.029	0.889 $\pm$ 0.009	0.610 $\pm$ 0.025	0.467 $\pm$ 0.029	0.889 $\pm$ 0.009	82.0 $\pm$ 7.4	0.039 $\pm$ 0.014	12536.20 $\pm$ 52.22	137.8 $\pm$ 8.6
gaussian	CauScale	5	0.784 $\pm$ 0.011	0.867 $\pm$ 0.018	0.717 $\pm$ 0.022	0.592 $\pm$ 0.019	0.654 $\pm$ 0.019	0.542 $\pm$ 0.025	41.0 $\pm$ 3.2	0.298 $\pm$ 0.018	5.98 $\pm$ 0.09	59.2 $\pm$ 2.7
gaussian	SDCD	5	0.703 $\pm$ 0.017	0.803 $\pm$ 0.021	0.627 $\pm$ 0.020	0.514 $\pm$ 0.030	0.585 $\pm$ 0.031	0.459 $\pm$ 0.031	50.2 $\pm$ 5.0	0.323 $\pm$ 0.036	142.96 $\pm$ 2.48	56.4 $\pm$ 4.6

Appendix

Table 37: Qualitative comparison without marginalization (

n=2000

d=50

, degree 3, mechanism additive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.688 $\pm$ 0.016	0.967 $\pm$ 0.018	0.536 $\pm$ 0.021	0.642 $\pm$ 0.018	0.902 $\pm$ 0.016	0.500 $\pm$ 0.022	37.2 $\pm$ 2.3	0.252 $\pm$ 0.019	1.82 $\pm$ 0.09	40.0 $\pm$ 3.5
gaussian	Spade-Gauss	5	0.713 $\pm$ 0.021	0.952 $\pm$ 0.022	0.573 $\pm$ 0.027	0.703 $\pm$ 0.023	0.938 $\pm$ 0.026	0.565 $\pm$ 0.028	33.6 $\pm$ 3.2	0.104 $\pm$ 0.011	0.53 $\pm$ 0.03	43.2 $\pm$ 3.1
gaussian	Topic	5	0.650 $\pm$ 0.025	0.688 $\pm$ 0.025	0.619 $\pm$ 0.031	0.620 $\pm$ 0.028	0.656 $\pm$ 0.031	0.590 $\pm$ 0.030	49.2 $\pm$ 2.8	0.157 $\pm$ 0.024	139.67 $\pm$ 9.67	64.2 $\pm$ 2.9
gaussian	Cam	5	0.574 $\pm$ 0.035	0.422 $\pm$ 0.035	0.914 $\pm$ 0.032	0.528 $\pm$ 0.031	0.388 $\pm$ 0.032	0.841 $\pm$ 0.029	104.4 $\pm$ 11.7	0.100 $\pm$ 0.017	12483.49 $\pm$ 44.34	158.4 $\pm$ 12.6
gaussian	CauScale	5	0.740 $\pm$ 0.010	0.878 $\pm$ 0.013	0.641 $\pm$ 0.018	0.514 $\pm$ 0.038	0.609 $\pm$ 0.043	0.446 $\pm$ 0.036	46.0 $\pm$ 2.5	0.336 $\pm$ 0.029	5.93 $\pm$ 0.06	52.8 $\pm$ 4.9
gaussian	SDCD	5	0.677 $\pm$ 0.027	0.834 $\pm$ 0.016	0.571 $\pm$ 0.030	0.548 $\pm$ 0.021	0.675 $\pm$ 0.016	0.462 $\pm$ 0.024	46.4 $\pm$ 2.4	0.341 $\pm$ 0.011	139.54 $\pm$ 6.00	49.2 $\pm$ 3.9

Appendix

Table 38: Qualitative comparison without marginalization (

n=2000

d=50

, degree 3, mechanism neveradditive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.798 $\pm$ 0.029	0.961 $\pm$ 0.008	0.686 $\pm$ 0.039	0.783 $\pm$ 0.031	0.942 $\pm$ 0.017	0.673 $\pm$ 0.040	34.4 $\pm$ 5.0	0.099 $\pm$ 0.032	2.58 $\pm$ 0.10	68.2 $\pm$ 4.2
gaussian	Spade-Gauss	5	0.808 $\pm$ 0.026	0.974 $\pm$ 0.007	0.693 $\pm$ 0.037	0.805 $\pm$ 0.025	0.971 $\pm$ 0.009	0.691 $\pm$ 0.036	32.0 $\pm$ 5.0	0.044 $\pm$ 0.025	0.84 $\pm$ 0.05	68.0 $\pm$ 3.7
gaussian	Topic	5	0.760 $\pm$ 0.026	0.821 $\pm$ 0.012	0.709 $\pm$ 0.037	0.751 $\pm$ 0.028	0.811 $\pm$ 0.016	0.701 $\pm$ 0.039	44.2 $\pm$ 6.1	0.058 $\pm$ 0.035	207.03 $\pm$ 13.31	82.4 $\pm$ 3.7
gaussian	Cam	5	0.676 $\pm$ 0.013	0.549 $\pm$ 0.014	0.882 $\pm$ 0.016	0.673 $\pm$ 0.011	0.546 $\pm$ 0.013	0.878 $\pm$ 0.014	81.0 $\pm$ 2.6	0.024 $\pm$ 0.011	13761.87 $\pm$ 161.24	154.0 $\pm$ 5.7
gaussian	CauScale	5	0.773 $\pm$ 0.021	0.890 $\pm$ 0.010	0.686 $\pm$ 0.031	0.610 $\pm$ 0.022	0.703 $\pm$ 0.025	0.541 $\pm$ 0.024	52.4 $\pm$ 4.3	0.270 $\pm$ 0.028	5.95 $\pm$ 0.10	73.6 $\pm$ 3.4
gaussian	SDCD	5	0.686 $\pm$ 0.018	0.808 $\pm$ 0.007	0.599 $\pm$ 0.029	0.546 $\pm$ 0.013	0.644 $\pm$ 0.018	0.476 $\pm$ 0.018	64.0 $\pm$ 3.5	0.302 $\pm$ 0.020	137.10 $\pm$ 2.35	71.0 $\pm$ 4.5

Appendix

Table 39: Qualitative comparison without marginalization (

n=2000

d=50

, degree 4, mechanism additive).

noise	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
gaussian	Spade-Hist	5	0.624 $\pm$ 0.026	0.948 $\pm$ 0.017	0.469 $\pm$ 0.033	0.554 $\pm$ 0.025	0.842 $\pm$ 0.026	0.416 $\pm$ 0.030	58.8 $\pm$ 4.5	0.366 $\pm$ 0.023	1.95 $\pm$ 0.09	47.6 $\pm$ 4.3
gaussian	Spade-Gauss	5	0.683 $\pm$ 0.034	0.927 $\pm$ 0.012	0.546 $\pm$ 0.045	0.665 $\pm$ 0.033	0.904 $\pm$ 0.019	0.532 $\pm$ 0.044	49.4 $\pm$ 5.5	0.162 $\pm$ 0.025	0.62 $\pm$ 0.04	56.6 $\pm$ 5.3
gaussian	Topic	5	0.671 $\pm$ 0.024	0.761 $\pm$ 0.010	0.603 $\pm$ 0.037	0.597 $\pm$ 0.029	0.678 $\pm$ 0.027	0.537 $\pm$ 0.037	62.8 $\pm$ 5.3	0.208 $\pm$ 0.042	167.81 $\pm$ 15.06	75.6 $\pm$ 4.3
gaussian	Cam	5	0.567 $\pm$ 0.004	0.417 $\pm$ 0.006	0.888 $\pm$ 0.014	0.507 $\pm$ 0.009	0.373 $\pm$ 0.008	0.794 $\pm$ 0.018	139.6 $\pm$ 9.1	0.128 $\pm$ 0.019	13762.52 $\pm$ 185.92	205.2 $\pm$ 13.5
gaussian	CauScale	5	0.686 $\pm$ 0.032	0.859 $\pm$ 0.033	0.577 $\pm$ 0.042	0.523 $\pm$ 0.054	0.655 $\pm$ 0.066	0.439 $\pm$ 0.050	63.2 $\pm$ 6.2	0.287 $\pm$ 0.038	6.20 $\pm$ 0.14	64.2 $\pm$ 4.5
gaussian	SDCD	5	0.622 $\pm$ 0.025	0.827 $\pm$ 0.022	0.504 $\pm$ 0.035	0.512 $\pm$ 0.029	0.678 $\pm$ 0.013	0.416 $\pm$ 0.036	66.6 $\pm$ 4.6	0.336 $\pm$ 0.027	132.93 $\pm$ 5.03	58.8 $\pm$ 5.3

Appendix

Table 40: Qualitative comparison without marginalization (

n=2000

d=50

, degree 4, mechanism neveradditive).

dataset	n_samples	n_features	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges
causal_chamber	10000	23	Spade-Hist	5	0.514 $\pm$ 0.009	0.591 $\pm$ 0.013	0.456 $\pm$ 0.013	0.502 $\pm$ 0.014	0.577 $\pm$ 0.014	0.446 $\pm$ 0.017	34.0 $\pm$ 0.7	0.087 $\pm$ 0.006	0.97 $\pm$ 0.09	30.2 $\pm$ 1.2
causal_chamber	10000	23	Topic	5	0.471 $\pm$ 0.010	0.409 $\pm$ 0.010	0.554 $\pm$ 0.010	0.188 $\pm$ 0.016	0.164 $\pm$ 0.015	0.221 $\pm$ 0.017	61.6 $\pm$ 1.5	0.431 $\pm$ 0.032	285.54 $\pm$ 17.29	52.8 $\pm$ 0.7
causal_chamber	10000	23	Cam	5	0.334 $\pm$ 0.002	0.212 $\pm$ 0.001	0.795 $\pm$ 0.008	0.082 $\pm$ 0.010	0.052 $\pm$ 0.007	0.195 $\pm$ 0.025	146.8 $\pm$ 1.7	0.656 $\pm$ 0.031	1861.98 $\pm$ 23.31	146.4 $\pm$ 2.0
causal_chamber	10000	23	CauScale	5	0.365 $\pm$ 0.020	0.335 $\pm$ 0.024	0.405 $\pm$ 0.022	0.274 $\pm$ 0.014	0.253 $\pm$ 0.020	0.303 $\pm$ 0.005	59.2 $\pm$ 3.5	0.267 $\pm$ 0.022	10.00 $\pm$ 2.62	47.8 $\pm$ 3.5
causal_chamber	10000	23	SDCD	5	0.628 $\pm$ 0.005	0.785 $\pm$ 0.011	0.523 $\pm$ 0.006	0.493 $\pm$ 0.015	0.617 $\pm$ 0.023	0.410 $\pm$ 0.011	28.6 $\pm$ 0.7	0.123 $\pm$ 0.010	519.69 $\pm$ 15.35	26.0 $\pm$ 0.5
causal_chamber	10000	23	Globe	5	0.254 $\pm$ 0.025	0.483 $\pm$ 0.039	0.174 $\pm$ 0.022	0.124 $\pm$ 0.037	0.253 $\pm$ 0.077	0.082 $\pm$ 0.025	43.2 $\pm$ 1.8	0.221 $\pm$ 0.076	1535.25 $\pm$ 188.01	14.2 $\pm$ 1.6

Appendix

Table 41: Real-world benchmark table for the Causal Chamber setting used in the main paper.

sachs_transform	n_samples	n_features	method	n	skel_f1	skel_prec	skel_rec	f1	prec	rec	shd	order	runtime	pred_edges	true_edges
none	853	11	Spade-Hist	5	0.422 $\pm$ 0.038	1.000	0.271 $\pm$ 0.030	0.348 $\pm$ 0.047	0.810 $\pm$ 0.055	0.224 $\pm$ 0.034	13.2 $\pm$ 0.6	0.506 $\pm$ 0.040	0.13 $\pm$ 0.07	4.6 $\pm$ 0.5	17.0
none	853	11	Spade-Gauss	5	0.595 $\pm$ 0.011	1.000	0.424 $\pm$ 0.012	0.413 $\pm$ 0.027	0.696 $\pm$ 0.049	0.294 $\pm$ 0.019	12.0 $\pm$ 0.3	0.424 $\pm$ 0.051	0.03 $\pm$ 0.00	7.2 $\pm$ 0.2	17.0
none	853	11	Topic	5	0.655 $\pm$ 0.038	0.835 $\pm$ 0.038	0.541 $\pm$ 0.039	0.454 $\pm$ 0.050	0.575 $\pm$ 0.050	0.376 $\pm$ 0.048	12.4 $\pm$ 0.7	0.306 $\pm$ 0.029	2.89 $\pm$ 0.10	11.0 $\pm$ 0.5	17.0
none	853	11	Cam	5	0.605 $\pm$ 0.014	0.535 $\pm$ 0.036	0.718 $\pm$ 0.043	0.377 $\pm$ 0.036	0.333 $\pm$ 0.035	0.447 $\pm$ 0.051	20.6 $\pm$ 1.7	0.482 $\pm$ 0.051	27.39 $\pm$ 0.37	23.4 $\pm$ 2.4	17.0
none	853	11	CauScale	5	0.506 $\pm$ 0.045	0.925 $\pm$ 0.075	0.353 $\pm$ 0.037	0.201 $\pm$ 0.030	0.356 $\pm$ 0.040	0.141 $\pm$ 0.024	15.2 $\pm$ 0.6	0.624 $\pm$ 0.063	7.39 $\pm$ 1.83	6.6 $\pm$ 0.7	17.0
none	853	11	SDCD	5	0.527 $\pm$ 0.021	0.828 $\pm$ 0.023	0.388 $\pm$ 0.024	0.222 $\pm$ 0.035	0.344 $\pm$ 0.046	0.165 $\pm$ 0.029	15.6 $\pm$ 0.2	0.682 $\pm$ 0.030	47.37 $\pm$ 5.26	8.0 $\pm$ 0.5	17.0

Appendix

Table 42: Sachs observational-condition benchmark under the 17-edge bnlearn reference DAG. Rows compare preprocessing transformations for condition 1 of the Benchpress Sachs data; entries are means with standard errors over bootstrap seeds.

Score-Based Causal Discovery

See all 11 papers

TriOpt: A Scalable Algorithm for Linear Causal Discovery
May 17, 2026Rafat Ashraf Joy, Elena ZhelevaStructural Causal Models Causal Discovery
University of Illinois Chicago
Optimization-Free Topological Sort for Causal Discovery via the Schur Complement of Score Jacobians
Apr 28, 2026Rui Wu, Hong XieScore-Based Causal Discovery Causal Discovery
School of Computer Science and Engineering University of Science and Technology of China
SCDM: Scalable Causal Discovery in Nonlinear Temporal Systems with Meta-Learning
Oct 21, 2026Jingbo Wang, Kegeng Tang, Zihao Wang +1Time-Series Causal Discovery Causal Discovery
University of Tennessee at Chattanooga

May 17, 2026J/K move · Enter open · S save

TriOpt: A Scalable Algorithm for Linear Causal Discovery

Rafat Ashraf Joy, Elena Zheleva

University of Illinois Chicago

Structural Causal Models Causal Discovery Causal Structure Learning

Open paper AskPDF arXiv

Learning causal relations from observational data is challenging because the graph search space grows super-exponentially with the number of variables. Ordering-based methods reduce this space by first identifying the topological ordering, whereas continuous optimization methods explore most likely regions of the space by casting DAG learning as a differentiable objective with an acyclicity constraint. Despite their conceptual appeal, both paradigms face significant scalability limitations in high-dimensional settings, restricting their practical applicability. In this work, we introduce a new formulation for linear causal discovery that tightly integrates these two paradigms to achieve substantial gains in scalability without sacrificing accuracy. Our approach, TriOpt, decomposes the problem into two efficient stages. First, it recovers the topological ordering by exploiting the Sherman-Morrison rank-1 downdate together with the additive structure of linear kernels, enabling fast and scalable ordering estimation. Second, given this ordering, we reformulate structure learning as a convex continuous optimization problem that entirely avoids the need for enforcing costly acyclicity constraints. We theoretically show that, under the true ordering, TriOpt exactly recovers the underlying linear DAG. Empirically, across synthetic, semi-synthetic, and real-world datasets, TriOpt achieves orders-of-magnitude speedups over state-of-the-art linear causal discovery methods in high-dimensional regimes, while maintaining comparable or superior accuracy.

Abstract

Score-Based Causal Discovery

Explore similar work

TriOpt: A Scalable Algorithm for Linear Causal Discovery

Optimization-Free Topological Sort for Causal Discovery via the Schur Complement of Score Jacobians

SCDM: Scalable Causal Discovery in Nonlinear Temporal Systems with Meta-Learning