Differentially private GNNs (Graph Neural Networks) have been recently studied to provide high accuracy in various tasks on graph data while strongly protecting user privacy. In particular, a recent study proposes an algorithm to protect each user's feature vector in an attributed graph with LDP (Local Differential Privacy), a strong privacy notion without a trusted third party. However, this algorithm does not protect edges (friendships) in a social graph or protect user privacy in unattributed graphs. How to strongly protect edges with high accuracy in GNNs remains open. In this paper, we propose a novel LDP algorithm called the DPRR (Degree-Preserving Randomized Response) to provide LDP for edges in GNNs. Our DPRR preserves each user's degree hence a graph structure while providing edge LDP. Technically, we use Warner's RR (Randomized Response) and strategic edge sampling, where each user's sampling probability is automatically tuned to preserve the degree information. We prove that the DPRR approximately preserves the degree information under edge LDP. We focus on graph classification as a task of GNNs and evaluate the DPRR using four social graph datasets. Our experimental results show that the DPRR significantly outperforms three baselines and provides accuracy close to a non-private algorithm in all datasets with a reasonable privacy budget, e.g., epsilon=1.
翻译:最近对不同的私人GNN(Graph Neal Networks)进行了研究,以在图表数据中提供高精度的保护,同时大力保护用户隐私。特别是,最近的一项研究提议了一个算法,在与LDP(地方差异隐私)的推算图中保护每个用户的特性矢量。这是一个强大的隐私概念,没有信任第三方。然而,这种算法并不保护社会图中的边缘(朋友)或保护未归属图形中的用户隐私。如何以高精度保护GNNS的边缘。在本文中,我们仍然开放。我们提议了一个名为 DPR(Degree-Prescave 随机响应) 的新的LDP 算法, 以提供GNR的边缘。我们的DPRR将每个用户的学位保留为图形结构,同时提供边缘LDPDP。技术上,我们使用Warner RR(兰度反应反应)和战略边缘取样的概率自动调整,以保存程度信息。我们证明DPRRR(Degrade)大约保留了边缘的深度信息。我们专注于在LDP-PER(Degraphal DP)下的数据,我们用GNUR 3 的精确数据分类,我们用G-D-DRRRU) 的精确的数据显示了所有的精确度。</s>