Towards Locally Differentially Private Generic Graph Metric Estimation

Qingqing Ye, Haibo Hu, Man Ho Allen Au, Xiaofeng Meng, Xiaokui Xiao

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

5 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationProceedings - 2020 IEEE 36th International Conference on Data Engineering, ICDE 2020
Number of pages4
ISBN (Electronic)9781728129037
Publication statusPublished - 20 Apr 2020
Event36th IEEE International Conference on Data Engineering, ICDE 2020 - Dallas, United States
Duration: 20 Apr 202024 Apr 2020

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627


Conference36th IEEE International Conference on Data Engineering, ICDE 2020
Country/TerritoryUnited States


  • Graph metric
  • Local differential privacy
  • Privacy-preserving graph analysis

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Signal Processing

Cite this