Releasing Graph Neural Networks with Differential Privacy Guarantees
Authors: Iyiola Emmanuel Olatunji
Thorben Funke
Megha Khosla
Venue: Accepted by TMLR ()

Abstract: With the increasing popularity of graph neural networks (GNNs) in several sensitive applications like healthcare and medicine, concerns have been raised over the privacy aspects of trained GNNs. More notably, GNNs are vulnerable to privacy attacks, such as membership inference attacks, even if only black-box access to the trained model is granted. We propose PRIVGNN, a privacy-preserving framework for releasing GNN models in a centralized setting. Assuming an access to a public unlabeled graph, PRIVGNN provides a framework to release GNN models trained explicitly on public data along with knowledge obtained from the private data in a privacy preserving manner. PRIVGNN combines the knowledge-distillation framework with the two noise mechanisms, random subsampling, and noisy labeling, to ensure rigorous privacy guarantees. We theoretically analyze our approach in the Rènyi differential privacy framework. Besides, we show the solid experimental performance of our method compared to several baselines adapted for graph-structured data. Our code is
available at https://github.com/iyempissy/privGnn.

Published in Transactions on Machine Learning Research (06/2023)
Releasing Graph Neural Networks with Differential Privacy Guarantees
Tyiola E. Olatunji L3S Research Center Germany
Thorben Funke
tfunke
L3S Research Center, Germany
Megha Khosla TÚ Delft, Netherlonds
m. m.kkosla@tudelff
Reviewed on OpenReview:
https: // openreview. net/ forum? wk8oXROkFA
Abstract
With the increasing popularity of graph neural networks (GNNs) several sensitive applica- tions like healthcare and medicine, concerns have been raised over the privacy aspects of trained GNNs. More notably, GNNs are vulnerable to privacy attacks, such as membership inference attacks, even if only black-box access to the trained model is granted. We propose PRIVGNN, a
framework for relcasing GNN models in centralized setting, Assuming an access to public unlabeled graph, PRIVGNN provides a framework to release GNN models trained explicitly on public data along with knowledge obtained from the private data a privacy preserving manner. PRIVGNN combines the knowledge-istillatte framework with the two noise mechanisms, random subsampling, and noisy labeling, to ensure rigorous privacy guarantees. We theoretically analyze approach in the Rênyi differential privacy framework. Besides, show the solid experimental performance of our method compared to several baselines adapted for graph-structured data. Our code is available at http://tttb..ccmmmyyaeaaarrrrt/r
Introduction
In the past few years, graph neural networks (GNNs) have gained much attention due to their superior performance in a wide range of applications, such social networks Hamilton et al. (2017), biology Ktena
et al. (2018), medicine Ahnnett-Aristizaaa et al. (2021), and recommender systems Fan et al. (2019); Zheng
et al. 2021 Specifically, GNNs achieve state-of-the-rrt results various graph- based learning tasks, such as node classification, link prediction, and community detection.
Real-world graphs, such as medical and economic networks, are associated with sensitive information about individuals and their activities. Hence, they cannot always be made public. Releasing models trained such data provides opportunity for using private knowledge beyond company boundaries Ahmedt- Aristizabal ct al. 2021). For instance, social networking company might want to relcase content labelling model trained on the private user data without eudangering the privacy of the parlicipants Morrow et al. (2022). However, recent works have shown that GNNs are vulnerable to membership inference attacks Olatunji et al.
(2021); He et al. (2021) ; Duddu et al. (2020). Specifically, membership inference attacks aim identify which data points have been used for training the model. The higher vulnerability of GNNs such attacks compared to traditional models has been altributed to their encoding of the graph structure within the

---

Published in Transactions on Machine Learning Research (06/2023)
model Olatunji et al. (2021]. In addition, the current legal data protection policies (e.g. GDPR) highlight compelling need to develop prieacy-preserving GNNs.
We propose our framework PRIVGNN, which builds on the rigid guarantees of differential privacy (DP), allowing us to protect sensitive data while releasing the trained GNN model. DP is one of the most popular approaches for releasing data statistics or trained models while concealing the information about individuals present in the dataset Dwork et al. (2006). The key idea of DP is that we query dataset containing N individuals, the query's result will be almost indistinguishable (in probabilistic sense) from the result of querying a neighboring dataset with one less one more individual. Hence, each individual's privacy is guaranteed with specific probability. Such probabilistic indistinguishabiiiy is usually achieved by incorporating sufficient noise into the query result.
PUBLIC
PRIVATE
PUBLIC
Public Data
Query
Private
Data
Poisson Sampling
KNN from Poisson Subsample
Train
Pseudo-label
Train
Public
Release
GNN
m + Noise
GNN
Model
Figure 1: Workflow of PRIVGNN. Given labeled private and unlabeled public datasets, PRIVGNN starts by retrieving a subset of the private data using Poisson sampling. We then obtain the K-nearest neighbor nodes based on the features of the public query node. The teacher GNN model is trained on the graph induced on K-nearest neighbors. We obtaín a pscudo-label for the query node by adding independent noise to the output posterior. The pseudo-label and data from the public graph are used in training the student model, which is then released.
The seminal work of Abadi et al. 2016 proposed differential private stochastic gradient descent (DP-SGD) algorithm to achieve differential privacy guarantees for deep learning models. Specifically, in each training step, DP-SGD adds appropriate noise to the f2-clipped gradients during the stochastic gradient descent. optimization. The incurred privacy budget ε for training is computed using the moment's accountant technique. This technique keeps track of the privacy loss across multiple invocations of the noise addition mechanism applied to random subsets of the input dataset.
Besides the slow training process of DP-SGD, the injected noise is proportional to the number of training epochs, which further degrades performance. While DP-SGD is designed for independent and identically distributed data (i.i.d),, the nodes in graph data are related. In fact, GNNs make explicit use of the relational structure by recursive feature propagation over connected nodes. Hence, the privacy guarantee of DP-SGD, which requires a set of i.i.d. examples to form batches (subset of the training data that is used in a single iteration of the model training process) and lots (group of one or more batches), does not trivially hold for GNNs and graph data Igamberdiev & Habernal (2021).
To work around DP-SGD's dependency on the training procedure, such the mumber of epochs, Papernot et al. (2016) proposed Private Aggregation of Teacher Ensembles (PATE). PATE leverages large ensemble of teacher models trained on disjoint subsets of private data to transfer knowledge to student model, which is then released with privacy guarantees. However, splitting graph data into multiple disjoint training sets destroys the structural information and adversely affects accuracy.
Since existing DP methods are not directly applicable GNNs, we propose a privacy-preservigg framework, PRIVGNN, for releasing GNN models with differential privacy guarantees. Similar to PATE's dataset assumption, we are given two graphs: labeled private graph and an unlabeled public graph. PRIVGNN leverages the paradigm of knowledge distillation. The knowledge of the teacher model trained on the private graph is transferred to the student. model trained only on the public graph in a differential privacy manner. PRIVGNN achieves practical privacy guarantees by combining the student-teacher training with two noise mechanisms: random subsampling using Poisson sampling and noisy labeling mechanism obtain pseudo-labels for public nodes. In particular, we release the student GNN model, which trained using a small number of public nodes labeled using the teacher GNN models developed exclusively for each public
2

---

