Uehara's causal discovery protocol cuts expert queries to 1+K bound

Eichi Uehara's new paper tackles a fundamental problem in causal discovery: current algorithms return a directed graph but cannot distinguish which edge directions are justified by the data versus those assigned under untestable assumptions. Under standard Markov and faithfulness conditions, observational data only identifies a Markov equivalence class, leaving orientations ambiguous. Uehara introduces a protocol that assigns each edge a discrete impossibility certificate: a RESOLVED code records the identifiability theorem used, while an IMPOSSIBLE code documents the failure mode and the exact question a domain expert must answer to resolve it.

The protocol extends a bivariate cascade with five gated identifiability tiers—LSNM, IGCI, Stein, MDL, and PEIT—that abstain when their precondition tests reject. To minimize expert involvement, two oracle primitives (meta-hub query and node-children query) jointly guarantee an upper bound of 1+K expert interactions to recover any DAG, where K is the number of non-leaf vertices. Under ideal-oracle assumptions, the bound is met exactly on the asia, sachs, child, and alarm benchmark networks. The work provides both theoretical guarantees and practical tools for researchers needing reliable causal graphs from mixed data and domain knowledge.