Publishing Graph Degree Distribution with Node Differential Privacy
Graph data publishing under node differential privacy (node DP) is challenging due to the huge sensitivity of queries. However, since a node in graph data oftentimes represents a person, node DP is necessary to achieve personal data protection. In this paper, we investigate the problem of publishing the degree distribution of a graph under node DP by exploring the projection approach to reduce the sensitivity. We propose two approaches based on aggregation and cumulative histogram to publish the degree distribution. The experiments demonstrate that our approaches greatly reduce the error of approximating the true degree distribution and have significant improvement over existing works. We also present the introspective analysis for understanding the factors of publishing the degree distribution with node DP.
SIGMOD Conference