# Improving the Efficiency of the PC Algorithm by Using Model-Based Conditional Independence Tests

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 33 references that are in the map.
- First posted on arXiv 12 Nov 2022.

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

- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [D'ya like DAGs? A Survey on Structure Learning and Causal Discovery](https://mlsanity.com/paper/2103.02582/) (2021)
- [Approximate Kernel-based Conditional Independence Tests for Fast Non-Parametric Causal Discovery](https://mlsanity.com/paper/1702.03877/) (2017)
- [A fast PC algorithm for high dimensional causal discovery with multi-core PCs](https://mlsanity.com/paper/1502.02454/) (2015)
- [Model-Powered Conditional Independence Test](https://mlsanity.com/paper/1709.06138/) (2017)
- [Bayesian Network Constraint-Based Structure Learning Algorithms: Parallel and Optimised Implementations in the bnlearn R Package](https://mlsanity.com/paper/1406.7648/) (2014)
- [Efficient and Scalable Structure Learning for Bayesian Networks: Algorithms and Applications](https://mlsanity.com/paper/2012.03540/) (2020)
- [The Reduced PC-Algorithm: Improved Causal Structure Learning in Large Random Networks](https://mlsanity.com/paper/1806.06209/) (2018)
- [Efficient Markov Network Structure Discovery Using Independence Tests](https://mlsanity.com/paper/1401.3478/) (2014)
- [A Fast PC Algorithm with Reversed-order Pruning and A Parallelization Strategy](https://mlsanity.com/paper/2109.04626/) (2021)

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

- [MEC-IP: Efficient Discovery of Markov Equivalent Classes via Integer Programming](https://mlsanity.com/paper/2410.18147/) (2024)

## Abstract (arXiv)

Learning causal structure is useful in many areas of artificial intelligence, including planning, robotics, and explanation. Constraint-based structure learning algorithms such as PC use conditional independence (CI) tests to infer causal structure. Traditionally, constraint-based algorithms perform CI tests with a preference for smaller-sized conditioning sets, partially because the statistical power of conventional CI tests declines rapidly as the size of the conditioning set increases. However, many modern conditional independence tests are model-based, and these tests use well-regularized models that maintain statistical power even with very large conditioning sets. This suggests an intriguing new strategy for constraint-based algorithms which may result in a reduction of the total number of CI tests performed: Test variable pairs with large conditioning sets first, as a pre-processing step that finds some conditional independencies quickly, before moving on to the more conventional strategy that favors small conditioning sets. We propose such a pre-processing step for the PC algorithm which relies on performing CI tests on a few randomly selected large conditioning sets. We perform an empirical analysis on directed acyclic graphs (DAGs) that correspond to real-world systems and both empirical and theoretical analyses for ErdHos-Renyi DAGs. Our results show that Pre-Processing Plus PC (P3PC) performs far fewer CI tests than the original PC algorithm, between 0.5% to 36%, and often less than 10%, of the CI tests that the PC algorithm alone performs. The efficiency gains are particularly significant for the DAGs corresponding to real-world systems.