Iterative Causal Discovery: Per-Edge Impossibility Certificates, Tier-Aware Oracle Queries, and the 1+K Lower Bound
Not on the map. Why?
Abstract (arXiv)
Causal-discovery algorithms return a directed graph, yet provide no principled means of distinguishing edge directions identified by the data from those assigned without an identifying assumption. Under the standard Markov and faithfulness conditions, the observational distribution identifies only a Markov equivalence class; orientations within that class are not determined by the joint distribution and cannot be recovered from additional samples alone, but require either a functional restriction or an intervention. We introduce a protocol for observational causal discovery on continuous data that attaches to each candidate edge a discrete impossibility certificate: a RESOLVED code records the identifiability theorem under which the direction was committed, while an IMPOSSIBLE code records the failure mode together with the specific question a domain expert must answer to resolve it. The bivariate cascade is extended with five gated identifiability tiers LSNM, IGCI, Stein, MDL, and PEIT that abstain when their precondition test rejects. Two oracle primitives, the meta-hub query and the node-children query, jointly establish an upper bound of 1+K expert interactions sufficient to recover any DAG, where K denotes the number of non-leaf vertices. Under an ideal-oracle assumption, the bound is met exactly on the asia, sachs, child, and alarm benchmarks.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 14 of its 49 references that are in the map. First posted on arXiv 26 May 2026.
Builds on
14 of 49 references.
References · 14
- 2018DAGs with NO TEARS: Continuous Optimization for Structure Learningcited by 752
- 2013Learning Bayesian Networks: The Combination of Knowledge and Statistical Datacited by 187
- 2021Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy To Gamecited by 161
- 2022DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterizationcited by 140
- 2022Score matching enables causal discovery of nonlinear additive noise modelscited by 111
- 2021DiBS: Differentiable Bayesian Structure Learningcited by 106
- 2022Amortized Inference for Causal Structure Learningcited by 90
- 2021BCD Nets: Scalable Variational Approaches for Bayesian Causal Discoverycited by 68
- 2015Learning Causal Graphs with Small Interventionscited by 63
- 2022On the Identifiability and Estimation of Causal Location-Scale Noise Modelscited by 56
- 2022Interventions, Where and How? Experimental Design for Causal Models at Scalecited by 49
- 2021Variational Causal Networks: Approximate Bayesian Inference over Causal Structurescited by 43
Built on by
Not cited yet.