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

• URL: http://arxiv.org/abs/2605.27477v1
• Date: Tue, 26 May 2026 12:01:32 GMT
• Title: Iterative Causal Discovery: Per-Edge Impossibility Certificates, Tier-Aware Oracle Queries, and the $1+K$ Lower Bound
• Abstract summary: Causal-discovery algorithms return a directed graph, but provide no principled means of distinguishing edge directions identified by the data from those assigned without an identifying assumption.<n>We introduce a protocol for observational causal discovery on continuous data that attaches to each candidate edge a discrete impossibility certificate.<n>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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• RAD: Rule-Augmented Relational Anomaly Detection [11.251069238986483]
  Anomaly detection is often applied to data stored in relational databases.<n>Most existing methods require flattening multiple tables into a single feature matrix.<n>We propose RAD, a rule-augmented relational anomaly detector.
  arXiv  Detail & Related papers  (2026-08-24T16:36:17Z)
• Intrinsic Structure: Spectral Identifiability for Mechanistic Interpretability [51.56484100374058]
  We prove the first identifiability theorem for a mechanistic-interpretability primitive.<n>The spectrum is an identifiable, model-intrinsic fingerprint with a stated error bar, not a legible decomposition.
  arXiv  Detail & Related papers  (2026-08-10T19:42:01Z)
• SEER: A Self-Grounded Evidence Interface for Controlled Spatial Relation Classification [71.9783246097687]
  SEER hides candidate relations during pair localization, constructs a query-specific view with explicit subject/object roles, and retains the full image and sparse box geometry as complementary evidence.<n>For relation-choice protocols with exact inverse support, an optional refinement swaps the entity roles and changes the forward decision only when exactly one visual state obeys the corresponding inverse relation.<n>The unchanged protocol yields +4.35 to +11.79 on all 2,434 filtered EmbSpatial pair-relation questions across three models.
  arXiv  Detail & Related papers  (2026-08-04T13:16:15Z)
• GoT-CD: Graph-of-Thoughts Causal Discovery and the Fragility of Post-hoc Path-Specific Fairness Audits [2.1092701269163436]
  We show that Graph-of-Thoughts reasoning yields acyclic discovered graphs that are structurally competitive with large language model (LLM) baselines.<n>We introduce GoT-CD, in which the reasoning unit is a complete candidate edge set.<n>GoT-CD returns a valid DAG on all five reported benchmarks and achieves the best DAG-valid F1 score among LLM methods on Asia, Alzheimer's, and COVID-Respiratory datasets.
  arXiv  Detail & Related papers  (2026-08-03T20:59:26Z)
• Towards Anomaly Detection on Relational Data [51.473064583839296]
  We propose a reconstruction-based framework that captures anomalies from both attribute and relational edge reconstruction.<n>RelAD consistently outperforms other baselines while achieving competitive efficiency.
  arXiv  Detail & Related papers  (2026-06-17T02:36:32Z)
• Query-Limited Community Recovery in Stochastic Block Models [6.498092697159669]
  We study exact community recovery in the two-community block model on $n$ vertices under limited and noisy access to network data.<n>We consider both oracle-only access and a combined model where the learner also observes a single subsampled copy of the underlying graph.<n>We show that a two-stage adaptive strategy succeeds with $n+o(n)$ queries in a regime where balanced uniform querying requires $m n$ queries for some $m>1$.
  arXiv  Detail & Related papers  (2026-06-01T10:44:00Z)
• Domain-Aware Hierarchical Contrastive Learning for Semi-Supervised Generalization Fault Diagnosis [49.89578655034085]
  We propose a unified framework termed domain-aware hierarchical contrastive learning (DAHCL) for fault diagnosis.<n>DAHCL captures source-domain geometric characteristics and calibrates pseudo-label predictions across heterogeneous source domains.<n>We also develop a hierarchical contrastive learning module that combines dynamic confidence stratification with fuzzy contrastive supervision.
  arXiv  Detail & Related papers  (2026-04-22T08:41:27Z)
