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

Jun 19, 2026cs.LG

A Framework for Directed Acyclic Hypergraph Learning

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.

Zhiyuan Dong, Carlos Mundo-Levano, Wei Qian +2

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

Ask PDF

May 19, 2026cs.LG

Exploiting Non-Negativity in DAG Structure Learning

This work addresses the problem of learning directed acyclic graphs (DAGs) from nodal observations generated by a linear structural equation model. DAG learning is a central task in signal processing, machine learning, and causal inference, but it remains challenging because acyclicity is a global combinatorial property. Continuous acyclicity constraints have led to important algorithmic advances by replacing the discrete DAG constraint with smooth equality constraints. However, existing formulations still involve difficult non-convex optimization landscapes and may suffer from degenerate first-order optimality conditions. Here, we restrict attention to DAGs with non-negative edge weights and exploit this additional structure to obtain a simpler characterization of acyclicity. Building on this characterization, we formulate a regularized non-negative DAG learning problem and develop an algorithm based on the method of multipliers. We further analyze the benign optimization landscape induced by non-negativity. In the population regime, we show that the true DAG is the unique global minimizer of the proposed augmented-Lagrangian formulation; moreover, the landscape contains no spurious interior stationary points, and the true DAG is the only acyclic KKT point. Numerical experiments on synthetic and real-world data show that the proposed method improves over state-of-the-art continuous DAG-learning alternatives.

Samuel Rey, Madeline navarro, Gonzalo Mateos

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

Acyclic Graphs Graph Representation Learning Causal Inferences

Ask PDF

Aug 5, 2026cs.LG

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

Bayesian causal discovery seeks to determine the posterior distribution of causal theories, which are interpreted as directed acyclic graphs (DAGs) that explain the observed data. The resulting posterior allows systematic reasoning regarding epistemic uncertainty within these theories. Nonetheless, finding such graphs is difficult due to identifiability problems and limited observational data. Furthermore, precisely approximating posterior over graphs is challenging given vast range of potential DAGs. Recent Bayesian approaches have addressed some of these challenges, yet they remain limited as they fail to encode dependencies between edges, and lack principled ways to incorporate domain knowledge as inductive biases during the search process. To overcome these limitations, we propose SVI-DAG, a structured variational inference approach to Bayesian causal discovery using observational data and prior beliefs that uses normalizing flows to model dependencies between edges, supporting expressive and multimodal posterior learning over DAGs. To mitigate mode seeking behaviour in evidence lower bound optimization and promote mode coverage, we use stein variational gradient descent to update the node potentials using a kernel in acyclicity space. We evaluate SVI-DAG against 5 state-of-the-art Bayesian DAG learning methods and demonstrate superior performance in uncertainty quantification while remaining competitive in terms of structural accuracy.

Shrenik Zinage

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.

Causal Discovery Methods Bayesian Networks Variational Inference Discovery

Ask PDF