Adaptive Privacy for Differentially Private Causal Graph Discovery

Causal Graph Discovery (CGD) enables the estimation of directed acyclic graph (DAG) that represents the joint probability distribution of observational data. To estimate DAGs, typical constraint-based CGD algorithms run a sequence of conditional independence (CI) tests, making the estimation process prone to privacy leakage. Now, privacy affects utility, and due to the high inter-dependency, initial CI tests need to be more accurate to avoid error propagation through subsequent iterations. Based on this key observation, we present CURATE (CaUsal gRaph AdapTivE privacy), a differentially private constraint-based CGD algorithm. In contrast to the existing works, in CURATE we propose a privacy preserving framework with adaptive privacy budgeting by minimizing error probability while keeping the cumulative leakage bounded. To validate our framework, we present comprehensive set of experiments on several datasets and show that CURATE achieves significantly higher utility compared to the existing DP-CGD algorithms.1