PEGS: A Graph Synthesis Approach Based on Local Differential Privacy Preference

Large-scale social networks can be modeled as decentralized graphs, where each node holds a part of the overall network. Local differential privacy (LDP) has been widely adopted in decentralized graph analysis to ensure privacy for individual nodes. However, existing LDP-based methods often fail to accommodate personalized privacy requirements due to their uniform encoding and equal perturbation mechanisms. To address this issue, we propose PEGS, a novel privacy-preserving decentralized graph synthesis approach that significantly improves utility while respecting user-specific privacy preferences. Specifically, we introduce interactive local differential privacy (iLDP), a new edge-level definition of LDP that relaxes the constraints of node-independent perturbation, thereby enabling the fulfillment of individual privacy needs. Furthermore, we develop a decentralized graph perturbation framework offering three levels of privacy settings. To optimize the balance between information preservation and privacy, we design encoding and perturbation mechanisms leveraging information entropy tailored to different privacy levels. Extensive experimental evaluations and rigorous theoretical analysis demonstrate that our method produces high-quality synthetic graphs while adhering to iLDP guarantees.