# Testing Causal Models with Hidden Variables in Polynomial Delay via Conditional Independencies

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 69 references that are in the map.
- First posted on arXiv 22 Sep 2024.

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

- [BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery](https://mlsanity.com/paper/2112.02761/) (2021)
- [Bayes-Ball: The Rational Pastime (for Determining Irrelevance and Requisite Information in Belief Networks and Influence Diagrams)](https://mlsanity.com/paper/1301.7412/) (2013)
- [An Algorithm for Deciding if a Set of Observed Independencies Has a Causal Explanation](https://mlsanity.com/paper/1303.5435/) (2013)
- [Quantifier Elimination for Statistical Problems](https://mlsanity.com/paper/1301.6698/) (2013)
- [A factorization criterion for acyclic directed mixed graphs](https://mlsanity.com/paper/1406.6764/) (2014)
- [A cautious approach to constraint-based causal model selection](https://mlsanity.com/paper/2404.18232/) (2024)
- [Graphical Models and Exponential Families](https://mlsanity.com/paper/1301.7376/) (2013)
- [Towards standard imsets for maximal ancestral graphs](https://mlsanity.com/paper/2208.10436/) (2022)

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

- [Less Greedy Equivalence Search](https://mlsanity.com/paper/2506.22331/) (2025)

## Abstract (arXiv)

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.