• AEGIS: From Clues to Verdicts -- Graph-Guided Deep Vulnerability Reasoning via Dialectics and Meta-Auditing [9.271196825503417]
  Large Language Models (LLMs) are increasingly adopted for vulnerability detection, yet their reasoning remains fundamentally unsound.<n>We present AEGIS, a novel multi-agent framework that shifts detection from ungrounded speculation to forensic verification over a closed factual substrate.<n>It reduces the false positive rate by up to 54.40% compared to leading baselines, at an average cost of $0.09 per sample without any task-specific training.
  arXiv  Detail & Related papers  (2026-03-21T04:12:04Z)
• Node-Level Uncertainty Estimation in LLM-Generated SQL [13.436696325103147]
  We introduce a semantically aware labeling algorithm that assigns node-level correctness without over-penalizing structural containers or alias variation.<n>We represent each node with a rich set of schema-aware and lexical features - capturing identifier validity, alias resolution, type compatibility, ambiguity in scope, and typo signals.<n>We interpret these probabilities as uncertainty, enabling fine-grained diagnostics that pinpoint exactly where a query is likely to be wrong.
  arXiv  Detail & Related papers  (2025-11-17T23:31:45Z)
• Towards Multiple Missing Values-resistant Unsupervised Graph Anomaly Detection [10.061847825452677]
  We propose M$2$V-UGAD, a multiple missing values-resistant unsupervised GAD framework on incomplete graphs.<n>M$2$V-UGAD consistently outperforms existing unsupervised GAD methods across varying missing rates.
  arXiv  Detail & Related papers  (2025-11-13T03:30:43Z)
• Unsupervised Conformal Inference: Bootstrapping and Alignment to Control LLM Uncertainty [49.19257648205146]
  We propose an unsupervised conformal inference framework for generation.<n>Our gates achieve close-to-nominal coverage and provide tighter, more stable thresholds than split UCP.<n>The result is a label-free, API-compatible gate for test-time filtering.
  arXiv  Detail & Related papers  (2025-09-26T23:40:47Z)
• DeCaFlow: A deconfounding causal generative model [48.86777554649186]
  We introduce DeCaFlow, a deconfounding causal generative model.<n>We extend previous results on causal estimation under hidden confounding to show that a single instance of DeCaFlow provides correct estimates for all causal queries identifiable with do-calculus.<n>Our empirical results on diverse settings show that DeCaFlow outperforms existing approaches, while demonstrating its out-of-the-box applicability to any given causal graph.
  arXiv  Detail & Related papers  (2025-03-19T11:14:16Z)
• SPADE: Semi-supervised Anomaly Detection under Distribution Mismatch [58.04518381476167]
  SPADE shows state-of-the-art semi-supervised anomaly detection performance across a wide range of scenarios with distribution mismatch. In some common real-world settings such as model facing new types of unlabeled anomalies, SPADE outperforms the state-of-the-art alternatives by 5% AUC in average.
  arXiv  Detail & Related papers  (2022-11-30T23:39:11Z)
• SIOD: Single Instance Annotated Per Category Per Image for Object Detection [67.64774488115299]
  We propose the Single Instance annotated Object Detection (SIOD), requiring only one instance annotation for each existing category in an image. Degraded from inter-task (WSOD) or inter-image (SSOD) discrepancies to the intra-image discrepancy, SIOD provides more reliable and rich prior knowledge for mining the rest of unlabeled instances. Under the SIOD setting, we propose a simple yet effective framework, termed Dual-Mining (DMiner), which consists of a Similarity-based Pseudo Label Generating module (SPLG) and a Pixel-level Group Contrastive Learning module (PGCL)
  arXiv  Detail & Related papers  (2022-03-29T08:49:51Z)
• SoQal: Selective Oracle Questioning for Consistency Based Active Learning of Cardiac Signals [17.58391771585294]
  Clinical settings are often characterized by abundant unlabelled data and limited labelled data. One way to mitigate this burden is via active learning (AL) which involves the (a) acquisition and (b) annotation of informative unlabelled instances. We show that BALC can outperform start-of-the-art acquisition functions such as BALD, and SoQal outperforms baseline methods even in the presence of a noisy oracle.
  arXiv  Detail & Related papers  (2020-04-20T18:20:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.