Differentially private graph publishing with degree distribution preservation
Differentially private graph publishing with degree distribution preservation
复制标题
具有度分布保存的差分私有图发布
DOI：
10.1016/j.cose.2021.102285
复制
发表时间：
2021-04
期刊：
影响因子：
--
通讯作者：
Fu Nan
中科院分区：
文献类型：
--
作者：
Zhang Sen;Ni Weiwei;Fu Nan
隐私保护图发布的目标是在保持数据效用的同时保护发布的图数据中的个人隐私。度分布作为许多图分析任务的基本操作，是一个重要的数据工具。然而，现有的方法使用差分隐私（DP）不能很好地保持度分布，因为他们提取一个图到一组结构统计（如d K-系列等）。它只捕获局部度相关性，并且需要添加大量噪声来掩盖单个边缘的变化。最近，生成对抗网络图（NetGAN）在机器学习中起着关键作用，因为它能够通过有偏随机游走捕获图的局部和全局度分布。此外，它允许我们将隐私保护的负担转移到它的学习过程中，而不是提取的结构特征。受此启发，我们提出了Priv-GAN，一个基于NetGAN的私有发布模型。我们没有提取然后发布图表，而是发布了以DP方式使用原始数据训练的Priv-GAN模型。通过Priv-GAN，数据持有者能够生成具有度分布保留的合成图数据。与其他解决方案相比，我们的突出之处在于：（i）将具有梯度估计的私有Langevin设计为用于梯度估计的优化器，其提供理论梯度上界并通过向梯度添加噪声来实现DP;以及（ii）重要的是，从理论上分析了噪声Langevin方法的误差界，这表明通过适当的参数设置，Priv-GAN能够保持高效用保证。实验结果证实了我们的理论研究结果和Priv-GAN的有效性。
The goal of privacy-preserving graph publishing is to protect individual privacy in released graph data while preserving data utility. Degree distribution, serving as fundamental operations for many graph analysis tasks, is a crucial data utility. Yet, existing methods using differential privacy (DP) cannot well preserve degree distribution, since they distill a graph into a set of structural statistics (eg d K-series, etc.) that only captures local degree correlations, and require massive noise added to mask the change of a single edge. Recently Generative Adversarial Network for graphs (NetGAN) plays a key role in machine learning, due to its ability to capture the local and global degree distribution of the graph via biased random walks. Further, it allows us to move the burden of privacy-preserving to the learning procedure of its discriminator, rather than the extracted structure features. Inspired by this, we propose Priv-GAN, a private publishing model based on NetGAN. Instead of distilling and then publishing graphs, we publish the Priv-GAN model that is trained using the original data in a DP manner. With Priv-GAN, data holders are able to produce synthetic graph data with degree distribution preservation. Compared to alternative solutions, ours highlights that (i) a private Langevin with gradient estimate is designed as an optimizer for discriminator, which provides a theoretical gradient upper bound and achieves DP by adding noise to the gradients; and (ii) importantly, the error bound of the noisy Langevin method is theoretically analyzed, which demonstrates that with appropriate parameter settings, Priv-GAN is able to maintain high utility guarantees. Experimental results confirm our theoretical findings and the efficacy of Priv-GAN.
登录
查看更多内容
DOI：
10.1109/icccnt56998.2023.10306417
发表时间：
2022-02
期刊：
2023 14th International Conference on Computing Communication and Networking Technologies (ICCCNT)
影响因子：
--
作者：
Gilad Cohen;Raja Giryes
通讯作者：
Gilad Cohen;Raja Giryes
DOI：
10.1201/b17320-16
发表时间：
2008-09
期刊：
--
影响因子：
--
作者：
Prithviraj Sen;Galileo Namata;M. Bilgic;L. Getoor;Brian Gallagher;Tina Eliassi-Rad
通讯作者：
Prithviraj Sen;Galileo Namata;M. Bilgic;L. Getoor;Brian Gallagher;Tina Eliassi-Rad
DOI：
10.1137/1.9781611975994.34
发表时间：
2020-03
期刊：
--
影响因子：
--
作者：
Marek Eliáš;M. Kapralov;Janardhan Kulkarni;Y. Lee
通讯作者：
Marek Eliáš;M. Kapralov;Janardhan Kulkarni;Y. Lee
影响因子：
2.5
作者：
John C. Duchi;Michael I. Jordan;M. Wainwright;Andre Wibisono
通讯作者：
John C. Duchi;Michael I. Jordan;M. Wainwright;Andre Wibisono
影响因子：
0.9
作者：
Sen, Prithviraj;Namata, Galileo;Eliassi-Rad, Tina
通讯作者：
Eliassi-Rad, Tina