论文标题
在当地差异隐私下，图形神经网络的学位随机响应具有随机响应
Degree-Preserving Randomized Response for Graph Neural Networks under Local Differential Privacy
论文作者
论文摘要
最近已经研究了差异化私有GNN（图形神经网络），以在图形数据的各种任务中提供高精度，同时强烈保护用户隐私。特别是，最近的一项研究提出了一种算法，以保护每个用户的特征向量在属性图中，其中包括特征向量以及节点ID和边缘，以及LDP（本地差异隐私），这是一个没有值得信赖的第三方的强大隐私概念。但是，该算法不能在社交图中保护边缘（友谊），因此无法在未归类的图中保护用户隐私，其中仅包括节点ID和边缘。如何在未归类的图中提供高精度的强大隐私仍然开放。在本文中，我们提出了一种称为DPRR的新型LDP算法（具有学位的随机响应），以提供GNN中边缘的LDP。我们的DPRR保留了每个用户的学位，因此在提供Edge LDP时具有图形结构。从技术上讲，我们的DPRR使用Warner的RR（随机响应）和战略边缘采样，其中每个用户的采样概率都是使用Laplacian机制自动调整的，以保留Edge LDP下的学位信息。我们还提出了一种隐私预算分配方法，以使华纳的RR和Laplacian机制中的噪音较小。我们专注于图形分类作为GNN的任务，并使用三个社交图数据集评估DPRR。我们的实验结果表明，DPRR明显胜过三个基准，并在所有数据集中提供了具有合理隐私预算的所有数据集中的非私有算法的准确性，例如Epsilon = 1。最后，我们将数据中毒攻击引入了我们的DPRR，并防御了攻击。我们使用三个社交图数据集对它们进行评估，并讨论实验结果。
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, which includes feature vectors along with node IDs and edges, 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, hence cannot protect user privacy in unattributed graphs, which include only node IDs and edges. How to provide strong privacy with high accuracy in unattributed graphs 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, our DPRR uses Warner's RR (Randomized Response) and strategic edge sampling, where each user's sampling probability is automatically tuned using the Laplacian mechanism to preserve the degree information under edge LDP. We also propose a privacy budget allocation method to make the noise in both Warner's RR and the Laplacian mechanism small. We focus on graph classification as a task of GNNs and evaluate the DPRR using three 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. Finally, we introduce data poisoning attacks to our DPRR and a defense against the attacks. We evaluate them using the three social graph datasets and discuss the experimental results.
