AsgLDP: Collecting and Generating Decentralized Attributed Graphs with Local Differential Privacy

A large amount of valuable information resides in a decentralized attributed social graph, where each user locally maintains a limited view of the graph. However, there exists a conflicting requirement between publishing an attributed social graph and protecting the privacy of sensitive information contained in each user's local data. In this paper, we aim to collect and generate attributed social graphs in a decentralized manner while providing local differential privacy (LDP) for the collected data. Existing LDP-based synthetic graph generation methods either fail to preserve important graph properties (such as modularity and clustering coefficient) due to excessive noise injection or are unable to process attribute data, thus limiting their adoption and applicability. To overcome these weaknesses, we propose AsgLDP, a novel technique to generate privacy-preserving attributed graph data while satisfying LDP. AsgLDP preserves various graph properties through carefully designing the injected noise and estimating the joint distribution of attribute data. There are two key steps in AsgLDP: 1) collecting and generating graph data while satisfying LDP, and 2) optimizing the privacy-utility tradeoff of the generated data while preserving general graph properties such as the degree distribution, community structure and attribute distribution. Through theoretical analysis as well as experiments over 6 real-world datasets, we demonstrate the effectiveness of AsgLDP in preserving general graph properties such as degree distribution, community structure and attributed community search, while rigorously satisfying LDP. We also show that AsgLDP achieves a superior balance between utility and privacy as compared to the state-of-the-art approaches.