The paper introduces COARSE, a score‑based method for learning cluster directed acyclic graphs (DAGs) from interventional data. COARSE retains the two‑phase structure of prior constraint‑based approaches—first identifying clusters, then edges—but replaces the edge‑learning phase with a score‑based local search under a cluster‑level BIC score, assuming linear Gaussian relationships. The authors prove polynomial‑time complexity and consistency (given correct intervention targets) and demonstrate that COARSE achieves comparable edge recovery to state‑of‑the‑art methods while being up to two orders of magnitude faster, even on dense graphs with hundreds of nodes.
By Gaetano Tedesco (University of Amsterdam), Alex Markham (University of Copenhagen)
The paper introduces DECO, a non‑parametric hybrid framework that uses directional evidence from observational data to prune the search space of parent‑set configurations before performing exact DAG optimization. By eliminating empirically unsupported parent configurations, DECO achieves an exponential reduction in the admissible configuration space while maintaining flexibility for plausible edge orientations. Experiments on benchmark Bayesian networks and synthetic DAGs show substantial search‑space reduction and competitive structure‑recovery performance, with favorable structural Hamming distances across many settings.
By Upala Junaida Islam, Abdelmonem Elrefaey, Rong Pan
arXiv:2601. 16249v3 Announce Type: replace-cross Abstract: Learning DAG structures from purely observational data remains a long-standing challenge across scientific domains.
By Vy Vo, He Zhao, Trung Le, Edwin V. Bonilla, Dinh Phung
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 exac...
The paper evaluates four main approaches to scalable nonlinear causal discovery—differentiable, amortized, score‑matching, and combinatorial search—highlighting their distinct accuracy‑runtime trade‑offs. It introduces SPADE, a spline‑based score‑evaluation method that compiles and reuses sufficient statistics, reducing combinatorial search complexity from O(nd³) to O(nd²+d³). Empirical results show SPADE dramatically extends the scalability‑accuracy frontier, solving large‑scale problems with high structural accuracy on both synthetic and real‑world data.
By Hendrik Suhr, Sascha Xu, Jilles Vreeken
The paper tackles selecting a cost‑constrained set of experiments that most effectively tighten bounds on a partially identifiable causal query. It formalizes this as the NP‑hard max‑potency problem, introduces efficient graphical pruning rules to reduce the search space, and demonstrates the approach on synthetic graphs and real NHANES data to estimate the effect of physical activity on diabetes.
By Tobias Maringgele, Jalal Etesami
arXiv:2606. 18807v1 Announce Type: cross Abstract: The field of learning-augmented algorithms has demonstrated that machine-learned predictions can bypass worst-case lower bounds across a wide range of problems.
By Tatiana Belova, Yuriy Dementiev, Danil Sagunov
arXiv:2603. 03672v2 Announce Type: replace Abstract: The Shapley value provides a principled foundation for data valuation, but exact computation is #P-hard due to the exponential coalition space.
By Xuan Yang, Hsi-Wen Chen, Ming-Syan Chen, Jian Pei
arXiv:2602. 14772v2 Announce Type: replace Abstract: The Winner Determination Problem (WDP) in combinatorial auctions is NP-hard, and no existing method reliably predicts which instances will defeat fast greedy heuristics.
By Sungwoo Kang
arXiv:2606. 01400v1 Announce Type: cross Abstract: Evaluating large language models (LLMs) across comprehensive benchmarks is expensive and time-consuming.
By Denica Kjorvezir, Marko Djukanovi\'c, Ana Gjorgjevikj, Gjorgjina Cenikj, Tome Eftimov
arXiv:2511.22435v2 Announce Type: replace
Abstract: Invariant learning on graphs aims to build predictors that rely on causal substructures rather than on environment-specific shortcuts. Current meth...
By Ali Ghasemi, Farooq Ahmad Wani, Maria Sofia Bucarelli, Fabrizio Silvestri
The paper introduces SURE-Ridge, a closed‑form estimator for recovering the directed acyclic graph of an equal‑variance linear Gaussian structural equation model. It performs parallel node‑wise regressions with regularization parameters selected via Stein's unbiased risk estimate and then applies adaptive thresholding to produce a DAG from a soft adjacency matrix. Experiments show that SURE‑Ridge attains the lowest structural Hamming distance in small‑sample settings and the fastest run time across all tested sample sizes compared to NOTEARS, DAGMA, and GBNSL.
By Sambit Mishra, Urbashi Mitra