Towards practical differentially private causal graph discovery
Lun Wang,Qi Pang,Dawn Song
Causal graph discovery refers to the process of discovering causal relation graphsfrom purely observational data. Like other statistical data, a causal graph mightleak sensitive information about participants in the dataset. In this paper, wepresent a differentially private causal graph discovery algorithm, Priv-PC, whichimproves both utility and running time compared to the state-of-the-art. The design of Priv-PC follows a novel paradigm called sieve-and-examine whichuses a small amount of privacy budget to filter out u201cinsignificantu201d queries, andleverages the remaining budget to obtain highly accurate answers for the u201csignificantu201d queries. We also conducted the first sensitivity analysis for conditional independence tests including conditional Kendallu2019s u03c4 and conditional Spearmanu2019s u03c1. We evaluated Priv-PC on 7 public datasets and compared with thestate-of-the-art. The results show that Priv-PC achieves 10.61 to 293.87 timesspeedup and better utility. The implementation of Priv-PC, including the codeused in our evaluation, is available at https://github.com/sunblaze-ucb/Priv-PC-Differentially-Private-Causal-Graph-Discovery.
