cuPC: CUDA-based Parallel PC Algorithm for Causal Structure Learning on GPU
This work addresses the computational bottleneck in causal structure learning for researchers in empirical sciences, offering a significant speedup but is incremental as it parallelizes an existing method.
The paper tackles the problem of learning causal structures from observational data by proposing cuPC, a GPU-based parallel algorithm that accelerates the PC algorithm, reducing runtime from over 11 hours to about 4 seconds in challenging cases and achieving average speedups of 500x to 1300x compared to CPU implementations.
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].