dK-Microaggregation: Anonymizing Graphs with Differential Privacy Guarantees

Masooma Iftikhar*, Qing Wang, Yu Lin

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    19 Citations (Scopus)


    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.

    Original languageEnglish
    Title of host publicationAdvances in Knowledge Discovery and Data Mining - 24th Pacific-Asia Conference, PAKDD 2020, Proceedings
    EditorsHady W. Lauw, Ee-Peng Lim, Raymond Chi-Wing Wong, Alexandros Ntoulas, See-Kiong Ng, Sinno Jialin Pan
    Number of pages13
    ISBN (Print)9783030474355
    Publication statusPublished - 2020
    Event24th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2020 - Singapore, Singapore
    Duration: 11 May 202014 May 2020

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume12085 LNAI
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Conference24th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2020


    Dive into the research topics of 'dK-Microaggregation: Anonymizing Graphs with Differential Privacy Guarantees'. Together they form a unique fingerprint.

    Cite this