Hold-Out Scoring for Efficient Gaussian DAG Learning

Donguk Shin; Byeongguk Kang; Inseol Lee; Gunwoong Park

stat.MLOct 2, 2026

Hold-Out Scoring for Efficient Gaussian DAG Learning

Authors: Donguk Shin, Byeongguk Kang, Inseol Lee, Gunwoong Park

Organizations: Department of Statistics, Seoul National University. · Interdisciplinary Program in Artificial Intelligence, Seoul National University. · Institute for Data Innovation in Science, Seoul National University.

Abstract

High-dimensional Gaussian DAG learning faces a statistical-computational gap: methods with sharp sample complexity rely on computationally expensive subset search and a supplied indegree bound, whereas polynomial-time alternatives have less favorable sample complexity. We introduce HOST, an efficient DAG learning algorithm that replaces subset search with nodewise hold-out scoring and convex regression, without requiring a supplied indegree bound. Our key insight is that recovering a correct ordering does not require uniformly small estimation errors in ordering scores but only one-sided control of those errors. In the ordering step, HOST exploits the fact that score estimation using hold-out samples inflates ordering scores in expectation, which is the favorable direction for candidates that should not yet be selected. Given the ordering, HOST recovers parents by recursively removing indirect effects from total effects between two nodes. Under suitable conditions, HOST exactly recovers a $p$ -node DAG of maximum indegree $d$ with sample complexity of order $d\log p$ in polynomial time. Experiments show that HOST achieves competitive graph recovery while exhibiting favorable runtime scaling.

Figures & tables

Reference	Sample complexity	Computational complexity	Irrep.	Input $q$
Ghoshal and Honorio (2018)	$n\gtrsim d_{\mathrm{m}}^{4}\log p$	$\widetilde{O}(p^{3}+pd_{\mathrm{m}}^{4})$	$\times$	$\times$
Chen et al. (2019)	$n\gtrsim d^{2}\log p$	$p^{O(q)}$	$\times$	$\checkmark$
Park et al. (2021)	$n\gtrsim d_{\mathrm{m}}^{2}\log p$	$O\{n(p^{3}+p^{2}d_{\mathrm{m}}^{2})\}$	$\checkmark$	$\times$
Gao et al. (2022)	$n\gtrsim d\log(p/d)$	$p^{O(q)}$	$\times$	$\checkmark$
Daskalakis et al. (2025) , Alg. 1	$n\gtrsim d\log(p/d)$	$p^{O(q)}$	$\times$	$\checkmark$
Daskalakis et al. (2025) , Alg. 2/3	$n\gtrsim d^{4}\log p$	$\operatorname{poly}(n,p)$	$\times$	$\checkmark$

Table 1: Comparison of Gaussian DAG learning algorithms. The results for Chen et al. (2019) concern ordering recovery only. In this table,

\gtrsim

suppresses constants, including model-dependent factors.

\widetilde{O}

suppresses logarithms. Irrep. denotes irrepresentability. Input

q

indicates whether a supplied indegree bound

q\geq d

is required.

Panel of Figure 1 — Figure 1: Panel (a) shows a 127-node layered DAG with the ancestral set $S$ shaded, the designated remaining source $X_{\rm src}$ in blue, and the designated remaining nonsource $X_{\rm ns}$ in red. Panel (b) shows mean Lasso ordering scores for in-sample (In) and hold-out (HO) scoring using $X_{S}$ on a log scale. Error bars indicate one standard deviation across repetitions, computed on the original score scale. Horizontal lines mark population scores of 0.75 for $X_{\rm src}$ and 1.93 for $X_{\rm ns}$ . Panel (c) shows the fraction of repetitions with $X_{\rm src}$ scoring below $X_{\rm ns}$ , with 95% Wilson intervals. Appendix D.1 gives the settings.

Panel of Figure 2 — Figure 2: Graph recovery rate of HOST with $\pm 1$ standard error over 200 repetitions. Panels (a)–(d) overlay curves for different $d$ at fixed $p$ , and (e)–(h) for different $p$ at fixed $d$ .

Panel of Figure 3 — Figure 3: Recovery accuracy and runtime scaling. Recovery uses $d$ = 3 and shows means $\pm 1$ standard error over 50 paired repetitions. Runtime uses $n$ = 100 and reports mean full-fit time in seconds (log scale), including tuning, over 20 paired repetitions.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 4 — Figure 4: Graph recovery for $d$ = 3. Panels (a)–(c) use $p$ = 50, and (d)–(f) use $p$ = 200. Columns show exact recovery, F1, and SHD. Points and error bars show means $\pm 1$ standard error over 50 paired repetitions.

Panel of Figure 5 — Figure 5: Mean full-fit time (seconds, log scale) at $n$ = 100, including tuning, over 20 paired repetitions. Panels (a)–(e) vary $d$ at fixed $p$ , and (f)–(j) vary $p$ at fixed $d$ .

Figure 6: Graph recovery for ER, hub, and bipartite DAGs in the first, second, and third rows, respectively, with

p

= 30. Columns show exact recovery, F1, and SHD. Points and error bars show means

\pm 1

standard error across 50 paired repetitions.

Figure 7: Ordering recovery and computational cost at

