# cuPC: CUDA-based Parallel PC Algorithm for Causal Structure Learning on GPU

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Dec 2018.

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

- [D-BIAS: A Causality-Based Human-in-the-Loop System for Tackling Algorithmic Bias](https://mlsanity.com/paper/2208.05126/) (2022)
- [Local Discovery by Partitioning: Polynomial-Time Causal Discovery Around Exposure-Outcome Pairs](https://mlsanity.com/paper/2310.17816/) (2023)
- [Local Causal Discovery for Structural Evidence of Direct Discrimination](https://mlsanity.com/paper/2405.14848/) (2024)
- [Partitioned hybrid learning of Bayesian network structures](https://mlsanity.com/paper/2103.12188/) (2021)
- [Causal Discovery over High-Dimensional Structured Hypothesis Spaces with Causal Graph Partitioning](https://mlsanity.com/paper/2406.06348/) (2024)
- [A Fast PC Algorithm with Reversed-order Pruning and A Parallelization Strategy](https://mlsanity.com/paper/2109.04626/) (2021)
- [Fast Parallel Bayesian Network Structure Learning](https://mlsanity.com/paper/2212.04259/) (2022)
- [A Fast Kernel-based Conditional Independence test with Application to Causal Discovery](https://mlsanity.com/paper/2505.11085/) (2025)
- [Transformer Is Inherently a Causal Learner](https://mlsanity.com/paper/2601.05647/) (2026)
- [Scalable Time-Series Causal Discovery with Approximate Causal Ordering](https://mlsanity.com/paper/2409.05500/) (2024)
- [Preserving Data Privacy in Learning Causal Structure with Fully Homomorphic Encryption](https://mlsanity.com/paper/2606.05129/) (2026)
- [Conditional Independence Tests for Constraint-Based Causal Discovery: A Survey](https://mlsanity.com/paper/2608.11156/) (2026)

## Abstract (arXiv)

The main goal in many fields in the empirical sciences is to discover causal relationships among a set of variables from observational data. PC algorithm is one of the promising solutions to learn underlying causal structure by performing a number of conditional independence tests. In this paper, we propose a novel GPU-based parallel algorithm, called cuPC, to execute an order-independent version of PC. The proposed solution has two variants, cuPC-E and cuPC-S, which parallelize PC in two different ways for multivariate normal distribution. Experimental results show the scalability of the proposed algorithms with respect to the number of variables, the number of samples, and different graph densities. For instance, in one of the most challenging datasets, the runtime is reduced from more than 11 hours to about 4 seconds. On average, cuPC-E and cuPC-S achieve 500 X and 1300 X speedup, respectively, compared to serial implementation on CPU. The source code of cuPC is available online [1].