📊 statistics

Iterative Causal Discovery: Per-Edge Impossibility Certificates, Tier-Aware Oracle Queries, and the $1+K$ Lower Bound

This paper introduces an iterative causal discovery protocol for continuous data that assigns per-edge identifiability certificates and failure-mode queries across five gated tiers, establishing a theoretical upper bound of $1+K$ expert interactions to fully recover any Directed Acyclic Graph.

Original authors: Eichi Uehara

Published 2026-05-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Eichi Uehara

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery: Who caused what? You have a pile of clues (data) showing that two things, let's call them "Smoke" and "Fire," often happen together.

Most existing detective tools (algorithms) will look at your clues and immediately draw a map saying, "Smoke causes Fire." But here's the problem: they might be guessing. They might be forcing a direction just to make the map look complete, even if the clues don't actually prove which way the arrow points.

This paper introduces a new, more honest detective protocol. Instead of just drawing a map, it attaches a digital "ID Card" to every single connection on the map.

The Three Types of ID Cards

For every pair of suspects (like Smoke and Fire), the protocol issues one of three types of certificates:

The "Proven" Card (resolved_*):
- The Analogy: The detective found a smoking gun.
- What it means: The data itself, using a specific mathematical rule (like a "Location-Scale Noise" test or an "Information-Geometry" test), proves beyond a doubt that A causes B. The algorithm didn't guess; the math did the work.
- Result: The direction is locked in. No questions asked.
The "Red Herring" Card (resolved_mediated):
- The Analogy: The detective realizes Smoke and Fire aren't directly connected; they are both caused by a third thing, like a "Match."
- What it means: The apparent connection is actually a middleman. The direct link is removed from the map.
The "I Need Help" Card (impossible_*):
- The Analogy: The detective hits a wall. The clues are too vague to tell if Smoke causes Fire or if Fire causes Smoke.
- What it means: The data isn't enough. But instead of just giving up or making a wild guess, this card tells you exactly what question to ask an expert to solve it.
- Example: The card might say, "We can't tell from the data. Ask the expert: 'Is the relationship between Smoke and Fire direct, or is there a hidden cause?'"

The "Tiered" Safety Net

The paper describes a "cascade" of tests, like a series of security checkpoints.

Imagine a bouncer at a club (the data).
The first bouncer checks if the data looks "linear" (simple). If it passes, great!
If it fails, the data moves to the next bouncer, who checks for "non-linear" patterns.
Crucial Rule: If a bouncer isn't sure (the precondition fails), they don't force a decision. They simply say, "I can't vouch for this," and pass the suspect to the next level. If no level can vouch for it, the suspect gets the "I Need Help" card.

This prevents the algorithm from confidently making mistakes just to fill in the blanks.

The "Expert Interview" Strategy

When the algorithm hits a wall (the "I Need Help" cards), it needs to ask a human expert for the answer. But asking questions is expensive (it takes time and effort). The paper proposes a clever way to ask the fewest possible questions to solve the whole mystery.

They introduce two special interview techniques:

The "Hub" Question: Instead of asking about one connection at a time, the expert is asked: "Who are the top K people in this network that have the most outgoing connections?" This identifies the "hubs" of the network instantly.
The "Children" Question: Once a hub is identified, the expert is asked: "Who are the direct children of this specific person?"

The Magic Number (1+K):
The paper proves that if you have a perfect expert who answers correctly, you only need 1 + K questions to solve the entire network, where K is the number of people who have children (non-leaf nodes).

Analogy: If you have a family tree, you don't need to ask "Is Dad the parent of Son?" for every single person. You just ask the parents, "Who are your kids?" and you get the whole tree structure in one go.

What They Tested

The authors tested this on four famous "mystery cases" (datasets named asia, sachs, child, and alarm).

The Result: When they used the "perfect expert" simulation, their method solved the entire mystery with 100% accuracy using exactly the minimum number of questions predicted by their math (1+K).
The Trade-off: If they didn't ask the expert and just relied on the data, they got some connections right but had to leave others blank (or mark them as "unsolvable") rather than guessing wrong.

Summary

This paper doesn't just give you a map; it gives you a map with a legend.

It tells you which parts of the map were found by the data.
It tells you which parts were ruled out.
It tells you exactly which parts are missing and what specific question you need to ask an expert to fill them in.
It proves you can solve the whole puzzle with a surprisingly small number of expert questions if you ask the right ones.

Technical Summary: Iterative Causal Discovery with Per-Edge Impossibility Certificates

Problem Statement
Current causal discovery algorithms typically return a fully oriented directed acyclic graph (DAG) but fail to distinguish between edge directions identified by the data and those imposed by the algorithm to satisfy output constraints. Under standard Markov and faithfulness conditions, observational data identifies only a Markov equivalence class; edge orientations not on v-structures are undetermined by the joint distribution. Existing methods either force orientations on unidentifiable edges (e.g., NOTEARS, DAGMA) without diagnostic justification, or leave them undirected (e.g., FCI) without specifying the specific prior information required to resolve them. Furthermore, continuous optimization methods have been shown to exploit data artifacts (e.g., varsortability) that mimic genuine identification. There is a lack of a principled protocol that provides per-edge auditability, explicitly separating data-driven identifiability from algorithmic imposition, and identifying the specific expert questions needed to resolve unidentifiable edges.

Methodology
The paper proposes a deterministic, three-stage protocol for observational causal discovery on continuous data. The protocol emits a discrete "impossibility certificate" for every candidate edge in a data-only skeleton, categorizing the edge as either resolved (data-identified or mediated) or impossible (data-insufficient, requiring expert input).

