New metrics and search algorithms for weighted causal DAGs

Davin Choo, Kirankumar Shiragur
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:5868-5903, 2023.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-choo23b, title = {New metrics and search algorithms for weighted causal {DAG}s}, author = {Choo, Davin and Shiragur, Kirankumar}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {5868--5903}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/choo23b/choo23b.pdf}, url = {https://proceedings.mlr.press/v202/choo23b.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T New metrics and search algorithms for weighted causal DAGs %A Davin Choo %A Kirankumar Shiragur %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-choo23b %I PMLR %P 5868--5903 %U https://proceedings.mlr.press/v202/choo23b.html %V 202 %X 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.
APA
Choo, D. & Shiragur, K.. (2023). New metrics and search algorithms for weighted causal DAGs. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:5868-5903 Available from https://proceedings.mlr.press/v202/choo23b.html.

Related Material