  Causal graph discovery refers to the process of discovering causal relation
graphs from purely observational data. Like other statistical data, a causal
graph might leak sensitive information about participants in the dataset. In
this paper, we present a differentially private causal graph discovery
algorithm, Priv-PC, which improves 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 which uses a small amount of privacy budget to filter out
"insignificant" queries, and leverages the remaining budget to obtain highly
accurate answers for the "significant" queries. We also conducted the first
sensitivity analysis for conditional independence tests including conditional
Kendall's tau and conditional Spearman's rho. We evaluated Priv-PC on 4 public
datasets and compared with the state-of-the-art. The results show that Priv-PC
achieves 10.61 to 32.85 times speedup and better utility.
