Structural Privacy in Graphs
Authors: Rucha Bhalchandra Joshi
Subhankar Mishra
Venue: Submitted to ICLR 2023 (2023)
Keywords: Privacy
Graph Neural Networks
Differential Privacy
Graph Structure

Abstract: Graph Neural Networks (GNNs) gained popularity to address the tasks over the graph-structured data that best represent many real-world systems. The privacy of the participants of these systems is at risk if the GNNs are not carefully designed. Existing works in privacy-preserving GNNs primarily ensure the privacy of features and labels of a node. In order to ensure complete privacy related to graph data, its structure also needs to be privatized. We provide a method SPGraph to privatize the graph structure by adding noise to the neighborhood data of the node. Our method addresses two challenges in introducing structural privacy in graphs. Applying randomization on the set of actual neighbors to introduce noise leads to a reduction in the degree of a node, which is undesirable. To overcome this first challenge, we introduce $\lambda$-selector that samples nodes to be added to the set of neighbors. The second challenge is to denoise the neighborhood so that the noise added in the neighborhood does not significantly impact the accuracy. In this view, we use $p$-hop neighborhood to compensate for the loss of actual neighbors in the randomization. We continue to use the node and label privacy as implemented in the previous methods for privacy in GNNs. We conduct extensive experiments over real-world datasets to show the impact of perturbation in the graph structure. 

Under review as a conference paper at ICLR 2023
STRUCTURAL PRIVACY IN GRAPHS
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) gained popularity to address the tasks over the graph-structured data that best represent many real-world systems. The privacy of the participants of these systems is at risk if the GNNs are not carefully de- GNNs primarily ensure the privacy
signed. Existing works in rivacy-preserving of features and labels of node. To ensure complete privacy related graph data, its structure also needs to be privatized. We provide a method SPGraph to pri- vatize the graph structure by adding noise to the neighborhood data of the node. Our method addresses two challenges in introducing structural privacy in graphs. Applying randomization on the set of actual neighbors to introduce noise leads a reduction in the degree of nodes, which is undesirable. To overcome this first challenge, we introduce X-selector that samples nodes to added to the set of neighbors. The second challenge is to denoise the neighborhood so that the noise added the neighborhood does not significantly impact the accuracy. In this view, we use the p-hop neighborhood to compensate for the loss of actual neighbors in the randomization.
We continue to use the node and label privacy as implemented in the previous methods for privacy in GNNs. We conduct extensive experiments over real-world datasets to show the impact of perturbation on the graph structure.
INTRODUCTION
Real-world systems such as social networks, citation networks, and molecular networks are popu- larly modeled as graphs. A graph richly represents such systems as it considers all the entities in the system well relationships between the entities. Graph Neural Networks (GNNs) are popularly used tackle the tasks, such as node classification, graph classification, and link prediction are ad- dressed using GNNs. The primary goal of GNNs is the aggregation of structural as well as feature information in an efficient manner. At the same time, addresses the tasks related to the systems represented graphs.
Problem and Motivation. The problem we address in this work is ensuring the users' data privacy in critical systems that can be represented using graphs. The term data privacy in the case of graphs signifies privacy related to the structure of the graph and the features of the nodes in the graph. We look at the privacy in GNNs for node-level tasks. Most of the previous works in the area of privacy in GNN have ensured the privacy of the features and labels of each of the nodes. It assumes that the server knows the connectivity information; hence in the previous works, the term data privacy means the privacy of node features and node labels. In this work, we consider the privacy of structural information, typically given by the edges in the graphs, along with the feature and label information of the nodes.
Challenges. To ensure complete privacy, that is, the privacy of nodes, edges and labels in graph, the following challenges need to be addressed: 1. Edge privacy or the privacy of the graph structure to be taken care of avoid the information from being compromised. The existing methods Sajadmanesh & Gatica-Perez (202T) perturb only the node features and the node labels, however as the graph structure remains publicly available, we need to consider that as private information as well. 2. To preserve structural privacy, there has to be mechanism to perturb the edges in the graph. Deciding the amount of noise to be added to the edge data and the mechanism to add noise one of the challenges. We also need mechanism to correct the added noise as to balance the accuracy of the predictions. 3. Determining the amount of structure perturbation and node and label perturbation to strike the right balance between privacy and utility in the graph data.

---

