The goal of privacy-preserving social graph release is to protect individual privacy while preserving data utility. 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 sacrifice 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 sensitivity is fixed, the feature captured by Katz index, which is presented in matrix form, requires privacy budget splits. As a result, plenty of noise is injected, mitigating global structural utility. Such splits cause plenty of noise injection, resulting in poor preservation of the global structure. To bridge this gap, we design 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 maintained. 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.

中文摘要：

1、 研究背景（Context）：
社交图对社区中个体的相关社交互动进行建模，被广泛用于社交网络分析中。社区结构是社交图中一个非常重要的性质，它们形成了网络的功能模块。本质上，一个社区是一组节点，其组内各节点联系十分紧密, 组间各节点联系比较稀疏。现实中，同一个社区中的个体通常映射共同的属性或扮演相似的角色，因此，社区结构是节点全局模式的重要体现。共享社交图有利于研究者对社区的内部结构进行研究，以帮助用户发现隐藏在大量数据中的规律和模式。而社交图中包含的独特结构模式的公开，可能导致网络中个体隐私的泄露，这也带来了社交图共享发布中的隐私安全保护问题。在不泄露个体隐私的同时，兼顾社区结构的维持是隐私保护图发布亟待解决的问题。
2、 目的（Objective）：
关注社交图发布的场景，针对现有基于差分隐私的图发布方法通常用可用性换取安全性的问题，提出满足节点差分隐私的图发布方法 (PrivCom)，实现重构社交图满足节点差分隐私约束的同时兼顾社区结构的有效维持。
3、 方法（Method）：
(1) 为降低节点差分隐私带来的敏感度过大问题，设计了一种基于 Katz Index的差分隐私图特征提取方法来捕获社交图的全局结构特征，同时通过敏感度调控策略降低全局敏感度。
(2) 为缓解Katz矩阵引起的隐私预算分割问题，提出了一种基于差分隐私的特征向量估计方法，从提取的低维向量中生成满足差分隐私的特征向量。
(3) 为进一步改善带噪音的 Katz 矩阵的可用性，从理论上分析扰动后的特征值和特征向量间的内在关联。
4、结果（Result & Findings）：
通过回答以下两个问题来评估所提方法的性能：(1) 隐私预算对 PrivCom 维持社区结构可用性的影响？(2) 隐私预算对 PrivCom 维持度分布可用性的影响？具体地，针对社区结构维持，采用Louvain 和 CPM两种社区检测方法探测原始图G 和合成图G' 间的社区结构。基于评估指标F-score，实验结果表明，在大多数测试数据集上隐私预算在0.1至3.5时，PrivCom实验效果优于同类隐私图发布方法；针对度分布维持，采用Kolmogorov-Smirnov距离作为评价指标，设置隐私预算为0.5和3.5，实验结果表明，即使在隐私预算取值较小的情况下，PrivCom生成的合成图对度分布的维持仍优于对比方法。
5、结论（Conclusions）：
(1) 提出的基于Katz Index的差分隐私图特征提取方法在捕获全局图结构特征的同时，能有效降低全局敏感度。
(2) 设计的差分隐私特征向量估计方法缓解了Katz矩阵引起的隐私预算过度分割问题。
(3) 理论上分析了扰动后的特征值和特征向量间的内在关联，在此基础上设计的动态隐私预算分配方法进一步改善了扰动后的Katz矩阵的可用性。
(4) 下一步，将对Katz 矩阵的生成机制进行更加深入地研究，设计针对Katz 矩阵的社交图重构方法，以进一步提升PrivCom 方法的可用性。

Key words: differential privacy, social graph, community structure

;