mlsanityData to 7 Oct 2026

Causal Discovery with Fewer Conditional Independence Tests

arXiv 2406.01823 ↗First posted 3 Jun 2024cs.LG cs.AI stat.MEcited by 13

Not on the map. Why?

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.

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

Builds on

17 of 55 references.

References · 17

  1. 2013Causal Inference and Causal Explanation with Background Knowledgecited by 168
  2. 2013Causal Inference in the Presence of Latent Variables and Selection Biascited by 165
  3. 2015Learning Causal Graphs with Small Interventionscited by 63
  4. 2022Greedy Relaxations of the Sparsest Permutation Algorithmcited by 63
  5. 2013Learning Sparse Causal Models is not NP-hardcited by 48
  6. 2022Causal Structure Learning: a Combinatorial Perspectivecited by 46
  7. 2015High-dimensional consistency in score-based and hybrid structure learningcited by 44
  8. 2013Parameter Priors for Directed Acyclic Graphical Models and the Characterization of Several Probability Distributionscited by 41
  9. 2013A Transformational Characterization of Equivalent Bayesian Network Structurescited by 41
  10. 2020Active Structure Learning of Causal DAGs via Directed Clique Treecited by 38
  11. 2016Ancestral Causal Inferencecited by 24
  12. 2013On the Logic of Causal Modelscited by 19
5 more
  1. 2022Verification and search algorithms for causal DAGscited by 18
  2. 2013Properties of Bayesian Belief Network Learning Algorithmscited by 13
  3. 2023Subset verification and search algorithms for causal DAGscited by 12
  4. 2013SparsityBoost: A New Scoring Function for Learning Bayesian Network Structurecited by 7
  5. 2023Meek Separators and Their Applications in Targeted Causal Discoverycited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 6; 2026: 7.

13 papers.

Sort:

By area:

  1. 2025Efficient Ensemble Conditional Independence Test Framework for Causal Discoverycited by 5
  2. 2025On Different Notions of Redundancy in Conditional-Independence-Based Discovery of Graphical Modelscited by 3
  3. 2025Causal Structure and Representation Learning with Biomedical Applicationscited by 3
  4. 2025A Fast Kernel-based Conditional Independence test with Application to Causal Discoverycited by 2
  5. 2025DAG DECORation: Continuous Optimization for Structure Learning under Hidden Confoundingcited by 2
  6. 2025Cluster-Dags as Powerful Background Knowledge For Causal Discoverycited by 1
  7. 2026On the Number of Conditional Independence Tests in Constraint-based Causal Discoverycited by 1
  8. 2026Fast Nonparametric Conditional Independence Testing via Two-Stage Regressioncited by 1
  9. 2026Fast Flow Matching based Conditional Independence Tests for Causal Discoverycited by 0
  10. 2026Learning Bayesian and Markov Networks with an Unreliable Oraclecited by 0
  11. 2026Non-Parametric Rehearsal Learning via Conditional Mean Embeddingscited by 0
  12. 2026A Recursive Decomposition Framework for Causal Structure Learning in the Presence of Latent Variablescited by 0
1 more
  1. 2026Relaxing Faithfulness with Intervention-Only Causal Discoverycited by 0