Directional Evidence Guided Search-Space Reduction for Exact DAG Learning

Upala Junaida Islam; Abdelmonem Elrefaey; Rong Pan

cs.LGOct 6, 2026

Directional Evidence Guided Search-Space Reduction for Exact DAG Learning

Authors: Upala Junaida Islam, Abdelmonem Elrefaey, Rong Pan

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

Abstract

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.

Figures & tables

Figure 1: DECO pipeline on the Asia network: (a) Dependency screening from mutual information, (b) Directional evidence extraction and admissible parent-set construction from the proposed asymmetry measures (confidence of these directions is implied through edge thickness, and ambiguous edges are dashed in gray), (c) Final DAG obtained after the exact optimization over the restricted search space (the false positive edge is marked red).

Network	Method	Omission Rate $\downarrow$	Commission Rate $\downarrow$
Asia	MI	$\mathbf{0.09\pm 0.076}$	$0.21\pm 0.048$
	MMD	$0.75\pm 0$	$0.56\pm 0.029$
	G-Lasso	$0.36\pm 0.1020$	$0.17\pm 0.086$
Sachs	MI	$\mathbf{0.01\pm 0.0226}$	$0.32\pm 0.008$
	MMD	$0.25\pm 0.0318$	$0.68\pm 0.017$
	G-Lasso	$0.56\pm 0.0591$	$0.05\pm 0.022$

Table 1: Comparison of skeleton quality measured by omission (missing-edge)

=\frac{FN}{TP+FN}

and commission (extra-edge)

=\frac{FP}{FP+TN}

rates. Lower omission preserves true parent relations, whereas lower commission yields a smaller admissible search space.

Figure 2: Trade-off between search-space reduction and Type II error illustrating the effect of increasing the MI threshold. Each point corresponds to one threshold value for the ER graph with $n=50,p=0.05$ and variable $N$ .

Figure 3: Average search-space reduction achieved by DECO on Erdős-Rényi DAGs of varying size and edge probability $=0.15$ . The reduction ratio is computed as $1-\frac{\Omega_{DECO}}{\Omega_{Full}}$

Figure 4: Sensitivity of directional evidence thresholds $\delta_{S}$ and $\delta_{NS}$ . Increasing the thresholds generally improves the reliability of committed orientations at the expense of directional coverage and increased ambiguity. The outlined cell indicates the threshold pair used in the main experiments.

Network	Type	Node	Arc/Density
Asia	BN	8	8
Sachs	BN	11	17
Child	BN	20	25
Insurance	BN	27	52
Water	BN	32	66
Hailfinder	BN	56	66

Table 2: Reference networks with their features

Panel of Figure 5 — Figure 5: Structural Hamming Distance (SHD) comparison of DECO and other competing methods on (a) benchmark discrete Bayesian networks and (b) nonlinear Gaussian Erdős-Rényi DAGs, all at $N=10,000$ observations. Error bars denote one standard deviation over repeated runs. Lower values indicate better structure recovery. The y-axis is displayed on a logarithmic scale.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6: Sensitivity of MI-based dependency screening to $\delta_{MI}$ across graph sizes $n$ and sample size to graph size ratio $N/n$ for discrete Erdős–Rényi DAGs with $p=0.05$ . Increasing $\delta_{MI}$ generally decreases commission and increases search-space reduction, but eventually increases omission, illustrating the trade-off between structural preservation and pruning.

Data size	Method	SHD $\downarrow$	FDR $\downarrow$	TPR $\uparrow$	FPR $\downarrow$
Network: Asia (Nodes: 8, Arcs: 8)
1000	PC	11.36 $\pm$ 0.975	0.88 $\pm$ 0.065	0.12 $\pm$ 0.070	0.14 $\pm$ 0.033
	GES	12.58 $\pm$ 1.002	0.89 $\pm$ 0.051	0.12 $\pm$ 0.047	0.17 $\pm$ 0.028
	HC	4.04 $\pm$ 2.191	0.35 $\pm$ 0.226	0.59 $\pm$ 0.180	0.06 $\pm$ 0.040
	GOBNILP	2.82 $\pm$ 1.506	0.24 $\pm$ 0.134	0.74 $\pm$ 0.098	0.04 $\pm$ 0.026
	DECO	1.00 $\pm$ 0.283	0.01 $\pm$ 0.030	0.88 $\pm$ 0.035	0.00 $\pm$ 0.005

Appendix

Table 3: Comparison of DAG learning performance on benchmark discrete networks

Data size	Method	SHD $\downarrow$	FDR $\downarrow$	TPR $\uparrow$	FPR $\downarrow$
Nodes: 25, Edge probability: 0.15
1000	PC	19.38 $\pm$ 5.779	0.3 $\pm$ 0.085	0.74 $\pm$ 0.114	0.03 $\pm$ 0.007
	GES	16.28 $\pm$ 5.923	0.27 $\pm$ 0.087	0.82 $\pm$ 0.088	0.02 $\pm$ 0.009
	HC	19.82 $\pm$ 6.069	0.31 $\pm$ 0.099	0.63 $\pm$ 0.092	0.02 $\pm$ 0.008
	GOBNILP	31.80 $\pm$ 5.437	0.43 $\pm$ 0.083	0.30 $\pm$ 0.054	0.02 $\pm$ 0.003
	DECO	13.96 $\pm$ 5.269	0.23 $\pm$ 0.094	0.69 $\pm$ 0.094	0.02 $\pm$ 0.007

