摘要
The goal of privacy-preserving social graph release is to protect individual privacy while preserving data util-ity.Community structure,which is an important global pattern of nodes,is a crucial data utility as it is fundamental to many graph analysis tasks.Yet,most existing methods with differential privacy(DP)commonly fall into edge-DP to sacri-fice security in exchange for utility.Moreover,they reconstruct graphs from the local feature-extraction of nodes,resulting in poor community preservation.Motivated by this,we develop PrivCom,a strict node-DP graph release algorithm to maximize the utility on the community structure while maintaining a higher level of privacy.In this algorithm,to reduce the huge sensitivity,we devise a Katz index based private graph feature extraction method,which can capture global graph structure features while greatly reducing the global sensitivity via a sensitivity regulation strategy.Yet,under the condition that the sensitivity is fixed,the feature captured by the Katz index,which is presented in matrix form,requires privacy budget splits.As a result,plenty of noise is injected,mitigating global structural utility.To bridge this gap,we de-sign a private eigenvector estimation method,which yields noisy eigenvectors from extracted low-dimensional vectors.Then,a dynamic privacy budget allocation method with provable utility guarantees is developed to preserve the inherent relationship between eigenvalues and eigenvectors,so that the utility of the generated noise Katz matrix is well main-tained.Finally,we reconstruct the synthetic graph via calculating its Laplacian with the noisy Katz matrix.Experimental results confirm our theoretical findings and the efficacy of PrivCom.
作者
张森
倪巍伟
付楠
Sen Zhang;Wei-Wei Ni;Nan Fu(School of Computer Science and Engineering,Southeast University,Nanjing 211189,China;Key Laboratory of Computer Network and Information Integration(Southeast University),Ministry of Education,Nanjing 211189,China)
基金
A preliminary version of the paper was published in the Proceedings of ICDM 2020
supported by the National Natural Science Foundation of China under Grant No.61772131
the Science and Technology Project of the State Grid Corporation of China under Grant No.5700-202018268A-0-0-00.
