# Causal Discovery with Fewer Conditional Independence Tests

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 55 references that are in the map.
- First posted on arXiv 3 Jun 2024.

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

- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Causal Inference in the Presence of Latent Variables and Selection Bias](https://mlsanity.com/paper/1302.4983/) (2013)
- [Greedy Relaxations of the Sparsest Permutation Algorithm](https://mlsanity.com/paper/2206.05421/) (2022)
- [Learning Causal Graphs with Small Interventions](https://mlsanity.com/paper/1511.00041/) (2015)
- [Learning Sparse Causal Models is not NP-hard](https://mlsanity.com/paper/1309.6824/) (2013)
- [High-dimensional consistency in score-based and hybrid structure learning](https://mlsanity.com/paper/1507.02608/) (2015)
- [Causal Structure Learning: a Combinatorial Perspective](https://mlsanity.com/paper/2206.01152/) (2022)
- [Parameter Priors for Directed Acyclic Graphical Models and the Characterization of Several Probability Distributions](https://mlsanity.com/paper/1301.6697/) (2013)
- [A Transformational Characterization of Equivalent Bayesian Network Structures](https://mlsanity.com/paper/1302.4938/) (2013)
- [Active Structure Learning of Causal DAGs via Directed Clique Tree](https://mlsanity.com/paper/2011.00641/) (2020)
- [Ancestral Causal Inference](https://mlsanity.com/paper/1606.07035/) (2016)
- [On the Logic of Causal Models](https://mlsanity.com/paper/1304.2355/) (2013)
- [Verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2206.15374/) (2022)
- [Properties of Bayesian Belief Network Learning Algorithms](https://mlsanity.com/paper/1302.6792/) (2013)
- [Subset verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2301.03180/) (2023)
- [SparsityBoost: A New Scoring Function for Learning Bayesian Network Structure](https://mlsanity.com/paper/1309.6820/) (2013)
- [Meek Separators and Their Applications in Targeted Causal Discovery](https://mlsanity.com/paper/2310.20075/) (2023)

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

- [Efficient Ensemble Conditional Independence Test Framework for Causal Discovery](https://mlsanity.com/paper/2509.21021/) (2025)
- [On Different Notions of Redundancy in Conditional-Independence-Based Discovery of Graphical Models](https://mlsanity.com/paper/2502.08531/) (2025)
- [Causal Structure and Representation Learning with Biomedical Applications](https://mlsanity.com/paper/2511.04790/) (2025)
- [A Fast Kernel-based Conditional Independence test with Application to Causal Discovery](https://mlsanity.com/paper/2505.11085/) (2025)
- [DAG DECORation: Continuous Optimization for Structure Learning under Hidden Confounding](https://mlsanity.com/paper/2510.02117/) (2025)
- [Cluster-Dags as Powerful Background Knowledge For Causal Discovery](https://mlsanity.com/paper/2512.10032/) (2025)
- [On the Number of Conditional Independence Tests in Constraint-based Causal Discovery](https://mlsanity.com/paper/2603.21844/) (2026)
- [Fast Nonparametric Conditional Independence Testing via Two-Stage Regression](https://mlsanity.com/paper/2606.18011/) (2026)
- [Fast Flow Matching based Conditional Independence Tests for Causal Discovery](https://mlsanity.com/paper/2602.08315/) (2026)
- [Learning Bayesian and Markov Networks with an Unreliable Oracle](https://mlsanity.com/paper/2603.09563/) (2026)
- [Non-Parametric Rehearsal Learning via Conditional Mean Embeddings](https://mlsanity.com/paper/2605.08999/) (2026)
- [A Recursive Decomposition Framework for Causal Structure Learning in the Presence of Latent Variables](https://mlsanity.com/paper/2605.10651/) (2026)
- [Relaxing Faithfulness with Intervention-Only Causal Discovery](https://mlsanity.com/paper/2607.11816/) (2026)

## Abstract (arXiv)

Many questions in science center around the fundamental problem of understanding causal relationships. However, most constraint-based causal discovery algorithms, including the well-celebrated PC algorithm, often incur an exponential number of conditional independence (CI) tests, posing limitations in various applications. Addressing this, our work focuses on characterizing what can be learned about the underlying causal graph with a reduced number of CI tests. We show that it is possible to a learn a coarser representation of the hidden causal graph with a polynomial number of tests. This coarser representation, named Causal Consistent Partition Graph (CCPG), comprises of a partition of the vertices and a directed graph defined over its components. CCPG satisfies consistency of orientations and additional constraints which favor finer partitions. Furthermore, it reduces to the underlying causal graph when the causal graph is identifiable. As a consequence, our results offer the first efficient algorithm for recovering the true causal graph with a polynomial number of tests, in special cases where the causal graph is fully identifiable through observational data and potentially additional interventions.