Appendix

Table 4: Comparison of DAG learning performance on Erdős-Rényi Graphs and discrete data

Data size	Method	SHD $\downarrow$	FDR $\downarrow$	TPR $\uparrow$	FPR $\downarrow$
Nodes: 25, Edge probability: 0.15
1000	PC	21.53 $\pm$ 6.492	0.34 $\pm$ 0.090	0.71 $\pm$ 0.100	0.03 $\pm$ 0.009
	GES	21.90 $\pm$ 10.239	0.34 $\pm$ 0.110	0.81 $\pm$ 0.099	0.04 $\pm$ 0.015
	HC	29.10 $\pm$ 6.519	0.46 $\pm$ 0.080	0.70 $\pm$ 0.081	0.05 $\pm$ 0.008
	NOTEARS	25.27 $\pm$ 3.844	0.00 $\pm$ 0.013	0.46 $\pm$ 0.043	0.00 $\pm$ 0.001
	GOLEM	21.30 $\pm$ 4.518	0.02 $\pm$ 0.026	0.54 $\pm$ 0.049	0.00 $\pm$ 0.001

Appendix

Table 5: Comparison of DAG learning performance on Erdős-Rényi Graphs and continuous (Non-linear Gaussian) data

Data size	Method	SHD $\downarrow$	FDR $\downarrow$	TPR $\uparrow$	FPR $\downarrow$
Nodes: 25, Edge probability: 0.15
1000	PC	32.33 $\pm$ 10.162	0.41 $\pm$ 0.100	0.52 $\pm$ 0.140	0.03 $\pm$ 0.008
	GES	33.35 $\pm$ 30.075	0.42 $\pm$ 0.198	0.83 $\pm$ 0.146	0.06 $\pm$ 0.053
	HC	78.25 $\pm$ 13.139	0.71 $\pm$ 0.066	0.64 $\pm$ 0.097	0.13 $\pm$ 0.033
	NOTEARS	4.00 $\pm$ 5.172	0.02 $\pm$ 0.038	0.94 $\pm$ 0.056	0.00 $\pm$ 0.004
	GOLEM	1.25 $\pm$ 2.222	0.01 $\pm$ 0.022	0.99 $\pm$ 0.027	0.00 $\pm$ 0.002

Appendix

Table 6: Comparison of DAG learning performance on Erdős-Rényi Graphs and continuous (Linear Gaussian) data

Explore similar work

A Framework for Directed Acyclic Hypergraph Learning
Jun 19, 2026Zhiyuan Dong, Carlos Mundo-Levano, Wei Qian +2Directed Acyclic Graph Hypergraphs
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, Gonzalo MateosAcyclic Graphs Graph Representation Learning
Dept. of Signal Theory and Communications, Universidad Rey Juan Carlos, Madrid, Spain · Dept. of Electrical and Computer Engineering, Rice University, Houston, TX 77005, USA · Dept. of Electrical and Computer Engineering, University of Rochester, Rochester, NY 14627, USA
SVI-DAG: A Structured Variational Inference Approach to Bayesian Causal Discovery
Aug 5, 2026Shrenik ZinageCausal Discovery Methods Bayesian Networks
Massachusetts Institute of Technology · This work was conducted while the author was a PhD student at Purdue University, independently of the author’s dissertation research.

Jun 19, 2026, cs.LGJ/K move · Enter open · S save

A Framework for Directed Acyclic Hypergraph Learning

Zhiyuan Dong, Carlos Mundo-Levano, Wei Qian, Daniel Lau+1

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

Directed Acyclic Graph Hypergraphs Causal

Open paper AskPDF arXiv

Continuous optimization methods for learning Directed Acyclic Graphs (DAGs) operate on weighted adjacency matrices and are therefore limited to pairwise causal relationships. We propose a framework for learning Directed Acyclic Hypergraphs (DAHGs) from observational data, capturing joint parental influences that pairwise models cannot represent. Our approach rests on three components: (i) a generalized linear structural equation model (SEM) with multiplicative interaction terms whose non-zero weights correspond one-to-one with directed hyperedges; (ii) a weighted adjacency tensor representation whose acyclicity is characterized via nilpotency under the tensor t-product; and (iii) a differentiable acyclicity constraint derived through the Fourier decomposition of the t-product, which reduces tensor nilpotency to slice-wise matrix nilpotency and enables least-squares learning via the augmented Lagrangian method.

Abstract

Explore similar work

A Framework for Directed Acyclic Hypergraph Learning

Exploiting Non-Negativity in DAG Structure Learning

SVI-DAG: A Structured Variational Inference Approach to Bayesian Causal Discovery