GPU-Accelerated Constraint-Based Causal Structure Learning for Discrete Data
Christopher Hagedorn, Johannes Huegle · Society for Industrial and Applied Mathematics eBooks · 2021
Learning the causal structures from high-dimensional observational data is an omnipresent challenge in data science.State-of-the-art methods for constraint-based Causal Structure Learning (CSL) apply conditional independence (CI) tests to determine the underlying causal structures.In the context of discrete data, each CI test requires calculating the marginals over contingency tables based on the respective observations.This calculation leads to long overall execution times.In our work, we propose a parallel execution strategy tailored for constraint-based CSL on a Graphics Processing Unit (GPU) to accelerate the execution for discrete data.Hence, we introduce the gpuPC algorithm that performs all CI tests on a GPU and extends the existing parallel execution strategy for constraint-based CSL by calculating the marginals over contingency tables within units of threads.Further, gpuPC implements explicit memory management to handle the corresponding auxiliary data structures in GPU memory.An experimental evaluation shows that gpuPC scales well even for higher-dimensional settings, with auxiliary data structures exceeding on-chip memory.In particular, running on NVIDIA Tesla V100 hardware gpuPC outperforms a GPU baseline by factors of up to 45.6 and further outperforms existing parallel CPU-based implementations running on 40 cores by a factor of 62.1.