# Verification and search algorithms for causal DAGs

arXiv: https://arxiv.org/abs/2206.15374 · HTML: https://mlsanity.com/paper/2206.15374/

## 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 (most cited first, 14 of 14)

- [Domain-Adversarial Training of Neural Networks](https://mlsanity.com/paper/1505.07818/) (2015)
- [Invariant Risk Minimization](https://mlsanity.com/paper/1907.02893/) (2019)
- [Causality for Machine Learning](https://mlsanity.com/paper/1911.10500/) (2019)
- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Learning Causal Graphs with Small Interventions](https://mlsanity.com/paper/1511.00041/) (2015)
- [Learning to Pivot with Adversarial Networks](https://mlsanity.com/paper/1611.01046/) (2016)
- [Cost-Optimal Learning of Causal Graphs](https://mlsanity.com/paper/1703.02645/) (2017)
- [A Transformational Characterization of Equivalent Bayesian Network Structures](https://mlsanity.com/paper/1302.4938/) (2013)
- [Budgeted Experiment Design for Causal Structure Learning](https://mlsanity.com/paper/1709.03625/) (2017)
- [Active Structure Learning of Causal DAGs via Directed Clique Tree](https://mlsanity.com/paper/2011.00641/) (2020)
- [Distinguishing cause from effect using observational data: methods and benchmarks](https://mlsanity.com/paper/1412.3773/) (2014)
- [Learning and Testing Causal Models with Interventions](https://mlsanity.com/paper/1805.09697/) (2018)
- [Experimental Design for Cost-Aware Learning of Causal Graphs](https://mlsanity.com/paper/1810.11867/) (2018)
- [Size of Interventional Markov Equivalence Classes in Random DAG Models](https://mlsanity.com/paper/1903.02054/) (2019)

## Built on by (most cited first, 18 of 18)

- [Causal Discovery with Fewer Conditional Independence Tests](https://mlsanity.com/paper/2406.01823/) (2024)
- [Subset verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2301.03180/) (2023)
- [Active causal structure learning with advice](https://mlsanity.com/paper/2305.19588/) (2023)
- [Adaptivity Complexity for Causal Graph Discovery](https://mlsanity.com/paper/2306.05781/) (2023)
- [Sample Efficient Bayesian Learning of Causal Graphs from Interventions](https://mlsanity.com/paper/2410.20089/) (2024)
- [New metrics and search algorithms for weighted causal DAGs](https://mlsanity.com/paper/2305.04445/) (2023)
- [Meek Separators and Their Applications in Targeted Causal Discovery](https://mlsanity.com/paper/2310.20075/) (2023)
- [Interventional Causal Discovery in a Mixture of DAGs](https://mlsanity.com/paper/2406.08666/) (2024)
- [Causal Discovery under Off-Target Interventions](https://mlsanity.com/paper/2402.08229/) (2024)
- [Probably approximately correct high-dimensional causal effect estimation given a valid adjustment set](https://mlsanity.com/paper/2411.08141/) (2024)
- [Uncovering Bias Mechanisms in Observational Studies](https://mlsanity.com/paper/2506.01191/) (2025)
- [Design of Experiment for Discovering Directed Mixed Graph](https://mlsanity.com/paper/2509.01887/) (2025)
- [Efficient Causal Structure Learning via Modular Subgraph Integration](https://mlsanity.com/paper/2601.21014/) (2026)
- [A Closer Look at the Application of Causal Inference in Graph Representation Learning](https://mlsanity.com/paper/2604.08890/) (2026)
- [Relaxing Faithfulness with Intervention-Only Causal Discovery](https://mlsanity.com/paper/2607.11816/) (2026)
- [Falsifying Causal Graphs With Outlier Events](https://mlsanity.com/paper/2607.12145/) (2026)
- [FOCUS: Fixed-Confidence Online Causal Learning Using Sequential Adaptive Interventions](https://mlsanity.com/paper/2609.32165/) (2026)
- [Certifying Interventional Agreement Among Observationally Equivalent Causal Models](https://mlsanity.com/paper/2609.32247/) (2026)

## 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.