Published in Transactions on Machine Learning Research (06/2023)
query node. We present Rênyí differential privacy (RDP) analysis of our approach and provide tight bounds incurred privacy budget or privacy loss. Figure ssows an overview of our PRIVGNN approach.
To summarize, our key contributions include: (i) a novel prisacy-preserving framework for releasing GNN models (ii) theoretical analysis of the framework using the RDP framework (iii) large scale empirical analysis establishing the practical utility of the approach. Besides, we show the robustness of our model against two membership inference attacks.
2 Related Works
Graph neural networks (GNNs) Kipf & Welling (207)): Hamilton al. (2017): Veličkovié al. (2018), mainly popularized by graph convolution networks (GCNs) and their variants, compute node representations by recursive aggregation and transformation of feature representations of its neighbors. While they encode the graph directly into the model via the aggregalion scheme, GNNs are highly vulnerable to membership inference attacks Olatunji et al. (2021). thus highlighting the need to develop privacy-preseriing GNNs.
Existing works on values or /rndd labels are assumed to be private and distributed among multiple distrusting parties (Sajadmaneshi & Sattca-PPeee. 2020 Zhou et al., 2020 Wu al. 2021 Shan et al.) 2021p. Sajadmanesh & Gatica-Perez (2020) assumed that only the node features are scnsitive while the graph structure is publicly available. They developed local differential privacy mechanism to tackle the problem of node-level privacy.
GNNs mainly focused on a distributed sctting in which the node feature
Wu et al. (2021) proposed federated framework for privacy-preserving GNN-based recommendation systems while focusing on the task of subgraph level federated learning. Zhou et al. (2020) proposed a privacy- preserving GNN learning paradigm for node classification tasks among distrusting parties such that each party has access to the same set of nodes. However, the features and edges are split among them. [Shan et al. prrecc-preeerving GNN for the node-level task on a horizontally partitioned
(2021) proposed a server-aided cross-silo scenario via secure pooling aggregation mechanism. They assumed that all data holders have the same feature domains and edge types but differ in nodes, edges, and labels.
In the centralized setting, Sajadmanesh et al. 2022) obtained low-dimensional node features independent of the graph structure and preserve the privacy of the node features by applying DP-SGD for node-level privacy. These features are then combined with multi-hop aggregated node embeddings, to which Gaussian noise is added. [gamberdiev & Habernal (2021) adaptod differentialll-privaall gradient-based training, DP-SGD Abadi et al. (2016), to GCNs for natural language processing task. However, as noted by the authors, the privacy guarantees of their approach might not hold because DP-SGD requires set of ii.d. examples to form batches and lots to distribute the noise effectively, whereas, in GNNs, the nodes exchange information via the message passing framework during training. Other works that utilized DP-SGD in computing their privacy guarantees include Daigavane et al. (2021b; Zhang et al. (2022). In another line of work, Tran et al. 2022 directly perturbs the node features and graph structure using randomized response.
We provide a comprehensive comparison between PRIVGNN and existing works, outlining the specific differences in Appendix F.
3 Our Approach
Setting and notations. Here, we follow the setting of Papernot et al. (2016) in which, in addition to the private graph (with node features and labels), a public graph (with node features) exists and is available to us. This is fair assumption, even for sensitive medical datasets, there exist some publicly available datascts. We also note that companics usually have huge amounts of data but might only release a subset of it for research purposes. A few examples include item-user graphs in recommender systems like the Movielens GroupLensResearch (2021) and Netflix dataset. Furthermore, in the field of information retrieval, Microsoft has relcased the ORCAS datasct Craswell al.] (2020), which is a document-query graph that contains click-throne through data (for a practical real- wollworldd example, please refer to Appendix D.3). It is important note that the nodes of the public graph unlabeled.
3

---

Published in Transactions on Machine Learning Research (06/2023)
We denote graph by G = EV.E) where V is the node-set, and E represents the edges among the nodes. Let X denote the feature matrix for the node-set V, such that X corresponds to the feature vector for node i. We use additionally the superscript to denote private data, such as the private graph G = =(V,, EY) with node feature matrix Xt and labels Yt. For simplicity of notation, we denote public elements without any superscript, such as the public (student) GNN & or the set of query nodes Q C V. In addition, we denote a node e V and the f-hop neighborhood (*(v) with (o) {w} which is recursively defined as: (v) wu) E E and w (v)-
3.1 PRIVGNN Framework
We organize our proposed PRIVGNN method into three phases: pricate data selection, retrieval of noisy pseudo- labels, and sludenl. model Iraining. The pseudocode for our PRIVGNN method is provided in Algorithm [ We start by randomly sampling set of query nodes Q from the public dataset (line 1), We will use the set Q together with the noisy labels (extracted from the private data) for training the student GNN as described below.
Algorithm 1: PRIVGNN
Input: Private graph G (Vi, E²) with private node feature matrix X and private labels Y unlabeled public graph G (V, E) with public features X
Hyperparam K
the number of training data points for training Φt; B the scale of Laplacian noise; y the subsampling ratio
Output: Student GNN, &b Sample public query node-set Q C V for query U E Q do
Select random subset, Pt C Vt, using Poisson sampling: For ag ~ Ber(t), u, Vt select Vt {uylo, 1, Vt)
3
Retrieve the K-nnereest-niighboss of in Vt; (V) = argming (d(X(v), (1)),,, Vtj Construct the induced subgraph H of the node-set (v) from the graph Gt
6 Initialize and train the GNN कt on subgraph H using the private labels y/1
Compute pseudo-label Do using noisy posterior of x
Te = argmax ( + (1/,772 ..... ne). n7 ~ 3)
Train GNN & on G using the training set Q with the pseudo-labels Y= (Nr/v /v E Q} return Trained student GNN model +
3.1.1 Private data selection (Lines 4-5)
Corresponding to query, we first obtain random subsample of the private data using the Poisson subsampling mechanism with sampling ratio y defined as follows (see Def. D.. We denote the retrieved subset of private nodes by Dt. We will see in our privacy analysis that such a data sampling mechanism leads to amplification in privacy.
Definition 1 (PoissonSample). Given a dotaset X, the mechanism PoissonSample outputs a subset of the data (z.lo; = 1, [ni}} by sampling o; ~ Ber(7) independently for i = I,..., n.
The mechanism equivalent to the "sampling without replacement" scheme which involves finding random Binomial(y,n).. As 00, 7 - 0 while -yn S. the Binomial
subset of size m at random with distribution converges to a Poisson distribution with parameter Tn Poisson sampling, each data point is selected independently with certain probability, determined by the sampling rate 7. This method ensures that the overall privacy budget is conserved and allows us to more precisely characterize the RDP of our method (See Appendix
Generating query-specific private subgraph. Our next step is to generate a private subgraph train query-specific teacher GNN. We will then use the trained GNN to generate pseudo-label for the
4

---

Published in Transactions on Machine Learning Research (06/2023)
corresponding query. To generate a query-specific subgraph, we extract the K-nearest neighbors of the query node from the retrieved subset Vt. In other words, for query node Q, we retrieve the node-set (NNN()) with:
(v)( (
where d(.))) denoles a distance function, such as Euclidean distance cosine distance, and X X()) is the feature vector of the node The subgraph H induced by the node-set (t)( of the private graph Gt with the subset of features Xi and the subset of labels x constitute the selected private data (for the query node v). We use this selected private data to train a query-specific GNN.
3.1.2 Retrieving noisy pseudo-labels (Lines 6-7)
As the next step, we want to retrieve pseudo-label for the public query node We train the private teacher GNN tt using the selected private data: the subgraph H with features X and labels Y :- Then, we retrieve the prediction & (v) using the é-hop neighborhood (v) (corresponding to E-layer GNN) of the query node v and the respective subset of feature vectors from the public data. To preserve privacy, we add independent Laplacian noise to each coordinate of the posterior with noise scale 3 = 1/x to obtain the noisy pseudo-labe To of the query node v
................................ U. argmax (+*(v) + (m1 ..... :ee3) M) Lap(O,
We note that the teacher GNN is applied in an inductive setting. That is, to infer labels on public query node that was not seen during training. Therefore, the GNN model most effective in inductive setting like GraphSAGE Hamilton et al. (2017) should be used as the teacher GNN.
3.1.3 Student model (transductive) training
Our private models øl only answer the selected number of queries from the public graph. This is because each time model &t is queried, it utilizes the model trained private data, which will lead to increased privacy costs. The privately (pseudo-)labeled labbeled query nodes and the unlabeled public data are used to train a student model & in transductive setting. We then release the public student model & and note that the public model is differentially private. The privacy guarantee a result of the two applied noise mechanisms, which lead to the plausible deniability of the retrieved pseudo-labed labels and by the post- post-processing property of differential privacy.
3.1.4 Privacy analysis
We start by describing DP and the related privacy mechanism, followed by more generalized notion of DP, i.c. RDP. Specifically, we utilize the bound on subsampled RDP and the advanced composition thcorem for RDP to derive practical privacy guarantees for our approach. For a complete derivation of our privacy guarantee, see Appendix
Differential privacy Dwork et al. (2006). DP is the most common notion of privacy for algorithms on statistical databases. Informally, DP bounds the change in the output distribution of mechanism when there is a small change in its input. Concretely, c-DP puts multiplicative upper bound on the worst-case change in output distribution when the input differs by exactly one data point.
Definition 2 (s-DP), ). A mechanism M: X + θ is E-DP if for every pair of neighboring datasets X'X' E X, and every possible (measurable) outpul set F. C θ the following inequality holds:
Pr[M(X) E F < e PP(M((X) E R.)
Differential privacy for graph datasets. In this work, we consider the case where the adjacent datasets are represented by neighboring graphs, namely and G'. One can then consider node-DP in which and G' differ by a single node and its corresponding adjacent edges edge-DP DP in which the neighboring graphs
5

---

Published in Transactions on Machine Learning Research (06/2023)
differ by single edge. In this paper, provide guarantees for node-DP which also provides stronger give stronger privacy protection than edge differential privacy.
An example of an e-DP algorithm is the Laplace mechanism which allows releasing a noisy output to an arbitrary query with values in R". The mechanism is defined as
Lef(x) a f(x) + Lap(O,
where Lap is the Laplace distribution and A is the & sensitivity of the query f. Since GNN tt returns probability vector, the l sensitivity is Here the second parameter, A1/E is also referred the scale parameter of the Laplacian distribution. Our final guarantees expressed using (e, (eP which is relaxation of E-DP and is defined as follows.
Definition 3 ((e,0)-DP) ) A mechanism M:X Q is (e,6)-DP if for every pair of neighboring datasets X, E X, and every possible (measurablee) output set E S θ the following inequality holds:
Pr[M(X) E EJ S S Pr(M(X') E E
Rênyi differential privacy (RDP). RDP is generalization of DP based on the concept of Rènyi divergence. We use the RDP framework for our analysis as it is well-suited for expressing guarantees of the composition of heterogeneous mechanisms, especially those applied to data subsamples.
Definition (RDP Mironov (2017)). A mechanism M is (a,E)-RDP with order a E (1, if for all neighboring dalasets X, X" the Jollowing holds
(a(M(X)IM(())) a log Fanx ( (
)"} Sc.
As + 00, RDP converges to the pure s-DP. In its functional form, we denote EM(() the RDP of M at order The function EM(+) provides a clear characterization of the privacy guarantee associated with M. In this work, we will use the following RDP formula corresponding to the Laplacian mechanism
a a-11 (
2a - (2a-1)
cLAP(a) = a log
e m-1 +
for 1, where is the scale paramcter of the Laplace distribution. More generally, we will use the following result to convert RDP to the standard (e for any 8 >>1 0.
Lemma 5 (From RDP to (e,8)-DP). If a mechanism Mi satisfies (D,e)-DDP, then Mi also satisfies (s log 1/6 1/6 a-1 6)P for any 8 E 1).
For a composed mechanism M = (Mi,..., we employ Lemma 5 to provide an (s, 0)-DP guarantee
8 + 8 E()) min log(1/5) + (a 1),
a>1 a
Another notable advantage of RDP over (s, DP is that it composes very naturally.
Lemma 6 (Composition with RDP). Let M (MM,...,MM, be mechanisms where M; can potentially depend on the outputs of Mi-...,M-11. Then M obeys RDP with em(-) Et EM (.).
Lemma 6 implies that the privacy loss by the composition of two mechanisms Mi and M2 is
(M.xM, = [s +
Privacy amplification by subsampling. A commonly used approach in privacy is subsampling in which the DP mechanism applied the randomly selected sample from the data. Subsampling offers a stronger privacy guarantee in that the one data point that differs between two neighboring datasets has decreased probability of appearing in the smaller sample. See Appendix B Theorem for details.

---

Published in Transactions on Machine Learning Research (06/2023)
3.2 Privacy Guarantees of PRIVGNN
Theorem 7. Por any 8 > O, Algorithm
is (s, (s, with
S log
[Q] log (1 + +² (ge110 10 + + -
210 - 1)))
(2)
where Q is the set of query nodes chosen from the public dataset, B is the scale of the Laplace mechanism.
Proof Sketch. First, using the Laplacian mechanism, the computation of the noisy label for each public query node is 1/a-DP. We perform the transformation of the privacy variables using the RDP formula for the Laplacian mechanism. As the model uses only a random sample of the data to select the nodes for training the private model, we, therefore, apply the tight advanced composition of Theorem to obtain (a)) To obtain bound corresponding to Q queries, further use the advanced composition theorem of RDP. The final expression is obtained by appropriate substitution of and finally invoking Lemma 5 for the composed mechanisms. The detailed proof is provided in Appendix B.2
Remark. We remark that Equation equation 2 provides only rough upper bound. It is not suggested to use it for manual computation of as it would give a much larger estimate. We provide it here for simplicity and to show the effect of the number of queries and sampling ratio on the final privacy guarantee. For our experiments, following Mironov (2017), we numerically compute the privacy budget with 8 < 1/Iv* while varying a E ( 323 and report the corresponding best E.
4 Experimental Evaluation
With our experiments, we aim to answer the following research questions:
RQ 1. How do the performance and privacy guorantees of PRIVGNN compare to that of the baselines?
RQ 2. What is the effect of sampling different. K-nearest neighbors the performance of privale PRIVGNN method?
RQ 3. How does the final privacy budget of different approaches compare with an increase in the namber of query nodes (!Q))?
RQ 4. What the effect of varying the sampling ratios on the privacy- utility trade-off for PRIVGNN?
RQ 5. How do various design choices of PRIVGNN affect its performance!
Besides, we conduct additional experiments to investigate (i) the robustness of PRIVGNN towards two membership inference attacks (c.f. Section C. (ii) the sensitivity of PRIVGNN (c.f. Appendix D.2 to the size
of private/pubis public datasels and (iii) the effect of pre-training the accuracy of PRIVGNN (c.f. Appendix D.7 We also discuss the time and space requirements of PRIVGNN in Appendix H and the behavior of PRIV GNN and PATE basclines when the fcatures are more informative than the graph structure in Appendix D.1
4.1 Experimental Setup
Datasets. We perform our experiments on four representative datasets, namely Amazon Shehur et al. 2018) Amazon2M Chiang et al. (0019). Reddit Hamilton et al. (2017) and Facebook Traud et al. (2012). We also perform additional experiments on ArXiv Hu et al. (2020) and Credit defaulter graph Agarwal et 2021
with highly informative fcatures. The detailed description of the datascts is provided in Appendix and their statistics in Table II
Baselines. We compare our PRIVGNN approach with three baselines. These are (i) non-private inductive baseline (B1) in which we train GNN model on all private data and test the performance of the model on the public lest set, (ii) non-privale transductive baseline (B2) in which we train the GNN model using the public train split with the ground truth labels. The performance on the public test split estimates the "best possible" performance on the public data (iii) two variants of PATE baseline namely PATEM and PATEG, which use MLP and GNN respectively as their teacher models. A detailed deseription of the basclines is provided in Appendix G
7

---

Published in Transactions on Machine Learning Research (06/2023)
Model and Hyperparameter Setup. For the private and public GNN models, we employ two-layer GraphSAGE, model Hamilton et al. (2017) with hidden dimension of 64 and ReLU activation function with batch normalization. For the MLP used in PATEM, we used three fully connected layers and ReLU activation layers. All methods are compared using the same hyperparamoter settings described in Appendix G.1
Privacy Parameters. We set the privacy parameter À = 1/s. To demonstrate the effects of this parameter, vary and report the corresponding privacy budget for all queries. We the reference values as follows (0.1, 0.2, 0.4, 0.8, 1}. We set 8 to 10 for Amazon, Facebook, Credit, and Reddit, and 10 for ArXiv and Amazon2M. We fix the subsampling ratio y to 0.3 for all datasets except for Amazon2M, which is set to 0.1. All our experiments were conducted for 10 different instantiations, and we report the mcan values across the runs in the main paper. The detailed results with the standard deviation are provided in Appendix A
5 Results
We now discuss the results of our five rescarch questions presented in Section
5.1
Privacy-utility Trade-off (RQ 1
Amazon
Amazon2M
Reddit
Facebook
Accuracy
0.8
PrivGNN
0.6
PATEM
PATEG
0.4
B1
0.2
B2
0.0
0.2
0.4
0.6
0.8 1.0
0.2 0.4 0.6 0.8 1.0 À
0.2 0.4 0.6 0.8 1.0
0.2 0.4 0.6
0.8 1.0
À
À
A
(a) Accuracy vs. Noise (xx 1/1) injected each query.
Amazon
Amazon2M
Reddit
Facebook
103
E10
PrivGNN
PATEM
10a
PATEG
100
0.2 0.4 0.6 0.8 1.0
0.2 0.4 0.6 0.8 1.0 X
0.2 0.4 0.6 0.8 1.0 X
0.2 0.4 0.6 0.8 1.0
A
À
(b) Privacy budget vs. Noise (x !/x) injected to each query.
Figure 2: Privacy-utility analysis. Here, |Q] to 1000. For PRIVGNN, y is set 0.1 for Amazon2M and 0.3 for other datasets.
Figure 2 shows the performance our privacy- privacy-preservig PRIVGNN mothod as compared to two private and two non-private baselines. Since the achieved privacy guarantees depend on the injected noise level, we report the performance (c.f. Figure (2a) and the final incurred privacy budget (c.f. Figure 2b) with respoct
X = 1/3 which inversely proportional to the injected noise for each query. Here, we set [Q]= 1000 for all three private methods.
First, the performance of our PRIVGNN approach converges quite fast to the non-private method, B1, as the noise level decreases. Note that B1 used all the private data for training and has no privacy guarantees. The reason for this convergence is that as the noise level decreases in PRIVGNN, the amount of noise introduced to the psuedo-labels decreases. As result, the model can rely more on the less noisy psuodo-labels, loading to improved performance that approaches that of B1. The second non-private baseline, B2, trained using part of the public data, achieves slightly higher results than B1. This is because B2 benefits from the larger
8

---

Published in Transactions on Machine Learning Research (06/2023)
size of the public dataset, which provides more diverse and representative samples for training. By having access to larger and more varied set of data, B2 can capture a wider range of patterns and information, resulting in slightly improved performance compared to B1. For Amazon2M, Facebook and Reddit, PRIVGNN outperforms B1 for À > 0.4.
Secondly, compared with the private methods (PATEM and PATEG), PRIvGNN achieves significantly better performance. For instance, at a smaller À = 0.2, we achieved 40% and 300% improvement in accuracy (with respect to private baselines), respectively, average degree (Amazon2M, Facebook, and Reddit), PRIVGNN achieved higher improvements of up to 134% and 2672% in accuracy when compared to the PATE methods. Morcover, as we will discuss next, PRIVGNN incurs significantly lower privacy costs as compared to the two private baselines.
the Amazon dataset. We observe that for datasets with a high
Thirdly, we plot the incurred privacy budget E corresponding to different in Figure 2b PRIVGNN achieves a relatively small of 2.83 on the Amazon2M datasct, while on the Amazon, Reddit, and Facebook datasct, a & of 8.53 at À 0.2. The correspouding value of on PATEM and PATEG for the datasets are 167.8) on Amazon, 173.82 on Amazon2M, 157.90 for Reddit, and 170.41 for Facebook. In fact, PRIVGNN achieves the performance of non-private baseline at E equal to 5.94 and 19.81 for Amazon2M and Reddit datasets respectiuely.
It is not surprising that both PATEM and PATEG have similar & on all datasets except for Reddit. This is because PATE methods depend on agreement or consensus among the teacher models, which further reduces E. This indicates that there no consensus among the teachers. We observe that the privacy budget increases as the Ả gets larger. This phenomenon is expected since larger implies low privacy and higher risk (high e)-
Summary. PRIVGNN outperforms both variants of PATE by incurring lower privacy budget and achieving better accuracy. We attribute this observation to the following reasons. First, our privacy budget is primarily reduced due to the subsampling mechanism, whereas PATE uses the complete private data. Second, in the case of PRIVGNN, we train a personalized GNN for each query node using nodes closest to the query node and the induced relations among them. We believe that this leads to more accurate labels used to train the student model, resulting in better performance. On the other hand, the worse privacy and accuracy of PATE indicates larger disagreement among the teachers. The random data partitioning in PATE destroys the graph structure. Moreover, teachers trained on disjoint and disconnected portions of the data might overfit specific data portions, hence the resulting disagreement. The Appendix (Table 5 contains the mean and standard deviation of the results shown in Figure 2a
5.2
Effect of K on the Accuracy (RQ
To quantify the effect of the size of the random subset of private nodes on the accuracy of PRIVGNN, we vary the number of neighbors K used in K-nearest neighbors. Note that the computed privacy guarantee is independent of K. For the Amazon dataset, we set K to (300, 750), and for the Amazon2M, Reddit, and Facebook dataset, we set to {750, 1000, 30003. We select smaller K for Amazon due to the small size of the private dataset.
As shown in Table 1 general observation is that the higher the K, the higher the accuracy. For instance, sampling K = 750 nodes achieve over 50% improvements on the Amazon dataset than using K 330 private nodes for training. On the Amazon2M, Reddit, and Facebook datasets, a value of K above 1000 only increases the accuracy marginally. From the above results, we infer that the value of the hyperparameter K should be chosen based on the average degree of the graph. A small K suffices for sparse graphs (Amazon), while for graphs with a higher average degree (Amazon2M, Reddit, and Facebook), a larger K leads to better performance. We further quantify the effect of K in PRIVGNN by removing KNN and directly training with the entire private graph in ablation studics(c.f. Section 5.5
5.3 Effect of [Q) on the Accuracy and Privacy (RQ 3
Since the privacy budget is highly dependent on the number of queries answered by the teacher GNN model, compare the performance and relative privacy budget incurred for answering different numbers of queries.
9

---

Published in Transactions on Machine Learning Research (06/2023)
Table 1: Accuracy for varying K and [Q| = 1000.
Amazon
Amazon2M
Reddit
Facebook
A/K
300
750 750
1000
3000
750
1000
3000
750
1000
3000
0.1
0.17
0.40
0.22
0.26
0.30
0.30
0.33
0.35
0.15
0.23
0.24
0.2
0.34
0.64
0.36
0.41
0.42
0.48
0.53
0.61
0.26
0.41
0.45
0.4
0.53
0.80
0.41
0.57
0.60
0.65
0.72
0.80
0.33
0.55
0.60
0.8
0.56
0.82
0.44
0.59
0.66
0.69
0.76
0.86
0.38
0.69
0.72
1.0
0.59
0.83
0.47
0.64
0.70
0.71
0.77
0.88
0.40
0.76
0.80
Amazon
Amazon2M
Reddit
Facebook
0.8
Accuracy
0.6
|Q|
500
0.4
1000
0.2
0.2
0.4
0.6
0.8
1.0
0.2 0.4
0.8 1.0 À
0.6
0.2 0.4 0.6
0.8 1.0 A
0.2 0.4 0.6
0.8 1.0
À
Figure 3: Accuracy for the different number of queries answered by the teacher model of PRIVGNN
In Figure 3 we observe a negligible difference in accuracy when 1000 query nodes are pscudo-labeled and when only 500 queries are employed across all datasets at different noise levels except on Amazon2M. Further looking at detailed results in Table 2] for the different ranges of on the Amazon, Reddit, and Facebook datasets, we observe up to 46% decrease in privacy budget of PRIVGNN for answering 500 queries over answering 1000 queries. On the Amazon2M datasct, we observe up to 45% decrease in privacy budget. This implies that smaller [Q] is desirable, which PRIVGNN offers.
In Table 2 also compare PRIVGNN with PATE variants with respect to the incurred privacy budget for answering the different number of queries. Our method offers significantly better privacy guarantee (over 20 times reduction in S) than PATEM and PATEG across all datasets. While decreasing the number of queries shows a negligible change in accuracy, it greatly reduces the incurred privacy budget for PRIVGNN. In particular, the privacy budget (see Table 2), e, of PRIVGNN reduced by 50% on the Amazon, Reddit, and Facebook datasets and by 40% on the Amazon2M dataset with only slight reduction accuracy. To determine the point at which the tradeoff between privacy and utility becomes severely compromised, we conducted additional experiments by adjusting the number of queries, using the additional reference values (300, 200, 100, 10}. The results of these experiments are available in Appendix D.6
We remark that we also experimented with more intelligent strategies for query selection which did not show any performance gains. In particular, we employed sineturoobbsed approaches such as clustering and ranking based on centrality measures such as PageRank and degree centrality to choose the most. representative query nodes but observed no performance gains over random selection.
5.4 Varying Subsampling Ratio (RQ 4
A smaller sampling ratio will reduce the amount of private data used for training which will, in turn, reduce the privacy budget e. Therefore, to validate the effectiveness of the sampling ratio, we vary y from 0.1 to 0.3. This allows us to further benefit from the privacy amplification by subsampling as explained in Section B.I Since y affects the amount of the available data used training the teacher model, we only perform this experiment on reprosentative datasets (Amazon2M and Reddit). Table 3 demonstrates that the accuracy achieved using a sampling ratio of ? = 0.1 on the Amazon2M dataset only slightly lower than that of y = 0.3 for À= 0.4, with a decrease of only 6%. This indicates that the sampled data at 7 0.1 captures
10

---

Published in Transactions on Machine Learning Research (06/2023)
Table 2: Privacy budget (e) (lower the better) for varying number queries [Q
answered by the teacher.
Q2I -
0.1
0.2
0.4
0.8
1.0
PRIVGNN
2.67
5.69
13.15
31.10
14.07
500
PATEM
27.82
87.82
223.08
233.46
220.57
AMAZON
PATEG
27.82
87.82
327.82
800.97
1000.97
PRIVGNN
3.90
8.53
19.81
55.30
81.23
1000
PATEM
47.82
167.82
434.69
449.36
424.78
PATEG
47.82
167.82
647.82
1600.97
1967.58
PRIVGNN
0.97
1.96
4.03
8.73
11.17
AMAZON2M
500
PATEM
33.82
93.82
294.89
379.92
416.65
PATEG
33.82
93.82
333.82
801.73
1000.73
PRIVGNN
1.39
2.83
5.94
12.98
17.73
1000
PATEM
53.82
173.82
573.80
751.09
850.63
PATEG
53.82
173.82
653.82
1601.73
2001.73
PRIVGNN
2.67
5.69
13.15
31.10
44.07
500
PATEM
29.43
83.73
243.45
392.23
415.35
REDDIT
PATEG
29.43
89.43
329.43
801.17
1001.17
PRIVGNN
3.90
8.53
19.81
55.30
81.23
1000
PATEM
49.43
157.90
496.61
775.95
808.43
PATEG
49.43
169.43
649.43
1601.17
2001.17
PRIVGNN
2.67
5.96
13.15
31.10
44.07
FACEBOOK
500
PATEM
30.41
90.41
293.44
151.02
136.41
PATEG
30.41
90.41
330.41
801.30
1000.30
PRIVGNN
3.90
8.53
19.81
55.30
81.23
1000
PATEM
50.41
170.41
579.15
306.12
282.63
PATEG
50.41
170.41
650.41
1601.30
2001.30
similar underlying patterns and distributions to the data with 7 0.3. On the Reddit dataset, we observe a 35% decrease in the accuracy when 7 0.1 at the same X. Nonetheless, we observe 315% reduction in the privacy budget when 7 0.1. This implies that smaller offers better on both datasets at a relatively lower drop in accuracy. We conclude that PRIVGNN provides an overall good privacy-utility trade-off with respect to In other words, for larger datasets, a significant reduction in privacy costs can be achieved (when using smaller 7) with a relatively lower degradation in accuracy.
Table 3: Performance and the respective privacy budget for different sampling ratios with Q 1000 for Amazon2M and Reddit. The non-private baseline B1 achieves an accuracy of 0.62 and 0.78 for Amazon2M and Reddit, respectively. PRIVGNN already achieves comparable or better accuracy with e of 5.94 and 19.81, respectively (marked in bold).
7 = 0.1
= 0.3
Reddit
Amazon2M
Reddit
Amazon2M
e
Accuracy
Accuracy
Accuracy
Accuracy
0.1
1.20
0.19
1.39
0.30
3.90
0.35
4.45
0.35
0.2
2.47
0.37
2.83
0.42
8.53
0.61
9.69
0.51
0.4
5.20
0.52
5.94
0.60
19.81
0.80
22.11
0.64
0.8
11.82
0.63
12.98
0.66
55.30
0.86
57.60
0.69
1.0
15.44
0.65
17.17
0.70
81.23
0.88
83.53
0.77
11

---

Published in Transactions on Machine Learning Research (06/2023)
5.5 Ablation Studies (RQ
Table 4: Ablation studies. Here, we present the accuracy of different. methods with varying À and |Q]= 1000. We show for representative datasets
Amazon2M and Reddit with 7 = 0.1 and 0.3 respectively.
A 0.1
0.2
0.4
0.8
1.0
Reddit
PRIvGNN
0.35
0.61
0.80
0.86
0.88
KNNREM
0.34
0.58
0.75
0.79
0.81
SINGLEGNN
0.28
0.54
0.72
0.77
0.79
Amazon22
PRIVGNN
0.30
0.12
0.60
0.66
0.70
KNNREM
0.28
0.39
0.49
0.56
0.59
SINGLEGNN
0.25
0.32
0.43
0.54
0.56
To answer RQ 5 we conducted ablation studies by varying different components of our proposed model. First, we removed the KNN component (Line in Algorithm D and constructed the induced subgraph on the entire subsampled dataset for each query. We refer to this KNNREM. Secondly, besides removing the KNN component, only sample once from the private data instead of sampling for each query. Hence, we only train single teacher model using the graph induced by subsampling. We refer to this as SINGLEGNN. We present our results in Table 4 We remark that, theoretically, the same privacy guarantees as our method holds for these two ablations. In practice, on the other hand, PRIVGNN would offer bet ter privacy because only a smaller portion of the private sample is used for teacher training compared to the ablations which the KNN component is removed.
We make the following observations from our results. First, we up to 18% and 8% drop in accuracy with KNNREM on the Amazon2M and Reddit datasets, respectively. This indicates the importance of our KNN approach since only the most informative node for the query node is used in training and predicting the pseudo-label.
Secondly, considering the performance of SINGLEGNN, the advantage of the multiple subsampling and the KNN components is prominent in both datasets, At a higher noise level (when = 0.2), we observe a performance drop of 23% and 12% on the Amazon2M and Reddit dataset, respectively, when SINGLEGNN is used compared to PRIVGNN.
Additional experiments. We performed several additional experiments. This includes two membership inference attacks to evaluate the privacy leakage of the released model. We observe that PRIVGNN reduces the attacks to a random guess (Appendix Ch. We analyze the impact of informative node features on the performance of PRIVGNN in Appendix D.1 The result indicates that PRIVGNN in the presence of highly informative node features performs well than both PATEM and PATEG basclines. To better understand the influence of the private-public graph size on the performance of PRIVGNN we perform a sensitivity analysis by flipping the graphs. The result shows that PRIvGNN is not sensitive to the size of the private-puli public graphs (Appendix D.2h. We also perform experiment that utilizes pre-training technique to improve the performance of PRIVGNN. The result shows slight improvement in the performance of PRIVGNN (Appendix D.7. In Appendix D44, we compare our method to an additional non-private baseline. This baseline involves the joint training of a single GNN on both the private and public graphs. Furthermore, in Appendix [D.5] we evaluate another private baseline where Laplacian noise is directly applied to the ground truth label of each query node. Finally, we analyze the runtime and space requirements of PRIVGNN in Appendix and highlight the limitations and future works (Appendix T
6 Conclusion
We propose PRIVGNN, a novel privacy-preserving framework for releasing GNN models with differential privacy guarantees. Our approach leverages the knowledge distillation framework, which transfers the knowledge of the teacher models trained on private data to the student model. Privacy is intuitively and
12

---

Published in Transactions on Machine Learning Research (06/2023)
theoretically guaranteed due to private data subsampling as well as the noisy labeling of public data. Moreover, as we build personalized teacher models by using the K-nearest neighbors of the corresponding query nodes, the trained teacher model is more confident in its prediction. Results from the ablation studies further support our design choices. We present the privacy analysis of our approach by leveraging the Rênyi differential privacy framework. Our experiment results on six real-world datasets show the eflectiveness of our approach in obtaining good accuracy under practical privacy guarantees.
References
Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang, Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communicatiinss securily, pp. 308-318, 318, 2016.
Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. Towards unified framework for fair and stable graph representation learning. In Uncertainty in Artificial Intelligence, pp. 2114 2124. PMLR, 2021.
David
Mohammad Ali Armin, Simon Denman, Clinton Fookes, and Lars Petersson. Graph-based deep learning for medical diagnosis and analysis: Past, present and future. Sensors (Basel, Switzerland), 21(14). 2021.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. arXiv preprint NxX::1807.01647, 2018.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 257-266, 2019.
Nick Craswell, Daniel Campos, Bhaskar Mitra, Emine Yilmaz, and Bodo Billerbeck. Orcas: 18 million clicked query-document pairs for analyzing scarch. arXiv preprint arXiv:2006. 05324, 2020. URL https
//microsoft. geaiiigggtuuu... htwitttub.oo/mmmarr////Reaeee html
Ameya Daigavane, Gagan Madan, Aditya Sinha, Abhradeep Guha Thakurta, Gaurav Aggarwal, and Prateek
Jain. Node-level differentially private graph neural networks. arXiv preprint arXiv:2111.15521 2021.
Vasisht Duddu, Antoine Boutet, and Virat Shejwalkar. Quantifying privacy leakage in graph embedding. arXiv preprint Xrx:::20000000 00906, 2020.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to scnsitivity in private data analysis. In Theory of cryplography conference, pp. 265 284. Springer, 2006.
Lisa Ehrlinger and Wolfram WöB. Towards a definition of knowledge graphs. SEMANTICS (Posters, Demos, SuCCESS), 48(1-4):2, 2016.
Dumitru Erhan, Aaron Courville, Yoshua Bengio, and Pascal Vincent. Why does unsupervised pre-training help deep learning? In Proceedings of the thirteenth international conference artificial intelligence and statistics, pp. 201-208. JMLR Workshop and Conference Proceedings, 2010.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The World Wide Web Conference, pp. 417-426, 2019.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint ar Xrx: 02488, 2019.
Mingkun Gao, Ziang Xiao, Karrie Karahalios, and Wai-Tat Fu. To label or not to label: The effect of stance and credibility labels on readers' selection and perception of news articles. Proceedings of the ACM on Human- Computrr Intercction, 2(CSCW):1 2018.
CroserhnsSeeeeachh. Movielens, Dec 2021. URL http:://ggaappeas.rrrraaaatttttt
13

---

Published in Transactions on Machine Learning Research (06/2023)
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs. In NIPS, 2017.
Xinlei He, Rui Wen, Yixin Wu, Michael Backes, Yun Shen, and Yang Zhang. Node-level membership inference attacks against graph neural networks. arXiv preprint arXi::2122004420 054.29 2021.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. arXiv preprint 1it::905.12266 2019.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint WrXiv:2005.00687 2020.
Timour Igamberdiev and Ivan Habernal. Privacy-preservic graph convolutional networks for text classification. arXiv preprinl ar Xix:21 (2. 09604, 2021.
Thomas N. Kipl and Max Welling. Semiissueervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Sofia Ira Ktena, Sarah Parisot, Enzo Ferrante, Martin Rajchl, Matthew Lee, Ben Glocker, and Daniel Rucckert. Metric learning with spectral graph convolutions on brain connectivity networks. Neurolmage, 169:431 442, 2018.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton van den Hengel. Image-based recommendations on styles and substitutes. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 43 43-52, 2015.
Iya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Synposium (CSF), pp. 963-275, IEEE, 2017.
Garrett Morrow, Briony Swire-Thomppon, Jessica Montgomery Polny, Matthew Kopec, and John P Wihbey. The emerging science of content labeling: Contextualizing social media content moderation. Journal of the Association for Information Science and Technology, 73(10):1365-1388) 2022.
Iyiola E Olatunji, Wolfgang Nejdl, and Megha Khosla. Membership inference attack on graph neural networks.
Xivi preprint arXiv:2101.06577 2021.
Nicolas Papernot, Martín Abadi, Ulfar Erlingsson, Ian Goodfellow, and Kunal Talwar. Semi-supervised knowledge transfer for deep learning from private training data. arXiv preprint arXiv:1610.0577 2016.
Nicolas Papernot, Shuang Song, Nya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson. Scalable private learning with pate. arXiv preprint orXix:1802.0880 2018.
Thomas Pellissier Tanon, Denny Vrandečié, Sebastian Schaffert, Thomas Steiner, and Lydia Pintscher. From frecbase to wikidata: The great migration. In Proceedings of the 25th international conference on world wide web, pp. 1419 1428, 2016.
Sina Sajadmanesh and Danicl Gatica-Porez. Locally private graph neural networks. arXiv preprint arXiv:2006.0553 2020.
Sina Sajadmanesh, Ali Shahin Shamsabadi, Aurélien Bellet, and Daniel Catica-Perez, Gap: Disferentially private graph neural networks with aggregation perturbation. arXiv preprint 22XX::2203300949 2022.
Emily Saltz, Claire R Leibowicz, and Claire Wardle. Encounters with visual misinformation and labels across platforms: An interview and diary study to inform ecosystem approaches to misinformation interventions. In Extended Abstracts of the 2021 CHil Conference on Human Factors in Computing Systems, pp. 6, 2021.
Chuanqiang Shan, Huiyun Jiao, and Jie Fu. Towards representation identical seeracc-preeevingg graph neural network via split learning. arXio preprint or Xii:2107700917 2021.
14

---

Published in Transactions on Machine Learning Research (06/2023)
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günneeman. Pitfalls of graph neural network evaluation. arXiv preprinl or Xrn: 181 1.05868, 2018.
Amit Singhal. Introducing the knowlodge graph: Things, not strings, May 2012. URL https::/blog..ooo/
Khang Tran, Phung Lai, NhatHai Phan, Issa Khalil, Yao Ma, Abdallah Khreishah, My Thai, and Xintao
Wu. Heterogeneous randomized response for differential privacy in graph neural networks. arxie preprinl arXiv:2211.05700 2022.
Amanda L Traud, Peter J Mucha, and Mason A Porter. Social structure of facebook networks. Physica A: Stolistical Mechanics and ils Applications, (11)::4:165-4414 2012.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph Atlention Networks. International Conference on Leurning Represenlations, 2018.
Denny Vrandečíé and Markus Krötzsch. Wikidata: free collaborative knowledgebase. Communications of the ACM, 57(10):78 85, 2014.
Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. In The 22nd International Conference on Artificial Intellgence and Slatislics, pp. 1226 1235. PMLR, 2019.
Chuhan Wu, Fangzhao Wu, Yang Cao, Yongfeng Huang, and Xing Xic. Fodgun: Federated graph neural network for privacy-preserving recommendation. arXiv preprint arXiv:2102.04400 2021.
Qiuchen Zhang, Jing Ma, Jian Lou, Carl Yang, and Li Xiong. Towards training graph neural networks with node-level differential privacy. arXiv preprint arXiv:221000444 2022.
Yu Zheng, Chen Gao, Liang Chen, Depeng Jin, and Yong Li. Dgen: Diversified recommendation with graph convolutional networks. In Proceedings of the Web Conference 2021, pp. 401-412, 2021.
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 privacy-presorving node classification. arXiv preprint Xrxi::2005.1 1903, 2020.
Yuqing 7hu and Yu-Xiang Wang. Poission subsampled rényi differential privacy. In International Conference on Machine Learning, pp. 7634 7642. PMLR, 2019.
Appendix
Organization. The Appendix is organized as follows. We begin by providing the detailed accuracy scores of different methods in Appendix A Missing theoretical details and proof are provided in Appendix B We launch two black-box membership inference attacks in Appendix C followed by the analysis of the influence of highly informative features (Appendix [.I), the effect of the size of the public graph (Appendix D.2 a real-world example and motivation (Appendix D.3). additional baselines including the joint training on the private and public graph (Appendix DD4), adding noise directly to the groundtruth labels of the query nodes (Appendix D.5p, privacy utility tradeoff with varying amount of queries (Appendix D.6 and the use of pre-training improve performance (Appendix D.7). Appendix D outlines the distinctions between prior works and clarifies why our approach cannot be compared directly. Appendix F provides detailed description of datasets used followed by details baselines, hyperparameters. and training in Appendix G The runtime and space requirement of PRIVGNN is discussed in Appendix H Lastly, the limitations of the work are highlighted in Appendix [
A Detailed Results
In Tables and 6 WC present the mean accuracy of the different methods as plotted in Figure and 3 respectively.
15

---

Published in Transactions on Machine Learning Research (06/2023)
Table Performance of each method all datasets. Note that the non-private baselines B3 and 132 are not changing with different X.
Method À 0.1
== 0.2
0.4
== 0.8
x=1
PRIVGNN
0.40 + 0.08
0.64
0.80 + 0.13
0.82 + 0.17
0.10
Amazon
PATEM
0.28 0.04
0.05 0.00
0.00
0.70
PATEG
0.05
0.88 0.16
0.15
0.18
0.20
B1
0.02
0.88
0.88 0.82
B2
0.91
0.91
0.91
0.002
0.02
0.91
Amazon2M
PRIVGNN
0.30 +: 0.05
0
0.60
0.66
0.70
PATEM
0.04
0.28 0.02
0
0.44
0.47
PATEG
0.02 0.01
0.03
0.02
0.04
B1
0.00
0.62
0.62
0.01
0.02
0.02
B2
0.78
0.78 = 0.01
0.78
0.78
0.78
PRIVGNN
0.35 0.09
0.61 + 0.18
0.80
0.13
0.07
Reddit
PATEM
0.26 0.00
0.07
0.03
0.05
PATEG
0.03 0.00
0.03
0.06
0.04 0.04
B1
0.00 0.83
0.03
0.00
0.01
B2
0.00
0.92
0.92
0.92
PRIVGNN
0.08
0.45
0.15
0.72
0.80
Facebook
PATEM
0.03 =
0.00
0.37
0.38 0.03
PATEG
0.02 0.03
0.02
0.03
0.04 0.00
B1
0.69 0.001
0.69 = 0.01
0.69
0.01
0.01
0.09
B2
0.00
0.80
0.80 0.01
0.00
0.80
Table 6: Mean accuracy of varying the number of queries [Q]-
Amazon
Amazon2M
Reddit
Facebook
a/10
500
1000
500
1000
500
1000
500
1000
0.1
0.31
0.4
0.22
0.30
0.28
0.35
0.18
0.24
0.2
0.54
0.64
0.37
0.42
0.45
0.61
0.35
0.45
0.4
0.76
0.8
0.51
0.60
0.75
0.80
0.56
0.60
0.8
0.79
0.82
0.55
0.66
0.79
0.86
0.68
0.72
1.0
0.77
0.83
0.64
0.70
0.83
0.88
0.76 0.80
16

---

Published in Transactions on Machine Learning Research (06/2023)
B
Detailed Proof
Here, we provide missing theoretical details and the full proof of Theorem 7 In the following, we motivate the use of private data subsampling to achieve a reduction in the privacy budget. We use Theorem X in our analysis to bound the privacy budget (in the RDP framework) of our Poisson subsampled Laplacian mechanism.
B.1 Privacy Amplification by Subsampling
A commonly used approach privacy is subsampling in which the DP mechanism applied to the randomly selected sample from the data. Subsampling offers stronger privacy guarantee in that the one data point that differs between two neighboring datasets has decreased probability of appearing in the smaller sample. That is, when apply an (e,8)-DP mechanism to a random y-subset of the data, the entire procedure satisfies 76)-DP. The intuitive notion of amplifying privacy by subsampling is that the privacy guarantec of the DP mechanism is lighter by applying it to a small random subsample of records from a given dataset. This is also referred to as the subsampling lemma in the literature [alle et al. (2018). Under some restrictions on a, we can represent the combination of the subsampling lemma, and the tight advanced composition of RDP Wang et al. (2019) Zhu & Wang (2019) as: MoSample, (a) < (()))v((x)) In this paper, we apply the Poisson subsampled RDP -amplifffiatiion bound from Zhu & Wang (2019)
Theorem 8 (General upper bound Zhu & Wang (2019)) Let M be any mechanism that obeys (a,E(a))-RDP. Let y be the subsampling probability, then for integer a 2 2, the privacy budget is
MoPrissonSampieee S log (1 - (1-7)a-1(a7) + (1) (9) 72 (12)))=2))12
a (1 (f (e-1))))
+3
t=3
B.2 Proof of our Privacy Guarantee
Proof of Theorem 7 Our algorithm is composed of (i) sampling mechanism in which small sample of private data is used to train the private GNN model and (ii) Laplacian mechanism (with scale paramcter B), which is used to generate a noisy label for the public node (queried on corresponding private GNN).
First, note that as the L1 norm of the posterior bounded by 1, we add independent Laplacian noise to each posterior clement with scale 3 (Note that each postcrior element also bounded by 1). The computation of noisy label for each public query node is, therefore, 1/3-DP. The sequential composition Dwork al. (2006) over N queries will result in crude bound over the DP guarantee of our approach, namely N/8. To obtain tighter bound that takes the effect of the private data subsampling into account, we perform the transformation of the privacy variables using the RDP formula for the Laplacian mechanism for a >
1
log (( (2a-))
- 2a
(LAp(a)) a- 2a -
+
e
(3)
-
Moreover, the model uses only random sample of the data to select the nodes for training the private model. We, therefore, apply the tight advanced composition of Theorem to obtain an upper bound of EtAvoPois (a). To simplify the expression, we set a = in the corresponding bound and obtain
LApoPois (2) S log (1 72 +
(4)
Substituting (2) in equation we obtain
ELAPoPoI (2) = log 72 +2²
2 1/8
+ 3
e 2/8) -2118)
))
(5)
3
17

---

Published in Transactions on Machine Learning Research (06/2023)
Now applying the advanced composition for RDP (Lemma 6 for [Q] queries, get the upper bound on the total privacy loss of our approach at a =
E (2) - log 1 11 + 11= ea/B + -2/0 )
For any given 8 > 0, we use Lemma 5 and Eq. equation 1 to obtain the (e, 6)DD guarantee, Specifically for any 8 > 0 we obtain
log(1/6)
E(6) = min 0>
+ ePRNvoN(a -
(6)
Substituting 3 in the above obtain the stated upper bound, i.e.,
=(0) S log
1
+ |Q|log
11 1/8 _ 2/18 -1))
2/8
V8
3
thereby completing the proof.
C PrivGNN and Membership Inference Attacks
In addition to the theoretical guarantee of differential privacy, here, we empirically lest the robustness of PRIVGNN against membership inference (MI) attacks. In particular, we apply the attack of Olatunji et al. (201)) in two different settings. In the first setting (Attack-1), the goal of the adversary is to distinguish private nodes from public nodes. In contrast, in the second setting (Attack-2), the goal of the adversary is distinguish the public nodes which were privately labeled from the unlabeled public nodes.
Overall our two MI attacks consist of three phases: the training of shadow model, the training of an attack model, and the membership inference phase, which involves using the trained attack model to infer the membership status of any given query from the target (attacked) model. Tn summary, we first generate posteriors for the shadow dataset using the shadow model. This generated data is then used to train the allack model, which is a binary classifier that distinguishes between the training and non-training nodes. For more details about the MI attack, we refer the reader Olatunji et al. (2021) and their publicly available implementation.
In the following, describe our two allack variants and the corresponding results: Attack-1 aims at determining the private nodes (the original training data), and Attack-2 aims to determine the pseudo-labeled public nodes (the noisy training set for the public student model). For all the attacks, we select the student model with the largest À = 1, which corresponds to a lower privacy guarantee and the highest information leakage based on the achieved e as the target model.
C.1 Identifying Private Nodes via MI (Attack-1)
Here, we assume that the attacker does not know the training paradigm of the released student model but is aware of the architecture of the released model (target model). She wants infer the private nodes used for training from the dataset available her (for example, by some means, she was able to get hold of the Facebook social network). After training her attack model, the attacker queries the target model with nodes of interest and inputs her posteriors into her trained attack model to infer membership.
We compare the performance of the altack on a non-private model (B1) and PRIVGNN. As shown in Figure 4a in the non-private model, the attacker can accurately identify private nodes which were used training the target GNN model with high AUROC (> 0.75) on all datascts. However, the performance of that attack PRIvGNN reduced to random guess (5 0.54).
C.2
Identifying Private Nodes by Proxy via MI (Attack-2)
For this attack, we assume that the attacker knows that the released student model (target model) is trained using the knowledge distillation paradigm. Therefore, for such a strong attacker, her goal is to determine the
18

---

Published in Transactions on Machine Learning Research (06/2023)
B1
PrivGNN
B1
PrivGNN
0.8
0.8
AUROC
0.6
AUROC
0.6
0.4
0.4
0.2
0.2
0.0
0.0
Amazon
Arxiv Data
Reddit
Amazon
Arxiv Data
Reddit
(a) MI Attack-1.
(b) MI Attack-2.
Figure 4: Performance of MI Attack-1 and Attack-2 on PRIVGNN. B1 refers to the MI attack on the non-private GNN model.
public nodes that were privately labeled and used by PRIVGNN in training the target model from the other public nodes. The rationale is that if an attacker can confideully determine the public nodes that are privately (noisily) labeled, then it might reveal some information about the private dataset. For instance, consider an attacker that aware that PRIVGNN utilizes KNN in selecting the private nodes used in labeling a public node. If she determines such public node that was privately labeled, she might infer private information of up to K private nodes assuming that she has access the entire graph but does not know which is private public. Therefore, the private nodes are said to be identified by 'proxy'.
As shown in Figure 4b our PRIVGNN method reduces the MI attack to random guess achieving an AUROC of 0.40, 0.51, and 0.54 on the Amazon, ArXiv, and Reddit datasets, respectively, as compared to the non-private MI attack (corresponding to the MI attack on Bascline B1) with AUROC 0.82, 0.75, and 0.87. This is because of the two noise mechanisms that PRIVGNN adopts. Specifically, the random subsampling limits the private data used for the KNN procedure. Moreover, the knowledge transferred to the student model limited due to noisy pscudo-labels.
D Additional Experiments
D.1 Impact of Highly Informative Node Features
Here, two datasets, ArxiV and Credit, whose features already highly informative for the task. To verify this, we first train the datasets three-layer ML.P using only the features, and we obtained relatively high accuracy as compared to B2, which in addition uses the graph structure, as shown in Table 7
As shown in Figure 5 on both datasets, the performance of PATEM is on par with PRIVGNN. On the ArXiv dataset, we achieved a 15% decrease over PATEM (when
Table 7: MLP accuracy of Credit and ArXiv. B2 utilizes the GNN model
0.2). Note that the teacher models of PATEM are MLPs and do not utilize graph structure. The observed result is probably because the average node degree of ArXiv is very small (< 2). Thus, GNNs, which use the aggregation of the neighbors of a node to make predictions, might not benefit from such low-degree graphs. However, against PATEG, we achieved a 1169% improvement in performance which uses graph structure. Recall that PATEG teacher models are queried on graph data when they are trained like MLP (due to the low connectivity among training nodes), which explains its worse performance than PATEM. Moreover, the Credit dataset, the
Credit
ArXiv
MLP 0.78 B2
0.55
0.81
0.63
19

---

Published in Transactions on Machine Learning Research (06/2023)
privacy budget is very low, indicating high agreement among the teacher models in PATEM. We also observe that PATEG performs better this dataset which further supports our argument that the feature is highly informative as compared to the performance on other datasets in Figure 2 We will like to emphasize that the drop in the privacy budget of the Credit dataset as lcss noise is added is not surprising. This is due to the data-dependent analysis that PATEM utilizes (see Papernol el. al. (2016))
Arxiv
Credit
0.8 +
PrivGNN PATEM
Accuracy
0.6
0.4
PATEG
B1
0.2
B2
0.0
0.2
0.4
0.6 0.8 1.0 A
0.2 0.4 0. 0.8 1.0
(a) Accuracy vs. Noise (ox 1/x) injected to each query.
Arxiv
Credit
103
E10
PrivGNN
PATEM
101
PATEG
0.2 0.4 0.8... X
0.2 ...4..4. 0.8.6.66.... 0.20440.6..11.
A
(b) Privacy budget vs. Noise (x 1/x) injected to each query.
Figure 5: Privacy-utility analysis of the impact of highly informative node features. Here, |Q] is set to 1000. For PRIVGNN, y set to 0.3.
D.2 Effect of the Size of the Public Dataset
To investigate the effect of the size of the public dataset on the performance of PRIVGNN, we flip the public and private portions corresponding to different datasets. For instance, instead of having 2500 nodes in the private dataset shown for Amazon in Table II have 6000 nodes for the private dataset and 2500 for the public datasct. As shown in Figure 6. there are no significant differennees in the results of our model when there is a larger public dataset available (c.f Figure 2a). For fair comparison, we run all baselines, including PATEM and PATEG, on the flipped data. PRIVGNN outperforms all private baselines on the flipped datasets. As expected, the result of the non-private basclines (B1 and B2) are interchanged. We observe that our model is not sensitive the size of the private or public datasets. Therefore, our method is suitable in settings where the available private public data is large and in settings with limited private public dataset.
20

---

Published in Transactions on Machine Learning Research (06/2023)
Amazon
Arxiv
Reddit
0.8
PrivGNN-flip
Accuracy
PATEM-flip
0.6
PATEG-flip
0.4
B1
0.2
B2
0.0
0.2
0.4
0.6
0.8 1.0
0.2 0.4 0.6
0.8 1.0
0.2 0.4 0.6
0.8 1.0
A
A
Figure 6: Performance of different models after flipping the public and private datasets.
D.3 Real-world Scenario / Motivation
Our framework has range of applications in real-world scenarios where public and private graphs exist simultancously. One example of such a sccnario is the Wikidata (Vrandečié & Krötzsch 2014), which is a publicly available knowledge graph that is constructed using Wikipedia's content and can be easily downloaded. In contrast, the Google knowledge graph (Singhal 2012 (which is a superset of Wikidata) is a private knowledge graph that is not openly accessible to the public. The implementation details of the Google knowlodge graph are not officially documented, and the raw data is not available to anyone Ehrlinger & WöB (2016). The Google knowledge graph can only be accessed through an API, which provides black-box access. However, it's worth noting that the Google knowledge graph is partly based on the contents of Freebase, which was later acquired by Wikidata Pellissier Tanon et al. (2016). Therefore, both public and private graph data exist in real-world scenarios and can potentially be utilized by the owner of private data (in this case Google) to train and deploy a private GNN model.
Similarly, in finance, there may be sensitive financial information that needs to be kept private, but combining this information with public economic data can lead to valuable insights for investors and policymakers.
D.3.1 Application Example
One motivation for our approach is the practical content labeling problem Morrow et al. (2022 Saltz et al. (2021); ; Gao et al. (2018). Content labeling is form of content moderation where labels are assigned to each content. Content labeling helps deal with misinformation, conspiracy theories, and misleading content (disinformation) that may affect day-to-day activitics like voting, health behaviors, and promoting hate speech.
As an example, social network companies like Facebook have millions of (nodes) and connections(edgees) The profiles of some users are public and can be manually curated. For specific snapshot (a point in time), Facebook assigns attributes (e.g., labels) to a subset of the users based on their contents or activities on the social network to identify bots and real users to tackle disinformation. Furthermore, Facebook could release a content labeling model trained on their private data (e.g., as an API) without endangering the participants' privacy or releasing trade secrets.
If model trainod on private data, such as a content labeling model, released without any privacy protection, it could potentially violate intellectual property trade secrets as manually annolating/assia /assignninn attributes to data can be expensive. Moreover, such release could also put the privacy of participants enabling attacks like membership inference attacks. Therefore, it is crucial to have framework that combines both public and private information while accounting for the classic adversarial game where the adversary tries to recover private data from the model that is released publicly using data from a similar distribution, like a different snapshot of Facebook.
risk by
With tech companics competing to gain a competitive advantage through the use of advanced machine learning and artificial intelligence techniques, there is arms race to launch AT models trained their
21

---

Published in Transactions on Machine Learning Research (06/2023)
collected data. However, this has also raised concerns about the privacy of the individuals whose data is being used, well as the potential for misuse of the models by those who have access to them. Our approach has great potential to be adopted by such companies looking to balance the need for advanced machine learning tochniques with the need to protect the privacy of their users' data.
D.4 Joint Training of the Private and Public Graph
As an additional non-private baseline, conduct joint training on both the private and public graphs, which we refer to as baseline B3. A single GNN is trained on with all nodes in the private graph and the train nodes of the public graph. Note that all the edges of both the private and public graph are used for training. The model is evaluated on the test set of the public graph, which is the same test. set used for all experiments and basclinos.
Table 8: Porformance of all baselines including the joint training baseline (B3).
Data
B1
B2
B3
Amazon
0.88 + 0.02
0.91 + 0.02
0.93 = 0.02
Amazon2M
0.62 + 0.01
0.78 0.01
0.78 = 0.02
ArXiv
0.61 + 0.01
0.63 + 0.01
0.65 0.01
The results of the joint training (B3) and B2 are com- parable, as shown in Table g with some cases being the same. This joint training supports our hypothesis that the B2 accuracy is the "best possible" estimate of the graph performance (see Baselines in Section 4.1
Reddit
0.83 = 0.01
0.92 0.01
0.92 = 0.02
Facebook
0.69 + 0.01
0.80 = 0.01
0.83 0.02
Credit
0.81 + 0.01
0.81 0.01
0.81 = 0.01
D.5 Adding Noise Directly to the Groundtruth Label of Query Nodes
To further evaluate the performance of PRIVGNN against a noisy "oracle', we add Laplace noise directly to the groundtrthh label of each query nodes. We call this baseline B4. We note that this baseline is not feasible in our setting since the groundtruth label of the public model is not obtainable. Hence, noisy oracle. The procedure is as follows. We first represent the true groundtruth label of the query nodes as onc-hot encoded vector of all zeros except in the position of the groundtruth label. We then add Laplacian noise to the one-hot encoded vector. We set the negative values of the noisy label vector to zero and normalize the obtained vector. The normalized label vector for each query is then used in training the student model. We show the privacy-utility tradcoff of PRIVGNN and B4 in Table g The accuracy of B4 is not surprising since noise is directly added to the true groundtruth labels. On all datasets, the performance of B4 is similar slightly better than PRIVGNN. However, the extremely high privacy budget of B4 renders it useless. Such crude approach, although unrcalistic, can achieve higher performance but also at higher value of c.
D.6 Privacy-utility Tradeoff by Varying the Number of Queries
To observe the privacy-utility tradeoff based on the number of queries answered by the teacher model, we fix the value of noise parameter À 0.4 and vary number of queries in the range {1000, 500, 300, 200, 100, 10). Note that this experiment is an extended version of Section 5.3 in which we vary the number of answered queries from 500 to 1000. To visually observe the privacy-utility tradeoff at for different number of queries, we plot the accuracy on the left y-axis and the corresponding privacy in Figure 7 On all datasets, we observe that lower queries leads to lower accuracy and higher privacy guarantee (low epsilon). Furthermore, we obscrve a severe degradation in performance when the number of queries is below 400. Although the privacy guarantee is appealing but unsurprisingly the utility suffers because of noisy and limited training data used to train the public data.
D.7 Improving Performance via Pre-training
As shown in Section D.2. PRIVGNN is not sensitive to the size of the public or private data. However, in settings where a larger public dataset is available, we ask whether the student model can benefit from such large 'unlabeled' data. Therefore, we propose to leverage the abundance of the unlabeled dataset. by
22

---

Published in Transactions on Machine Learning Research (06/2023)
Table Privacy-utility tradeoff of PRIVGNN and B4 (adding noise directly to the groundtruth output). Note that B4 does not change with X.
0.1
0.2
0.4
0.8
1.0
PRIVGNN
0.40 + 0.08
0.64 + 0.07
0.80 + 0.13
0.82
0.17
0.83
0.10
AMAZON
ACCURACY
B4
0.42 + 0.05
0.63 + 0.04
0.82 + 0.03
0.84 + 0.05
0.85 + 0.07
PRIVGNN
3.90
8.53
19.81
55.3
81.23
100
200
300
400
500
PRIVGNN
0.30 + 0.05
0.42
+ 0.10
0.60
+ 0.18
0.66
+ 0.08
0.70
+ 0.19
ACCURACY
ZON2M
B4
0.32 + 0.04
0.46 = 0.05
0.63 + 0.07
0.68 + 0.04
0.77 + 0.02
AMA-
PRIVGNN
1.38
2.82
5.94
12.97
17.73
B4
100
200
300
400
500
PRIVGNN 0.26 +: 0.03
0.33
+: 0.02
0.43
+ 0.05
0.48
+ 0.04
0.52 + 0.05
ACCURACY
ARXIV
0.28 1. 0.02
0.38 + 0.01
0.46
0.03
0.51
0.02
0.54
0.04
PRIVGNN
4.45
9.69
22.11
57.60
83.53
B4
100
200
300
400
500
PRIVGNN 0.35 + 0.09
0.61
+ 0.18
0.80 + 0.10
0.86 + 0.13
0.88
0.07
ACCURACY
REDDIT
B4
0.35 + 0.04
0.63 + 0.03
0.82 + 0.04
0.87 + 0.02 0.88 + 0.03
PRIVGNN
3.90
8.53
19.81
55.3
81.23
100
200
300
400
500
PRIVGNN 0.24 + 0.08
0.45
+ 0.07
0.60
+ 0.15
0.72
+ 0.11
0.80 + 0.11
ACCURACY
B4
0.28 + 0.06
0.47 = 0.03
0.63 + 0.08
0.74 = 0.05
0.83 + 0.07
FACE- BOOK
PRIVGNN
3.90
8.53
19.81
55.3
81.23
B4
100
200
300
400
500
PRIVGNN 0.65 1: 0.02
0.70
+ 0.05
0.73
+: 0.05
0.78
1 0.04
0.80 +. 0.06
ACCURACY
CREDIT
0.65 1 0.01
0.71 +. 0.02
0.73
0.04
0.79
0.02
0.02
PRIvGNN
3.90
8.58
19.81
35.3
81.23
B4
100
200
300
400
500
23

---

Published in Transactions on Machine Learning Research (06/2023)
0.8
20
0.8
20
15
15
0.3
0.3
0.1
0.1
400
Queries
Queries
(a) Amazon
(b) Amazon2M
0.9
0.9
20
20
0.7
0.7
15
15
0.5
0.5
11
0.3
0.3
0.1
0.1
400
1000
1000
Queries
Queries
(c) ArXiv
(d) Reddit
0.9
0.9
20
-0
0.7
0.7
0.5
0.5
10
0.3
10
400
600
800
1000
200
400
600
1000
Queries
Queries
(e) Facebook
(f) Credit
Privacy-utility tradeoff for different values of [Q]. We fix A = 0.4 and y 0.3 for all datasets except for Amazon2M with = 0.1. The accuracy is represented by the red line on the left y-axis, while the achieved privacy is indicated by the blue line on the right y-axis. The markers on both lines correspond to the civvacy-utllity tradeoff for a specific number of queries.
Figure 7:
pre-training the student GNN model using unsupervised objectives on the public dataset. The unsupervised objective is based on the graph reconstruction objective Hamilton et al. (2017) which assigns similar embedding to connected nodes. After pre-training,
initialize the student model with the pre- rre-trained model and fine-tune the student model using the privately labeled nodes. We emphasize that the pre-training does not constitute any privacy risks since the data is public. One major advantage of unsupervised pre-training is that. it acts as a regularizer and provides belter generalization than randomly initializing the weights Erhan et al. (2010). We conducted a preliminary experiment on the Amazon2M and ArXiv datasets. As shown in Table 10 on smaller number of queries (?Q)=300), we obtain an increment of up 35% on Amazon2M and 17% on ArXiv over the randomly initialized PRIVGNN. We also observe up to 4% and 9% increase on higher number of queries ([Q)=1000) Amazon2M and ArXiv, respectively.
24

---

Published in Transactions on Machine Learning Research (06/2023)
As pointed out by Hu al. (2019) pre-training GNNs is still relatively difficult and may require domain expertise to carefully select examples that are well correlated to the downstream task to avoid "negative" transfer (hurt generalization). Therefore, we leave an in-depth study of how pre-training can help the better performance of PRIVGNN on more datasets as future work.
Table 10: Performance of pre-training the student model Amazon2M and ArXiv dataset. A indicates the % difference between PRIVGNN without pre-training and the pre-trained PRIVGNN (Pre-PRIvGNN))
IQ1
0.1
0.2
0.4
0.8
1.0
PRIVGNN
0.30
0.42
0.60
0.66
0.70
1000
PRE-PRIVGNN
0.31
0.44
0.61
0.68
0.72
AMAZON2M
3%
4%
2%
3%
3%
PRIVGNN
0.22
0.37
0.51
0.55
0.64
500
PRE-PRIVGNN
0.24
0.40
0.53
0.58
0.67
9%
8%
4%
5%
5%
PRIVGNN
0.12
0.19
0.28
0.34
0.36
300
PRE-PRIVGNN
0.17
0.22
0.30
0.36
0.43
35%
15%
7%
6%
18%
PRIVGNN
0.26
0.33
0.43
0.48
0.52
1000
PRE- PRIVGNN
0.28
0.36
0.47
0.51
0.54
A
7%
9%
9%
6%
4%
PRIVGNN
0.21
0.28
0.32
0.39
0.41
ARXIV
PRE-PRIVGNN
0.22
0.30
0.34
0.42
0.42
A
4%
7%
6%
7%
2%
PRIVGNN
0.10
0.16
0.30
0.34
0.36
300
PRE-PRIVGNN
0.12
0.19
0.34
0.37
0.40
A
18%
17%
12%
8%
11%
E Differences with Existing Works
The following section explicitly outlines the differences between our approach and existing works.
E.1 Differences with LPGNN Sajadmanesh & Gatica-Perez (2020)
In LPGNN, noise is directly added both the node features and the true labels via local DP. Therefore, their derived DP guarantee based the multi-bit mechanism that adds noise to the node features and randomized response mechanism that adds noise to the true labels. This makes LPGNN not directly comparable with the privacy guarantee of PRIVGNN. LPGNN primarily aims to achieve local differential privacy for individual node features whereas PRIVGNN focuses on the global differential privacy for the entire graph and the released GNN model.
E.2 Differences with VFGNN Zhou et al. (2020)
Although VFGNN assumnes that the computational graph of GNN is split into two where the private data- related computations are handled by the data holders, and the non- non-private data-related computations is handled by semi-honest server, their approach is largely disparate from PRIVGNN.
First, the initial embedding of the nodes of each data holder is computed by applying a secure multi-party computation (SMC) technique individually. Then, a local embedding is generated by aggregating the features of neighboring nodes, and either James-Stein Estimator Gaussian noise is added directly to the local embedding ensure DP. Finally, the local embedding is later combined for different data holders form a global node embedding.
25

---

Published in Transactions on Machine Learning Research (06/2023)
One possible modification to compare the performance of VFGNN with PRIVGNN is to remove the SMC technique, which is the key strength of their privacy framework, and obtain the local embedding without this cryptographic measure. However, this modification has a major drawback as it requires adding Gaussian noise directly to the local embedding to guarantee local differential privacy, which is not as strong as the privacy guarantee of PRIVGNN. Therefore, it not. feasible to make a fair comparison wet the two methods.
E.3 Differences with FedGNN Wu et al. (2021)
The FedGNN framework relies on each data holder possessing a complete dataset consisting of nodes, edges, and labels. The first step in FedGNN involves training local GNNs with the original data and correct labels for each data holder to obtain local gradients. To ensure differential privacy, noise is added to the local gradients. FedGNN adopts horizontal federated learning approach, where parties collaborate on the same task while retaining their data locally.
On the other hand, PRIVGNN cannot carry out local training as the public graph does not contain the nccessary labels for computing local GNN. Additionally, the DP guarantees of FedGNN are achieved by adding noise directly to the local gradient of each local GNN, which is not feasible in PRIVGNN.
E.4 Differences with SAPGNN Shan et al. 2001
SAPGNN, like FedGNN, generates local embeddings for each data holder and updates global model by combining all local embeddings. However, SAPGNN ensures privacy using an n-out-of-n secret sharing mechanism to update local model weights. Each data holder secretly shares their local gradient with the others, adds up the shares, and reconstructs the entire gradient by gathering the aggregated results from others. The use cut layer ensures that raw data is only involved in local computations and will not accessible to others, guaranteeing data privacy. Thus, comparing PRIVGNN with SAPGNN not feasible.
E.5 Differences with HETERORR Tran et al. (2022)
HETERORR adopts a similar approach to the previous works above by incorporating noise addition mechanism using randomized response to perturb the node features and graph structure directly. The original dataset is discarded, and only the noisy data is employed for training. As a result, HETERORR relies on node-level local DP and edge-level local DP guarantees, Thus, the privacy guarantees of PRIVGNN cannot be compared.
E.6 Differences with GAP Sajadmanesh et al. (2022)
The approach employed by GAP involves obtaining lower-dimensional node features independent of the graph structure and preserving the privacy of the node features by applying DP-SGD in the case of node-level privacy, followed by the addition of Gaussian noise to the multi-hop aggregated node embeddings. During the encoding phase of GAP, node features and labels are required to compute the embedding, which differs from PRIvGNN where not all node features and labels are available. Moreover, the GAP framework also requires both the node labels, non-aggregated node embeddings (output of the encoder module), and the aggregated embeddings to train the classification module. It should be noted that the public data of PRIVGNN does not have any labels. Therefore, GAP and PRIVGNN cannot. be compared due the differences in their data requirements.
However, just to consider the possibility or to explore the idea of comparison, can present rough comparison as use the same Amazon dataset (Amazon2M in PRIVGNN). According to Figure (right) of the GAP paper, at an value of 16, GAP achieved 78% accuracy while PRIVGNN achieved comparable accuracy of 70% al a similar e. It should be noted that the Amazon dataset used in GAP has been preprocessed to include nodes with the top 10 classes, providing high-quality data for training, whereas PRIVGNN uses the default dataset with 47 classes. Additionally, PRIVGNN used only 1000 labeled nodes (querics) for training the released model, while GAP used 1.3 million labeled nodes for training. is essential to emphasize that this comparison is not reasonable due to the differences in the experimental settings, but it provides idea.
26

---

Published in Transactions on Machine Learning Research (06/2023)
E.7 Differences with Zhang et al. (2022)
The paper employs the approximale personalized PageRank (APPR) to protect graph topology information, by either adding Gaussian noise or applying the exponential mechanism to output the top-K relevant neighbors for computing the node feature aggregation. They replace the message passing algorithm of a standard GNN model with APPR. and train the modified model using DPSGD. However, their approach cannot be directly compared with PRIVGNN for several reasons. Firstly, their method of using DPSGD not applicable to current of-ate-f-thh-art GNN models that are based on the message passing algorithm as DPSGD assumes data independence, a condition violated for graphs. Secondly, their privacy guaranlee is somewhat unclear. The authors themselves cannot represent the overall epsilon, which is combination of epr and Esgd, result, they kept one fixed and the other variable. To compare the two methods fairly, one could naively fix the value of K, Epr: and Eagd of their approach against the epsilon at lambda-0.4 of PRIVGNN. However, such a comparison would lack a fair basis.
E.8 Differences with Daigavane et al. (2021)
The paper, like Zhang et al. 2022 mentioned earlier, employs DPSGD to ensure privacy during GNN training. Also, their privacy guarantees are limited to 1-layer GNN, which renders comparison infeasible. Besides, as the authors note, if an r-layer GNN is employed, then during inference for a node U, the features of all other nodes in the entire r-layer neighborhood of U must be available non-privately. That is, to perform inference on a node U multi-layer GNN, one needs access the features of all nodes up to r-layers which are not achievable in our setting. More precisely, their method is not equipped to deal with the inductive scenario where there exist two separate graphs that do not intersect, which is the in the framework of PRIVGNN.
neighborhood
F Datasets
In the following, we describe the datasets used in this work.
Amazon. We use the Amazon Computers dataset Shehur et al. 2018 which is subset of the Amazon co-purchase graph McAuley et al. (2015). The nodes represent products, and the node features are product The edges indicate that two products are frequently bought together,
reviews represented as bag-of-worde while class labels are the product categories. We created the private graph on 2500 nodes and used 3000 nodes each for the public train and test sets. The task for this dataset is to assign products to their respective product category.
Amazon2M. The Amazon2M dataset Chiang al. (2019) the largest Amazon co-purchasing network where each node is product, and the features are extracted via rag-of-words on the product description. Edges represent whether two products are purchased together. It consists of over 2 million nodes. Hence, Amazon2M. We created a private graph on million nodes and a public graph on the remaining nodes.
Reddit. The Reddit dataset Hamilton et al. (017) represents the post-to-post interactions of a user. An edge between two posts indicates that the samn user commented on both posts. The labels correspond to the community of post. We randomly sampled 300 nodes from each class for the private graph and selected 15000 nodes each for the public train and public test nodes, respectively.
Facebook. The Facebook dataset Traud et al. (0122) is anonymized Facebook social network of users from 100 American institutions. We utilized the social network among UTUC students where the task is to predict their class year. The nodes represent Facebook users(studentss), and the edges indicate friendship. The private graph is constructed over half the nodes and the public graph on the other half.
ArXiv.
The ArXiv datasct Hu et al. (2020) paper and edges represent that a paper cites the other. The node feature is a 128-dimensional feature vector obtained by averaging the embedding of words in the title and abstract of each paper. Our private graph is
citation network where each node represents an arXiv
27

---

Published in Transactions on Machine Learning Research (06/2023)
created from 90941 papers published until 2017. We used 48603 papers published in 2018 and 29799 papers published since 2019 for our public train nodes and test nodes, respectively.
Credit. The Credit defaulter graph Agarwal et al. (2021) is a financial network where nodes are individuals and edges exist between individuals based on the similarity of their spending and payment pattern. The task is to determine whether individual will default their credit card payment. The private and public graphs consist of 10000 and 15000 nodes, respectively.
We remark that irrespective of the size of the public data, we only pseudo-label very small number of query nodes (in our experiments, the maximum query size was 1000) of the public graph to train the student model.
Data Statistics. [V] and |E] denote the number of vertices and edges in the corresponding graph dataset. deg is the average degree of the graph. We select 50% of Amazon, Amazon2M, Reddit and Credit, 40% of ArXiv, and 20% of the Facebook dataset as the test set from the public graph.
Table 11:
Private
Public
#class
|X]
|Vt
|ET]
deg
[V]
[
deg
Amazon
10
767
2500
11595
4.64
6000
37171
6.20
M
47
100
1M
12.7M
12.73
1.4M
21.8M
15.08
Reddit
41
602
12300
266148
21.64
30000
876846
29.23
Facebook
34
501
13401
270992
20.22
13402
266141
24.82
ArXiv
40
128
90941
187419
2.06
78402
107900
1.38
Credit
2
13
10818
185916
17.19
15000
361093
24.07
G Baselines
Non-Private Inductive Baseline (B1). In the non-private inductive baseline, train single GNN model on all private data and test the performance of the model on the test set of the public data. This corresponds to releasing the model trained on complete private data without any privacy guarantees.
Non-Private Transductive Baseline (B2). This non-private baseline estimates the "best possible" performance on the public data. Specifically, a GNN model trained using the training set (50% of the public data for Amazon, Amazon2M, Reddit, and Credit, 60% of ArXiv, and 80% of the Facebook dataset) and their corresponding ground truth labels in a transductive setting. We then test the model the test set (the remaining 50% of the public data for Amazon, Amazon2M, Reddit, and Credit, and 40% of ArXiv and 20% of the Facebook dataset).
PATE. We adopt the PATE framework Papernot et al. (016) where the private node-set is partitioned into n disjoint subsets of nodes. Then we train GNN models (teacher models) on each dataset (the corresponding induced graph) separately. We query each of the teacher models with nodes from the public domain and aggregate the prediction of all teacher models based on their label counts. Then, independent random noise is added to each of the vote counts. The obtained noisy label is then used in training the student model, which is later released. We call this PATEG. We also used multilayer perceptron (MLP) instead of GNN models for training on the disjoint node subset of the private graph. We denote the ML. approach as PATEM. Note that only the features (no edge information) will be used for training teacher models in PATEM. Our choice of n was experimentally chosen. We observe that n > 20 for the Amazon, Facebook, Credit, and Reddit datasets and n > 50 for the ArXiv lead to extremely small data in each partition and low accuracy. We also set = 50 for Amazon2M.
G.1 Model and Hyperparameter Setup
For each of the private (teacher) (#f) and public (student) (.) GNN models, we used two-layer GraphSAGE model Hamilton et al. (2017) with hidden dimension of 64 and ReLU activation function. We applied batch normal normalization to the output of the first layer. We applied dropout of 0.5 and learning rate of 0.01. For
28

---

Published in Transactions on Machine Learning Research (06/2023)
the multilayer perceptron model (MLP) used in PATEM, we used three fully connected layers and ReLU activation layers. We trained all models for 200 epochs using the negative log-likelihood loss function for node classification with the Adam optimizer. All our experiments were conducted for 10 different instantiations using PyTorch Geometric library Fey & Lenssen (2019) and Python3 on 11GB GeForce GTX 1080 Ti GPU.
The Runtime and Space Requirement of PRIVGNN
We remark that the runtime and space requirements of our proposed PRIVGNN are on par or even less than that other private models like PATE. Importantly, since the user only exposed to the public model, we point out that the time and space requirements of the released model are the same that of the corresponding non-private GNN models.
For the training time, we train Q models corresponding to Q queries. As shown in Figure we can decrease Q to 500 (equivalent to training 500 teacher models). The runtime of PRIVGNN can be further reduced by parallel training of models. Note that the original PATE trains a sufficiently large number of teacher models to achieve a reasonable privacy-aceuracy trade-off. For instance, on the Glyph dataset (See Table of Papernot et al. (018)), PATE trained 5000 teacher models. With our requirement of teacher models, PRIVGNT faster or better than PATE terms of time and space requirements.
much smaller number
The space requirement of PRIVGNN is the same as the space requirements of GNN model because need not save the trained teacher model after qucrying them once with the qucry nodes. Therefore, they be discarded after training which leads to no significant space overhead. For PATE, on the other hand, all teacher models are required to answer each query leading to its higher space requirements.
Limitations and Future Works
Query reduction. As observed in the experiments, fewer queries significantly reduced the overall privacy budget e. However, this has a relative effect on the accuracy of the released model. Hence, a more sophisticated active learning approach or unsupervised methods for query reduction that can achieve a high accuracy are worth exploring.
Analysing PrivGnn's behavior. The use of explanation methods to analyze the properties of the learned representation of the PRIVGNN is desirable. This analysis will help understand the internal workings of private models and compare the representations of private and non- non-private models.
29


Reviews:
[{"review_id": "7r4qLTl03l", "reviewer": "Reviewer_v6ag", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n+ The research topic is significant.\n+ The empirical results look promising.\n\nWeaknesses\nThere are many significant concerns regarding the proposed approach, as follows:\n\n- The most critical concern is the correctness of the proposed approach. The paper does not discuss the level of privacy protection offered by PrivGNN, i.e., node-level protection or edge-level protection. The paper appears to focus on node-level protection reflected through the node-level membership inference attack evaluation in Appendix C. However, that raises the question about the definition (1) neighboring induced graphs? and (2) GNN model sensitivity given neighboring induced graphs, especially given the k-nearest-neighbors of a particular node. There is no proof that the induced subgraph preserves DP. Removing one node in the induced subgraph can significantly change all other nodes' posterior (prediction). How does  PrivGNN upper-bound this sensitivity to provide DP protection? The proof is shallow and does not help justify the DP protection level (even the proofs in Appendices). For instance, if a node has many connections compared with other nodes, it will have a higher probability of appearing in more induced subgraphs given the same number of queries. In addition, there is no protection for the nodes’ features and the private labels. That can significantly affect both node-level and edge-level privacy protection of the proposed approach. \n\n- The advantages of the proposed approach are not well justified, especially in comparison with PATE. Using only one induced subgraph to return the noisy posterior labels for a specific query should not provide better model utility than using several teacher models as in PATE. What is the missing ingredient making PrivGNN so effective? \n\n- The setting is impractical. The privacy budget is heavily affected by the number of queries. That means an end-user can only submit a limited number of queries and must know the number of queries |Q| in advance. This is impractical in real-world applications. In addition, this is problematic since an adversary can pretend to be multiple different end-users to submit a sufficient number of queries to destroy the privacy protection offered by the proposed approach completely. \n\n- Experimental results are unconvincing. Critical baselines are missing, which depends on the theoretical correctness of the proposed approaches (which level of privacy protection). For instance, [1-4] and more. In addition, experiments must reflect a practical setting between the service provider against the adversary, given varying factors, including the number of queries and k-nearest neighbors. Why k-nearest neighbors in comparison with other measures? Why Laplace mechanism in protecting the posterior labels? Any other methods, such as Label-DP?\n\n[1] Towards Training Graph Neural Networks with Node-Level Differential Privacy. 2022\n\n[2] Heterogeneous Randomized Response for Differential Privacy in Graph Neural Networks. 2022\n\n[3] Node-level differentially private graph neural networks. 2021\n\n[4] Gap: Differentially Private Graph Neural Networks with Aggregation Perturbation. 2022\n\n- The presentation must be improved. Section 3.1.4 can be moved to the Appendix to reserve space for justifying the proposed approach's correctness, advantages, and novelty. A clear threat model is needed. Also, focusing on shedding light on understanding these factors rather than “reporting” the results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposed an approach to train GNN models with differential privacy based on the setting of teachers and students (PATE). The proposed approach, PrivGNN, includes three main steps: (1) Use Poisson sampling to select a random subset of nodes, which is used to induce a subgraph by gathering all k-nearest neighbors of the selected nodes. Train teacher GNNs based on the induced subgraphs and private labels; (2) Compute noisy posterior labels using the Laplace mechanism; and (3) Train student models using the noisy posterior labels. Experimental results were conducted on several datasets in comparison with several baseline models. The results show that the proposed PrivGNN achieves better accuracy – privacy trade-offs compared with the baselines. In addition, PrivGNN further reduced the performance of membership inference attacks.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address all comments.", "broader_impact_concerns": "The setting is incorrect and impractical.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "VACxP9CTHS", "reviewer": "Reviewer_3G6U", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Conditional on accepting the proposed setting, the approach is well motivated. The paper is well written, well organized, and easy to follow. The authors do a good job of supporting all of their claims with solid theoretical and experimental evidence. The ablation study is well executed and convincingly shows that all introduced components are necessary. The baselines are reasonable (additional baselines can be helpful see requested changes). The addition of the membership inference attacks is appreciated.\n\nOne weakness of the approach is in the setting itself since it implicitly assumes that *all* information (features and structure) about *all* test nodes is public. That is, the privacy of the test nodes is not protected at all. This scenario seems quite narrow. For example, while it might be reasonable that a given node $v$ knows the information about its neighbors (e.g. I know information about my friends in a social network), this approach assumes that everyone in the graph knows the features and neighbors of everyone else. It would be helpful if the authors can talk about in more detail the real-world settings where their approach would be useful.\n\nRelatedly, a second weakness of the approach is that the empirical results are likely too optimistic due to the experimental setup. Namely, the public and private graph are artificially constructed from the same original graph. In most applications it does not seem realistic that the private and public graph are essentially \"the same\". Can you specify a real-world scenario where roughly half of the graph is public and the other half is private? For example, in a social network, all users need to have their privacy protected.\n\nAn important oversight of the current manuscript is that it is not explicitly stated exactly what is protected with differential privacy. In general, in DP we have two neighboring inputs $X$ and $X'$ where the neighboring relation are defined depending on the context. For example $X$ and $X'$ can be two datasets that differ in one instance. In the DP+Graphs literature there are usually two notions of neighboring graphs that lead to node-level DP if $G$ and $G'$ differ in one node, or edge-level DP if they differ in one edge. The author should clearly state what is the neighboring relation that they consider. Relatedly, the use the worst possible bound on the L1 norm of the difference in predictions for the teacher. Depending on the definition of neighboring graph this can be quite pessimistic.\n\nMinor:\n- It would be helpful to add more details on the membership attack. Currently it's hard to judge the strength of the attacker.\n- In the statement \"In addition, the current legal data protection policies highlight a compelling  need to develop privacy-preserving GNNs\" which policies are you referring to?\n- In \"form batches and lots\", the definition of \"lots\" is not clear\n- In paragraph 2 of section 5.2 there is an extra empty line\n- While it's true that the Binomial converges to the Poisson it is not clear why this is relevant in this setting. The sampling that is performed is IID Bernoulli (or equivalently Binomial), so why is it called Poisson sampling? Does the amplification theory require Poisson sampling, and if yes what does this mean for the guarantee?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose a paradigm for training GNN models with differential privacy guarantee in the specific scenario where we have a private labeled graph (the teacher) and a public unlabeled graph (the student), and the goal is to release a model that can give predictions for the public graph. The main idea is to obtain noisy labels from a teacher (trained on private data) for a small number of query nodes and use them to train a public model on the public graph. To obtain DP guarantees Laplace noise is added to the teacher predictions. To amplify the privacy budget sub-sampling is used. Simple membership inference attacks are performed as a sanity check.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The following additional baselines might be helpful to better compare the trade-offs of the proposed model:\n- Train a single GNN on the *joint* public and private graph (i.e. the original dateset), importantly, this would include the cross-edges between the public and private components of the graph\n- To validate the usefulness of the teacher the authors should compare to a private baseline where Laplace noise is added directly to the ground-truth labels of the query nodes\n- While some of the mentioned related works are indeed designed for a distributed setting, in principle they can be also applied (maybe with small modifications) in the same setting as PrivGNN. Are there any arguments for not comparing with them? How does the proposed approach compare to methods for computing private node embeddings? \n\nThis is a minor question, but it would be interesting to study the performance when using different models for the private GNN and public GNN.", "broader_impact_concerns": "There are no specific concerns that I want to raise. However, given that the paper proposes an approach for preserving privacy I would encourage the authors to further highlight the limitations of their approach, and specifically discuss what kind of privacy protection is or is not offered by their approach, as well as the limitations of DP in general. Moreover, a discussion of how to interpreted the guarantees, e.g. what a given value of $\\epsilon$ means would be useful. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "pYNTJJMmyh", "reviewer": "Reviewer_cD6a", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The proposed method seems novel to me. While the privacy method is comprised of multiple parts, the combination seems clever to me. \n* Extensive empirical evaluation for the proposed method. Authors consider several interesting research question in the experiments that provide solid ground for understanding how the method is affected by various hyperparameters.\n\nWeaknesses:\n* While the empirical evaluation covers many important questions, I think the results could be presented better. In the current form, different parameter settings tend to lead to different privacy parameters and different accuracies. Now it is really difficult to compare the setting while both of these vary. I would suggest authors to for example keep the $\\epsilon$ fixed and report the accuracies obtained using different settings.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a novel method for learning Graph Neural Networks (GNN) under DP. The solution is based on PATE like framework, where the teachers are trained with private data to provide labels for previously unlabelled public data set to the student through noisy channel. The student then trains their model using the public features and the teacher provided noisy labels. However, compared to the standard PATE framework, authors suggest a subsampled method that avoids the data set splitting that is usually required for the PATE teacher training, and also improves the privacy budget through subsampling amplification. In the empirical evaluation, the method is shown to reach non-private classification accuracy with $\\epsilon \\approx 6$ for the Amazon2M data set. The method is shown to beat a private baseline of using the standard PATE framework.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Recommendations and questions:\n* In the \"Differences with Existing Works\", you mention that in prior work either the graph structure or part of the nodes are assumed to be public, and in contrast your work treats the \"whole graph\" as private. However, you do need the public feature set for your training right? If that is the case, I would think that this difference to earlier work should be clarified.\n* Currently only the average accuracy is reported. I would suggest authors to also report the variability across the repeats to assess how robust the method is.\n* Can you explain the intuition behind PrivGNN outperforming B1?\n* \"we conclude that the value of the hyperparameter K should be chosen based on the average degree of the graph\", is the average degree of the graphs discussed somewhere? It would be nice to know those in order to evaluate this conclusion.\n* Section 5.3: I find the conclusion of smaller $Q$ being better rather intuitive. However, it would be really interesting to see how small can you go before you start to get worse the privacy-utility trade-offs. So maybe you could plot Accuracy for several Q's while keeping the $\\epsilon$ fixed.\n* Table 3 would be much easier to interpret if you would keep the $\\epsilon$ fixed between the $\\gamma=0.1$ and $\\gamma=0.3$ cases.\n\nMinor things:\n* Alg. 1, Step 5: The $(v)$ in subscript of $V^\\dagger_{KNN}$ is inconsistent with the notation of previous step. Or maybe there is some difference that is not clear to me. It also seems to happen again in Section 3.1.1.\n* \"The mechanism is equivalent to the “sampling without replacement” scheme with\": this is bit unclear if you don't say that $m$ is the batch size\n* It seems that you have $m$ in the Input for Alg. 1, but I'm not sure if it is ever used.\n* Might be worth mentioning that the GNN $\\Phi^\\dagger$ returns a probability vector (just so that the l1-sensitivity of 1 is clear).\n* There is a weird looking line break in the 2nd paragraph of Section 5.2\n* Maybe a typo: \"is slightly higher with only 6% decrease\"\n\n", "broader_impact_concerns": "I don't think the paper raises broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: During the discussion period, the authors provided convincing replies and a revised version of their manuscript addressing the reviewers' requests. One reviewer remained unresponsive during the discussion period, but I consider that the authors clarified the key points and appropriately addressed the raised concerns. In light of the discussion, the other two reviewers support acceptance. I believe that this work is an interesting addition to the private GNN literature, and also recommend acceptance.

That being said, an important part of the discussion revolved around the positioning and comparison to prior work on private GNNs. The authors provided some clarifications, and incorporated additional references and discussion in Appendix E. However, in the current version, this appendix is not referenced in the main text and contains imprecise statements, such as "One major difference between PrivGnn and existing works is that other methods rely on local DP for privacy guarantees, PrivGNN utilizes global DP to protect the privacy of the entire dataset", which not hold e.g. for Sajadmanesh et al. (2022). On the other hand, the related work section of the main text (Section 2) misses key references.

Therefore, the authors are asked to make a minor revision of their manuscript with the following changes:
- Incorporate the references from Appendix E into Section 2 and update the section accordingly. Detailed discussions can be kept in Appendix E, with a reference to it in Section 2.
- Update imprecise statements that are still present in Section 2 and Appendix E (such as the one mentioned above).
- Make the setting considered in this paper (public unlabeled graph + partial access to private labeled graph) more explicit in the abstract and in the intro, as this is an important element that makes the approach different from some of the prior work.


Decision: Accept (poster)