dK-Projection: Publishing Graph Joint Degree Distribution with Node Differential Privacy

Network data has great significance for commercial and research purposes. However, most networks contain sensitive information about individuals, thereby requiring privacy-preserving mechanisms to publish network data while preserving data utility. In this paper, we study the problem of publishing higher-order network statistics, i.e., joint degree distribution, under strong mathematical guarantees of node differential privacy. This problem is known to be challenging, since even simple network statistics (e.g., edge count) can be highly sensitive to adding or removing a single node in a network. To address this challenge, we propose a general framework of publishing dK-distributions under node differential privacy, and develop a novel graph projection algorithm to transform graphs to θ -bounded graphs for controlled sensitivity. We have conducted experiments to verify the utility enhancement and privacy guarantee of our proposed framework on four real-world networks. To the best of our knowledge, this is the first study to publish higher-order network statistics under node differential privacy, while enhancing network data utility.