# Towards practical differentially private causal graph discovery

arXiv: https://arxiv.org/abs/2006.08598 · HTML: https://mlsanity.com/paper/2006.08598/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2020.

## Built on by (most cited first, 10 of 10)

- [Valid Inference After Causal Discovery](https://mlsanity.com/paper/2208.05949/) (2022)
- [Towards Practical Federated Causal Structure Learning](https://mlsanity.com/paper/2306.09433/) (2023)
- [Causal Inference with Latent Variables: Recent Advances and Future Prospectives](https://mlsanity.com/paper/2406.13966/) (2024)
- [Private independence testing across two parties](https://mlsanity.com/paper/2207.03652/) (2022)
- [Enabling Runtime Verification of Causal Discovery Algorithms with Automated Conditional Independence Reasoning (Extended Version)](https://mlsanity.com/paper/2309.05264/) (2023)
- [Differentially Private and Federated Structure Learning in Bayesian Networks](https://mlsanity.com/paper/2512.01708/) (2025)
- [Differentially Private Conditional Independence Testing](https://mlsanity.com/paper/2306.06721/) (2023)
- [CURATE: Scaling-up Differentially Private Causal Graph Discovery](https://mlsanity.com/paper/2409.19060/) (2024)
- [Towards Privacy-Aware Bayesian Networks: A Credal Approach](https://mlsanity.com/paper/2509.18949/) (2025)
- [PRISM: Differentially Private Synthetic Data with Structure-Aware Budget Allocation for Prediction](https://mlsanity.com/paper/2602.10228/) (2026)

## Abstract (arXiv)

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.