Testing Causal Models with Hidden Variables in Polynomial Delay via Conditional Independencies
Open Access
- 11 April 2025
- journal article
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 39 (25) , 26813-26822
Abstract
Testing a hypothesized causal model against observational data is a key prerequisite for many causal inference tasks. A natural approach is to test whether the conditional independence relations (CIs) assumed in the model hold in the data. While a model can assume exponentially many CIs (with respect to the number of variables), testing all of them is both impractical and unnecessary. Causal graphs, which encode these CIs in polynomial space, give rise to local Markov properties that enable model testing with a significantly smaller subset of CIs. Model testing based on local properties requires an algorithm to list the relevant CIs. However, existing algorithms for realistic settings with hidden variables and non-parametric distributions can take exponential time to produce even a single CI constraint. In this paper, we introduce the c-component local Markov property (C-LMP) for causal graphs with hidden variables. Since C-LMP can still invoke an exponential number of CIs, we develop a polynomial delay algorithm to list these CIs in poly-time intervals. To our knowledge, this is the first algorithm that enables poly-delay testing of CIs in causal graphs with hidden variables against arbitrary data distributions. Experiments on real-world and synthetic data demonstrate the practicality of our algorithm.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Use of directed acyclic graphs (DAGs) to identify confounders in applied health research: review and recommendationsInternational Journal of Epidemiology, 2020
- Learning a Health Knowledge Graph from Electronic Medical RecordsScientific Reports, 2017
- Causal inference and the data-fusion problemProceedings of the National Academy of Sciences, 2016
- Space-optimal, backtracking algorithms to list the minimal vertex separators of a graphDiscrete Applied Mathematics, 2010
- Functional genomic hypothesis generation and experimentation by a robot scientistNature, 2004
- Markov Properties for Acyclic Directed Mixed GraphsScandinavian Journal of Statistics, 2003
- Marginal Structural Models and Causal Inference in EpidemiologyEpidemiology, 2000
- The Logic of Causal Inference: Econometrics and the Conditional Analysis of CausationEconomics and Philosophy, 1990
- Independence properties of directed markov fieldsNetworks, 1990
- On generating all maximal independent setsInformation Processing Letters, 1988