# The Reduced PC-Algorithm: Improved Causal Structure Learning in Large Random Networks

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2018.

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

- [Causal Discovery for Fairness](https://mlsanity.com/paper/2206.06685/) (2022)
- [Learning Bayesian Networks in the Presence of Structural Side Information](https://mlsanity.com/paper/2112.10884/) (2021)
- [Improving Efficiency and Accuracy of Causal Discovery Using a Hierarchical Wrapper](https://mlsanity.com/paper/2107.05001/) (2021)
- [The Dual PC Algorithm and the Role of Gaussianity for Structure Learning of Bayesian Networks](https://mlsanity.com/paper/2112.09036/) (2021)
- [Learning Directed Acyclic Graphs from Partial Orderings](https://mlsanity.com/paper/2403.16031/) (2024)
- [Improving the Efficiency of the PC Algorithm by Using Model-Based Conditional Independence Tests](https://mlsanity.com/paper/2211.06536/) (2022)
- [Your Assumed DAG is Wrong and Here's How To Deal With It](https://mlsanity.com/paper/2502.17030/) (2025)
- [On the Number of Conditional Independence Tests in Constraint-based Causal Discovery](https://mlsanity.com/paper/2603.21844/) (2026)
- [Inference of Causal Networks using a Topological Threshold](https://mlsanity.com/paper/2404.14460/) (2024)
- [Fair Data Pre-Processing with Imperfect Attribute Space](https://mlsanity.com/paper/2603.26456/) (2026)

## Abstract (arXiv)

We consider the task of estimating a high-dimensional directed acyclic graph, given observations from a linear structural equation model with arbitrary noise distribution. By exploiting properties of common random graphs, we develop a new algorithm that requires conditioning only on small sets of variables. The proposed algorithm, which is essentially a modified version of the PC-Algorithm, offers significant gains in both computational complexity and estimation accuracy. In particular, it results in more efficient and accurate estimation in large networks containing hub nodes, which are common in biological systems. We prove the consistency of the proposed algorithm, and show that it also requires a less stringent faithfulness assumption than the PC-Algorithm. Simulations in low and high-dimensional settings are used to illustrate these findings. An application to gene expression data suggests that the proposed algorithm can identify a greater number of clinically relevant genes than current methods.