Local Differential Privacy in Graph Neural Networks: a Reconstruction
  Approach
Graph Neural Networks have achieved tremendous success in modeling complex
graph data in a variety of applications. However, there are limited studies
investigating privacy protection in GNNs. In this work, we propose a learning
framework that can provide node privacy at the user level, while incurring low
utility loss. We focus on a decentralized notion of Differential Privacy,
namely Local Differential Privacy, and apply randomization mechanisms to
perturb both feature and label data at the node level before the data is
collected by a central server for model training. Specifically, we investigate
the application of randomization mechanisms in high-dimensional feature
settings and propose an LDP protocol with strict privacy guarantees. Based on
frequency estimation in statistical analysis of randomized data, we develop
reconstruction methods to approximate features and labels from perturbed data.
We also formulate this learning framework to utilize frequency estimates of
graph clusters to supervise the training procedure at a sub-graph level.
Extensive experiments on real-world and semi-synthetic datasets demonstrate the
validity of our proposed model.
Karuna Bhaila, Wen Huang, Yongkai Wu, Xintao Wu
# Local Differential Privacy in Graph Neural Networks: a Reconstruction Approach

###### Abstract

Graph Neural Networks have achieved tremendous success in modeling complex graph data in a variety of applications. However, there are limited studies investigating privacy protection in GNNs. In this work, we propose a learning framework that can provide node privacy at the user level, while incurring low utility loss. We focus on a decentralized notion of Differential Privacy, namely Local Differential Privacy, and apply randomization mechanisms to perturb both feature and label data at the node level before the data is collected by a central server for model training. Specifically, we investigate the application of randomization mechanisms in high-dimensional feature settings and propose an LDP protocol with strict privacy guarantees. Based on frequency estimation in statistical analysis of randomized data, we develop reconstruction methods to approximate features and labels from perturbed data. We also formulate this learning framework to utilize frequency estimates of graph clusters to supervise the training procedure at a sub-graph level. Extensive experiments on real-world and semi-synthetic datasets demonstrate the validity of our proposed model.

 graph neural networks, local differential privacy, frequency estimation, learning from label proportions

## I Introduction

Graph data are ubiquitous in the modern world allowing graph-structured representation for complex data in the realm of social networks, finance, biology, and so on. Graph Neural Networks (GNNs) have been widely adopted in such domains to model the expressive nature of graph-structured data [1, 2]. GNNs rely on _message-passing_ mechanisms to propagate information between graph nodes and output embeddings that encode both node features and neighborhood features aggregated using graph adjacency information. These embeddings are used in predictive downstream tasks for meaningful applications such as drug discovery [3], traffic prediction [4], recommendation [5]. This widespread prevalence of GNNs, however, raises concerns regarding the privacy of sensitive information whose leakage may lead to undesirable and even harmful consequences. GNNs have been shown to be vulnerable to several privacy risks including membership inference [6], link re-identification [7], and attribute disclosure [8]. This risk of data leakage is considerably higher in GNNs compared to traditional learning models due to the presence of additional graph structure information [6]. To ensure compliance with legal data protection guidelines [9] and for the protection of user privacy, GNNs must thus be trained and deployed in a privacy-preserving manner.

In this paper, we aim to address such privacy concerns in GNNs. We focus on a specific scenario of node privacy wherein node-level features and labels are held locally by each user and the global graph structure is available to the server that hosts applications. The server could benefit from users' feature data which paired with graph topology can be utilized for embedding generation and/or predictive modeling via GNNs. However, collecting user feature and label data, possibly containing sensitive and identifying information, may incur serious privacy issues. To this end, Local Differential Privacy (LDP) [10] is often adopted in data collection for training machine learning or releasing statistics in a private manner [11]. Furthermore, it has been deployed in large-scale data-gathering of user behavior and usage statistics at Apple [12] and Google [13] motivating the integration of LDP in data collection for GNNs as well.

**Challenges** The main challenge in training GNNs with privately collected data arises due to the utility-privacy trade-off of differentially private mechanisms. With randomization of data at an individual level, privatized data oftentimes misrepresents the data distribution of the population. A learning model that learns feature and label correlation from this data overfits the noise and is unable to achieve good utility on predictive and analytical tasks with unseen data. Furthermore, since GNNs propagate information throughout the graph to output node embeddings, the quality of the embeddings also suffers due to additive noise present in the training data after applying LDP mechanisms.

**Prior Work** A few recent works have attempted to address node privacy in GNNs [14, 15] but they enforce privacy only during training and/or model release which puts user information at risk if the server is malicious. Most notably, Sajadmanesh and Gatica-Perez [16] propose a node-level LDP framework in the distributed setting where features and labels are held private by the user, and the graph structure is known to the server. They propose an LDP protocol called multi-bit mechanism to perturb node features by extending the 1-bit mechanism [17] to multidimensional features. The multi-bit mechanism randomly selects a subset of features for each user, transforms each selected feature value to either 1 or -1, and indiscriminately reports the value 0 for the remaining ones. To protect label privacy, node labels are perturbed using Randomized Response (RR) [18]. A GCN-based multi-hop aggregator is then prepended to the GNN model for implicit