arXiv：cs.LG· Upala Junaida Islam, Abdelmonem Elrefaey, Rong Pan·· 4 小时前AI 评分37
DECO：方向性证据引导的精确 DAG 学习搜索空间缩减
Directional Evidence Guided Search-Space Reduction for Exact DAG Learning
AI 导读
研究者提出非参数混合框架 DECO，从观测数据中提取依赖与方向性证据，在精确优化前构建可接受的父节点集，从而缩减搜索空间。理论分析证明可接受父节点集配置空间呈指数级缩减，并量化了有界边级遗漏对保留真实父结构概率的影响。在基准贝叶斯网络及合成离散、连续 DAG 上的实验显示搜索空间大幅缩减，同时保持有竞争力的结构恢复性能。
正文
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.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.09136 [cs.LG] |
| (or arXiv:2610.09136v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.09136 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Upala Junaida Islam [view email]
[v1]
Tue, 6 Oct 2026 21:29:15 UTC (3,486 KB)
来源：arXiv：cs.LG · arxiv.org