LF-GDPR: A Framework for Estimating Graph Metrics With Local Differential Privacy
Open Access
- 24 December 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 34 (10) , 4905-4920
Abstract
Local differential privacy (LDP) is an emerging technique for privacy-preserving data collection without a trusted collector. Despite its strong privacy guarantee, LDP cannot be easily applied to real-world graph analysis tasks such as community detection and centrality analysis due to its high implementation complexity and low data utility. In this paper, we address these two issues by presenting LF-GDPR, the first LDP-enabled graph metric estimation framework for graph analysis. It collects two atomic graph metrics—the adjacency bit vector and node degree—from each node locally. LF-GDPR simplifies the job of implementing LDP-related steps (e.g., local perturbation, aggregation and calibration) for a graph metric estimation task by providing either a complete or a parameterized algorithm for each step. To address low data utility of LDP, it optimally allocates privacy budget between the two atomic metrics during data collection. To demonstrate the usage of LF-GDPR, we show use cases on two common graph analysis tasks, namely, clustering coefficient estimation and community detection. The privacy and utility achieved by LF-GDPR are verified through theoretical analysis and extensive experimental results.Keywords
Funding Information
- National Natural Science Foundation of China (62072390, U1636205, 91646203, 61941121, 61972332)
- Research Grants Council, Hong Kong SAR, China (15238116, 15222118, 15218919, 15203120, C1008-16G)
- Ministry of Education - Singapore (MOE2018-T2-2-091)
This publication has 51 references indexed in Scilit:
- Correlated network data publication via differential privacyThe VLDB Journal, 2013
- On learning cluster coefficient of private networksSocial Network Analysis and Mining, 2013
- Community structure and scale-free collections of Erdős-Rényi graphsPhysical Review E, 2012
- What Can We Learn Privately?SIAM Journal on Computing, 2011
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- Calibrating Noise to Sensitivity in Private Data Analysis2006
- Protecting respondents identities in microdata releaseIEEE Transactions on Knowledge and Data Engineering, 2001
- Objective Criteria for the Evaluation of Clustering MethodsJournal of the American Statistical Association, 1971
- Randomized Response: A Survey Technique for Eliminating Evasive Answer BiasJournal of the American Statistical Association, 1965
- The Large-Sample Distribution of the Likelihood Ratio for Testing Composite HypothesesThe Annals of Mathematical Statistics, 1938