Graph-based Complexity for Causal Effect by Empirical Plug-in

Rina Dechter, Anna K Raichev, Jin Tian, Alexander Ihler
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:4798-4806, 2025.

Abstract

This paper focuses on the computational complexity of computing empirical plug-in estimates for causal effect queries. Given a causal graph and observational data, any identifiable causal query can be estimated from an expression over the observed variables, called the estimand. The estimand can then be evaluated by plugging in probabilities computed empirically from data. In contrast to conventional wisdom which assumes that high dimensional probabilistic functions will lead to exponential evaluation time, we show that estimand evaluation can be done efficiently, potentially in time linear in the data size, depending on the estimand’s hypergraph. In particular, we show that both the $\it{treewidth}$ and $\it{hypertree width}$ of the estimand’s structure bound the evaluation complexity, analogous to their role in bounding the complexity of inference in probabilistic graphical models. In settings with high dimensional functions, the hypertree width often provides a more effective bound, since the empirical distributions are sparse.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-dechter25a, title = {Graph-based Complexity for Causal Effect by Empirical Plug-in}, author = {Dechter, Rina and Raichev, Anna K and Tian, Jin and Ihler, Alexander}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {4798--4806}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/dechter25a/dechter25a.pdf}, url = {https://proceedings.mlr.press/v258/dechter25a.html}, abstract = {This paper focuses on the computational complexity of computing empirical plug-in estimates for causal effect queries. Given a causal graph and observational data, any identifiable causal query can be estimated from an expression over the observed variables, called the estimand. The estimand can then be evaluated by plugging in probabilities computed empirically from data. In contrast to conventional wisdom which assumes that high dimensional probabilistic functions will lead to exponential evaluation time, we show that estimand evaluation can be done efficiently, potentially in time linear in the data size, depending on the estimand’s hypergraph. In particular, we show that both the $\it{treewidth}$ and $\it{hypertree width}$ of the estimand’s structure bound the evaluation complexity, analogous to their role in bounding the complexity of inference in probabilistic graphical models. In settings with high dimensional functions, the hypertree width often provides a more effective bound, since the empirical distributions are sparse.} }
Endnote
%0 Conference Paper %T Graph-based Complexity for Causal Effect by Empirical Plug-in %A Rina Dechter %A Anna K Raichev %A Jin Tian %A Alexander Ihler %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-dechter25a %I PMLR %P 4798--4806 %U https://proceedings.mlr.press/v258/dechter25a.html %V 258 %X This paper focuses on the computational complexity of computing empirical plug-in estimates for causal effect queries. Given a causal graph and observational data, any identifiable causal query can be estimated from an expression over the observed variables, called the estimand. The estimand can then be evaluated by plugging in probabilities computed empirically from data. In contrast to conventional wisdom which assumes that high dimensional probabilistic functions will lead to exponential evaluation time, we show that estimand evaluation can be done efficiently, potentially in time linear in the data size, depending on the estimand’s hypergraph. In particular, we show that both the $\it{treewidth}$ and $\it{hypertree width}$ of the estimand’s structure bound the evaluation complexity, analogous to their role in bounding the complexity of inference in probabilistic graphical models. In settings with high dimensional functions, the hypertree width often provides a more effective bound, since the empirical distributions are sparse.
APA
Dechter, R., Raichev, A.K., Tian, J. & Ihler, A.. (2025). Graph-based Complexity for Causal Effect by Empirical Plug-in. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:4798-4806 Available from https://proceedings.mlr.press/v258/dechter25a.html.

Related Material