Under review as a conference paper at ICLR 2023
29
52000
30
36000
Server
148000
470.00
ago
salary
26 48000
Closs 1
Class
40000
25 45000
Figure 1:
A network of users where users want to keep their sensitive data such as age and salary private. This information is privatized by perturbing the node feature and label information. The change is labels is shown with a change in the node color. We address the problem of structure perturbation in such network before passing on the perturbed information the server further process the data by applying GNN to answer the questions on the graph.
Contributions. We propose completely locally private graph neural networks. Complete local pri- vacy is obtained by privatizing the edge information in addition node and label information. Our method SPGRAPP privatizes the structure of the nodes in the graph data. We provide experimental evidence of the performance of the model by varying the parameters that control the noise added to the edges for perturbations where we perturb the edges according to the structure privatization approach.
Paper Organization. This paper is organized as follows. Introduction, motivation, challenges, and contribution of our work are described in section [ In section [2] we discuss the works related to the topic. Section gives the preliminaries with problem definition and background. Our proposed method is described section 4 The experimental setup and the results are discussed section and section caciion6ocone concludes the paper.
RELATED WORKS
With different possible attacks on Graph Neural Networks, the privacy of the data involved can be compromised. He et al. (2021) introduced seven different link stealing attacks Graphs. The adversary has black-box access to Graph Neural Networks, and it can infer whether or not any two nodes used in the training of the GNN have link between them. Wu et al.) (2021b) introduced similar attack called Link Teller attack that concerns the privacy of the edges in the graph. In setting where the node features and the adjacency information are with different parties, the party with the adjacency matrix trains the GNN upon receiving the node features from the other party and provides back the inference API. The party holding the node features provides the test node features and also can query API for predictions related to test nodes. The LinkTeller attack tries to infer the links present between nodes, based on the queries. The other works Olatunji et al. (202T). Zügner et al.) (2020), Duddu et al. (2020) discuss the attacks possible on GNNs, such as membership inference attack, graph reconstruction attack, and attribute inference attack.
A federated framework for crivacy-rreservngg GNNs for recommendation systems is presented in Wu et al. (202 The GNNs are trained locally at the users' end and they upload the local gradients to server for aggregation. To enhance the privacy of users by protecting user-item interaction, local differential privacy techniques are applied to the locally computed gradients. Zhou et al. (2020) is another work involving federated graph neural networks for the features, and the edges are split among the users, while all the users have the access to the same set of nodes.
classification tasks,
2

---

Under review as a conference paper at ICLR 2023
KProp, multbit Decoder
Perturbed Nodes
Parturbed Neighbourhood
A-selector, KProp
Perlurbed Labels
N-drop
Figure 2: ensure complete privacy, addition to node and feature perturbation we perturb the neighborhood using SPGRAPH that uses X-selector and KProp.
To get the differentially private node embeddings, DPNE Xu et al. (2018) applies objective perturba- tion the objective function of matrix factorization. Sajadmanesh & Gatica-Peres (2021) proposes a privacy- sewaacypreserving GNN learning algorithm for the privacy of nodes where the node features and their labels assumed be private while the structure of the graph is not private.
PRELIMINARIES
3.1 PROBLEM DEFINITION
Definition 3.1 (Graph) graph defined as G F,, X, XYY) where, = is a set union of labeled nodes VL and unlabeled nodes Vy and [V] n. E is a set of edges and [E] X the feature matrix corresponding to the graph where X E Raxd and d is the size of feature vector corresponding to each of the nodes in the graph. Y {0, 1jnxe, where is the total number of classes nodes belong to, the matrix of one-hot encodings of the labels corresponding to labeled nodes and it is vector of all zeros for the unlabeled nodes in the graph. The neighborhood of node is given as N(v) that contains nodes u such that (u, v) E E.
Consider client-server system where the clients are the users represented by nodes and the server where the Graph Neural Network runs and predicts the labels of unlabeled nodes. The nodes are aware of their feature vectors and their neighbors. The server is aware only of the vertex set V. The GNN needs to be trained for given task on the server side. The problem we try to address is how to train the GNN the server side while preserving neighborhood privacy in addition to preserving the privacy of node features and labels.
3.2
BACKGROUND
3.2. GRAPH NEURAL NETWORK
Graph neural networks are typically used to answer questions based some graph data. The tasks such as node classification, link prediction, and graph classification can addressed using GNNs. A graph G (V, E) with matrix feature vectors X E Rnxd where of the feature vector zu of node E V. We represent the intermediate embedding of node v at Ith layer as ht The final representation of each node is then passed to the downstream deep network so as to make the desirable predictions related to the task. To get the representation of each node in the graph, GNN has primary steps each layer for every node: 1. Aggregation of node's neighborhood and 2. Updating the node's 's embedding. These steps are applied as many times as the number of layers in the GNN.
[V] and d is the size
K'y = AGGREGATE (IM-): :uE
h UPDATE ((1,-,,
(2)
In Iquation AGGREGATE is differentiable, permutation invariant function that aggregates the feature vectors from layer - of the nodes negihborhood (Noo) of the node v. The neigh- borhood is defined (u)) {u: (u, F). ). In equation UPDATE is differentiable function.

---

Under review as a conference paper at ICLR 2023
Our Contribution
User Side
selector
Encoder
RR
Rectifiete
Server Side
Krrop
KProp
Figure 3: Overview of SPGraph algorithm with edge privacy in addition to the node features and label privacy. The nodes' structure is perturbed using the À selector and then applying randomized response on the set of neighborhoods.
3.2.2 DIFFERENTIAL PRIVACY
Local differential privacy (LDP) enables users to share noisy private data with the untrusted aggre- gator instead of their true private data while maintaining considerable accuracy group queries. has been used in the last decade for collecting sensitive private data and answering group queries such statistical mean and count. Companies like Apple Cormode et al. (2018), Google Ülfar Er- lingsson et al. (2014), and Microsoft Ding et al. (2017) have already started including LDP in their products.
Definition 3.2 (Local Differential Privacy) An algorithm A satisfies c-local differential privacy (c-LDP), if and only for any input x and x', we have
Vy E Ronge Pr[A(a) = v) s Pr(A(')) =
where Range(.A) A) is the set of all possible outputs of the algorithm A and c 2 0.
4 PROPOSED METHOD
This section describes our method to introduce structural privacy in Graph Neural Networks. For particular node v, we add the noise to the set of its neighbors. This will ensure that the actual neighborhood information is not passed to the server. A neighbor is either dropped from the set of neighbors on the application of the randomization mechanism. It will keep or remove the neighbors with some associated probability. Figure 4.1 shows the algorithm, which we describe step-by-step here.
4.1 PRIVACY IN GRAPH STRUCTURE
To preserve privacy in the graph's structure, we perturb the connectivity information of the graph. This is done by introducing noise in the neighborhood the nodes. We propose the methodology that we call X selector to induce noise and is given algorithm !
The noise is added as shown in the algorithm I things.
This, however, needs to consider the following
4.1.1 CHOOSING THE VALUE OF À
Our method considers the set Ntr) of actual neighborhood nodes the node We cannot domize this set of nodes, as the randomization will only lead to removing some the existing neighbors. It will result in reduction in the degree of the node and also reduction in the average
4

---

Under review as a conference paper at ICLR 2023
Algorithm X Selector Algorithm
Input: u: A node the vertex V. E: The set of neighboring nodes of node v, Number of
extra nodes to be added to a. Vc,; The set of nodes in the cluster containing node v
Output: (v): noisy set of neighbors of node v
1: MI <- Sample a set of nodes the set Vc. /A, uniformly at random without replacement
2: A < apply randomization mechanism on the set A.p
3: return set set (v) as the noisy neighborhood set
degree of the nodes in the graph. With backtracking, it is still possible that the actual neighborhood information compromised. Additionally, there no noise added to the neighborhood information when randomization is applied only on the original neighborhood. For this reason, we consider more nodes in addition to A. for applying randomization. The hyperparameter À is to specify how many more nodes consider in addition the actual neighborhood. A randomization mechanism is applied to the set of nodes with the actual neighborhood nodes plus À sampled nodes.
When the value of À is too high, the privacy budget gets reduced significantly per neighborhood node, resulting in the addition of less noise. On the other hand, when the value of i too less, though it will add noise to the actual neighborhood, mostly results in the subsets of the neighborhood or a very less number of additional nodes depending on the value of X. Both of these scenarios are not desirable. Hence the choice of the value of is important.
4.1.2 SET TO SAMPLE NODES FROM
The choice of the value of X, as well as the set from which the many nodes are chosen, is crucial. We apply randomization over all nodes in the graphs if select À = de, the randomization will be applied to all the nodes. The privacy budget e for edge perturbation gets distributed over nodes. Hence, the privacy budget becomes e per neighbor. The noise is proportional to the privacy budget, due to which ce/n privacy budget per neighbor does not add significant amount of noise in the neighborhood, as the privacy budget gets divied across all the n nodes in the graph, where n. is quite large.
As we understand that in a graph, similar nodes are connected, choosing randomly from the set of all nodes except the actual neighborhood nodes may lead to sampling nodes that are many hops away from the node consideration, v. These nodes far away from e may not be similar it. Given the neighborhood aggregation in GNN, the neighbors contribute significantly to the node's embedding. irrelevant nodes are added to the neighborhood. they would highly affect the final embedding of the node. This is unlike the desirable case where only the relevant neighbors impact the node's s final embedding. Adding distant nodes to the neighborhood would result in a drop in accuracy.
To overcome this challenge, we propose considering the nodes in the cluster to which the node u belongs using a differentially private clustering algorithm to sample À nodes. Differentially private clustering algorithms clusters from which we can sample À nodes. This can avoid adding distant nodes as neighbors and keep the perturbed edge list confined to the local cluster. Other methods of differentially private sharing of neighbors upon query get a noisy neighborhood may be used as well.
(2020); Bun et al. (202I); Mille et al. (2015) can be used to get
4.1.3 ADDITION OF NOISE RANDOMIZATION
Once we have the set of nodes sampled from the clusters and the actual neighbors, we can apply randomization mechanism add noise to the data. We use the randomized response as the ran- domization mechanism. For each user, adjacency vector a, randomized response algorithm creates a perturbed edge a, for every edge a;-
This vector d: is the perturbed neighborhood the user can share with the server. This ensures the privacy of the graph's structure when every node is sharing the perturbed neighborhood.
Lemma 4.1 Edge perturbation through randomized response satisfies e-local differential privacy Dwork et al. (2014).
5

---

Under review as a conference paper at ICLR 2023
4.1.4 REMOVAL OF ADDED NOISE
Adding noise the neighborhood means that some nodes are not connected the node in the original graph, but the edge exists in the perturbed neighborhood. This will lead to the node being connected the neighbobbg nodes, which will contribute to the nodes' final embeddings and affect the predictions done by the GNN. We leverage the KProp algorithm Sajadmanesh & Gatica- Perez (021) to cancel this noise. aggregates the representations of the neighbors that are up hops away. Initially in section 4.1.2 we carefully choose the set from which we sample X. As these are nodes in the vicinity of the node question, we do not deviate much from the embedding that the node would have produced with the original neighborhood. The node embedding is updated as shown in the equation in parallel for & times for all the nodes the graph.
h (x) = AGGREGATE (f=r kf. Vu E (' {x}})
(4)
h UP (r))))
(5)
where (v) is the perturbed neighborhood of node v.
4.2 PRIVACY IN NODE FEATURES
Node features are privatized using multi-bit encoder, which is built upon 1-bit mechanism, on the user-side. The feature vector corresponding to node is requested by the server, the multi-bit mech- anism applied on get the encoded feature vector which is sent to the server. This gives a biased output which is rectified server-side using a multi-bit rectifier. The differential privacy budget for node feature perturbation Eg. The estimation error is inversely proportional to the num- ber of neighbors of node, but in real graphs, the size of the neighborhood is usually small. To overcome this issue KProp layer is used as a first GNN layer order to denoise the input to the GNN. It considers the k-hopp neighborhood of node for denoising the perturned node features at server-side.
4.3 PRIVACY IN NODE LABELS
Each node participating in training has to perturb the labels as they are considered private. This can be done using an LDP mechanism, which in this case is Randomized Response. The perturbed labels are sent to the server where KProp is applied on node labels. GCN aggregator is used as the aggregate function in KProp as it leads to lower estimation eπror. The differential privacy budget for node feature perturbation Ey. The label denoising with propagation (Drop) Sajadmanesh & Gatica-Perez (2021) is used for training using perturbed node features and node labels.
4.4 PRIVACY ANALYSIS OF SPGRAPH
For each user, adjacency vector a, randomized response algorithm creates a perturbed edge aj for every edge d, Here a; could be 0 or 1. Randomized response algorithm is defined as below:
with probability $
d
with probability 1
(6)
ai with probability 1 f-f
Relevant probabilities are:
P(ay 1/a; = =1) -11=11+11----- - 1
(7)
P(a = 1/a; = 00 5f
(8)
In the algorithm, selector, the algorithm keeps the neighborhood intact and only applics randomized response the À percentage of nodes. Without loss of generality, let the adjacency vector to be perturbed be represented by i.e. a" (b, = 1,..., b, = 1, b,41 = O, b, = 0}.
Let the R.R. represent the ratio between adjacent neighborhood a' and which differ by only one edge. Let the a' differ at the ith position as the perturbed neighborhood only differs by one row. Given the independence of each edge, we only need consider the edge that changed.

---

Under review as a conference paper at ICLR 2023
RR P(A(a) = v)
P(a. = 1 aa; = =1) 1 2/
S mar
(9)
P(A(a') v)
Pla. 1 aa; 0) 2
1
é (RR) = In 2
(10)
2
We combine perturbations in node features, labels, and neighborhoods with privacy budgets ens Ey and 6e respectively in SPGRAPH.
Theorem 4.2 Algorithm SPGRAPH satisfies ex + Eg Eg-local differential privacy.
Theorem 4.2
follows from the post-processing composition theorem [Sengupta et al. (202T). We process only the output the LDP mechanisms on features, labels, and edges of node. LDP mechanism is applied only once on the nodes, and hence any post-processing does not affect differ- ential privacy Dwork al, (2014).
4.4.1 SPGGRAPH'S ' IMPACT ON EMBEDDING
To node v's embedding, on average, the contribution of each of its neighbors be thought of as by [N"[]]- Similarly, node that is p hop away from the node will contribute dex(s)o h. to the node e's embedding. Considering this, after the perturbation, the contribution the new embedding from the À sampled nodes that belong to the cluster with radius is given as À deg(v)p h.. The ratio of the
which comes to deg(u)", It embeddings of node before and after perturbation is h. An h2
should be noted that this analysis is based on the assumption that the neighborhood nodes contribute equally to the generated embedding the node.
EXPERIMENTS
DATASET DESCRIPTION
We perform the experiments on four popular datasets, namely Cora and Pubmed Yang et al. (2016),
Facebook Rozeeberezki et al. (202T) and LastEM |Rozemberezki Sarkar (2020). The dataset
statistics given in the table
1. Cora and Pubmed Yang et al. (016): These are citation networks, where each node repre- sent document and if document cites document j. then (i,j) E E and (j,t) E E. The feature vector corresponding to node is the bag-of-words representation of the document. The labels are the categories the document belong to.
2. Facebool[Roeemeerrzz et al. (202T): Nodes in this dataset are verified Facebook pages and edges are the mutual likes between them. The classification is on the site caterogy and the feature vector are extracted from the site desciption.
3. LastF MastFMMRRzzeeerrzk & Sarkar (2020): Nodes represent the users radio streaming ser- vice LastFM, while the edges represent the friendships amoung the users. The nodes' features are constituted based on the artists user likes. The classification task is to predict the home country of the user. The current usage of the dataset is only limited top 10 countries.
5.1 EXPERIMENTAL. SETUP
We conduct experiments on the all four datasets to study the effect of the addition of noise in the edge data and the effect of varying privacy budgets for edges in the graph. The experimental setup for privacy of node features and node labels remains similar to that in LPGNN Sajadmanesh & Patica-PPrezz (2021
The nodes in all the datasets are split in the ratio of 50:25:25 in training, validation, and test sets. The node features are normalized between [0, 1]. The privacy is applied on the graph neural network
7

---

Under review as a conference paper at ICLR 2023
Table 1: The statistics of the datasets
Dataset
Classes
Nodes
Edges
Features
Average Degree
Cora
7
2708
5278
1433
3.90
Pubmed
3
19717
44324
500
4.50
Facebook
4
22470
170912
4714
15.21
LastFM
10
7083
25814
7842
7.29
models namely GCN & Welling (000)) GAT Velickovi et al. 20 and GraphSAGE Hamil- ton al. (2017). Feature perturbation and edge perturbation are applied during training, validation, and testing, and the label perturbation is applied during the training and validation only, The privacy budgets for edge perturbation e, are taken from the set {0.01, 1, 8, Jo vary the amount of noise (in percentage) À added to the edges for perturbing the neighborhood of the nodes. We select three values deg, deg/ /2, and deg/ 4 for based on each dataset's s average degree deg. The set of lambda values for Cora is {4, 2, 1}. for Pubmed, it is {5, 3, }}. for Facebook, it is {15, 8, 4) and for LastEM, it {7, 4, 2). The other parameters for training using the Drop are the same as that of LPGNN Sajadmanesh & Gatica-Perez. (2021)
For experimental purposes, in place of private clustering algorithms, we consider the p-hop neigh- borhood of the node for simplicity. In this place, any private clustering algorithm can be used. We experiment with values k = 1, 2, 3, and oo with k = oc considering all the other nodes in the graph. The sampling of neighborhood nodes is done from these clusters.
We use Adam optimizer to train the model, and based on validation loss, we pick the best model for testing. Our code will be available on Github.
5.2
EXPERIMENTAL RESULTS
p=
p=
p
mo00el gen Accuraay
80-
80
80
80
60-
80
2.0
0.1
model sage (Accracy
40
40
40
20
20
20
20
0.1
1.0
2.0
Inf
0.1
1.0
2.0
8.0
Inf
0.1
1.0
2.0
8.0
Inf
0.1
1.0
2.0
8.0
inf
modell gat Acouracy
60-
60
60
60
40-
40
40
40
20
20
0.1
1.0
2.0
8.0
0.1
2.0
8.0
inf
0.1
1.0
2.0
8.0
inf
0.1
1.0
2.0
inf
Figure 4: Accuracy for by SPGRAPII with different values of X, p. and e, for Facebook dataset.
8

---

Under review as a conference paper at ICLR 2023
We vary the added noise X, the radius p of the clusters, and the privacy budget ce for the edge perturbation. The privacy-acuuracy trade-off is well observed in the results. The hyperparameter À decides the amount of neighborhood that will be perturbed. In figure 4 can see the lambda values' effect on the LastFM dataset. We see a drop in accuracy as we increase the value of X. This is result of the fact that the À contributes to the privacy of the neighborhood data. As X increases, we are sampling more nodes from the set of nodes that are not the actual neighbors of a node. This results in the contribution of more noisy data to the node's 's embedding. Depending on how much noise is added, the prediction accuracy falls.
The amount of perturbation in the selected edges is given by the privacy budget 6, for edge pertur- bation. We experiment with the different values of privacy budget e, for edge perturbation. When the privacy budget is less, we expect the model to be more private and hence also to be less accurate. We see in figure 4 the effect of the privacy budget on the accuracy of different GNN models we use for the LastFM dataset. As the privacy budget increases, the amount of noise added through randomization decreases, leading to better accuracy.
To sample the À from, we carefully select a set as discussed in section 4.1.2 As for our experimental purposes, we use the y-hop neighborhood, which can also be seen the radius of the private clusters. We see the effect of different values of p. We see our intuition behind our approach working from experiments, which leads to the conclusion that the accuracy is better when the value of is less. This is because the lower radius of the cluster means that the neighhorhood is closer to the node. With an increase in the radius, we tend to sample from distant nodes that may not be related to the node we are interested in. The effect of value of is shown in figure
We provide experimental results depicting the effects of the values of cc, X, and p in the appendix for the rest of the datasets. In some datasets, such as Cora, that have a less average degree, we see that as the value of A increases, the accuracy also increases, which is not in line with our earlier claim. This can be seen in figures 5 6 This exception is seen because in the dataset with smaller average degree, such as 4 in the case Cora, dropping one actual neighborhood also contributes significantly to the embeddings. Similarly, adding the distant nodes would lead to drop in accuracy.
We also learned from these results that the model accuracy is better when the samples for adding noise to the node's neighborhood are chosen from smaller clusters. As the size of the clusters increases, the accuracy drops. This is justified as the smaller cluster enables sampling of nodes similar to the node to which the noise is added. The addition of similar nodes does not affect the final embeddings much and hence gives better accuracy than the sampled from the clusters with larger sizes.
6 CONCLUSION
In this paper, we introduced an approach SPGRAPH to ensure the privacy of the graph structure. solves an important issue of having a privacy-preserving mechanism that ensures that the en- tire graph data privately shared with the server. We discuss the İ selector that samples À nodes from a set. Adding À nodes is essential as that adds noise to the structural information. We then study the significance and selection of the value of X and the set from which it should be sampled. To compensate for the added noise in the neighborhood, we utilize the method KProp to denoise the neighborhood so that the added noise does not significantly hamper the final prediction's ac- curacy. We demonstrate that our method upholds the privacy-accurage trade-off after extensively experimenting with various cases of perturbations and values of different parameters that control the addition of noise to the graph's 's structure.
To further improve privacy in overall graph data, we list a few directions for future work. Firstly a better sampling mechanism can be explored. Specifically, the set from which the noisy neighborhood is sampled can be improved to include distant neighbors that are similar to give better prediction accuracy. Secondly, the existing mechanism for node feature perturbation provided in the earlier works is inadequate as it tends to lose substantial feature information. Better methods that can retain most of the feature information provided. And finally, similar prreecy-res mechanisms can be explored for the graphs that assume heterophily among the nodes.
be explored. Additionally, tighter bounds privacy could be

---

Under review as a conference paper at ICLR 2023
REFERENCES
Mark Bun, Marek Elias, and Janardhan Kulkarni. Differentially private correlation clustering. In International Conference on Machine Learning, pp. 1136-1 1146. PMLR, 2021.
Graham Cormode, Somesh Jha, Tejas Kulkarni, Ninghui Li, Divesh Srivastava, and Tianhao Wang.
Privacy scale: Local differential privacy in practice. In Proceedings of the 2018 International
Conference on Management of Data, SIGMOD '18 pp. 1655-1658, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 978 9781450347037. doi: 10.1 10.1145/3183713.319722
URL httpttttp//oiiii. 0ttp//0..145/311771155 1111331117133311733333 3197390
Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. In Proceedings of the 31st International Conference on Neural Information Processing Sys- tems, NIPS' 17, pp. 3574-3583, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
Vasisht Duddu, Antoine Boutet, and Virat Shejwalkar. Quantifying privacy leakage in graph em- bedding. In Mobiquitous 2020-17th EAI International Conference on Mobile and Ubiquitous Systems: Computing. Networking and Services, pp. 76 25- 2020.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-0077 2014.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Xinlei He, Jinyuan Jia, Michael Backes, Neil Zhenqiang Gong, and Yang Zhang. Stealing links from graph neural networks. In 30th USENIX Security Symposium (USENIX Security 21), pp- 2669-2686, 2021.
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1609.0000, 2016.
Yvonne Mülle, Chris Clifton, and Klemens Böhm. Privacy-integrate graph clustering through differential privacy. In EDBT/ICTT Workshops, volume 157, 2015.
Iyiola E Olatunji, Wolfgang Nejdl, and Megha Khosla. Membership inference attack on graph neural networks. arXiv preprint
2021.
Benedek Rozemberczki and Rik Sarkar. Characteristic functions on graphs: Birds of a feather, from statistical descriptors to parametric models. In Proceedings of the 29th ACM International Conference on Information and Knowledge Management, 2020.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding, 2021.
Sina Sajadmanesh and Daniel Gatica-Perez Locally private graph neural networks. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pp. 2130- 2145, 2021.
Poushali Sengupta, Sudipta Paul, and Subhankar Mishra. Learning with differential privacy. In Handbook of Research on Cyber Crime and Information Privacy, pp. 372-395. IGI Global, 2021.
Uri Stemmer. Locally private k-means clustering. In SODA, pp. 548-559, 2020.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10903 2017.
Chuhan Wu, Fangzhao Wu, Yang Cao, Yongfeng Huang, and Xing Xie. Fedgnn: Federated graph neural network for privacy-preseree recommendation. arXiv preprint arXiv:2102.0499 2021a.
Fan Wu, Yunhui Long. Ce Zhang, and Bo Li. Linkteller: Recovering private edges from graph neural networks via influence analysis. In Proceedings of the Symposium on Security and Privacy, 2021b.
10

---

Under review as a conference paper at ICLR 2023
Depeng Xu, Shuhan Yuan, Xintao Wu, and HaiNhat Phan. Dpne:
Differentially private network embedding. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 235-246. Springer, 2018.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. 2016.
Jun Zhou, Chaochao Chen, Longfei Zheng. Huiwen Wu, Jia Wu, Xiaolin Zheng, Bingzhe Wu, Ziqi Liu, and Li Wang- Vertically federated graph neural network for preaeccii node classification. arXiv preprini arXiv:2005. 1700,, 2020.
Daniel Zügner, Oliver Borchert, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks graph neural networks: Perturbations and their patterns. ACM Trans. Knowl, Discov. Data, 14(5), jun 2020. ISSN 1556-4681. doi: 10.1145/3394520. URL https:://ci.orgg////ooo 1145/ 3394520
Ülfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable ordinal response. In Proceedings of the 21st ACM Conference on Computer and Communications Security, Scottsdale, Arizona, 2014. httttp::://.i...o.eettretee wwtp.raiiiv...........a org/ abs/
1407. 6981
A ADDITIONAL RESULTS
This section demonstrate the results in addition the ones reported in section 5.2
2.0
3.0
inf
model gea Accurecy
60-
60
40-
40
40
40
20
20
20
20
0.1
1.0
2.0
8.0
inf
0.1
1.0
2.0
8.0
int
0.1
1.0
2.0
8.0
1n1
0.1
1.0
2.0
8.0
model - sage Accuracy
80-
80
60-
60
60
60
40-
40-
40
40
0.1
1.0
8.0
0.1
1.0
2.0
8.0
0.1
1.0
2.0
8.0
0.1
1.0
8.0
model gat Accuracy
80-
80
80
80
60-
60
40-
40
1.0
8.0
1.0
8.0
1.0
8.0
0.1
1.0
8.0
Figure Accuracy for by SPGRAPH with different values of X, p. and 6, for Cora dataset.
11

---

Under review as a conference paper at ICLR 2023
1.0
2.0
3.0
moddel gen A
80-
80
60
60
40-
40
40
40-
20
20
0.1
1.0
2.0
8.0
Inf
0.1
1.0
2.0
8.0
Inf
0.1
1.0
2.0
8.0
Inf
0.1
1.0
2.0
8.0
Inf
wodee sage Accuracy
80
80
60-
60
60
60-
40
40
1.0
8.0
1.0
8.0
0.1
1.0
8.0
0.1
1.0
8.0
(tdde gat (Accuracy
80-
80
80-
80
60-
60
60
60
40-
40
1.0
8.0
1.0
8.0
0.1
1.0
8.0
0.1
1.0
8.0
Figure 6: Accuracy for by SPGRAPH with different values of X, p, and 6. for Pubmed dataset.
2.0
3.0
inf
model gea Accuracy
60-
60
40-
40-
40
40
2.0
20
20
0.1
1.0
2.0
8.0
inf
0.1
1.0
2.0
8.0
inf
0.1
1.0
2.0
8.0
1nt
0.1
1.0
2.0
8.0
model = sage Acouracy
80
80
60-
60
60
60
40-
40
40
40
1.0
8.0
1.0
8.0
1.0
8.0
0.1
1.0
8.0
model get Accuracy
80-
80
80
80
60-
60
40-
40
1.0
8.0
1.0
8.0
1.0
8.0
0.1
1.0
8.0
Figure Accuracy for by SPGRAPH with different values of X, p. and 6, for LastFM dataset.
12


Reviews:
[{"review_id": "rVl8KX7JPkk", "reviewer": "Reviewer_nZ2k", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an method that aims to protect the privacy of sharing a graph structure.\nA claim is made that an entire graph is to be privately shared, without a clear definition of how such whole-graph privacy would arise.\nThe type of noise addition following constitutes the addition of nodes sampled from a set by a local-differentially private clustering algorithm, while the added noise is compensated for by a Kprop method, derived from previous work, that aggregates the representatives of neighbor up to k hops away.\nAn experimental study claims to examine the tradeoff between privacy and accuracy.", "summary_of_the_review": "This paper proposes an method that aims to protect the privacy of sharing a graph structure.\nA claim is made that an entire graph is to be privately shared, without a clear definition of how such whole-graph privacy would arise.\nThe type of noise addition following constitutes the addition of nodes sampled from a set by a local-differentially private clustering algorithm, while the added noise is compensated for by a Kprop method, derived from previous work, that aggregates the representatives of neighbor up to k hops away.\nAn experimental study examine the tradeoff between privacy and accuracy.\n\nHowever, it is not clear what privacy guarantees the proposed method offers in practice. The differential privacy guarantee, in a graph context, would imply that a difference of one graph element would not be noticeable to an adversary under noise addition. However, this guarantee says nothing about the ability to derive large-scale graph properties, which could threaten the privacy of individual indeed. Past research has shown [CIKM 2012] that most graph measures can be recovered under noise addition, and that it is hard to even obscure the length of a path in a graph structure. This paper appears to be incognizant of such concerns, as well as of the limitations of differential privacy when it comes to sharing correlated structural idea. Thus, it is not clear what consequences the proposal local differentially privacy algorithms have in effect. A discussion of these concerns is due.", "strength_and_weaknesses": "Stength:\nProposes a reasonable method for graph sharing by noise addition.\n\nWeakness:\nDoes not offer intelligible and consequential privacy guarantees for sharing the whole graph structure as claimed.\nNo results on the privacy side of privacy-accuracy tradeoff.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "Tv9AHcKV8k", "reviewer": "Reviewer_Q4eW", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper investigates the problem of preserving the privacy of edges in the training graph in GNNs. The authors propose to perturb the edges of each node to achieve local differential privacy. ", "summary_of_the_review": "While this paper investigates an interesting problem, the proposed method and analysis seem trivial or wrong.", "strength_and_weaknesses": "Strength:\n\n1) The problem of preserving the privacy of the graph structure is an interesting problem and may be practically useful.\n\n2) According to the claim of this paper, this is the first work trying to investigate the structural privacy problem in GNNs.\n\n\nWeaknesses:\n\n1) The proposed method and analysis do not seem to be specific to GNNs. It is weird that one can claim the privacy of the GNN training algorithm without involving the GNN in the analysis.\n\n2) The lemma and theorem are essentially stated without proof. Either they are incorrect or they are direct applications of existing results. In either case, there is little novel technical contribution.\n\n3) The clarity can be improved. Below are some concrete cases that are unclear in writing.\n\n- Section 4.1.3 states that \"We use the randomized response as the randomization mechanism\". The \"randomized response\" method should be explained with citations. \n- Algorithm 1 states that randomization will be applied to edges to the neighborhood of each node plus lambda nodes. But section 4.1.3 states that randomization will be applied to every edge. \n- Lambda is defined as an integer in Algorithm 1 indicating a number of nodes. In section 4.4, there is a phrase \"lambda percentage of nodes\", which is confusing.\n\n4) Typos.\n\n- Page 5. \"... is too less, ...\" -> is too small\n- Page 5 and Algorithm 1. A_v not defined. There seems to be a change of notation from N(v) to A_v.\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "Btk7HAUdbp", "reviewer": "Reviewer_nodK", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a strategy to add noise / privacy to the structure of a graph.", "summary_of_the_review": "My main concern is that the paper is insufficiently clear.", "strength_and_weaknesses": "The writing, the formalization and the English language used are rather poor, making it often hard or impossible to infer the meaning of the text.\n\nIn general, the paper may have interesting ideas, but it is hard to appreciate then given the current writing.  Also, it is unclear whether the proposed result is very deep, it may be a direct application of earlier work by Dwork (lemma 4,1).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject