Node-Level Differentially Private Graph Neural Networks
Authors: Ameya Daigavane
Gagan Madan
Aditya Sinha
Abhradeep Guha Thakurta
Gaurav Aggarwal
Prateek Jain
Venue: ICLR 2022 Submitted (2022)
Keywords: differential privacy
graph neural networks
node-level privacy

Abstract: Graph neural networks (GNNs) are a popular technique for modelling graph-structured data that compute node-level predictions via aggregation of information from the local neighborhood of each node. However, this aggregation implies increased risk of revealing sensitive information, as a node can participate in the inference for multiple nodes. This implies that standard privacy preserving machine learning techniques like differentially private stochastic gradient descent (DP-SGD) – which are designed for situations where each node/data point participate in inference of one point only – either do not apply or lead to inaccurate solutions. In this work, we formally define the problem of learning 1-layer GNNs with node-level privacy, and provide a method for the problem with a strong differential privacy guarantee. Even though each node can be involved in the inference for multiple nodes, by employing a careful sensitivity analysis and a non-trivial extension of the privacy-by-amplification technique, our method is able to provide accurate solutions with solid privacy parameters. Empirical evaluation on standard benchmarks demonstrates that our method is indeed able to learn accurate privacy preserving GNNs, while still outperforming standard non-private methods that completely ignore graph information.

Under review as a conference paper at ICLR 2022
NOVE-LEVEL DIFFERENTIALLY PRIVATE NEURAL NETWORKS
GRAPH
Anonymous authors Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) are popular technique for modelling graph- structured data that compute node-level representations via aggregation of infor- mation from the local neighborhood of each node. However, this aggregation implies increased risk of revealing sensitive information, as node can participate in the inference for multiple nodes. This implies that standard privacy preserv- ing machine learning techniques, such as differentially private stochastic gradi- ent descent (DP-SGD) which are designed for situations where each data point participates in the inference for one point only either do not apply, or lead to inaccurate solutions. In this work, we formally define the problem of learning I-layer GNNs with node-level privacy, and provide an algorithmic solution with a strong differential privacy guarantee. Even though each node can be involved in the inference for multiple nodes, by employing a careful sensitivity analysis and non-trivial extension of the privacy-by by-mmliification technique, our method is able to provide accurate solutions with solid privacy parameters. Empirical evalu- ation on standard benchmarks demonstrates that our method is indeed able learn accurate privacy preserving GNNs, while still outperforming standard non- poniriivate methods that completely ignore graph information.
INTRODUCTION
Graph Neural Networks (GNNs) are powerful modeling tools that capture structural information provided by a graph. Consequently, they have become popular a wide array of domains such biology (Ktena al. 20188), medicine AAissit-Arittizaaall et al.) (021), chemistry (McCloskey
et al.
2019). computer vision (Wang et al. 2019). and text classification Yao et al. 2019).
GNNs allow aggregation of data from the neighbors of given node in the graph, thus evading the challenge of data searcity per node. Naturally, such solutions are quite attractive in modeling users- each node of the graph is represented by the user and the connections represent interactions between the users - for a variety of recommendatiio//aakinn tasks, where it is challenging to obtain and store
user data (Fan al. 2019 Budhiraja et al. 2020 Levy al. 202T).
However, such solutions are challenging to deploy as they are susceptible to leaking highly sensitive private information about the users. It is well-known that standard ML models without GNN style data aggregation can leak highly sensitive information about the training data (Carlini et al., 2019). The risk of leakage is significantly higher in GNNs as each prediction based on not just the individual node, but also an aggregation of data from the neighborhood of the given node. In fact, there are two types of highly-sensitive information about an individual node that can be leaked: a) the features associated with each node/user, b) the connectivity information of individual node/user.
In this work, we study the problem of designing algorithms to learn GNNs while preserving node- level privacy, i.c.. preserving both the features well as connectivity information of an individual node. We use differential privacy as the notion of privacy (Dwork et al., (2066) of a node, which roughly-speaking requires that the algorithm should leam similar GNNs despite perturbation of an entire node and all the data points or predictions associated with that node.
Example scenarios for such solution include ranking/rcommnendttion of entities like docu- ments/emails in an organization. Here, the graph can be formed by a variety of means like how users interact with each other, and the goal would be to learn user features that can enable more

---

Under review as a conference paper at ICLR 2022
accurate ranking of emails/documents. Naturally, user interaction data well individual users' features (like the topics in which user is interested in) would be critical to preserve, and any reve- lation of such data can be catastrophic. Furthermore, once GNNs are learned to model users while preserving privacy, they can be used in different settings hased on the problem requirement. For ex- ample, in settings where node can access it's r-hop neighbors data, GNNs (if they are trained with DP). Similarly, in certain scenarios, we would want to learn GNNs over a large enterprise and deploy the same model for small enterprise, where inference time neighborhood information (like managerial reporting structure) might be publicly accessible within the enterprise but not across enterprises. See Section 4 for a detailed discussion.
directly apply r-layer
Recent works have explored the problem of differentially private learning of GNNs, but they either consider a restricted setting of edge-level privacy which often insufficient for real-world problems or they restrict themselves to simpler settings like bipartite graphs or node-level privacy without
preserving individual connectivity information (Wu et al. 2021a b Zhou et al. 2020).
In contrast, our proposed method preserves the privacy of the features of each node ('user'), their labels as well as their connectivity information. To this end, we adapt the standard DP-SGD method (Song et al. 2013 Basssiy et al. 2014] Abadi et al. (0166) to our setting. But, analysis of the standard DP-SGD method does not directly extend to GNNs, as each gradient term in GNNs can depend on multiple nodes. The key technical contribution of our work is two-fold: i) we provide careful sensitivity analysis for the special case of 1-layer GNNs, ii) we extend the standard privacy by amplification technique to GNNs where one gradient term can depend multiple users. Note that the standard privacy by amplification method only applies to scenarios where each point corresponds one user/entity. By combining the above two results with the standard Rényi Differential Privacy (RDP) accounting, we obtain formal proof of privacy for our method.
Finally, we evaluate our DP-GNN method on standard benchmarks. We demonstrate that DP-GNN is reasonably accurate compared to the standard I-layer GCN models, while providing privacy pa- rameters of about < 30 which are close the industry standard. More critically, compared to stan- dard MLP (multi-layer perceptron) based methods that completely discard graph side-information, our method can be 5-6% more accurate while still providing strong privacy guarantees. That is, demonstrate that GNN based techniques can indeed be deployed in practice with the benefits of improved accuracy over vanilla MLP style methods while still preserving sensitive user data.
Contributions: We propose Node-Level Differentially Private Graph Neural Network that works well in practice and provides formal privacy guarantees. This is the first work, to the best of our knowledge, to provide such strong privacy guarantees for each individual node in the graph learning regime. Our main contributions are organised as follows:
we formalize the problem of node-level differentially private GNNs, and discuss various important settings in which a solution to the problem is applicable.
Formulation: In Section 3,
Method:
In Section 4 we describe our algorithm that adapts standard DP-SGD to train differen- tially private GNNs, with a strong privacy guarantee that extends standard privacy amplification by sampling.
we evaluate our framework on multiple benchmark graph datasets on the task of node classifiation.. We demonstrate that our DP-GNN method can outper- form non- pon-piivate and private MLP methods that cannot utilize graph information.
Empirical Evaluation: In Seccionn 5
2 RELATED WORK
Mechanisms to make the training process of machine learning models private primarily fall into two categories: model-agnostic methods such as PATE (Papernot et al., (017), and model-aware methods such DP-SGD (Abadi et al.) 2016). which augment the standard paradigm of gradient- based training to be differentially private. DP-SGD, in particular, has been used successfully to train neural network models to classify images (Abadi al. 2016) and text (Anil et al. 2021
Today, there are many varieties of graph neural networks employed: Graph Convolutional Neural Networks (Kipf & Welling 2016), Graph Attention Networks (Veličković al. 2018), GraphSAGE (Hamilton et al. 2017), and Message-Passen Neural Networks (Gilmer et al.] 2017), to name a few. Broadly, these models compute node-level representations via aggregation of neighbourhood-level
2

---

