Learning Bayesian Networks Under Local Differential Privacy

Bayesian networks are widely used for causal discovery and probabilistic modeling across diverse domains including healthcare, multi-dimensional data analysis, environmental modeling, and industrial processes. Although previous work has studied the learning of Bayesian networks under centralized differential privacy, to the best of our knowledge, the problem of learning Bayesian networks under local differential privacy (LDP) remains open. In this paper, we address this problem by proposing two solution methods for learning Bayesian networks under LDP: LDP-BN and LDP-BN+. Our first solution called LDP-BN utilizes a novel algorithm for computing mutual information values necessary for building a Bayesian network under LDP, but it suffers from high utility loss since the privacy budget needs to be divided into many pairs of attributes and candidate parent sets. To reduce the amount of noise, we propose LDP-BN+ which utilizes a novel density-aware covering design algorithm that ensures all necessary mutual information values will be computed while the privacy budget is used more effectively. We experimentally evaluate LDP-BN and LDP-BN+ using multiple utility metrics and datasets. Results show that LDP-BN+ outperforms LDP-BN and enables the generation of high-utility Bayesian networks that can be used in practice.