TY - JOUR
T1 - AsgLDP
T2 - Collecting and Generating Decentralized Attributed Graphs with Local Differential Privacy
AU - Wei, Chengkun
AU - Ji, Shouling
AU - Liu, Changchang
AU - Chen, Wenzhi
AU - Wang, Ting
N1 - Funding Information:
Manuscript received October 18, 2019; revised March 15, 2020; accepted March 16, 2020. Date of publication April 3, 2020; date of current version April 29, 2020. This work was supported in part by the National Key Research and Development Program of China under Grant 2018YFB0804102, in part by NSFC under Grant 61772466, Grant U1936215, and Grant U1836202, in part by the Zhejiang Provincial Natural Science Foundation for Distinguished Young Scholars under Grant LR19F020003, in part by the Zhejiang Provincial Natural Science Foundation under Grant LSY19H180011, in part by the Zhejiang Provincial Key Research and Development Program under Grant 2019C01055, in part by the Ant Financial Research Funding, in part by the Information Technology Center of Zhejiang University, and in part by the Alibaba-ZJU Joint Research Institute of Frontier Technologies. The work of Changchang Liu was supported in part by the U.S. Army Combat Capabilities Development Command Army Research Laboratory and was accomplished (ARL Cyber Security CRA) under Agreement W911NF-13-2-0045. The work of Ting Wang was supported in part by the National Science Foundation under Grant 1910546, Grant 1953813, and Grant 1846151. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Mauro Conti. (Corresponding authors: Shouling Ji; Wenzhi Chen.) Chengkun Wei and Wenzhi Chen are with the College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China (e-mail: weichengkun@zju.edu.cn; chenwz@zju.edu.cn).
Funding Information:
This work was supported in part by the National Key Research and Development Program of China under Grant 2018YFB0804102, in part by NSFC under Grant 61772466, Grant U1936215, and Grant U1836202, in part by the Zhejiang Provincial Natural Science Foundation for Distinguished Young Scholars under Grant LR19F020003, in part by the Zhejiang Provincial Natural Science Foundation under Grant LSY19H180011, in part by the Zhejiang Provincial Key Research and Development Program under Grant 2019C01055, in part by the Ant Financial Research Funding, in part by the Information Technology Center of Zhejiang University, and in part by the Alibaba-ZJU Joint Research Institute of Frontier Technologies. The work of Changchang Liu was supported in part by the U.S. Army Combat Capabilities Development Command Army Research Laboratory and was accomplished (ARL Cyber Security CRA) under Agreement W911NF-13-2-0045. The work of Ting Wang was supported in part by the National Science Foundation under Grant 1910546, Grant 1953813, and Grant 1846151
Publisher Copyright:
© 2005-2012 IEEE.
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85084383164&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85084383164&partnerID=8YFLogxK
U2 - 10.1109/TIFS.2020.2985524
DO - 10.1109/TIFS.2020.2985524
M3 - Article
AN - SCOPUS:85084383164
SN - 1556-6013
VL - 15
SP - 3239
EP - 3254
JO - IEEE Transactions on Information Forensics and Security
JF - IEEE Transactions on Information Forensics and Security
M1 - 9056817
ER -