p

= 50. Rows show Kendall distance and runtime, and columns show

d

= 2, 3, 4. Points and error bars show means

\pm 1

standard error across 50 paired repetitions.

Figure 8: Parent recovery with the true ordering and oracle tuning at

p

= 50. Rows correspond to

d

= 2, 3, 4, and columns show SHD, precision, and recall. Each method selects

c\in\{0.5,1,2,3,4,5\}

by minimizing SHD separately in each repetition. Points and error bars show means

\pm 1

standard error across 50 paired repetitions.

Method	Parameters and selection procedure
HOST	Select $c_{\mathrm{ord}}\in\mathcal{C}$ by pooled two-fold CV, then $c_{j}\in\mathcal{C}$ for each node by EBIC.
HLSM	For each $c\in\mathcal{C}$ , fit with Lasso penalty $\lambda=c\sqrt{\log p/n}$ .
TD-BSS	For every $(q,c)\in Q\times\mathcal{C}$ , fit with supplied indegree bound $q$ and parent-selection threshold $\eta=c\log p/n$ .
TD-BIC	For each $q\in Q$ , select each parent set by minimizing nodewise BIC over subsets of at most $q$ earlier nodes.
TD-Lasso	For each $q\in Q$ , recover the ordering and select nodewise Lasso penalties by ten-fold cross-validation using the one-standard-error rule.
Daskalakis Alg. 1	For every $(q,c_{b})\in Q\times\mathcal{C}$ , fit with supplied indegree bound $q$ and $b_{\min}=c_{b}\sqrt{\log p/n}$ .

Appendix

Table 2: Real-data tuning parameters and candidate construction.

Method	F1	SHD	F1	SHD
	Sachs		Light Tunnel
HOST	0.385	16	0.518	41
HLSM	0.276	21	0.477	57
TD-BSS	0.303	23	0.344	80
TD-BIC	0.385	16	0.506	41
TD-Lasso	0.200	16	0.517	43

Appendix

Table 3: Directed F1 and SHD on the full Sachs and Light Tunnel datasets. Bold entries indicate the highest F1 or lowest SHD in each column.

Graph Structure Learning

Graph structure learning infers or adapts network connections from data for statistical discovery and downstream prediction.

See all 139 papers

Directional Evidence Guided Search-Space Reduction for Exact DAG Learning
Oct 6, 2026Upala Junaida Islam, Abdelmonem Elrefaey, Rong PanScore-Based Causal Discovery Bayesian Network Structure Learning
School of Computing and Augmented Intelligence, Arizona State University, Tempe, AZ 85281, USA.
A Framework for Directed Acyclic Hypergraph Learning
Jun 19, 2026Zhiyuan Dong, Carlos Mundo-Levano, Wei Qian +2Structural Causal Models Causal Structure Learning
Institute for Financial Services Analytics, University of Delaware, Newark, DE 19716, USA · Department of Electrical and Computer Engineering, University of Delaware, Newark, DE 19716, USA · Department of Applied Economics AND Statistics, University of Delaware, Newark, DE 19716, USA +1
Exploiting Non-Negativity in DAG Structure Learning
May 19, 2026Samuel Rey, Madeline navarro, Santiago Segarra +1Graph Structure Learning Structural Causal Models
Dept. of Electrical and Computer Engineering, University of Rochester, Rochester, NY 14627, USA

Oct 6, 2026J/K move · Enter open · S save

Directional Evidence Guided Search-Space Reduction for Exact DAG Learning

Upala Junaida Islam, Abdelmonem Elrefaey, Rong Pan

School of Computing and Augmented Intelligence, Arizona State University, Tempe, AZ 85281, USA.

Score-Based Causal Discovery Bayesian Network Structure Learning Causal Discovery Causal Structure Learning Bayesian Networks

Open paper AskPDF arXiv

Learning a directed acyclic graph (DAG) from observational data is a challenging combinatorial problem due to the exponential growth in the number of candidate parent-set configurations. Existing exact score-based methods often require computationally intensive combinatorial search, whereas constraint-based methods can become unreliable or computationally demanding as graph size and conditioning-set complexity increase. We develop a non-parametric hybrid framework, referred to as DECO (Directional Evidence-guided Configuration Optimization), that extracts dependency and directional evidence from observation data to construct admissible parent sets prior to exact optimization. It reduces the optimization search space by eliminating empirically unsupported parent configurations while preserving flexibility for all plausible edge orientations. Theoretical analysis establishes an exponential reduction in the admissible parent-set configuration space and quantifies how bounded edge-level omission affects the probability of retaining the true parent structure. Experiments on benchmark Bayesian networks and synthetic discrete and continuous DAGs demonstrate substantial search-space reduction while achieving competitive structure-recovery performance, with favorable structural Hamming distance across many evaluated settings. These results show that directional evidence can provide an effective preprocessing mechanism for reducing the computational burden of exact DAG learning without requiring a fixed parametric structural~model.

Abstract

Graph Structure Learning

Explore similar work

Directional Evidence Guided Search-Space Reduction for Exact DAG Learning

A Framework for Directed Acyclic Hypergraph Learning

Exploiting Non-Negativity in DAG Structure Learning