Efficient Publication of Distributed and Overlapping Graph Data Under Differential Privacy

作     者：Xu Zheng Lizong Zhang Kaiyang Li Xi Zeng Xu Zheng;Lizong Zhang;Kaiyang Li;Xi Zeng

作者机构：the School of Computer Science and EngineeringUniversity of Electronic Science and Technology of ChinaChengdu 611731China China Electronics Technology Cyber Security Co.Ltd.Chengdu 610000China 

出 版 物：《Tsinghua Science and Technology》 (清华大学学报（自然科学版（英文版）)

年 卷 期：2022年第27卷第2期

页      面：235-243页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 081201[工学-计算机系统结构] 0503[文学-新闻传播学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported by the National Natural Science Foundation of China(Nos.U19A2059 and 61802050) Ministry of Science and Technology of Sichuan Province Program(Nos.2021YFG0018 and 20ZDYF0343)。 

主　　题：graph data distributed data publication differential privacy 

摘      要：Graph data publication has been considered as an important step for data analysis and mining.Graph data,which provide knowledge on interactions among entities,can be locally generated and held by distributed data owners.These data are usually sensitive and private,because they may be related to owners’personal activities and can be hijacked by adversaries to conduct inference attacks.Current solutions either consider private graph data as centralized contents or disregard the overlapping of graphs in distributed manners.Therefore,this work proposes a novel framework for distributed graph publication.In this framework,differential privacy is applied to justify the safety of the published contents.It includes four phases,i.e.,graph combination,plan construction sharing,data perturbation,and graph reconstruction.The published graph selection is guided by one data coordinator,and each graph is perturbed carefully with the Laplace mechanism.The problem of graph selection is formulated and proven to be NP-complete.Then,a heuristic algorithm is proposed for selection.The correctness of the combined graph and the differential privacy on all edges are analyzed.This study also discusses a scenario without a data coordinator and proposes some insights into graph publication.