dK-Microaggregation: Anonymizing Graphs with Differential Privacy Guarantees
Date
2020
Authors
Wang, Qing
Lin, Yu
Iftikhar, Masooma
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
Abstract
With the advances of graph analytics, preserving privacy in publishing graph data becomes an important task. However, graph data is highly sensitive to structural changes. Perturbing graph data for achieving differential privacy inevitably leads to inject a large amount of noise and the utility of anonymized graphs is severely limited. In this paper, we propose a microaggregation-based framework for graph anonymization which meets the following requirements: (1) The topological structures of an original graph can be preserved at different levels of granularity; (2) ε-differential privacy is guaranteed for an original graph through adding controlled perturbation to its edges (i.e., edge privacy); (3) The utility of graph data is enhanced by reducing the magnitude of noise needed to achieve ε-differential privacy. Within the proposed framework, we further develop a simple yet effective microaggregation algorithm under a distance constraint. We have empirically verified the noise reduction and privacy guarantee of our proposed algorithm on three real-world graph datasets. The experiments show that our proposed framework can significantly reduce noise added to achieve ε-differential privacy over graph data, and thus enhance the utility of anonymized graphs.
Description
Keywords
Privacy-preserving graph data publishing, Differential privacy, Graph data utility, dK-graphs, Graph anonymization
Citation
Collections
Source
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Type
Conference paper
Book Title
Entity type
Access Statement
License Rights
Restricted until
2099-12-31
Downloads
File
Description