Locally private graph synthesis preserves neighborhood structures better
LDPGraph: Locally Differentially Private Graph Synthesis by Exploiting Neighborhood Structure
Databases
Summary
Sharing graph data can reveal sensitive connections between people, especially when data is kept by many separate users. The authors developed a method called LDPGraph that helps create a new, fake graph without exposing private details. Unlike older methods that lose important neighborhood information or add too much random noise, this method uses smart math to keep local connection patterns like triangles. It then adjusts these patterns together to build a more realistic graph that protects user privacy.
What this means in practice
- •For data privacy engineers: Generate synthetic graphs that protect user connections in decentralized networks using local privacy techniques preserving structural details.
- •For social network platform developers: Create realistic synthetic social graphs for testing and analysis without exposing individual user relationships or sensitive data.
Authors
Jiawei Dong, Zhikun Zhang, Quan Yuan, Zhe Liu, Yunjun Gao
Abstract
The widespread application of graph data inevitably brings significant privacy risks, as its unprotected use can lead to the leakage of sensitive information. These risks are particularly acute in the setting with an untrusted curator, where the data remains decentralized and each user only holds the connections to their neighbors. To mitigate such privacy risks, we adopt local differential privacy (LDP) to collect users' private information and generate a synthetic graph. However, existing methods suffer from either excessive noise injection by perturbing the local adjacency lists or significant structural information loss due to the simplistic graph encoding process. To address these issues, we propose LDPGraph, an effective graph synthesis algorithm that takes one step further by exploiting neighborhood structures under LDP. To obtain neighborhood statistics beyond degrees, LDPGraph aggregates a noisy global view from perturbed adjacency lists and combines it with projected local connections to estimate node-level triangle counts. To correct the structural inconsistency caused by separately perturbing degree and triangle count, LDPGraph jointly refines them into feasible degree-triangle targets. To reconstruct a global graph from these estimated targets, LDPGraph adopts a triangle-first strategy that first preserves local clustering structures and then fulfills remaining degree requirements. Extensive experiments on four real-world datasets and multiple commonly used graph metrics validate the superiority of LDPGraph. Source code is available at https://github.com/ZJU-TrustAID/LDPGraph.