Under review as a conference paper at ICLR 2022
information, that can lead to diffusion of private information across multiple nodes, thus making application of standard DP-SGD like techniques non-trivial.
There has been recent work in learning and evaluating edge-level private GNNs (Wu et al. 202 but they do not preserve node-level data. Private GNNs have also been studied from the perspective of local privacy (Sajadmanesh & Gateca-Perez 2020), where each node performs its share of the
GNN computation locally. In such a setting, each node sends noisy versions of its features and labels neighbouring nodes in order to learn shared weights, resulting in a elaborate learning algorithm that needs to correct for the bias in both the features and labels. (Wu et al. (021a) utilizes private GNNs for recommendation systems, but their method assumes a bipartite graph structure, and cannot naturally handle homogeneous graphs. Other approaches employ federated learning (Zhou et al.) 2020), but only guarantee that the GNN neighbourhood aggregation step is differentially private, which is insufficient to guarantee privacy of each node's ' neighborhood. Finally, other attempts GNNs exist, but these do not use the formal notion
(Shan et al. 2021) create of DP.
Model-agnostic methods, such as PATE, have recently been investigated to train GNNs (Olatunji et al. 2021]. In their current form, however, such methods require access to public data samples, which may not always be available for the task at hand.
In contrast to previous approaches which protect the privacy of node's features and labels only, additionally seek to protect every node's adjacency vector, which is its private list of connections to neighbouring nodes. This is because the existence of communication between pair of nodes can often be sensitive information in itself. Further, our approach extends the standard approaches of gradient-based training scalably train node-level differentially private GNNs in centralized setting, without any access to public data. Depending on the required privacy setting, this mechanism can be composed with locally differentially private mechanisms generate node-level predictions.
In different contexts, there has been extensive work on node-level DP (Raskhodnikova & Smith, 2016 Karwa et al. [201] Borgs et al. 2015 2018). But these methods generally deal with modeling 'global' graph-level statistics and do not support learning methods such as GNNs. In contrast, our approach aims to predict 'local' node-level statistics (like the label of a node) while preserving node-level privacy.
3 PROBLEM FORMULATION AND PRELIMINARIES
Consider a graph dataset G E,, Y) with directed graph G = (V, EV represented by adjacency matrix A E {0, 1|nxn, n is the number of nodes in G. V denotes the node set, E denotes the edge set. Each node in the graph equipped with a feature vector X. E Rd: X ga denotes the feature matrix. Y E over Q classes. Note that many of the labels in the label vector can be missing, which models the semi-supervised setting. In particular, we assume that node labels ye are only provided for a subset of nodes Ver C V. called the training set.
is the label matrix and y, is the label for the v-th node
Given the graph dataset G, the goal is to learn parameters of one-layer GNN while preserving privacy of individual nodes. GNN can be represented by the following operations:
P. GNN(A, X, e +) :- Saxe (Jaze (1Sene (X..) A 0}))
where y. is the prediction from the GNN for a given node v. fene is the encoder function that encodes node features with parameters O fagg is the neighborhood aggregation function with parameters
Ougg faee is the prediction decoder function with parameters Odec. and é := (Denc. Ougg. O
While our results apply to most 1-layer GNN models (Hamilton et al. 2017 Veličković al. 2018
Xu et al. 2018), for simplicity, we focus on 1-layer Graph Convolutional Network (GCN) modely" (Kipf & Welling 2016). These GCN models use multi-layer perceptron (MLP) for encoder and decoder functions, with non-linear activation function Ø:
GCN(A, X, ;: θ MLP dec (A,g onne (X) (x))
As is common in practice, we allow any normalization and addition of self-loops A.
3

---

Under review as a conference paper at ICLR 2022
Thus, "learning" GCN is equivalent to finding parameters θ a suitable loss:
@Cenc Ougg tdec) that minimize
= arg min O
((
(3)
NEV
L(G,8)
where e RQXQ + R is standard loss function such as categorical cross-entropy P
As mentioned earlier, we use differential privacy as the notion of privacy of a node. Before defining differential privacy, we first define the notion of adjacent graph datasets:
Definition 1 (Adjacent Graph Datasets). Two graph datasets G and G' are said to be node-level adjacent if one be obtained by adding removing node (with its features, labels and associ- ated edges) to the other. That is, G and G' are exactly the same except for the v-th node, i.e., X.,. yv and A, differ in the datasels.
Informally, A is said to be node-level differentially-private algorithm if the addition or removal of a node in A's input does not affect A's output significantly.
Definition 2 (Node-level Differential Privacy). Consider any randomized algorithm A that takes as input graph dataset. A is said to be (a,n) node-level Rényi differentially-priie (Mironov 2017b) if. for every pair of node-level adjacent datasets G and G':
(a(A(G) A(G')) S1
where Rényi divergence Da of order a between two random variables P and Q is defined as:
1 Da(P (1) a In E
P(x)
Q(x)
Note that we use Rényi differentially-private (RDP) (Mironov 2017b) as the formal notion dif- ferential privacy (DP), it allows for tighter composition of DP across multiple steps. This notion closely related to the standard (e, 3dddifferential privacy (Dwork et al. 2006); Proposition of
Mironov 2b) states that any (a, -DDDP mechanism also satisfies (7 log 1/6 3)-differential
privacy for any O < < 1.
Thus, the goal is find by optimizing equation while ensuring RDP (Definition 2 It is clear that node-level privacy is essential when training models on graph datasets with sensitive node-level information. However, node-level privacy significantly harder to achieve than the weaker notion of edge-level privacy. In the context of GNNs, the representation for a node is computed using not just the node's individual features, but also features of other nodes from the local neighbourhood. Thus, the removal of a node from graph dataset affects its entire local neighbourhood, which can be a very large set of nodes. This is contrast to the standard non- non-graph setting for differentially private models, where the representation of individual users would only depend on the user's own data.
We now define two concepts that critical in our design and analysis of private GNN learning method.
Definition 3. The node-level sensitivity A() of a function f defined on graph datasets is:
A(f)
max node-level adjacent
[lf( - f(G')l2
G,G'
The K- K-restricted node-level sensitivity AK (f) of a functio f defined graph datasets is: [I - f(G')ll2
Ak (x())=
deg(G), deg (G) leve adjacent G.G
Definition 4. We define the clipping operator C.ipo(-) as: (Vipo min (1, ( v, for any
vector or matrix e.
2 The analysis here holds for multi-lahel settings as well, which would instead use loss functions such as sigmoidal cross-entropy, for example.
4

---

Under review as a conference paper at ICLR 2022
Algorithm 1: DP-GNN (SGD): Differentially Private Graph Neural Network with SGD
Data:
Graph G = EV X, Y), GNN definition GNN, Training set Vtr, Loss function C, Batch size m. Maximum degree K, Learning rate n,, Clipping threshold C, Noise standard deviation a, Maximum training iterations T.
Result: GNN parameters Or-
Note that Vr is the subset of nodes for which labels are available (see Paragraph I of Section 3
Using Vtr, construct the set of training subgraphs S., with Algorithm
Construct the 0 - 1 adjacency matrix A: Avu =
(2, (2,u)= Str
Initialize +, randomly.
for [ t= 0 to T do
Sample set B3 S Vvr of size uniformly random from all subsets of Vir- Compute the update term u, as the sum of the clipped gradient terms in the batch B,:
U
C X, is (.):
DEB
Add independent Gaussian noise to the update term: u, u, 00
U Update the current estimate of the parameters with the noisy update: 0x+1 f- O 2 u
end
4 LEARNING GRAPH CONVOLUTIONAL NETWORKS (GCN) VIA DP-SGD
In this section, we provide variant of DP-SGD (Bassily et al. 2014) designed specifically for GCNs (Equation 2), and show that our method guarantees node-level DP (Definition 2
The first step in our method is to subsample the neighborhood of each node to ensure that each node has only K neighbors. This is important to ensure that influence of a single node is restricted to only K other nodes. Next, similar to standard mini-batch SGD technique, we sample subset B, of m nodes chosen uniformly at random from the set Ver of training nodes. In contrast to the standard mini- batih SGD, that samples points with replacement for constructing a mini-batch, our method samples mini-batch B, uniformly from the set of all training nodes. This distinction is important for our privacy amplification result. Once we sample the mini-batch, we apply the standard DP-SGD procedure of computing the gradient over the mini-batch, clipping the gradient and adding noise to it, and then use the noisy gradients for updating the parameters.
DP-SGD requires each update to be differentially private. In standard settings where each gradient term in the mini-batch corresponds to only one point, we only need to add ((C)) noise where C is the clipping norm of the gradient to ensure privacy. However, in the case of GCNs with node-level privacy, perturbing one node/point V can have impact loss term corresponding to all its neighbors Nç. So, to ensure the privacy of each update, gradient V [B,; O,) == EvEB. Clip- (V (GCN X, ug Dy):y.)) wrt an individual node v. To this end, we provide finer bound in Lemma 1 on the sensitivity of VeC(B, O.) based on the maximum degree of the graph G.
add noise according the sensitivity of aggregated
In traditional DP-SGD, a crucial component in getting a better privacy/utility trade-off over just adding noise according the sensitivity of the minibatch gradient. is privacy amplification by sam- pling (Kasiviswanathan et al. 2008 Bassily et al. (014)) This says that if an algorithm A is e-DP on data set D1, then on random subset D2 Dj it satisfies roughly [Da]
[D (c - 1)-DP. Unlike traditional ERMs, we cannot directly use this result in the context of GCNs. The reason is again that on two adjacent data sets, multiple loss terms corresponding to v and its neighbors N/ get modified. To complicate things further, the minibatch B, that gets selected may only contain a small random subset of Ng. To address these issues, we provide a new privacy amplification theorem (Theorem [] To prove the theorem, we adapt (Feldman et al.) 2018 Lemma 25) that shows a weak form of con- vexity of Renyi divergence for our specific instance, and provide a tighter bound by exploiting the special structure in our setting along with the bound on sensitivity discussed above.
Theorem 1 (Amplified Privacy Guarantee for any 1-Layer GCN). Consider the loss function L of the form: L(G, θ) = E (GCN(A, X, v; D.):y.). Recall, N is the number of training nodes Vir, K is an upper bound on the maximum degree of the imput graph, and m is the batch size.
5

---

Under review as a conference paper at ICLR 2022
For any choice of the noise standard deviation 0 and clipping threshold C, every iteration of Algorithm 1 is (a,7) node-level Rényi DP, where:
I exp (ala-1).
2p² ]] p Hypergeometric(N. K m.).
o2
Hypergeometric denotes the standard hypergeometric distribution (Forbes et al. 2011
By the standard composition theorem for Rényi Differential Privacy (Mironov 2017b over T iter- ations, Algorithm iis (/T) node-level Rényi DP, where 7 and a are defined above.
See Appendix A for detailed proof.
Remark 1: Roughly, for m > K and for = = (1), the above bound implies o = O(K) noise to be added per step to ensure RDP with (1) and y O(1). In contrast, the standard DP-SGD style privacy amplification do not apply to our setting as each gradient term can be impacted by multiple nodes.
We provide node-level privacy, that is the method preserves neighborhood information of each node as well. But, require asymmetric/direeted graph, that is, changing a row in the adjacency matrix does not impact any other part of the matrix. This is a natural assumption in variety of settings, for example, in social networks when the graph constructed by "viewership" data, edge (u, o') exists iff user u viewed post from user v'.
Remark 2:
Remark 3: While we provide a formal privacy guarantee for I-layer GCNs, the same applies for any l-layer GNN model.
Remark 4: We adapt DP version of the Adam (Kingma & Ba 2014 TFP) optimizer the GNN setting, called DP-GNN (Adam), with details in Appendix D
Note that Theorem guarantees that the GCN parameters @ that are learnt via Algorithm preserve privacy. However, unlike standard ML models where prediction for each point depends only on model parameters and the point itself, the privacy θ does not imply that inference using the GCN model (or any GNN model) will be privacy preserving. In general, the inference about node v can reveal information about its neighbors N₁. Broadly, there three settings where
Privacy at Inference Time:
infer labels for a given node while preserving privacy:
1. Each node has access to the features of its neighbors. In this setting, the aggregation of fea- tures from the neighbors does not lead to any privacy loss. Several real-world problems admit such a setting: for example, in social networks where any user has access to variety of activi- ties/documents/photos
their friends (neighbors).
Node features are completely private. In this setting, a node does not have direct access to the features of its neighbors N, Here, the standard GCN model is not directly applicable, but we can still apply GCNs by aggregating the neighborhood features with noise. Generally, the resulting prediction for node would be meaningful only if the degree of the node is reasonably large.
3. Training and test graph datasets are disjoint. In this setting, the goal is to privately learn + using the training graph, that can be "transferred" to the test graphs. Additionally, the feature information is shared publicly within test graph dataset nodes. A variety of problems can be modeled by this setting: organizations can be represented by a graph over its employees, with the goal to learn private ranking/rccommendattoo model that can easily be adapted for completely distinct organizations.
While there are multiple problems that can be modeled by the above mentioned settings, we focus on the first setting for our empirical results.
EXPERIMENTAL RESULTS
In this section, we present empirical evaluation of our method standard benchmarks from the widely used Open Graph Benchmark (OGB) suite (Hu et al. 2020). The goal is to demonstrate that method (DP-GNN) indeed learn privacy preserving llayyer GCNs accurately.

---

Under review as a conference paper at ICLR 2022
Table 1: Test aceuracy of DP-GNN compared to the baselines on different datasets. DP-GNN
clearly performs better than the Private and Non-Private MLP baselines across these datasets.
Algorithm
ogbn-arxiv
ogbn-products
ogbn-mag
GCN
68,422 0.267
76.139 0.519
34.680 0.424
DP-GNN (Adam)
63,934 + 0.469
69.576 + 0.276
30.059 0.252
DP-GNN (SGD)
64.137 + 0.621
69.041 + 0.126
30.147 = 00.241
MLP
55,236 + 0.317
61.364 0.132
26,969 0.361
DP-MLP
53,462 + 0.242
61.064 + 0.110
25.259 = 0.321
As mentioned earlier, in several data critical scenarios, practitioners cannot use sensitive graph in- formation, and have to completely discard GNN based models due to privacy concerns. Hence, the main benchmark of our evaluation is to demonstrate that DP-GNN is able to provide more accurate solutions than standard methods that completely discard the graph information. The key baselines for method are both standard non-private MLP models as well differentially private MLP models trained using DP-SGD and Dd-Adam. We also compare against the standard 1-layer GCNs (without any privacy guarantees) as it bounds the maximum accuracy we can hope to achieve out of our method.
5.1 DATASETS AND SETUP
OGB datasets:
We use three moderate-to-large sized node classification datasets from OGB suite ogbn-arxiv, ogbn-products and ogbn-mag. The ogbn-arxiv and ogbn-mag datasets consist of papers extracted from the Microsoft Academic Graph (MAG) dataset (Wang et al., 2020). The ogbn-arxiv dataset is paper citation network of arxiv papers and consists of around 169K nodes, while the agbn-mag dataset a heterogenous graph with node types papers, authors, institutions and topics and consists of around 1.9M nodes. However, following the standard approach in (Hu et al. 2020) we create a homogeneous graph of papers (736K nodes) from the ogbn-mag dataset. The ogbn- products dataset an Amazon products co-purchasing network and consists of 2.4M nodes. Each dataset consists of edges, node features and labels (multi-class), and is split into standard train, test and validation sets (Hu al., 2020). Finally, following (Hu et al., (020), we consider the transductive semi-supervised setting for all the datasets. i.e.. the entire graph is available during training but only a few nodes Vr, have labels available. See [Appendix E for additional details about the datasets.
For DP-GNN, we perform layer- gradient clipping. i.e., the gradients cor- responding to the encoder, aggregation and decoder functions are clipped independently with dif- ferent clipping thresholds. For each layer, the clipping threshold C' Algorithm 1] is chosen as Cj x C% where C' is scaling factor and C% is the 75th percentile of gradient norms for that layer at initialization on the training data. We finetune the C5 parameter for each dataset. We set the noise for each layer such that the noise multiplier À 2(++JCC is identical for each layer. where a / essentially the sensitivity. It not hard to observe that the overall privacy cost only depends on A.
Gradient Clipping:
Our method (Algorithm I special- ized for a 1-layer GCN with an MLP as the encoder and the decoder, b) GCN: A 1-layer GCN with an MLP encoder and decoder. This defines the highest possible numbers for our method but due to privacy concerns, non-private GCN might not be suitable for deployment in practice, c) MLP: A standard multi-layer perceptron (MLP) architecture on the raw node features as proposed in prior works (Hu et al. 2020). This model does not utilize any graph level information, d) DP-MLP: A DP version of MLP (with standard architecture) trained using DP-Adam (TFP).
Methods:
We benchmark the following methods: a) DP-GNN:
Detailed Setup and Hardware: DP-GNN and all the aforementioned baselines are implemented in TensorFlow 2.0 (Abadi et al. 2015) using Graph Nety and Sonne All experiments are performed on 2x2 TPU v2 Pods. We perform model selection for all the methods based on their performance on the validation set. We run each experiment nine times and report the mean and standard deviation for performance on the test set in Table
Hyperparameter Tuning: We perform exhaustive grid search over batch size, learning rate, tivation functions, and number of encoder and decoder MLP layers for the non-private baselines.
agg.ssaffrrl.ctuddee//mdgggggr hatp://oieoooooo...oooooooomnnnn nets
gitnhh.om/deepminnlgguhhh
gudubb.oomddeeminlloonne

---

Under review as a conference paper at ICLR 2022
71.0
65
72.5
Text Accuncyy
Teat Acruneyy
575
53.0
685
8
130
0P-01
575
Epsiaon (Piieacy Panemeler
Eowlon (Frivayy Paramateri
Epsikmn Prriceyy Panameter)
(a) ogbn-arxiv
(b) oghn-products
(c) ogbn-mag
Figure I: Performance of the proposed DP-GNN method well the baselines the oghn- arxiv, ogbn-products and ogbn-mag datasets. Clearly, DP-GNN offers a performance better than both of the Non-Private MLP and DP-MLP methods, with a reasonable privacy budget of - 30.
Additionally, tune noise multiplier (a in Algorithm 1 and clipping thresholds for the pri- vate baselines. We provide detailed information regarding the hyperparameters in Appendix H
Table compares DP-GNN's accuracy against baselines the ggbn-arxiv, rgbn-products and ogbn- mag datasets. We extensively tune baselines on the three datasets as mentioned above and able replicate, and some cases, improve the reported performance numbers for the baselines (Hu et al. 2020). We use the higher number of the two for comparison with our method.
Results:
Overall, observe that our proposed method DP-GNN significantly outperforms the Non-Private MLP (without any usage of the graphs) and DP-MLP (trained using standard DP-Adam) baselines on all of the datasets and with a reasonable privacy budget of s S 30. For example, for ogbn-arxio dataset, our method DP-GNN (SGD) is about 8% more accurate than MLP and 10% more accurate than DP-MLP. Similarly, for sebn-proddcct our method about 5% more accurate than both MLP and DP-MLP. Note that we also present numbers for DP-GNN (Adam) (see [ppendixx D) that uses Adam as the optimizer instead of SGD, as mentioned in Algorithm T Also, note that for rest of the section we DP-GNN (Adam) for generating accuracy numbers.
Next, Figure D provides a comparison of epsilon vs test set accuracy for the three benchmark datasets. Note that for 2 10. DP-GNN is significantly more accurate than DP-MLP. It is in- teresting to note that for about E 2 10, the accuracy of the DP-MLP saturates and does not increase significantly. In contrast, the accuracy of DP-GNN keeps increasing with larger e, and is in gen- eral much higher than both MLP and DP-MLP for higher values of e. Finally, on egbu-products DP-GNN is about 5% more accurate than DP-MLP for the entire range of considered values for s. and is about 2% more accurate than MLP for غ = 10.
Typically, for training non-convex learning models with user-level DP, E S 10 has become popu- lar choice (Papernot et al., 2020 Kairouz et al. (022I. But as the problem is more challenging in the case of GNNs multiple nodes can affect inference for given node and we intend protect privacy at the node-level higher seems like reasonable choice to encourage reasonable solu- tions. Moreover, as we observe on the egbu-producet dataset, larger dataset sizes can ensure better performance for the standard E values as well. Also, our algorithms satisfy stronger Rényi DP prop- erties (Mironov 2017b), which provide additional protection over traditional (e, 6)-DP guarantees.
5.2 ABLATION STUDIES
Batch size m: As has been noted in other DP-SGD works (Abadi et al.] 2016 Bagdasaryan et al.) 2019), we empirically observe that increasing the batch size helps the performance the learnt DP-GNN, up point. There are multiple effects at play here.
Larger batch sizes imply that the effective noise added per DP-SGD update step smaller. Thus, training is more stable with larger batch sizes, Figure shows. Furthermore, effeective privacy budget (E) provided by amplification result has a term of the form exp(Eo) - 1 where Eo is the privacy budget for step. So, unless Eo is small enough, i.e., the batch size is large enough, the amplification result would be weak. On the other hand, larger batch sizes tend to hurt generalization and training speed,
in the non-private case, the second column of Table 2 shows.
Thus, there is a trade-off between model performance, privacy budget and batch size. As the last column of Table 2 shows, the difference in performance between private and non-private models
8

---

Under review as a conference paper at ICLR 2022
Table 2: GCN and DP-GNN on the oghn- arxiv dataset with different batch sizes. The privacy budget for DP-GNN is < 30.
Table 3: GCN and DP-GNN on the ogbn- arxiv dataset with different degrees. The privacy budget for DP-GNN is & 30.
Banch Sizee
GCN (Aecs)
DP GNN (AQeee))
Accy
APNANN
Degree
GUN (daa))
DE.GNN (Agesea))
Agex - Aereess
08.36
63.439
5.124
08.945
2500
68.256
63.025
5.331
10
06.3772
64.100 103
4,269
5030
68.490
64.545
4.145
15
68.224
63.522
4,702
10000
68 062
64 304
17788
20
642
63,054
5.588
20000
68.491
62.062
6.429
32
68.152
61.901
6.251
Accuracy
Test Accuracy
27.3
00.1
Degree
500
2500
20000
450
25
Epsilon (Privacy Parameter)
Epsilon (Privacy Parameter)
(a) Varying Batch Size
(b) Varying Maximum Degree K
Figure 2: Ablation studies on DP-GNN the ogbn-arxiv dataset. (a) shows privacy-utility curves for a range of batch sizes for the DP-GNN. (b) shows privacy-utility curves when varying maximum degree K for the DP-GNN. In both analyses, the other hyperparameters are kept fixed.
tends to diminish as the batch size increases. However, for the reasons pointed out above, beyond batch size 10000, the accuracy goes down, as quantified by Table
Maximum Degree K: Compared to the batch size, the maximum degree K has less of an effect on both non-private and private models trained on ogbn-arxiv, as Table 3 shows. Generally, there is still trade-off: smaller K means lesser differentially private noise added each update step, but also fewer neighbours for each node to aggregate information from.
Finally, also conduct experiments to understand performance of DP-GNN conditioned the frequency class (how often a class appears in the dataset), with details in Appendix F On the whole, these experiments suggest that DP-GNN is able classify data points of "frequent" classes with reasonable accuracy, but struggles with classification accuracy on the data points of "rarer" classes. This observation is in line with previous claims from (Bagdasaryan al. 2019 Fioretto et al. (02TT) that differentially--rivaa models generally perform worse on low-frequency classes, and represent critical future direction study.
CONCLUSIONS AND FUTURE WORK
In this work, proposed method privately learn 1-layer GNN parameters, that outperforms both private and non-private baselines that do not utilize graph information. Our method ensures node-level differential privacy, by careful combination of sensitivity analysis of the gradients and a privacy amplification result extended to the GNN style settings. We believe that our work is a first step in the direction of designing powerful GNNs while preserving privacy. Promising avenues for future work include learning more general class of GNNs, investigating inference mechanisms mentioned in Section such as different train and test graph datasets, and understanding utility bounds for GNNs with node-level privacy.
7 REPRODUCIBILITY STATEMENT
We have taken all efforts to ensure that the results produced in the paper and the submitted ma- terial are reproducible, and the methodology easy to follow. For our theoretical contributions, we have discussed the problem setup and preliminaries in /Section 3, provided a detailed algorithm for proposed methodology in Section 4 for sound theoretical understanding of the problem

---

Under review as a conference paper at ICLR 2022
and our solution. For empirical results, we have detailed the information needed to reproduce the empirical results in [Section of the main paper and Appendix El We supply all the required information regarding the datasets, their pre-processing and source, implementation details for our method and the baselines, specifics regarding the architectures, hyperparameter search spaces and the best hyperparameters corresponding implementation, in the spirit of reproducible research.
experiments. We working towards open source
8
ETHICS STATEMENT
The interest in differentially-prine models largely stems from a need to protect the privacy of data samples used train these models. While we have proposed mechanism here to learn GNNs in privacy-preserving manner, differential privacy seems to exacerbate existing fairness issues on underrepresented classes as Appendix indiccaes.. This a concern across all models trained with differential privacy (Bagdasaryan et al. 2019) that needs to be addressed before such models can be deployed in the real world. While there have been recent attempts (Jagielski et al.) 2018 Fioretto et al. 202T) to mitigate the disparate effect of differentially private training, there is still a need for an effective practical solution. We anticipate no other negative consequences of our work.
REFERENCES
TensorFlow Privacy. httess//ataaa.ccm///eooooooo////
Accessed: 2021-10-
05.
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, An- drew Harp, Geoffrey Irving, Michael Isard, Yangging Jia, Rafal Jozefowicz, Lukasz Kaiser, Man- junath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Mar- tin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-Scal Ma- chine Learning on Heterogeneous Systems, 2015. URLhttps /wwww tensorf org/ Software available from tensorflow.org.
Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep Learning with Differential Privacy. In Proceedings of the 2016 ACM SIGSAC Conference Computer and Communications Security, CCS 16. pp. 308-318, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450341394 doi: 2978318
10.1145/2976749.297888 URL htRl:ttp::// http:::/ddoo.ogg/////// 111111..11419991
David Ahmedt--rissizzaaal Mohammad Ali Armin, Simon Denman, Clinton Fookes, and Lars Pe- tersson. Graph-Based Deep Learning for Medical Diagnosis and Analysis: Past, Present and Future. arXiv preprint arXiv:2/05.13133 2021.
Rohan Anil, Badih Ghazi, Vineet Gupta, Ravi Kumar, and Pasin Manurangsi. Large-Scale Dif- ferentially Private BERT. CoRR, abs/2108.01624 2021. URL holphtttpp://exiw..rrg
2108. 01624
Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov. Differential privacy has disparate im- pact on model accuracy. Advances in Neural Information Processing Systems, 32:15479-15588, 2019.
Raef Bassily, Adam Smith, and Abhradcep Thakurta. Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds. In Proc. of the 2014 IEEE 55th Annual Symp. on Foundations of Computer Science (FOCS), pp. 463, 2014.
Christian Borgs, Jennifer T. Chayes, and Adam Smith. Private Graphon Estimation for Sparse Graphs, 2015.
Christian Borgs, Jennifer Chayes, Adam Smith, and Ilass Zadik. Revealing Network Structure, Confidentially: Improved Rates for Node-Privan Graphon Estimation, 2018
10

---

Under review as a conference paper at ICLR 2022
Amar Budhiraja, Gaurush Hiramandani, Darshak Chhatbar, Aditya Sinha, Navya Yarrabelly, Ayush Choure, Oluwasanmi Koyejo, and Prateck Jain. Rich-Item Recommendations for Rich-Users Exploiting Dynamic and Static Side Information, 2020.
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks. In 28th USENIX Security Symposium (USENIX Security 19), pp. 267-284, Santa Clara, CA, August 2019. USENIX As- sociation. ISBN 978- 978-1-933133--0--9 URL https: wwww:.seeni.com wwwp:/iwww..rro/ooeeeeeeoeeee carm/iirliiii
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise to Sensitivity in Private Data Analysis. In Shai Halevi and Tal Rabin (eds.), Theory of Cryptography, pp. 265- 284, Berlin, Heidelberg. 2006. Springer Berlin Heidelberg. ISBN 978-3-540-32732-55.
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.
Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy Amplification by Iteration. 59th Annual IEEE Symp. on Foundations of Computer Science (FOCS), pp. 521-532, 2018.
Ferdinando Fioretto, Cuong Tran, and Pascal Van Hentenryck. Decision Making with Differential Privacy under Fairness Lens. CoRR, abs/2105.07513, 2021. URL htttps://axxi.... org/
abs/2105 07513
C. Forbes, M. Evans, N. Hastings, and B. Peacock. Statistical Distributions. Wiley, 2011. ISBN 9781118097823. URL httptt:/pcoook wtt.g/e......///oosse........... poophpoopp
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neu- ral Message Passing for Quantum Chemistry. CoRR, abs/1704.01212, 2017. URL http:
01212
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive Repressenaation Learning on Large 02216
Graphs. CoRR, abs/1706.02216, 2017. URL
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 wwxivv2005.00655 2020.
Matthew Jagielski, Michael Kearns, Jieming Mao, Alina Oprea, Aaron Roth, Saeed Sharifi- Malvajerdi, and Jonathan R. Ullman. Differentially Private Fair Learning. CoRR, abs/1812.02266.
2018. URL http::tt//// http://axxvvvvvo org/
/abb abs /111.11111. C2696
Peter Kairouz, Brendan Memahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and Private (Deep) Learning Without Sampling or Shuffling. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 2213-5225. PMLR, 18-24 Jul 2021. URL URL http:tts://ppcceelllaas httpp/eeeaanggnnn.ppeeess////aaa wtt.://eeeeee/////a/r/eeeo
mlx
html
Vishesh Karwa, Sofya Raskhodnikova, Adam Davison Smith, and Grigory Yaroslavtsev. Private analysis of graph structure. Proceedings of the VLDB Endowment, 4(11):1146-1155 146-11777 August 2011. ISSN 2150-8097.
Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. What Can We Learn Privately? In 49th Annual IEEE Symp. on Foundations of Computer Science (FOCS), pp. 531-540. 2008.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXiv 2014.
Thomas N. Kipf and Max Welling, Superviuee Classification with Graph Convolutional Net- works. CoRR, abs/1600.02207, 2016. http:ht:://aaxxw...t

---

Under review as a conference paper at ICLR 2022
Sofia Ira Ktena, Sarah Parisot, Enzo Ferrante, Martin Rajchl, Matthew Lee, Ben Glocker, and Daniel Rueckert. Metric learning with spectral graph convolutions on brain connectivity networks. Neu- rolmage, 169:431-4444 2018.
Daniel Levy, Ziteng Sun, Kareem Amin. Satyen Kale, Alex Kulesza, Mehryar Mohri, and Ananda Theertha Suresh. Learning with User-Level Privacy. CoRR, abs/2102.11845, 2021. URL
https::/arxiv.. wwt.:///.oogooooooooooooooooooo 2102. 11845
Kevin McCloskey, Ankur Taly, Federico Monti, Michael Brenner, and Lucy J Colwell. Using attribution to decode binding mechanism in neural network models for chemistry. Proceedings of the National Academy of Sciences, I 116(24): 1624-1 1629, 2019.
Iya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Sym- posium (CSF), pp. 263-275. IEEE, 2017a.
Ilya Mironov, Renyi Differential Privacy. CoRR, abs/ abs//102..0776, 2017b. URL http::/arrxi org/ wtt.///11..0...
Iyiola E. Olatunji, Thorben Funke, and Megha Khosla. Releasing Graph Neural Networks with Differential Privacy Guarantees, 2021.
Nicolas Papernot, Martín Abadi, Úlfar Erlingsson, lan J. Goodfellow, and Kunal Talwar. Semi- supervised Knowledge Transfer for Deep Learning from Private Training Data. In 5th Interna- tional Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https: htttps://ppenreviers
Forum? H
Nicolas Papernot, Steve Chien, Shuang Song, Abhradeep Thakurta, and Ulfar Erlingsson. Making the Shoe Fit: Architectures, Initializations, and Tuning for Learning with Privacy, 2020. URL
net htt.:///e/ooooordddddog
Sofya Raskhodnikova and Adam Smith. Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism. In 2016 IEEE 57th Anmual Symposium on Foundations of Computer Science (FOCS). pp. 495-504, 2016. doi: 10.1 1000/F/CS.200...60
Sina Sajadmanesh and Daniel Gatica-Perez. When Differential Privacy Meets Graph Neural Net- works. CoRR, abs/2006.05535, 2020.
05535
Chuanqiang Shan, Huiyun Jiao, and Jie Fu. Towards Representation Identical Privacy-Preservien Graph Neural Network via Split Learning. CoRR, abs/2100.055917, 2021. URL https://
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differ- entially private updates. In 2013 IEEE Global Conference Signal and Information Processing, pp. 245-248. IEEE, 2013.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks, 2018.
Kuansan Wang. Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1):396~ 413, 2020.
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic Graph CNN for Learning on Point Clouds. Acm Transactions On Graphics), 38(5): 2019.
Chuhan Wu, Fangzhao Wu, Yang Cao, Yongfeng Huang, and Xing Xie. FedGNN; Federated Graph Neural Network for DivaacyPrreeevvigg Recommendation. CoRR, abs/2102.04925,, 2021a. URL. org abs. httgg//bs//1000 2202. 04925
https://erxix:
Fan Wu, Yunhui Long, Ce Zhang, and Bo Li. LinkTeller: Recovering Private Edges from Graph Neural Networks via Influence Analysis, 2021b.
12

---

Under review as a conference paper at ICLR 2022
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful Graph Neural Networks? CoRR,
2018. URL BBL/attp://axxi.orrr abs httc:p//arr...ooo///////LL...0.0
Liang Yao, Chengsheng Mao, and Yuan Luo. Graph convolutional networks for text classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 7370-7377,
2019.
Jun Zhou, Chaochao Chen, Longfei Zheng, Xiaolin Zheng, Bingzhe Wu, Ziqi Liu, and Li Wang- Privacy-Preserving Graph Neural Network for Node Classification. CoRR, abs/2005. 1903, 2020.
URL httpt:h/taaasstt org/ 11903
APPENDIX
This appendix is segmented into four key parts:
1. Section gives detailed proofs for the Lemmas discussed in the main paper and additional lemmas that could be included in the paper due to space constraints.
2. Section D provides detailed description of learning Graph Convolutional Networks via DP-Adam.
3. Section discusses experimental details for reproducing the results in the main paper.
4. Section provides additional results for analysing the performance of the DP-GNN model as compared the GCN baseline.
A LEMMAS AND PROOFS
Lemma (Node-Level Sensitivity of any 1-Layer GCN), Consider the loss function C of the form:
O) = Σ = ((CCN(A.X...)):....)))
VEV
Let B, be any choice of unique nodes from graph G with maximum degree bounded above by K. Consider the following quantity u, from Algorithm 1
(G)
Σ Clipo (Ve (GCN(AA, O.):y.)) VER.
Note that u, (G) is 'clipped' version of Ve,(B,,
VeL(B, O, =) Σ x,
vEB,
Then, the following inequality holds:
A < 2(K +1C.
Proof. Let G be an arbitrary graph dataset with adjacency matrix A and maximum degree bounded above by K. Consider an adjacent graph dataset G' with adjacency matrix A' formed by removing single node & from G. We wish to bound the following quantity:
| (G) u. (G')llF
For convenience, for any node v, we denote the corresponding loss terms e, and & as:
E, = e (GCNN(A, X, 2; O.):y.)
E = E (GCN(A' X O.):y))
From the definition l,, is clear that the only gradient terms Vel, affected when adding or removing node V, are those of its neighbors and v itself. Thus,
u GG) - (G")
= Clipo((Vll)) IV E BJ}+
Σ NENS
(Cllpc(Vel..) CCip- ( (Vo,)) Ilu E B,
13

---

Under review as a conference paper at ICLR 2022
where I is the indicator random variable. Taking norms:
lu, l
- Clipc(Vel))- I[V E B.]] +
Σ
(Clipo(Vel..) (lipp(Ve))) Ilu E Bil
uENo
r
x [Clipe Il E Bills + Σ
(VClii) Clipo (Ve()) (V Ilu E B.]lle (triangle inequality)
MEN;
< (Clip((Velslll Σ
WENG
(I (0,
v (Vel)((
Σ
([Clipc(Velaalll [CCi [[Clipo
MENG
(triangle inequality)
S C+ (C+C)
WEN,
(gradient clipping)
= + 2C
(definition of dx)
= C(2dx + +1) C(2K +1) < 2(K + I)C.
(dg K,C 0)
As G and G' were an arbitrary pair of node-level adjacent graph datasets,
(u( =
max deg(G), deg(G') S leve- adjucent G,G'
|lu:(G) - ur (G'))l
< 2(K + I)C.
The proof for the bound on AK (G) when new node v is added the graph G follows analo- gously.
Lemma 2 (Un-amplified Privacy Guarantee for Each Iteration of Algorithm D.. Every iteration
Algorithm 1 is (a,7) node-level Rényi DP for when run graphs with maximum degree S K where:
a (A,(
20
Here ( is the K-restricted node-level sensitivity from Definition
Proof. Follows directly from (Mironov 2017a
Corollary 3).
Lemma 3 (Distribution of Loss Terms Per Minibatch). For any iteration in Algorithm 1 con- sider the minibatch B, of subgraphs. For any subset S of d unique nodes, define the ran- dom variable p as |S n B,). Then, the distribution of follows the hypergeometric distribution Hypergeometric(N.cc d))
N-
1m-3
P p= Plp
where N is the total number of nodes in the training set Ver and |B: = m is the batch size.
Proof. The minibatches B, in Algorithm I are formed by sampling nodes from Ver without re- placement. When p needs to pick nodes from S and the remaining i nodes from
14

---

Under review as a conference paper at ICLR 2022
Vir S to form batch of size Clearly, there are (15) m- (18+)1=1))) = (m=:) to do the second step. Finally, there are (mm) ways to choose minibatch B, of size m, each choice equally likely. In conclusion, we can claim:
(:) ways to do the first step, and
Plp = i]
which is exactly the Hypergeometric(NN d, m) distribution.
Lemma 4 (Adaptation of Lemma 25 from Feldman et al. (2018). Let .o...., Pn and Vo. be probability distributions over some domain Z such that:
Da(uo vo) S Eo
Dalun || Un) En
for some given Eg....,Er,
Let be probability distribution over [n] t0...., n). Denote by Up (respectively, vp) the probability distribution over Z obtained by sampling i from and then outputting a random sample
from μa (respectively, V,). Then:
DalUp 1p) S In Es-p [easla-1)]
In
prefi(a-1).
1=0
Proof. Let uig (respectively v/)) be the probability distribution over [n] Z obtained by sampling from p and then sampling random from μı (respectively, v;) and outputting (i. We obtain Mp from Hy by applying the function that removes the first coordinate; the same function applied gives up from v/g. Therefore, by the post-procsssing properties of the Renyi divergence, we obtain that:
Dalup |l 1/) S Dall', || v//))
Now, observe that for every E [n] and E 7, (b( = Pr (1(x). Therefore,
(1,x))
Da 11//)
In E ((i))mm
1/ (1, xr)
a
[i(x))
In Einp
Eawuy
0:
vx(x))
In Enup (e:(a-1))
n
In
peeila-1)
a
as required.
Lemma' 5. Let X be a non-negative continuous random variable with cumulative distribution func- tion Fx and density fx. Let g R220 R be differentiable function. Then:
E[g(X)] g(0) / ((x()(1-Fx(x)) dx
15

---

Under review as a conference paper at ICLR 2022
Proof.
0 (())(1 ((x)(1-Fx(x)) do / g' Pr > x] dr
g(x)) fx(t) dt dr
(x(x)x((t) dt dr
S g(())fx(() dr dt
[x(1) (('010) dx di
[x(1) (o(1) -g())
Elg(X) g(0) -
as claimed.
An analogous inequality holds for discrete random variables, taking values on Z.
Lemma 6. Let X be discrete random variable taking values Z with cumulative distribution function Fxx and probability mass function fx. Let g : - IR be a function. Then:
[[g(X)] = 90) + Σ (o(x + -1))))))))(((11111111 Fx(x))
Proof. The proof is identical to that of Lemma 5 by replacing integrals with sums.
Lemma 7. Let p and of be two random variables with the hypergeometric distribution:
Hypergeometric( N, N.k.m
p' Hypergeometric(MM KN km)
such that l 2 W. Then, p stochastically dominates p':
(t) 2 Fi()) for all i E
where F2 (respectively, Fg') the cumulative distribution function (CDF) of (respectively, gl).
Proof. Note the following representation of the hypergeometric random variable the sum of de-
pendent Bernuulii random variables:
X;
where each X; Bernoulli ) ).
Similarly, have:
X
where each X Bernoulli )- Now, k 2 W', by simple analysis for Bernoulli random variables, each X is stochastically dominated by X;:
Fx; 2 Fx.-
for each E {L....,m} m). Thus, as sums preserve stochastic dominance:
Fg F x
F Eis
F'
(4)
required.
n
16

---

Under review as a conference paper at ICLR 2022
Lemma 8. Let and pl be two non-negative random variables such that stochastically dominates p':
Fg(i) 2 F,(1) for all i R
where Fp (respectively, Ppt) the cumulative distribution fianction (CDF) of (respectively, P
Let g R200 - IR be non-decreasing differentiable function. Then, the following inequality holds: E[g(p')1 Elg(p)).
Proof. We first argue for the case where both and p' are continuous. By Lemma
we have that:
[[g(p)] 9(0) + / g'(x)(1 Fş(x)) de B[g(p')) 9(0) + { g((x)(1 (x)) dx.
and hence:
[[o(p)] - E[g(d / (((x)(Fp(x)) - -F(()) dz.
As g is non-decreasing, have that g' 2 0 everywhere. The theorem now follows directly.
The case where both and p' are discrete can be handled analogously, by using Lemma 6 above instead.
We now ready to supply the proof of the main theoretical result in this paper, Theorem
Proof of Theorem 1 We borrow notation from the proof of Lemma I Let G' be an arbitrary graph with adjacency matrix A and maximum degree bounded above by K. Consider an adjacent graph G" with adjacency matrix A' formed by removing a single node V from G. For convenience, for any node v, we denote the corresponding loss terms by and E. as:
L. = (GCN(A, X, i: O):yv)
E. = (GCN(A', X', DE 9):y))
As in Lemma !
(G( (G')
-Clip((Velt) I B
Σ (Celp)( Clip (Vol.)) Ilu E B, NEN;
(5)
where Z is the indicator function. With the notation from Algorithm we have:
ú (G) + (0, IT),
(G') + + +
We need show that:
D. (G')) 5
Let - {u u e ur u E )& be the set of nodes 'affected' by the removal of V. From Equution 5 we see that the sensitivity of u, depends on the number of nodes S that are present in B,;
[[,(G) - (G'')l
Clipa A EB
Clip (Cllp)((V MENo
Σ
I(u E B,]
Let o' be the distribution over (0, 1, de + 1} of the number of "affected" nodes in present in B, that is, p' =IS B,]. Lemma then gives us that the distribution of p is:
p Hypergeometric de 1, 1,m.
17

---

Under review as a conference paper at ICLR 2022
In particular, when o' = i, exactly nodes are sampled in B,. Then, it follows by the same argument
in the proof of Lemma that:
( o² i) < 21C.
Thus, conditioning on p' i, see that every iteration (t) where:
74) node-level Rényi DP, by Lemma
(2iC)²
21
20²
Define the distributions 14 and vs for each i .O..... d3 + 11. as follows:
14 ((G) of =
4 = Ū(G') |
Then, by Equation 7
Da(us || vi) S %
For the mixture distributions M4 = (G) and Up = (G').
Lemma 4 now tells us that:
DG(U(G) ([G))|U(C UG')) = D (14 Upr))
<
In In
lexp (1i(a 1))1
In Exmp' exp a1(a - 1) 212 O²
1
exp aala- 1) 20002
In E
In IE [f(''))
where:
1). 11)- exp (ala (ala-1)
C2
f(p') exp
Define another distribution as:
Hypergeometric(N, K + 1,.
As de I K, by Lemma 7 p stochastically dominates p'. Then, as non-decreasing. Lemma gives us:
E $ s
(9)
follows from Equation 8 and Equation 9 that:
(a(ū(G) || ((G') < a a-1 In E, exp (aja- - 1) σ²
2p²02 )
=
As this holds for an arbitrary pair of node-level adjacent graphs G and G', we are done.
18

---

Under review as a conference paper at ICLR 2022
B SAMPLING SUBGRAPHS
To bound the sensitivity of the mini-batch gradient in Algorithm we must carefully bound both the in-degree and out-degree of any node in the graph across all training subgraphs. Algorithm outputs set of training subgraphs that ensures these degree constraints are met.
Note that once the model parameters have been learnt, no such degree restriction is needed infer- ence time. This means predictions for the 'test" nodes can use the entire neighbourhood information.
Algorithm 2: Sampling Subgraphs with In-Degree and Out-Degree Constraints
Data: Graph G' (V, E, Y), Training set Vir. Maximum degree K. Result: Set training subgraphs Sty.
for E V do
I Initialize county f- 0. Initialize subgraph S, + {u}.
end
Shuffle Ver. for u E Ver do for u E N2 do
If count, = K, continue.
count, = K. break.
Add node subgraph S,, Add node to subgraph S.- Increment count,, by 1.
Increment count, by 1.
end end
Construct Str +- (Sp v E V.r. return Str.
C EXPERIMENTS WITH DIFFERENT GNN ARCHITECTURES
As mentioned in Section 4 the DP-GNN training mechanisms can be used with any 1-layer GNN
architecture.
We experiment with different GNN architectures, namely GIN (Xu al. 2018) and GAT (Veličkovid al. 2018) on the ogbn-arxiv dataset and report the results for the respective private and non-privee non-private models in Table 4] We use a variant of the original GAT architecture, utilizing dot dot-product attention instead of additive attention, with 10 attention heads.
We observe that DP-GNN performs reasonably well across different architectures.
Table 4: Test accuracy of DP-GNN (Adam) on the ogbn-arxiv dataset with a privacy budget of
8 < 30.
Architecture
Non-Private GNN
DP-GNN
GCN
68,422 0.267
63,934 + 0.469
GIN
67.485 = 0.391
63.888 0.709
GAT
65.702 0.674
58.853 + 0.246
19

---

Under review as a conference paper at ICLR 2022
D LEARNING GRAPH CONVOLUTIONAL NETWORKS (GCN) VIA DP-ADAM
In Algorithm 3| we provide the description of DP-Adam, which adapts Algorithm to use the pop- ular Adam (Kingma & Ba 2014) optimizer, instead of SGD. The privacy guarantee and accounting for Algorithm 3 is identical to that of Algorithm since the DP clipping and noise addition steps identical.
Algorithm 3: DP-GNN (Adam): Differentially Private Graph Neural Network with Adam
Data: Graph G = (V, E, X, Y), GNN definition GNN, Training set Vtr, Loss function L,
Batch size m, Maximum degree K, Learning rate n, Clipping threshold C, Noise standard deviation a, Maximum training iterations T, Adam hyperparameters (3,, 82).
Result: GNN parameters θr.
Note that V,, is the subset of nodes for which labels are available (see Paragraph of Section 3
Using Vtr, construct the set of training subgraphs St, with Algorithh
Construct the 0 - 1 adjacency matrix A: Avu 1 (U, u) Str
Initialize O randomly.
for i. to T do
Sample set B: S Vir of size m uniformly at random from all subsets of Vtr Compute the gradient term u, as the sum of the clipped gradient terms in the batch B,:
U1
Σ D
Clipo(Vel (GNN A, X, un (.):
Add independent Gaussian noise to the gradient term: ,, + u + NO0 o²1) Update first and second moment estimators with the noisy gradient, correcting for bias:
ft - 31 fe-1 + (1 - -1)) -ú,
8t B2
8t-1 8 (1 -.2)) @.)
fc -- ft
B1
8t f- S₁
82
Update the current estimate of the parameters with the noisy estimators:
0 t O n f
m
88
+
end
E EXPERIMENTAL DETAILS AND REPRODUCIBILITY
Table 5) provides details on the benchmark node classification datasets from the OGB suite used in the experiments. The following 3 datasets used demonstrate the effectiveness of our method: ogbn-arxiv"] and ogbn-mas" ? dataset consisting of papers extracted from the Microsoft Academic Graph (MAG) dataset (Wang al. 2020) and ogbn-product dataset which is co-purchasing network of Amazon products.
Hyperparameter configurations for all methods: We use the following 'inverse-degres normal- ization of the adjacency matrix for all GCN models:
À (d -I- II)
Adam (Kingma & Ba 2014) with B1 = 0.9 and 32 = 0.999, and SGD optimizers were used for training all methods for each of the datasets. We fix Cs, as 75.
20

---

Under review as a conference paper at ICLR 2022
Table 5: Statisties of datasets used in our experiments. On all of these datasets, the task is to classify individual nodes into one of multiple classes.
Dataset
# Nodes
Avg. Degree
# Features
Classes
Train/Val/Test Splits
ogbn-arxiv
169,343
13.7
128
40
0.54/0.1 18/0.28
ogbn-products 61, 1859,1100
50.5
100
47
0.08/0.02/0.90 0.85/0.09/0005
ogbn-mag 736,389
21.7
128
349
dataset-specific grid search was performed over the other hyperparameters for each method, men- tioned below. Ir refers to the learning rate, Peae refers the number of layers in the encoder MIP, dae refers to the number of layers the decoder MLP, À refers to the noise multiplier, Cý refers to the clipping scaling factor, and K refers to the sampling degree.
ogbn-arxiv:
Non-Private GCN: Ir {0.001, 0.002, 0.003), Nemc in (1, 2), Odde: {1, 2), Batch Size in {1000), Activation in (Rel.U), K in (7, 10).
DP-GNN: Ir (Adam) in {0.001, 0.002, 0.003), Ir (SGD) in {0.2. 0.5, 1.0), nene in {1. 2), Niec in {1. 2}. Batch Size in {10000), Activation in {Tanh), in {1.0), Cy in {1.0}. K in
{7, 10}.
Non-Private MLP: Ir in {0.001, 0.002, 0.003). Deme in (1, 2), Ride in {1, 2), Batch Size in {1000}, Activation in (ReLU).
DP-MLP: (r in {0.001, 0.002, 0.003), Nene in {1, naee in {1,2), Batch Size in {10000), Activation in [Tanh), X in {1.0), Cý in (1.0).
ogbn-products:
Non-Private GCN: Ir in {0.001, 0.002, 0.003), neme in {1, 2), Radec in {1, Batch Size in { {1000, 4096), Activation in (ReLU, Tanh), in {10).
DP-GNN: (Adam) in {0.001, 0.002, 0.003), Ir (SGD) in {0.01, 0.1, 1.0], nenc in {1, 2). Tidee in 2). Batch Size in {1000, 4096, 10000), Activation in {ReLU, Tanh), À in {0.8, 0.9, 1.0). Cy in {1.0}. K in {10).
Non-Private MLP: Ir in {0.001, 0.002, 0.003], Renc in (1, 2}, Ruee in {1, 2). Batch Size in {1000, 4096, 10000], Activation in (ReLU, Tanh).
DP-MLP: Ir in {0.001, 0.002. 0.003). fene in {1, 2). Oaee in {1, 2}. Batch Size in {1000, 4096, 10000), Activation in (ReLU, Tanh], A in {0.8, 0.9, 1.0), Cý in {1.0}.
ogbn-mag:
Non-Private GCN: Ir in {0.001, 0.002, 0.003], nmme in {1, 2}. Noec in {1. 2}. Batch Size (1000, 4096, 5000, 10000). Activation in (ReLU, Tanh}. K {3, 5, 10).
DP-GNN: Ir (Adam) in {0.001, 0.003. 0.01), Ir (SGD) in {0.1, 0.5, 0.8, 1.0). Teme in {1, 2}. Mite in {1, 2). Batch Size in (1000, 4096, 5000, 10000), Activation in {ReLU, Tanh). X {1.0, 0.8, 0.5). Cy in {1.0, 2.0, 4.0), K in (3, (.).
Non-Private MLP: Ir in (0.001. 0.003, 0.01), Reac in {1, 2), náee in {1, Batch Size in (1000, 4096, 5000, 10000). Activation (ReL.U, Tanh).
DP-MLP: in {0.001, 0.003, 0.01), Mene {1, 2). Tate: in (1, 2), Batch Size in {1000, 4096, 5000, 100003. Activation in {ReLU, Tanb), À in {1.0, 0.8, 0.5). Cy in {1.0, 2.0, 4.0).
Additionally, the best hyperparameters corresponding each experiment reproduce the results in the main paper are reported in Table
21

---

Under review as a conference paper at ICLR 2022
Table 6: Best hyperparameters corresponding each method across datasets to reproduce the results in the main paper.
Method
Dataset
Batch Size
Activation
Ooen
Aike
Cj
ogbu-arxiv arxiv
0,001
1000
ReLU
2
10
Non
Private GCN
pronuproducts
0,001
1000
ReLU
2
10
ogbn-mas mag
0.001
5000
ReLU
ogbn-arse arxiv
0.003
10000
Tanh
1.0
1.0
DP-GNN (Adam)
ogbn- -roddutssutss
0.003
10000
ReLU
1
0.8
1.0
10
ogbn-mag
0.001
4096
Tanh
1
1.0
4.0
5
ogbn-arxiv
1.0
10000
Tanh
1.0
DP-GNN (SGD)
ogbn- pron-products
1.0
10000
ReLU
1.0
ogbn-mag
1.0
10000
RcLU
2
1.0
1.0
5
ogbn-arxiv
0.001
1000
ReLU
2
Non Private MLP
ogbn- cebn-products
0.001
1000
RcLU
ogbn-mag mag
0.01
1000
Tanh
2
ogbn-arxiv 0.003
10000
Tanh
2
1.0
1.0
Private MLP
cebn-products
0.002
10000
ReLU
0.8
1.0
Lebn-mag
0.001
10000
RcLU
2
1.0
1.0
F CLASS-WISE ANALYSIS OF LEARNT MODELS
To better understand the performance of the private model compared the non-private baseline for our considering setting of multi-class classification at a node-level, we compare the accuracy of these two models for each dataset class-wise granularity. These results are summarized in Figure 3) We empirically observe that the performance of the private model degrades as the fre- quency of training data points for particular class decreases. This indicates that the model is able to classify data points of "frequent" classes with reasonable accuracy, but struggles with classifica- tion accuracy on the data points of "rarer" classes. This observation in line with previous claims from (Bagdasaryan et al. 2019 Fioretto et al., (2021) that infferentialll-priveee models generally perform disparately worse on redeerrepreeetee classes.
22

---

Under review as a conference paper at ICLR 2022
Method: GCN (Non-Private Model)
od: GCN
60-
100/00
(Ordored Frequancy)
Method: DP-GNN (Private Model)
Method: DP-GNN
GCH
CON DP-ONN
DA.CAN
62
02
Chu hrovean
Class 1Ordered by Trequency)
(a) ogbn-arxiv
(b) ogbn-products
Method: GCN (Non-Private Modell
1.0
Accursyy
0.6
0.4
0.0
Class [Grdered by Frequencyl
Method: DP-GNN (Private Model)
1.0
GEN GNN
Accuraoy
0.6
0.0
Class [ardered by Frequencyl
(c) ogbn-mag
Figure 3: Comparison of class-wise test accuracies of the non-private GCN model and private DP-GCN model on all datasets, ordered by the decreasing frequency of occurrence of classes in the training data from left to right. The dotted lines indicate the overall accuracy for the corresponding models. We observe that the private model performs relatively better for classes which have a high frequency in the training data, and the performance degrades as the frequency of the classes decreases.
23


Reviews:
[{"review_id": "jBO1ucnicFv", "reviewer": "Reviewer_Uu9v", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nThe stated privacy parameters of 30 seems high, although there have been other industrial use cases with such parameters.  I would be interested to know whether edge-level privacy with significantly lower privacy parameters actually ensures more privacy, in some sense, than node-level privacy with such a high parameter.  For edge-level, one can make statements about how if a node has a bounded number of edges, then one can make a node-level privacy guarantee by multiplying the privacy parameters accordingly.  It may not always be the case that you can go the other way, where node-level privacy of 30 gives a much lower edge privacy guarantee.\n\nThe privacy guarantee does not seem surprising because if any node is guaranteed to have at most K neighbors, then the node’s influence expands to K other nodes.  That is, to ensure edge level privacy, constant noise would ensure constant privacy parameters, but considering addition or removal of K edges, adding noise proportional to K would ensure constant privacy parameters.  Is the analysis presented here some how improving over this intuition or is there a more technical reason why this intuition breaks down?  This should be made more explicit.\n\nFor the experiments section, the gradient clipping procedure depends on the data, in particular the scaling factor.  The scaling factor is fine-tuned on each dataset, so is privacy really ensured?  Furthermore, an exhaustive grid search is done over several hyper-parameters.  In Figure 1, it looks like DP-MLP does better than DP-GNN for moderate privacy parameters, say < 7.  Is there any reason for why this might be and at what point would one method do better than another?\n\nAlthough the proposed procedure seems to improve over existing approaches for some privacy regimes, I would have liked to see more analysis on when the improvement actually occurs (when epsilon > some value).  Furthermore, there are several parameters that need to be tuned, so it is not clear if the extra privacy budget expended for choosing these parameters would actually lead to a better privacy guarantee than the edge-level privacy.  I also do not see the novelty in the algorithm, since we could just pre-process each node to have at most K edges then run an edge-level private algorithm to get the same node-level privacy guarantee.\n\n### UPDATE ###\nThe paper could significantly benefit from the feedback given here and the comments they plan to make.  I am still not convinced of the novelty here in the privacy analysis.  The authors point out that \"standard composition results do not allow for multiple changes in the input dataset\" but DP ensures group level privacy, so in particular can ensure k*eps-DP for groups of size k.  I will keep my score unchanged. \n", "summary_of_the_paper": "This work studies the problem of ensuring node-level privacy when training GNNs.  This privacy setting is much stronger than edge-level privacy because it considers the impact a single node can have on training, which may be connected to several other nodes, whereas edge-level privacy considers only the impact of a single edge in the graph.  \n", "summary_of_the_review": "Although the proposed procedure seems to improve over existing approaches for some privacy regimes, I would have liked to see more analysis on when the improvement actually occurs (when epsilon > some value).  Furthermore, there are several parameters that need to be tuned, so it is not clear if the extra privacy budget expended for choosing these parameters would actually lead to a better privacy guarantee than the edge-level privacy.  I also do not see the novelty in the algorithm, since we could just pre-process each node to have at most K edges then run an edge-level private algorithm to get the same node-level privacy guarantee.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "b6Qjhw-OjT_", "reviewer": "Reviewer_NdP7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The extension of the DP-SGD technique to the graph neural networks is very interesting, and the empirical performance seems improved.  I have the below questions.\n\n1. In algorithm 1, it aggregates subgraphs to get a set of subgraphs S_tr. And then it doesn't appear in any of the following steps. I'm confused about how it plays a role in the algorithm? \n\n2. One of the main modifications is that they subsample the neighborhood of each node to ensure that each node has only K neighbors. Then they add noise according to the sensitivity of aggregated gradient wrt an individual node. So basically, I think it works like using group privacy (also, there's a K*C term in lemma1). Somehow, I feel the algorithm just extends the traditional DP-SGD to something like the group privacy case (technically, the privacy is still at the node-level, but it just restricts the case to K corrected nodes). Then in the experimental sections, I feel the benefit over DP-MLP is from incorporating the graph information. Overall, the algorithm is not that very exciting. \n\n3. The paper claims that the mini-batch is uniformly sampled from all training nodes, which contrasts the sampling with replacement in the traditional method. What are the differences? There seems no discussion about why this modification is important for the privacy amplification results.\n\n4. For Table 2 and Table 3, what's the privacy parameter epsilon?\n\n\n", "summary_of_the_paper": "This paper proposes a private algorithm for Graph Neural Networks at the node level. The algorithm is based on some modifications to the DP-SGD, and it applies to directed graphs. The authors analyze the privacy guarantees through Renyi differential privacy and give amplified privacy guarantees for their algorithm. Empirical evaluation is provided to demonstrate the efficacy of the proposed algorithm.", "summary_of_the_review": "In summary, I think the technical contribution of this paper is not significant, but it's also worth having a DP algorithm for the GNNs.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Fn-gp8pj2SO", "reviewer": "Reviewer_Xcpu", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strong pints\n1. The main motivation of the paper is valid and active research area.\n2. It was written well and reasonable clear.\n\n## Weak Points\nEven though I have no experiences on private networks, I did some reading on it but try to judge the paper on mostly point of GNN view.\nHere is the points that I wanted to discuss with the authors.\n\n1. Differentially private networks protect training data from the end user. In this submission it is not clear from whom we need to protect node features and adjacency. Sometimes I thought they tried to protect node features and adjacency of each node from all rest of the nodes, but not sure. Thus, the usage scenario should be given by a toy example. For instance in (Wu et al., 2021b) there is great example scenario where Bob is customer  has node features and Alice is ML developer has adjacency. Bob sends this data to Alice to develop a GNN for some specific tasks. Alice should provide a trained model where Bob cannot find any part of adjacency by querying to trained model. So their aim is to provide edge level data privacy. Here the aim is to provide privacy both node feature and edge information, it seems the node features and adjacency should not be known by other nodes. But what about server side if the model is centralize? Do the central model knows all raw train data? \n\n2. In Related Work section, Graph level prediction tasks was cited as they are in different contexts. However, graph based prediction or node level predictions are not so different to each other. Any GNN architecture can be used for either node (or edge) or graph level prediction. Just the differences is to apply graph level readout after last GNN layer. So, whatever exist in graph level task while preserving privacy should be direct competitor of the proposed method. \n\n3. Node based prediction under transductive problem settings is the easiest problem setting for GNN. Because there is just one graph and  the graph is known in advance. Transferabililty from train graph to the test graph is not the problem. As it is mentioned example scenario in Introduction, the method must be tested under inductive problem settings, where the GNN learns something from train graph ( in example large enterprise) and tested on test graph ( small enterprise). In this way we can see if the learned coefficient can be transferable to the another graph well or not.\n\n4. The authors main concentration was on node level tasks. However there are much more important tasks on graph level prediction while node level privacy is still important (as the same scenario in Introduction, train graphs would belongs some enterprises and task would be predict something about each enterprise. Then we can test given new enterprise's graph by predicting enterprises level output).  The experiments can be extended on this context.\n\n5. Although  (Wu et al., 2021a)'s proposition was tested on bipartite graphs (user to items graphs), since they used a general GNN (the GNN architecture was not changed for bipartite graphs), it can easily extendable on concerned dataset in the paper. Thus their proposal has strong connection to this paper. I think the differences should be discussed in the paper and their method should be used as another baseline.\n\n6. Eq1 and Eq2 are not the general formulation of GNN. Usually we show it by message aggregation and update functions.  More specifically, the author defines GNN as arbitrary number of MLP on node features, aggregation operation based on graph adjacency, followed by arbitrary number of MLP on aggregated features. They used exactly one layer of aggregation but one or two MLP for both on node features and aggregated features.  For sure this equation defines a GNN, but not definitely GCN (Kipf 2016) GAT (velickovic, 2018) and other mentioned models (GIN, Xu 2018, GraphSage Hamilton 2017).\n\n7. Seems in the literature, differentially private networks results were performed for different privacy costs(Abadi et al., 2016). In this submission, it is selected as \\epsilon=30. It had better if we can see the result under different privacy cost in 2D plot, like Cost-accuracy scatter plot. I would like to know at what privacy cost, the accuracy of proposed method will be the same with non-private GNN.\n\n8. Is there any specific reason to do analyse for just single GNN layer? Is it extendable for arbitrary number of GNN layers?\n\n9. Does any specific GNN methods (GCN, GAT, ChebNet, GIN ...) perform better than others? In the paper just one type of special GNN (given in Eq1-2) is used. Can any well-known GNN be used in this context?\n\n\n\n \n\n   \n\n\n\n", "summary_of_the_paper": "The paper claim to proposed a novel training method of GNN under providing both node feature and adjacency privacy. Their main approach is to use existed differential privacy framework into GNN world. They claim that providing privacy on both node feature and their connectivity is novel. ", "summary_of_the_review": "Proposed method seems an application of existed DP method for the graph data. So the novelty of the paper is limited. Experimental section is insufficient. I recommend rejection for this paper. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "7S4o-o12u0P", "reviewer": "Reviewer_upoR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1.\tIt is the first work to provide strong privacy guarantees for each individual node in graph learning, and designs an optimization algorithm to achieve that;\n2.\tIt theoretically proves that the proposed algorithm is guaranteed to be differential private;\n3.\tThe paper is well-structured and easy to follow.\n\nWeakness: \n1. This work proves the differential privacy only on 1-layer GNNs. The methodology is directly extended from (Abadi et al., (2015)) and Feldman et al. (2018), with the consideration that a subset of K neighbors could appear in each update step. However, usually two or more layers are used for the graph-related tasks. Showing the form of DP in the more general r-layer case would make the contribution more significant.\n\n2. The experiments are not complete. Why other DP GNN approaches are not compared with? It only compared with vanilla GCN and MLP.\n\n3. The introduction is a little unclear. It talks about “preserves the privacy of the features of each node (‘user’), their labels as well as their connectivity information”, which is a little vague and no examples are provided to show the kind of privacy it can preserve. From the methodology and proof part, it seems to be that whether the graph containing a certain node cannot be detected. As a result, the motivation and application of preserving this type of privacy is not well-introduced.\n\nBesides, the introducing of background in introduction seems to be incorrect.  It introduced (Zhou et al., 2020b) as an existing work on “bi-partite graphs or node-level privacy without preserving individual connectivity”, but that work does not focus on graph at all. \n\nA typo seems to exist in proof of Lemma 7, should the ρ’ in first equation be changed to ρ?", "summary_of_the_paper": "This paper aims to achieve node-level differential privacy on GNNs. Through adding noises to calculated gradients at each optimization step, this work shows that trained GNN layer can be (α, γ) node-level Renyi differentially-private. Concretely, this work considers the 1-layer GNN case, and make the maximum degree of each node to be K. With these requirements, this work theoretically prove the scale of noises.\n\nIts contributions are as follows:\n1.\tPropose the task of learning node-level differential private GNNs,\n2.\tAdapt DP-SGD to work on graphs, through extending amplified privacy guarantee,\n3.\tEvaluate proposed optimization algorithm on benchmark graph datasets. ", "summary_of_the_review": "This paper considers the node-level DP problem on graphs, which is the first work on this task as far as I can see.  The problem is formally defined, and guaranteed privacy is proved. \n\nThe methodology is directly extended from (Abadi et al., (2015)) and Feldman et al. (2018), with the consideration that a subset of K neighbors could appear in each update step. However, the proof is incomplete as only 1-layer GNN is considered. Furthermore, none of existing DP GNNs are adopted as baseline approaches.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper received some additional discussion between the reviewers and the area chair. The reviewers were largely unswayed by the author responses. One concern was the level of technical novelty, feeling that this was largely a straightforward adaptation of DPSGD (as, admittedly, most works in the DP ML setting are). The primary technical contribution may be the sampling amplification theorem, which one reviewer felt was also straightforward from previous work. Other criticisms was that the privacy parameter epsilon is rather large, and that results are restricted to 1-layer GNNs. Generally, the work did not feel very novel to reviewers from either the privacy or the GNN community. However, they felt that the paper could benefit substantially from exploration and implementation of the comments made in the responses, so the authors are encouraged to pursue those directions. Some of the many suggestions from reviewer Xcpu may help the authors make the paper appeal more to the GNN community.
Decision: Reject