CISPA
Browse
usenixsecurity23-yuan-quan.pdf (1.85 MB)

PrivGraph: Differentially Private Graph Data Publication by Exploiting Community Information.

Download (1.85 MB)
conference contribution
posted on 2024-03-19, 13:35 authored by Quan Yuan, Zhikun ZhangZhikun Zhang, Linkang Du, Min ChenMin Chen, Peng Cheng, Mingyang Sun
Graph data is used in a wide range of applications, while analyzing graph data without protection is prone to privacy breach risks. To mitigate the privacy risks, we resort to the standard technique of differential privacy to publish a synthetic graph. However, existing differentially private graph synthesis approaches either introduce excessive noise by directly perturbing the adjacency matrix, or suffer significant information loss during the graph encoding process. In this paper, we propose an effective graph synthesis algorithm PrivGraph by exploiting the community information. Concretely , PrivGraph differentially privately partitions the private graph into communities, extracts intra-community and inter-community information, and reconstructs the graph from the extracted graph information. We validate the effectiveness of PrivGraph on four real-world graph datasets and seven commonly used graph metrics.

History

Primary Research Area

  • Trustworthy Information Processing

Name of Conference

Usenix Security Symposium (USENIX-Security)

Journal

USENIX Security Symposium

Page Range

3241-3258

BibTeX

@conference{Yuan:Zhang:Du:Chen:Cheng:Sun:2023, title = "PrivGraph: Differentially Private Graph Data Publication by Exploiting Community Information.", author = "Yuan, Quan" AND "Zhang, Zhikun" AND "Du, Linkang" AND "Chen, Min" AND "Cheng, Peng" AND "Sun, Mingyang", year = 2023, month = 8, journal = "USENIX Security Symposium", pages = "3241--3258" }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC