# New metrics and search algorithms for weighted causal DAGs

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 64 references that are in the map.
- First posted on arXiv 8 May 2023.

## Builds on (most cited first, 12 of 12)

- [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)
- [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)
- [Experimental Design for Cost-Aware Learning of Causal Graphs](https://mlsanity.com/paper/1810.11867/) (2018)
- [Efficient Intervention Design for Causal Discovery with Latents](https://mlsanity.com/paper/2005.11736/) (2020)
- [Verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2206.15374/) (2022)
- [Subset verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2301.03180/) (2023)
- [Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications](https://mlsanity.com/paper/2205.02654/) (2022)
- [Universal Lower Bound for Learning Causal DAGs with Atomic Interventions](https://mlsanity.com/paper/2111.05070/) (2021)

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

- [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)
- [Causal Discovery by Interventions via Integer Programming](https://mlsanity.com/paper/2412.01674/) (2024)

## Abstract (arXiv)

Recovering causal relationships from data is an important problem. Using observational data, one can typically only recover causal graphs up to a Markov equivalence class and additional assumptions or interventional data are needed for complete recovery. In this work, under some standard assumptions, we study causal graph discovery via adaptive interventions with node-dependent interventional costs. For this setting, we show that no algorithm can achieve an approximation guarantee that is asymptotically better than linear in the number of vertices with respect to the verification number; a well-established benchmark for adaptive search algorithms. Motivated by this negative result, we define a new benchmark that captures the worst-case interventional cost for any search algorithm. Furthermore, with respect to this new benchmark, we provide adaptive search algorithms that achieve logarithmic approximations under various settings: atomic, bounded size interventions and generalized cost objectives.