LFS: A Locally Private Framework for Degree Statistic Estimation With Laplace Mechanism

As a fundamental task in graph data analysis, degree statistic estimation serves as the foundation for many complex tasks. Local differential privacy (LDP) preserves the privacy inherent in raw degrees without a trusted third party. Existing methods struggle to balance different types of degree statistics. They either introduce excessive noise when estimating degree distribution due to not fully leveraging the properties of edge LDP, or are limited to polynomial statistic estimation only. We design a locally private framework for degree statistic estimation (LFS), using Laplace mechanism to provide appropriate privacy protection under edge LDP. LFS can estimate three types of degree statistics: polynomial, distribution and single-point. According to degrees with Laplace noise, we transform degree distribution estimation into a linear regression problem, then post-process the estimated distribution to mitigate the excessive smoothing introduced by the regularization term. We also achieve single-point statistic estimation considering the degree distribution and properties of Laplace noise. Systematic experiments on five datasets demonstrate that LFS consistently outperforms existing methods in four utility metrics.