mlsanityData to 14 Oct 2026

Verification and search algorithms for causal DAGs

arXiv 2206.15374 ↗First posted 30 Jun 2022cs.LG cs.DM cs.DScited by 18

Not on the map. Why?

Abstract (arXiv)

We study two problems related to recovering causal graphs from interventional data: (i) textitverification, where the task is to check if a purported causal graph is correct, and (ii) textitsearch, where the task is to recover the correct causal graph. For both, we wish to minimize the number of interventions performed. For the first problem, we give a characterization of a minimal sized set of atomic interventions that is necessary and sufficient to check the correctness of a claimed causal graph. Our characterization uses the notion of textitcovered edges, which enables us to obtain simple proofs and also easily reason about earlier known results. We also generalize our results to the settings of bounded size interventions and node-dependent interventional costs. For all the above settings, we provide the first known provable algorithms for efficiently computing (near)-optimal verifying sets on general graphs. For the second problem, we give a simple adaptive algorithm based on graph separators that produces an atomic intervention set which fully orients any essential graph while using O(log n) times the optimal number of interventions needed to textitverify (verifying size) the underlying DAG on n vertices. This approximation is tight as textitany search algorithm on an essential line graph has worst case approximation ratio of Omega(log n) with respect to the verifying size. With bounded size interventions, each of size ≤ k, our algorithm gives an O(log n · log k) factor approximation. Our result is the first known algorithm that gives a non-trivial approximation guarantee to the verifying size on general unweighted graphs and with bounded size interventions.

Key facts. Cited by 18 papers in the map (data through 14 Oct 2026). Builds on 14 of its 63 references that are in the map. First posted on arXiv 30 Jun 2022.

Builds on

14 of 63 references.

References · 14

  1. 2015Domain-Adversarial Training of Neural Networkscited by 3,044
  2. 2019Invariant Risk Minimizationcited by 1,854
  3. 2019Causality for Machine Learningcited by 243
  4. 2013Causal Inference and Causal Explanation with Background Knowledgecited by 170
  5. 2015Learning Causal Graphs with Small Interventionscited by 63
  6. 2016Learning to Pivot with Adversarial Networkscited by 55
  7. 2017Cost-Optimal Learning of Causal Graphscited by 44
  8. 2013A Transformational Characterization of Equivalent Bayesian Network Structurescited by 41
  9. 2017Budgeted Experiment Design for Causal Structure Learningcited by 38
  10. 2020Active Structure Learning of Causal DAGs via Directed Clique Treecited by 38
  11. 2014Distinguishing cause from effect using observational data: methods and benchmarkscited by 33
  12. 2018Learning and Testing Causal Models with Interventionscited by 29
2 more
  1. 2018Experimental Design for Cost-Aware Learning of Causal Graphscited by 25
  2. 2019Size of Interventional Markov Equivalence Classes in Random DAG Modelscited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 5; 2024: 5; 2025: 2; 2026: 6.

18 papers.

Sort:

  1. 2024Causal Discovery with Fewer Conditional Independence Testscited by 13
  2. 2023Subset verification and search algorithms for causal DAGscited by 12
  3. 2023Active causal structure learning with advicecited by 10
  4. 2023Adaptivity Complexity for Causal Graph Discoverycited by 7
  5. 2024Sample Efficient Bayesian Learning of Causal Graphs from Interventionscited by 4
  6. 2023New metrics and search algorithms for weighted causal DAGscited by 3
  7. 2023Meek Separators and Their Applications in Targeted Causal Discoverycited by 3
  8. 2024Interventional Causal Discovery in a Mixture of DAGscited by 3
  9. 2024Causal Discovery under Off-Target Interventionscited by 2
  10. 2024Probably approximately correct high-dimensional causal effect estimation given a valid adjustment setcited by 2
  11. 2025Uncovering Bias Mechanisms in Observational Studiescited by 0
  12. 2025Design of Experiment for Discovering Directed Mixed Graphcited by 0
6 more
  1. 2026Efficient Causal Structure Learning via Modular Subgraph Integrationcited by 0
  2. 2026A Closer Look at the Application of Causal Inference in Graph Representation Learningcited by 0
  3. 2026Relaxing Faithfulness with Intervention-Only Causal Discoverycited by 0
  4. 2026Falsifying Causal Graphs With Outlier Eventscited by 0
  5. 2026FOCUS: Fixed-Confidence Online Causal Learning Using Sequential Adaptive Interventionscited by 0
  6. 2026Certifying Interventional Agreement Among Observationally Equivalent Causal Modelscited by 0