# A Fast PC Algorithm with Reversed-order Pruning and A Parallelization Strategy

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 33 references that are in the map.
- First posted on arXiv 10 Sep 2021.

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

- [Learning Bayesian Networks: The Combination of Knowledge and Statistical Data](https://mlsanity.com/paper/1302.6815/) (2013)
- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Causal Discovery Toolbox: Uncover causal relationships in Python](https://mlsanity.com/paper/1903.02278/) (2019)
- [A fast PC algorithm for high dimensional causal discovery with multi-core PCs](https://mlsanity.com/paper/1502.02454/) (2015)
- [cuPC: CUDA-based Parallel PC Algorithm for Causal Structure Learning on GPU](https://mlsanity.com/paper/1812.08491/) (2018)
- [Comparative Benchmarking of Causal Discovery Techniques](https://mlsanity.com/paper/1708.06246/) (2017)

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

- [BALANCE: Bayesian Linear Attribution for Root Cause Localization](https://mlsanity.com/paper/2301.13572/) (2023)
- [Scalable Causal Structure Learning: Scoping Review of Traditional and Deep Learning Algorithms and New Opportunities in Biomedicine](https://mlsanity.com/paper/2110.07785/) (2021)
- [Improving the Efficiency of the PC Algorithm by Using Model-Based Conditional Independence Tests](https://mlsanity.com/paper/2211.06536/) (2022)

## Abstract (arXiv)

The PC algorithm is the state-of-the-art algorithm for causal structure discovery on observational data. It can be computationally expensive in the worst case due to the conditional independence tests are performed in an exhaustive-searching manner. This makes the algorithm computationally intractable when the task contains several hundred or thousand nodes, particularly when the true underlying causal graph is dense. We propose a critical observation that the conditional set rendering two nodes independent is non-unique, and including certain redundant nodes do not sacrifice result accuracy. Based on this finding, the innovations of our work are two-folds. First, we innovate on a reserve order linkage pruning PC algorithm which significantly increases the algorithm's efficiency. Second, we propose a parallel computing strategy for statistical independence tests by leveraging tensor computation, which brings further speedup. We also prove the proposed algorithm does not induce statistical power loss under mild graph and data dimensionality assumptions. Experimental results show that the single-threaded version of the proposed algorithm can achieve a 6-fold speedup compared to the PC algorithm on a dense 95-node graph, and the parallel version can make a 825-fold speed-up. We also provide proof that the proposed algorithm is consistent under the same set of conditions with conventional PC algorithm.