Stage 1: Skeleton and Mediator Search:
- Constructs a skeleton using FDR-controlled HSIC tests to discard marginally independent pairs.
- Performs a multi-tier mediator search to identify and drop edges mediated by observed variables.
Stage 2: Gated Identifiability Cascade:
- An eight-tier cascade evaluates remaining edges. The tiers include classical methods (Linear ANM $L_0$ , Nonlinear ANM $L_1$ , HOC LiNGAM $L_2$ ) and five new tiers introduced in this work: LSNM (Location-Scale Noise), IGCI (Information-Geometric), Stein (Score Matching), MDL (Algorithmic Markov Condition), and PEIT (Entropy-Inversion Test).
- Gating Mechanism: Each tier is preconditioned by statistical tests (e.g., Shapiro–Wilk for non-Gaussianity, heteroscedasticity tests). If a tier's precondition fails, it abstains rather than forcing an orientation.
- Cross-Tier Consensus: A "disagreement guard" demotes $L_0$ commits if higher-precision tiers (IGCI, Stein, MDL) contradict the direction, relabeling the edge as impossible_l0_disagrees_with_high_tier.
- Edges not resolved by any tier receive an impossible_* label, which encodes the specific failure mode (e.g., latent confounding, weak nonlinearity) and the corresponding question for a domain expert.
Stage 3: Targeted Oracle Queries:
- The protocol interacts with a domain expert only on edges labeled impossible_*.
- Query Primitives:
  - Per-edge query: Asks for direction (FWD/BWD) or absence.
  - Meta-hub query: Asks for the top- $K$ nodes by out-degree.
  - Node-children query: Asks for the direct children of a specific node, committing all outgoing edges simultaneously.
- Auto-Propagation: After each oracle commit, the system runs zero-cost auto-resolution passes (acyclicity checks, Meek rules, transitive d-separation) to resolve additional edges without further queries.

Key Contributions

Per-Edge Certificates: The protocol assigns a discrete code to every edge. resolved_* codes cite the specific theorem (e.g., $L_{Stein}$ ) justifying the direction, while impossible_* codes record the failure mode and the specific question required to resolve it.
Tier-Aware Abstention: The introduction of five new gated tiers (LSNM, IGCI, Stein, MDL, PEIT) ensures that directions are only committed when a specific identifiability theorem is satisfied. If a precondition fails, the system abstains rather than forcing a potentially spurious orientation.
1+K Interaction Bound: The paper establishes an information-theoretic upper bound of $1+K$ expert interactions to recover any ground-truth DAG, where $K$ is the number of non-leaf vertices. This is achieved by combining a single meta-hub query (to identify targets) with $K$ node-children queries.
Targeted Elicitation: Unlike active learning methods that may request full topological orders or broad interventions, this protocol isolates only the unidentifiable edges and requests the specific information needed to resolve them.

Experimental Results
The protocol was evaluated on four standard benchmarks (Asia, Sachs, Child, Alarm) and synthetic data designed to stress-test specific tiers.

Ideal Oracle Performance: Under the assumption of a perfect oracle, the protocol recovered the ground-truth DAG with Precision = Recall = F1 = 1.000 on all four benchmarks using exactly $1+K$ interactions.
- Alarm (V=37): 46 edges recovered in 27 interactions.
- Sachs (V=11): 17 edges recovered in 8 interactions.
Cascade Efficacy: On the Sachs dataset, the cascade alone resolved 5 of 19 true edges from data alone. The addition of the new safe tiers improved direction precision from 61.5% (base L0-L2) to 66.7% when the disagreement guard was active.
Tier Specificity: Synthetic stress tests confirmed that each new tier is precision-positive on its native regime (e.g., LLSNM on location-scale noise, LIGCI on near-deterministic data) and abstains (fires 0/40) on off-regime data, preventing false positives.
Pareto Frontier: On Sachs, the protocol demonstrated a trade-off between query count and F1 score. A "SAFE-only" approach (cascade without oracle) achieved F1=0.571 with 5 queries, while the full protocol achieved F1=1.000 with 13 queries (using the cascade to reduce the oracle burden).

Significance and Claims
The paper claims to address a fundamental gap in causal discovery: the inability of current methods to distinguish between data-identified directions and algorithmically imposed ones. By attaching a "certificate" to every edge, the protocol provides a transparent audit trail.

Theoretical Contribution: The $1+K$ bound represents the elicitation-side counterpart to intervention-budget bounds in active causal discovery, quantifying the minimum information required to resolve a DAG when expert knowledge is available.
Practical Utility: The protocol allows practitioners to focus expert effort exclusively on unidentifiable edges, reducing the cognitive load by presenting specific, regime-aware questions rather than raw edge directions.
Limitations: The authors explicitly note that the current scope is restricted to continuous variables; discrete Bayesian networks are treated only as a robustness check for the oracle layer. The protocol assumes a perfect oracle; handling noisy or probabilistic expert responses is identified as future work. Additionally, the skeleton construction phase imposes a recall limit, as edges pruned by the initial HSIC test cannot be recovered.

The work positions itself not as a replacement for scalable continuous optimization or constraint-based methods, but as an orthogonal approach that prioritizes per-edge auditability and minimizes the cost of expert elicitation through targeted, certificate-driven queries.

The Three Types of ID Cards

The "Tiered" Safety Net

The "Expert Interview" Strategy

What They Tested

Summary

More like this