Research map / Probabilistic and scientific modeling / Causal discovery
Causal Discovery with Fewer Conditional Independence Tests
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.
Proposes Causally Consistent Partition Graphs (CCPG), a coarser causal graph representation learnable with a polynomial (O(n^5)) number of CI tests, extended to interventional data to recover the full DAG when it is identifiable.
Problem
Constraint-based causal discovery (e.g., PC) requires an exponential number of conditional independence tests in graph degree; it is unclear what causal information can be learned with few CI tests.
Approach
Define CCPG, a partition of vertices into components with a DAG over components that is consistent with the causal graph; learn it by iteratively finding prefix vertex sets (sets closed under ancestors) using type-I to IV exclusion sets built from a constant or polynomial number of CI tests per step. With a verifying intervention set, CCPG reduces to the true DAG.
Key results
- CCPG learns a valid representation with O(n^5) CI tests, independent of graph degree.
- With a verifying intervention set, CCPG recovers the full causal DAG with at most O(n^5)+|I|O(n^3) CI tests.
- In experiments CCPG runs as fast as GSP and much faster than PC, FCI, RFCI, which scale only to about 20 nodes, and needs the fewest samples to recover the true graph.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use CCPG instead of PC, FCI, or RFCI | Synthetic in-star DAGs · Synthetic data | runtime | Helped |
| use CCPG instead of GSP | Synthetic in-star DAGs · Synthetic data | runtime | No clear effect |
| use CCPG instead of the compared methods | 10-node in-star DAG · Synthetic data | samples required to recover the true graph | Helped |
| use constraint-based methods instead of hybrid methods | Synthetic in-star DAGs · Synthetic data | sample efficiency | Helped |
| use constraint-based methods instead of hybrid methods | Synthetic in-star DAGs · Synthetic data | runtime | Hurt |
| use CCPG instead of PC | Airfoil example · Airfoil example | consistency with known causal relations | Helped |
| use CCPG instead of PC | Airfoil example · Airfoil example | information contained in the learned representation | Hurt |
Limitations
- Assumes causal sufficiency (no latent confounders), faithfulness and Markov property
- Output is coarser than the full DAG unless the graph is identifiable
- Polynomial bound O(n^5) is large in practice
Experimental setup
Datasets: synthetic linear Gaussian causal models Airfoil self-noise dataset
Benchmarks: synthetic in-star DAGs Airfoil example
Metrics: runtime sample complexity recovery of ground-truth DAG
Baselines: PC FCI RFCI GSP
Builds on: PC algorithm Meek rules covered edges verifying intervention sets (Greenewald et al.) GSP
Closest papers by meaning
- Characterization and Learning of Causal Graphs from Hard Interventions (NeurIPS 2025 · similarity 0.92)
- Foundations of Testing for Finite-Sample Causal Discovery (ICML 2024 · similarity 0.91)
- Testing Causal Models with Hidden Variables in Polynomial Delay via Conditional Independencies (AAAI 2025 · similarity 0.90)
- Stable Differentiable Causal Discovery (ICML 2024 · similarity 0.90)
- Signature Kernel Conditional Independence Tests in Causal Discovery for Stochastic Processes (ICLR 2025 · similarity 0.89)
- Differentiable Constraint-Based Causal Discovery (NeurIPS 2025 · similarity 0.89)
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.