Research map / Probabilistic and scientific modeling / Causal discovery
Testing Causal Models with Hidden Variables in Polynomial Delay via Conditional Independencies
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces the c-component local Markov property (C-LMP) for semi-Markovian causal DAGs and a polynomial-delay algorithm (ListCI) that lists the non-vacuous conditional independence tests needed to test a causal graph with hidden variables against arbitrary distributions.
Problem
Testing a hypothesized causal DAG with hidden variables against observational data requires listing CIs implied by the graph, but existing Markov properties either assume restrictive conditions or take exponential time to output even one CI.
Approach
Define C-LMP using ancestral c-components (c-components of ancestral subgraphs), showing a one-to-one correspondence between invoked CIs and ancestral c-components, and enumerate admissible ancestral c-components via a binary-search-tree style divide-and-conquer with a poly-time existence check (FindAAC).
Key results
- ListCI does not time out on many graphs up to n=80 nodes, whereas ListCIBF times out on some graphs with n=25 and ListGMP times out for n>=10.
- On the protein signaling dataset (853 samples, 11 nodes), seven of ten C-LMP CIs gave p > 0.05 under a kernel CI test, suggesting the expert DAG may need revision.
- C-LMP invokes O(n 2^s) CIs, an exponential improvement over the Theta(4^n) CIs of the global Markov property.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ListCI instead of ListGMP to list CI constraints | CI listing on bnlearn DAGs · bnlearn benchmark DAGs | runtime before timeout: ListGMP did not timeout on graphs with n < 10 nodes; ListCI did not timeout for many graphs up to n = 80 | Helped |
| Use ListCI instead of ListCIBF to list CI constraints | CI listing on bnlearn DAGs · bnlearn benchmark DAGs | runtime before timeout: ListCIBF did not time out for some graphs with up to n = 35 nodes, but there were other graphs with n=25 where the algor | Helped |
| Apply C-LMP CI tests to the expert-provided graph | Expert-provided protein signaling DAG · Protein signaling dataset | CI tests with p > 0.05: seven out of ten | Mixed |
| Add bidirected edges while c-components remain sparse | C-LMP · Random graphs | number of non-vacuous CIs: increases exponentially with s; O(n 2^s) | Mixed |
| Increase the number of bidirected edges as c-components become denser | C-LMP · Random graphs | number of non-vacuous CIs: decays exponentially with the number of bidirected edges | Helped |
Surprising findings
- C-LMP may invoke exponentially many CIs (e.g., 2^n + (n-3) in a 2n-node graph), so polynomial-size listing is not possible in general.
- Increasing bidirected edges in dense c-components can make the number of CIs decay exponentially with the number of bidirected edges.
Limitations
- C-LMP still invokes exponentially many CIs in the worst case, with no known poly-size Markov property for the general setting.
- ListCI times out on some graphs with n=70 nodes, so runtime is still limited in practice.
- Experiments use a single kernel CI test with a fixed p-value threshold of 0.05 for the real-world application.
Experimental setup
Datasets: bnlearn repository DAGs protein signaling dataset (Sachs et al.)
Benchmarks: bnlearn DAGs up to 100 nodes protein signaling dataset
Metrics: runtime number of non-vacuous CIs p-value of CI tests
Baselines: ListGMP ListCIBF
Builds on: local Markov property ordered local Markov property c-components global Markov property
Closest papers by meaning
- Causal Discovery with Fewer Conditional Independence Tests (ICML 2024 · similarity 0.90)
- Signature Kernel Conditional Independence Tests in Causal Discovery for Stochastic Processes (ICLR 2025 · similarity 0.89)
- Causal Discovery via Conditional Independence Testing with Proxy Variables (ICML 2024 · similarity 0.89)
- Identifiable Latent Polynomial Causal Models through the Lens of Change (ICLR 2024 · similarity 0.88)
- Local Identifying Causal Relations in the Presence of Latent Variables (ICML 2025 · similarity 0.87)
- Characterization and Learning of Causal Graphs from Hard Interventions (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.