NODE-LEVEL DIFFERENTIALLY PRIVATE GRAPH NEURAL NETWORKS
Year: 2021

Abstract:
Graph Neural Networks (GNNs) are a popular technique for modelling graphstructured data that compute node-level representations 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, such as differentially private stochastic gradient 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 1-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 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.

heading: 1 INTRODUCTION
text: Graph Neural Networks (GNNs) are powerful modeling tools that capture structural information provided by a graph. Consequently, they have become popular in a wide array of domains such as biology (Ktena et al., 2018), medicine (Ahmedt-Aristizabal et al., 2021), 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 a given node in the graph, thus evading the challenge of data scarcity 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 recommendation/ranking tasks, where it is challenging to obtain and store user data (Fan et al., 2019; Budhiraja et al., 2020; Levy et al., 2021).
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 is 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 an individual node/user.
In this work, we study the problem of designing algorithms to learn GNNs while preserving nodelevel privacy, i.e., preserving both the features as well as connectivity information of an individual node. We use differential privacy as the notion of privacy (Dwork et al., 2006) of a node, which roughly-speaking requires that the algorithm should learn similar GNNs despite perturbation of an entire node and all the data points or predictions associated with that node.
Example scenarios for such a solution include ranking/recommendation of entities like documents/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
accurate ranking of emails/documents. Naturally, user interaction data as well as individual users’ features (like the topics in which user is interested in) would be critical to preserve, and any revelation of such data can be catastrophic. Furthermore, once GNNs are learned to model users while preserving privacy, they can be used in different settings based on the problem requirement. For example, in settings where a node can access it’s r-hop neighbors data, we can directly apply r-layer 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 a small enterprise, where at 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.
Recent works have explored the problem of differentially private learning of GNNs, but they either consider a restricted setting of edge-level privacy which is 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; Bassily et al., 2014; Abadi et al., 2016) 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 a 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 on multiple users. Note that the standard privacy by amplification method only applies to scenarios where each point corresponds to one user/entity. By combining the above two results with the standard Rényi Differential Privacy (RDP) accounting, we obtain a 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 1-layer GCN models, while providing privacy parameters of about ≤ 30 which are close to the industry standard. More critically, compared to standard 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, we 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 a 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:
• Formulation: In Section 3, we formalize the problem of node-level differentially private GNNs, and discuss various important settings in which a solution to the problem is applicable.
• Method: In Section 4, we describe our algorithm that adapts standard DP-SGD to train differentially private GNNs, with a strong privacy guarantee that extends standard privacy amplification by sampling.
• Empirical Evaluation: In Section 5, we evaluate our framework on multiple benchmark graph datasets on the task of node classification. We demonstrate that our DP-GNN method can outperform non-private and private MLP methods that cannot utilize graph information.

heading: 2 RELATED WORK
text: 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., 2017), and model-aware methods such as DP-SGD (Abadi et al., 2016), which augment the standard paradigm of gradientbased training to be differentially private. DP-SGD, in particular, has been used successfully to train neural network models to classify images (Abadi et 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 (Veličković et al., 2018), GraphSAGE (Hamilton et al., 2017), and Message-Passing Neural Networks (Gilmer et al., 2017), to name a few. Broadly, these models compute node-level representations via aggregation of neighbourhood-level
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., 2021b) but they do not preserve node-level data. Private GNNs have also been studied from the perspective of local privacy (Sajadmanesh & Gatica-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 to 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., 2021a) 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 (Shan et al., 2021) to create privacy-preserving GNNs exist, but these do not use the formal notion 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 a node’s features and labels only, we 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 a pair of nodes can often be sensitive information in itself. Further, our approach extends the standard approaches of gradient-based training to scalably train node-level differentially private GNNs in a centralized setting, without any access to public data. Depending on the required privacy setting, this mechanism can be composed with locally differentially private mechanisms to generate node-level predictions.
In different contexts, there has been extensive work on node-level DP (Raskhodnikova & Smith, 2016; Karwa et al., 2011; 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.

heading: 3 PROBLEM FORMULATION AND PRELIMINARIES
text: Consider a graph dataset G = (V,E,X,Y) with directed graph G = (V,E) represented by a adjacency matrix A ∈ {0, 1}n×n. n is the number of nodes in G, V denotes the node set, E denotes the edge set. Each node v in the graph is equipped with a feature vector Xv ∈ Rd; X ∈ Rn×d denotes the feature matrix. Y ∈ Rn×Q is the label matrix and yv is the label for the v-th node 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 yv are only provided for a subset of nodes Vtr ⊂ V , called the training set. Given the graph dataset G, the goal is to learn parameters of a one-layer GNN while preserving privacy of individual nodes. A GNN can be represented by the following operations:
ŷv = GNN(A,X, v; Θ) := fdec (fagg ({fenc(Xu) |Avu 6= 0})) (1)
where ŷv is the prediction from the GNN for a given node v, fenc is the encoder function that encodes node features with parameters Θenc, fagg is the neighborhood aggregation function with parameters Θagg, fdec is the prediction decoder function with parameters Θdec, and Θ := (Θenc,Θagg,Θdec).
While our results apply to most 1-layer GNN models (Hamilton et al., 2017; Veličković et al., 2018; Xu et al., 2018), for simplicity, we focus on 1-layer Graph Convolutional Network (GCN) models1 (Kipf & Welling, 2016). These GCN models use a multi-layer perceptron (MLP) for encoder and decoder functions, with non-linear activation function σ:
ŷv = GCN(A,X, v; Θ) := MLPdec (Avσ(MLPenc(X))Θagg) (2)
1 As is common in practice, we allow any normalization and addition of self-loops to A.
Thus, “learning” a GCN is equivalent to finding parameters Θ := (Θenc,Θagg,Θdec) that minimize a suitable loss:
Θ∗ = arg min Θ ∑ v∈V
`(ŷv; yv)︸ ︷︷ ︸ L(G,Θ)
(3)
where ` : RQ×Q → R is a standard loss function such as categorical cross-entropy.2
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 can be obtained by adding or removing a node (with its features, labels and associated edges) to the other. That is, G and G′ are exactly the same except for the v-th node, i.e., Xv , yv and Av differ in the two datasets.
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 a graph dataset. A is said to be (α, γ) node-level Rényi differentially-private (Mironov, 2017b) if, for every pair of node-level adjacent datasets G and G′:
Dα(A(G) ‖ A(G′)) ≤ γ, where Rényi divergence Dα of order α between two random variables P and Q is defined as:
Dα(P ‖ Q) = 1
α− 1 lnEx∼Q
[ P (x)
Q(x)
]α .
Note that we use Rényi differentially-private (RDP) (Mironov, 2017b) as the formal notion of differential privacy (DP), as it allows for tighter composition of DP across multiple steps. This notion is closely related to the standard (ε, δ)-differential privacy (Dwork et al., 2006); Proposition 3 of Mironov (2017b) states that any (α, γ)-RDP mechanism also satisfies (γ + log 1/δα−1 , δ)-differential privacy for any 0 < δ < 1.
Thus, the goal is to find Θ by optimizing equation 3 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 is 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 a graph dataset affects its entire local neighbourhood, which can be a very large set of nodes. This is in contrast to the standard 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 are critical in our design and analysis of a private GNN learning method. Definition 3. The node-level sensitivity ∆(f) of a function f defined on graph datasets is:
∆(f) = max node-level adjacent
G,G′
‖f(G)− f(G′)‖2
The K-restricted node-level sensitivity ∆K(f) of a function f defined on graph datasets is: ∆K(f) = max
deg(G), deg(G′)≤K node-level adjacent
G,G′
‖f(G)− f(G′)‖2
Definition 4. We define the clipping operator ClipC(.) as: ClipC(v) = min (
1, C‖v‖F
) · v, for any
vector or matrix v. 2 The analysis here holds for multi-label settings as well, which would instead use loss functions such as sigmoidal cross-entropy, for example.
Algorithm 1: DP-GNN (SGD): Differentially Private Graph Neural Network with SGD Data: Graph G = (V,E,X,Y), GNN definition GNN, Training set Vtr, Loss function L,
Batch size m, Maximum degree K, Learning rate η, Clipping threshold C, Noise standard deviation σ, Maximum training iterations T .
Result: GNN parameters ΘT . Note that Vtr is the subset of nodes for which labels are available (see Paragraph 1 of Section 3). Using Vtr, construct the set of training subgraphs Str with Algorithm 2. Construct the 0− 1 adjacency matrix A: Avu = 1 ⇐⇒ (v, u) ∈ Str Initialize Θ0 randomly. for t = 0 to T do
Sample set Bt ⊆ Vtr of size m uniformly at random from all subsets of Vtr. Compute the update term ut as the sum of the clipped gradient terms in the batch Bt:
ut ← ∑ v∈Bt ClipC(∇Θ` (GNN(A,X, v; Θt); yv))
Add independent Gaussian noise to the update term: ũt ← ut +N (0, σ2I) Update the current estimate of the parameters with the noisy update: Θt+1 ← Θt − ηm ũt
end

heading: 4 LEARNING GRAPH CONVOLUTIONAL NETWORKS (GCN) VIA DP-SGD
text: In this section, we provide a 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 a subset Bt of m nodes chosen uniformly at random from the set Vtr of training nodes. In contrast to the standard mini-batch SGD, that samples points with replacement for constructing a mini-batch, our method samples mini-batch Bt 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 O(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 Nv̂. So, to ensure the privacy of each update, we add noise according to the sensitivity of aggregated gradient ∇ΘL(Bt; Θt) := ∑ v∈Bt ClipC(∇Θ` (GCN(A,X, v; Θt); yv)) wrt an individual node v̂. To this end, we provide a finer bound in Lemma 1 on the sensitivity of ∇ΘL(Bt; Θt) based on the maximum degree of the graph G.
In traditional DP-SGD, a crucial component in getting a better privacy/utility trade-off over just adding noise according to the sensitivity of the minibatch gradient, is privacy amplification by sampling (Kasiviswanathan et al., 2008; Bassily et al., 2014). This says that if an algorithm A is ε-DP on a data set D1, then on a random subset D2 ⊆ D1 it satisfies roughly |D2||D1| (e
ε − 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 neighborsNv̂ get modified. To complicate things further, the minibatch Bt that gets selected may only contain a small random subset ofNv̂. To address these issues, we provide a new privacy amplification theorem (Theorem 1). To prove the theorem, we adapt (Feldman et al., 2018, Lemma 25) – that shows a weak form of convexity 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,Θ) = ∑ v∈Vtr ` (GCN(A,X, v; Θt); yv) . Recall, N is the number of training nodes Vtr, K is an upper bound on the maximum degree of the input graph, and m is the batch size.
For any choice of the noise standard deviation σ > 0 and clipping threshold C, every iteration t of Algorithm 1 is (α, γ) node-level Rényi DP, where:
γ = 1
α− 1 lnEρ
[ exp ( α(α− 1) · 2ρ 2C2
σ2
)] , ρ ∼ Hypergeometric(N,K + 1,m).
Hypergeometric denotes the standard hypergeometric distribution (Forbes et al., 2011).

heading: By the standard composition theorem for Rényi Differential Privacy (Mironov, 2017b), over T iterations, Algorithm 1 is (α, γT ) node-level Rényi DP, where γ and α are defined above.
text: See Appendix A for a detailed proof.
Remark 1: Roughly, for m K and for T = O(1), the above bound implies σ = O(K) noise to be added per step to ensure RDP with α = O(1) and γ = 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.
Remark 2: We provide node-level privacy, that is the method preserves neighborhood information of each node as well. But, we require asymmetric/directed 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 a variety of settings, for example, in social networks when the graph is constructed by “viewership” data, edge (v, v′) exists iff user v viewed a post from user v′.
Remark 3: While we provide a formal privacy guarantee for 1-layer GCNs, the same applies for any 1-layer GNN model.
Remark 4: We adapt a DP version of the Adam (Kingma & Ba, 2014; TFP) optimizer to the GNN setting, called DP-GNN (Adam), with details in Appendix D.
Privacy at Inference Time: Note that Theorem 1 guarantees that the GCN parameters Θ that are learnt via Algorithm 1 preserve privacy. However, unlike standard ML models where prediction for each point depends only on the model parameters Θ and the point itself, the privacy of Θ 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 Nv . Broadly, there are three settings where we can 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 features 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 a variety of activities/documents/photos of their friends (neighbors).
2. Node features are completely private. In this setting, a node v does not have direct access to the features of its neighborsNv . 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 a 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 a private ranking/recommendation 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.

heading: 5 EXPERIMENTAL RESULTS
text: In this section, we present empirical evaluation of our method on standard benchmarks from the widely used Open Graph Benchmark (OGB) suite (Hu et al., 2020). The goal is to demonstrate that our method (DP-GNN) can indeed learn privacy preserving 1-layer GCNs accurately.
As mentioned earlier, in several data critical scenarios, practitioners cannot use sensitive graph information, 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 our method are both standard non-private MLP models as well as differentially private MLP models trained using DP-SGD and DP-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.

heading: 5.1 DATASETS AND SETUP
text: OGB datasets: We use three moderate-to-large sized node classification datasets from OGB suite3: 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 a paper citation network of arxiv papers and consists of around 169K nodes, while the ogbn-mag dataset is 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 ogbnproducts dataset is 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 et al., 2020). Finally, following (Hu et al., 2020), 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 in Vtr have labels available. See Appendix E for additional details about the datasets.
Gradient Clipping: For DP-GNN, we perform layer-wise gradient clipping, i.e., the gradients corresponding to the encoder, aggregation and decoder functions are clipped independently with different clipping thresholds. For each layer, the clipping threshold C in Algorithm 1 is chosen as Cf ×C% where Cf is a scaling factor and C% is the 75th percentile of gradient norms for that layer at initialization on the training data. We finetune the Cf parameter for each dataset. We set the noise for each layer σ such that the noise multiplier λ = σ2(K+1)C is identical for each layer, where σ/λ is essentially the sensitivity. It is not hard to observe that the overall privacy cost only depends on λ.
Methods: We benchmark the following methods: a) DP-GNN: Our method (Algorithm 1) specialized 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).
Detailed Setup and Hardware: DP-GNN and all the aforementioned baselines are implemented in TensorFlow 2.0 (Abadi et al., 2015) using Graph Nets4 and Sonnet5. 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 1.
Hyperparameter Tuning: We perform exhaustive grid search over batch size, learning rate, activation functions, and number of encoder and decoder MLP layers for the non-private baselines.
3 ogb.stanford.edu/docs/nodeprop 4 github.com/deepmind/graph nets 5 github.com/deepmind/sonnet
Additionally, we tune over noise multiplier (σ in Algorithm 1) and clipping thresholds for the private baselines. We provide detailed information regarding the hyperparameters in Appendix E.
Results: Table 1 compares DP-GNN’s accuracy against baselines on the ogbn-arxiv, ogbn-products and ogbn-mag datasets. We extensively tune baselines on the three datasets as mentioned above and are able to replicate, and in 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.
Overall, we 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 ε ≤ 30. For example, for ogbn-arxiv dataset, our method DP-GNN (SGD) is about 8% more accurate than MLP and 10% more accurate than DP-MLP. Similarly, for ogbn-products our method is about 5% more accurate than both MLP and DP-MLP. Note that we also present numbers for DP-GNN (Adam) (see Appendix D) that uses Adam as the optimizer instead of SGD, as mentioned in Algorithm 1. Also, note that for the rest of the section we use DP-GNN (Adam) for generating accuracy numbers.
Next, Figure 1 provides a comparison of epsilon vs test set accuracy for the three benchmark datasets. Note that for ε ≥ 10, DP-GNN is significantly more accurate than DP-MLP. It is interesting to note that for about ε ≥ 10, the accuracy of the DP-MLP saturates and does not increase significantly. In contrast, the accuracy of DP-GNN keeps on increasing with larger ε, and is in general much higher than both MLP and DP-MLP for higher values of ε. Finally, on ogbn-products, DP-GNN is about 5% more accurate than DP-MLP for the entire range of considered values for ε, and is about 2% more accurate than MLP for ε = 10.
Typically, for training non-convex learning models with user-level DP, ε ≤ 10 has become a popular choice (Papernot et al., 2020; Kairouz et al., 2021). But as the problem is more challenging in the case of GNNs – multiple nodes can affect inference for a given node and we intend to protect privacy at the node-level – higher ε seems like a reasonable choice to encourage reasonable solutions. Moreover, as we observe on the ogbn-products dataset, larger dataset sizes can ensure better performance for the standard ε values as well. Also, our algorithms satisfy stronger Rényi DP properties (Mironov, 2017b), which provide additional protection over traditional (ε, δ)-DP guarantees.

heading: 5.2 ABLATION STUDIES
text: 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 of the learnt DP-GNN, up to a point. There are multiple effects at play here.
Larger batch sizes imply that the effective noise added per DP-SGD update step is smaller. Thus, training is more stable with larger batch sizes, as Figure 2 shows. Furthermore, effective privacy budget (ε) provided by amplification result has a term of the form exp(ε0) − 1 where ε0 is the privacy budget for a step. So, unless ε0 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, even in the non-private case, as 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
Table 2: GCN and DP-GNN on the ogbnarxiv dataset with different batch sizes. The privacy budget for DP-GNN is ε ≤ 30.
Batch Size GCN (AGCN) DP-GNN (ADP-GNN) AGCN −ADP-GNN 100 68.075 40.814 27.261 500 68.393 58.882 9.511
1250 68.572 61.307 7.265 2500 68.356 63.025 5.331 5000 68.490 64.345 4.145 10000 68.062 64.304 3.758 20000 68.491 62.062 6.429
Table 3: GCN and DP-GNN on the ogbnarxiv dataset with different degrees. The privacy budget for DP-GNN is ε ≤ 30.
Degree GCN (AGCN) DP-GNN (ADP-GNN) AGCN −ADP-GNN 3 68.563 63.439 5.124 5 69.020 63.940 5.080 7 68.945 64.599 4.346 10 68.372 64.103 4.269 15 68.224 63.522 4.702 20 68.642 63.054 5.588 32 68.152 61.901 6.251
5 10 15 20 25 30 Epsilon (Privacy Parameter)
20
30
40
50
60
Te st
A cc
ur ac
y
Batch Size 500 2500 10000 20000
(a) Varying Batch Size m
5 10 15 20 25 30 Epsilon (Privacy Parameter)
45.0
47.5
50.0
52.5
55.0
57.5
60.0
62.5
65.0
Te st
A cc
ur ac
y
Degree 3 5 10 32
(b) Varying Maximum Degree K
Figure 2: Ablation studies on DP-GNN on 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 a batch size of 10000, the accuracy goes down, as quantified by Table 2.
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 a trade-off: a smaller K means lesser differentially private noise added at each update step, but also fewer neighbours for each node to aggregate information from.
Finally, we also conduct experiments to understand performance of DP-GNN conditioned on the frequency of a 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 to 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 et al., 2019; Fioretto et al., 2021) that differentially-private models generally perform worse on low-frequency classes, and represent a critical future direction to study.

heading: 6 CONCLUSIONS AND FUTURE WORK
text: In this work, we proposed a method to 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 a 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 4 such as different train and test graph datasets, and understanding utility bounds for GNNs with node-level privacy.

heading: 7 REPRODUCIBILITY STATEMENT
text: We have taken all efforts to ensure that the results produced in the paper and the submitted material are reproducible, and the methodology is easy to follow. For our theoretical contributions, we have discussed the problem setup and preliminaries in Section 3, provided a detailed algorithm for our proposed methodology in Section 4 for a sound theoretical understanding of the problem
and our solution. For our empirical results, we have detailed the information needed to reproduce the empirical results in Section 5 of the main paper and Appendix E. 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 to our experiments. We are working towards an open source implementation, in the spirit of reproducible research.

heading: 8 ETHICS STATEMENT
text: The interest in differentially-private models largely stems from a need to protect the privacy of data samples used to train these models. While we have proposed a mechanism here to learn GNNs in privacy-preserving manner, differential privacy seems to exacerbate existing fairness issues on underrepresented classes as Appendix F indicates. This is 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., 2021) 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.

heading: A LEMMAS AND PROOFS
text: Lemma 1 (Node-Level Sensitivity of any 1-Layer GCN). Consider the loss function L of the form: L(G,Θ) = ∑ v∈V ` (GCN(A,X,v; Θ); yv) .
Let Bt be any choice of m unique nodes from a graph G with maximum degree bounded above by K. Consider the following quantity ut from Algorithm 1:
ut(G) = ∑ v∈Bt ClipC(∇Θ` (GCN(A,X, v; Θt); yv))
Note that ut(G) is a ‘clipped’ version of∇ΘL(Bt; Θt, G): ∇ΘL(Bt; Θt,G) = ∑ v∈Bt ∇Θ` (GCN(A,X, v; Θt); yv)
Then, the following inequality holds:
∆K(ut) < 2(K + 1)C.
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 a single node v̂ from G. We wish to bound the following quantity:
‖ut(G)− ut(G′)‖F For convenience, for any node v, we denote the corresponding loss terms `v and `′v as:
`v = ` (GCN(A,X, v; Θt); yv) `′v = ` (GCN(A ′,X′, v; Θt); yv)
From the definition of `v , it is clear that the only gradient terms ∇Θ`v affected when adding or removing node v̂, are those of its neighbors and v̂ itself. Thus,
ut(G)− ut(G′) = ClipC(∇Θ`v̂) · I[v̂ ∈ Bt] + ∑ u∈Nv̂ (ClipC(∇Θ`u)− ClipC(∇Θ`′u)) · I[u ∈ Bt]
where I is the indicator random variable. Taking norms:
‖ut(G)− ut(G′)‖F
= ∥∥∥∥∥∥ClipC(∇Θ`v̂) · I[v̂ ∈ Bt] + ∑ u∈Nv̂ (ClipC(∇Θ`u)− ClipC(∇Θ`′u)) · I[u ∈ Bt] ∥∥∥∥∥∥ F
≤ ‖ClipC(∇Θ`v̂) · I[v̂ ∈ Bt]‖F + ∑ u∈Nv̂ ‖(ClipC(∇Θ`u)− ClipC(∇Θ`′u)) · I[u ∈ Bt]‖F
(triangle inequality) ≤ ‖ClipC(∇Θ`v̂)‖F + ∑ u∈Nv̂ ‖(ClipC(∇Θ`u)− ClipC(∇Θ`′u))‖F
(I ∈ {0, 1}) ≤ ‖ClipC(∇Θ`v̂)‖F + ∑ u∈Nv̂ ( ‖ClipC(∇Θ`u)‖F + ‖ClipC(∇Θ` ′ u)‖F ) (triangle inequality)
≤ C + ∑ u∈Nv̂ (C + C)
(gradient clipping) = C + dv̂ · 2C
(definition of dv̂) = C(2dv̂ + 1) ≤ C(2K + 1) < 2(K + 1)C.
(dv̂ ≤ K,C > 0)
As G and G′ were an arbitrary pair of node-level adjacent graph datasets,
∆K(ut) = max deg(G), deg(G′)≤K
node-level adjacent G,G′
‖ut(G)− ut(G′)‖F
< 2(K + 1)C.
The proof for the bound on ∆K(ut(G)) when a new node v̂ is added to the graph G follows analogously.
Lemma 2 (Un-amplified Privacy Guarantee for Each Iteration of Algorithm 1). Every iteration t of Algorithm 1 is (α, γ) node-level Rényi DP for when run on graphs with maximum degree ≤ K where:
γ = α · (∆K(ut))2
2σ2
Here ∆K(·) is the K-restricted node-level sensitivity from Definition 3.
Proof. Follows directly from (Mironov, 2017a, Corollary 3).
Lemma 3 (Distribution of Loss Terms Per Minibatch). For any iteration t in Algorithm 1, consider the minibatch Bt of subgraphs. For any subset S of d unique nodes, define the random variable ρ as |S ∩ Bt|. Then, the distribution of ρ follows the hypergeometric distribution Hypergeometric(N, d,m):
ρi = P [ρ = i] =
( d i )( N−d m−i )( N m
) . where N is the total number of nodes in the training set Vtr and |Bt| = m is the batch size.
Proof. The minibatches Bt in Algorithm 1 are formed by sampling nodes from Vtr without replacement. When ρ = i, one needs to pick i nodes from S and the remaining m − i nodes from
Vtr − S to form a batch of size m. Clearly, there are (|S| i ) = ( d i ) ways to do the first step, and(|Str|−|S|
m−i ) = ( N−d m−i ) to do the second step. Finally, there are ( N m ) ways to choose a minibatch Bt of
size m, each choice equally likely. In conclusion, we can claim:
P [ρ = i] =
( d i )( N−d m−i )( N m
) which is exactly the Hypergeometric(N, d,m) distribution.
Lemma 4 (Adaptation of Lemma 25 from Feldman et al. (2018)). Let µ0, . . . , µn and ν0, . . . , νn be probability distributions over some domain Z such that:
Dα(µ0 ‖ ν0) ≤ ε0 . . .
Dα(µn ‖ νn) ≤ εn
for some given ε0, . . . , εn.
Let ρ be a probability distribution over [n] = {0, . . . , n}. Denote by µρ (respectively, νρ) the probability distribution over Z obtained by sampling i from ρ and then outputting a random sample from µi (respectively, νi). Then:
Dα(µρ ‖ νρ) ≤ lnEi∼ρ [ eεi(α−1) ] = 1
α− 1 ln n∑ i=0 ρie εi(α−1).
Proof. Let µ′ρ (respectively ν ′ ρ) be the probability distribution over [n]× Z obtained by sampling i from ρ and then sampling a random x from µi (respectively, νi) and outputting (i, x). We can obtain µρ from µ′ρ by applying the function that removes the first coordinate; the same function applied gives νρ from ν′ρ. Therefore, by the post-processing properties of the Renyi divergence, we obtain that:
Dα(µρ ‖ νρ) ≤ Dα(µ′ρ ‖ ν′ρ).
Now, observe that for every i ∈ [n] and x ∈ Z, µ′ρ(i, x) = ρi · µi(x). Therefore,
Dα(µ ′ ρ ‖ ν′ρ) =
1
α− 1 lnE(i,x)∼ν′ρ
[ µ′ρ(i, x)
ν′ρ(i, x) ]α = 1
α− 1 lnEi∼ρ
[ Ex∼νi [ µi(x)
νi(x) ]α] = 1
α− 1 lnEi∼ρ
[ eεi(α−1) ] = 1
α− 1 ln n∑ i=1 ρie εi(α−1)
as required.
Lemma 5. Let X be a non-negative continuous random variable with cumulative distribution function FX and density fX . Let g : R≥0 → R be a differentiable function. Then:
E[g(X)] = g(0) + ∫ ∞
0
g′(x)(1− FX(x)) dx
Proof. ∫ ∞ 0 g′(x)(1− FX(x)) dx = ∫ ∞ 0 g′(x) Pr [X > x] dx
= ∫ ∞ 0 g′(x) ∫ ∞ x fX(t) dt dx
= ∫ ∞ 0 ∫ ∞ x g′(x)fX(t) dt dx
= ∫ ∞ 0 ∫ t 0 g′(x)fX(t) dx dt
= ∫ ∞ 0 fX(t) (∫ t 0 g′(x) dx ) dt
= ∫ ∞ 0 fX(t) (g(t)− g(0)) dt = E[g(X)− g(0)] = E[g(X)]− g(0).
as claimed.
An analogous inequality holds for discrete random variables, taking values on Z. Lemma 6. Let X be a discrete random variable taking values on Z with cumulative distribution function FX and probability mass function fX . Let g : Z→ R be a function. Then:
E[g(X)] = g(0) + ∞∑ x=0 (g(x+ 1)− g(x))(1− FX(x)).
Proof. The proof is identical to that of Lemma 5, by replacing integrals with sums.
Lemma 7. Let ρ and ρ′ be two random variables with the hypergeometric distribution:
ρ ∼ Hypergeometric(N, k,m) ρ′ ∼ Hypergeometric(N, k′,m)
such that k ≥ k′. Then, ρ stochastically dominates ρ′:
Fρ′(i) ≥ Fρ(i) for all i ∈ R
where Fρ (respectively, Fρ′ ) is the cumulative distribution function (CDF) of ρ (respectively, ρ′).
Proof. Note the following representation of the hypergeometric random variable as the sum of dependent Bernoulli random variables:
ρ = m∑ i=1 Xi
where each Xi ∼ Bernoulli( kN ). Similarly, we have:
ρ′ = m∑ i=1 X ′i
where each X ′i ∼ Bernoulli(k ′ N ). Now, as k ≥ k ′, by a simple analysis for Bernoulli random variables, each X ′i is stochastically dominated by Xi:
FX′i ≥ FXi .
for each i ∈ {1, . . . ,m}. Thus, as sums preserve stochastic dominance:
Fρ′ = F∑N i=1X ′ i ≥ F∑N i=1Xi = Fρ (4)
as required.
Lemma 8. Let ρ and ρ′ be two non-negative random variables such that ρ stochastically dominates ρ′:
Fρ′(i) ≥ Fρ(i) for all i ∈ R where Fρ (respectively, Fρ′ ) is the cumulative distribution function (CDF) of ρ (respectively, ρ′).
Let g : R≥0 → R be a non-decreasing differentiable function. Then, the following inequality holds: E[g(ρ′)] ≤ E[g(ρ)].
Proof. We first argue for the case where both ρ and ρ′ are continuous. By Lemma 5, we have that: E[g(ρ)] = g(0) + ∫ ∞
0
g′(x)(1− Fρ(x)) dx
E[g(ρ′)] = g(0) + ∫ ∞
0
g′(x)(1− Fρ′(x)) dx.
and hence:
E[g(ρ)]− E[g(ρ′)] = ∫ ∞
0
g′(x)(Fρ′(x)− Fρ(x)) dx.
As g is non-decreasing, we have that g′ ≥ 0 everywhere. The theorem now follows directly. The case where both ρ and ρ′ are discrete can be handled analogously, by using Lemma 6 above instead.
We are now ready to supply the proof of the main theoretical result in this paper, Theorem 1.
Proof of Theorem 1. We borrow notation from the proof of Lemma 1. 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̂ fromG. For convenience, for any node v, we denote the corresponding loss terms `v and `′v as:
`v = ` (GCN(A,X, v; Θ); yv) `′v = ` (GCN(A ′,X′, v; Θ); yv)
As in Lemma 1,
ut(G)− ut(G′) = ClipC(∇Θ`v̂) · I[v̂ ∈ Bt] + ∑ u∈Nv̂ (ClipC(∇Θ`u)− ClipC(∇Θ`′u)) · I[u ∈ Bt] (5)
where I is the indicator function. With the notation from Algorithm 1, we have: ũt(G) = ut(G) +N (0, σ2I), ũt(G ′) = ut(G ′) +N (0, σ2I).
We need to show that:
Dα(ũt(G) ‖ ũt(G′)) ≤ γ. Let S = {u | u = v or u ∈ Nv̂} be the set of nodes ‘affected’ by the removal of v̂. From Equation 5, we see that the sensitivity of ut depends on the number of nodes in S that are present in Bt:
‖ut(G)− ut(G′)‖F
= ∥∥∥∥∥∥ ClipC(∇Θ`v̂) · I[v̂ ∈ Bt] + ∑ u∈Nv̂ (ClipC(∇Θ`u)− ClipC(∇Θ`′u)) · I[u ∈ Bt] ∥∥∥∥∥∥ F
Let ρ′ be the distribution over {0, 1, . . . dv̂ + 1} of the number of ‘affected’ nodes in S present in Bt, that is, ρ′ = |S ∩ Bt|. Lemma 3 then gives us that the distribution of ρ′ is:
ρ′ ∼ Hypergeometric(N, dv̂ + 1,m). (6)
In particular, when ρ′ = i, exactly i nodes are sampled in Bt. Then, it follows by the same argument in the proof of Lemma 1 that:
∆K(ut | ρ′ = i) < 2iC.
Thus, conditioning on ρ′ = i, we see that every iteration is (α, γi) node-level Rényi DP, by Lemma 2 where:
γi = α · (2iC)2 2σ2 = α · 2i 2C2 σ2 . (7)
Define the distributions µi and νi for each i ∈ {0, . . . , dv̂ + 1}, as follows: µi = [ Ũ(G) | ρ′ = i ] νi = [ Ũ(G′) | ρ′ = i
] Then, by Equation 7:
Dα(µi ‖ νi) ≤ γi
For the mixture distributions µρ′ = Ũ(G) and νρ′ = Ũ(G′), Lemma 4 now tells us that:
Dα(U(G) ‖ U(G′)) = Dα(µρ′ ‖ νρ′)
≤ 1 α− 1 lnEi∼ρ′ [exp (γi(α− 1))]
= 1
α− 1 lnEi∼ρ′
[ exp ( α(α− 1) · 2i 2C2
σ2 )] = 1
α− 1 lnEρ′
[ exp ( α(α− 1) · 2ρ ′2C2
σ2 )] = 1
α− 1 lnE [f(ρ′)] . (8)
where:
f(ρ′) = exp ( α(α− 1) · 2ρ ′2C2
σ2 ) Define another distribution ρ as:
ρ ∼ Hypergeometric(N,K + 1,m).
As dv̂ ≤ K, by Lemma 7, ρ stochastically dominates ρ′. Then, as f is non-decreasing, Lemma 8 gives us:
E [f(ρ′)] ≤ E [f(ρ)] . (9)
It follows from Equation 8 and Equation 9 that:
Dα(Ũ(G) ‖ Ũ(G′)) ≤ 1
α− 1 lnEρ
[ exp ( α(α− 1) · 2ρ 2C2
σ2
)] = γ.
As this holds for an arbitrary pair of node-level adjacent graphs G and G′, we are done.

heading: B SAMPLING SUBGRAPHS
text: To bound the sensitivity of the mini-batch gradient in Algorithm 1, we must carefully bound both the in-degree and out-degree of any node in the graph across all training subgraphs. Algorithm 2 outputs a 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 at inference 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,X,Y), Training set Vtr, Maximum degree K. Result: Set of training subgraphs Str. for v ∈ V do
Initialize countv ← 0. Initialize subgraph Sv ← {v}. end Shuffle Vtr. for v ∈ Vtr do
for u ∈ Nv do If countu = K, continue. If countv = K, break. Add node u to subgraph Sv . Add node v to subgraph Su. Increment countu by 1. Increment countv by 1.
end end Construct Str ← {Sv | v ∈ Vtr}. return Str.

heading: C EXPERIMENTS WITH DIFFERENT GNN ARCHITECTURES
text: 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 et al., 2018) and GAT (Veličković et al., 2018) on the ogbn-arxiv dataset and report the results for the respective private and non-private models in Table 4. We use a variant of the original GAT architecture, utilizing dot-product attention instead of additive attention, with 10 attention heads.
We observe that DP-GNN performs reasonably well across different architectures.

heading: D LEARNING GRAPH CONVOLUTIONAL NETWORKS (GCN) VIA DP-ADAM
text: In Algorithm 3, we provide the description of DP-Adam, which adapts Algorithm 1 to use the popular Adam (Kingma & Ba, 2014) optimizer, instead of SGD. The privacy guarantee and accounting for Algorithm 3 is identical to that of Algorithm 1, since the DP clipping and noise addition steps are 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 η, Clipping threshold C, Noise standard deviation σ, Maximum training iterations T , Adam hyperparameters (β1, β2).
Result: GNN parameters ΘT . Note that Vtr is the subset of nodes for which labels are available (see Paragraph 1 of Section 3). Using Vtr, construct the set of training subgraphs Str with Algorithm 2. Construct the 0− 1 adjacency matrix A: Avu = 1 ⇐⇒ (v, u) ∈ Str Initialize Θ0 randomly. for t = 0 to T do
Sample set Bt ⊆ Vtr of size m uniformly at random from all subsets of Vtr Compute the gradient term ut as the sum of the clipped gradient terms in the batch Bt:
ut ← ∑ v∈Bt ClipC(∇Θ` (GNN(A,X, v; Θt); yv))
Add independent Gaussian noise to the gradient term: ũt ← ut +N (0, σ2I) Update first and second moment estimators with the noisy gradient, correcting for bias:
ft ← β1 · ft−1 + (1− β1) · ũt st ← β2 · st−1 + (1− β2) · (ũt ũt)
f̂t ← ft 1− βt1 ŝt ←
st 1− βt2
Update the current estimate of the parameters with the noisy estimators:
Θt+1 ← Θt − η
m f̂t√ ŝ2t + ε
end

heading: E EXPERIMENTAL DETAILS AND REPRODUCIBILITY
text: Table 5 provides details on the benchmark node classification datasets from the OGB suite used in the experiments. The following 3 datasets were used to demonstrate the effectiveness of our method: ogbn-arxiv6 and ogbn-mag7 dataset consisting of papers extracted from the Microsoft Academic Graph (MAG) dataset (Wang et al., 2020) and ogbn-products8 dataset which is a co-purchasing network of Amazon products.
Hyperparameter configurations for all methods: We use the following ‘inverse-degree’ normalization of the adjacency matrix for all GCN models:
Â = (d+ I)−1(A + I).
Adam (Kingma & Ba, 2014) with β1 = 0.9 and β2 = 0.999, and SGD optimizers were used for training all methods for each of the datasets. We fix C% as 75.
6 https://ogb.stanford.edu/docs/nodeprop/#ogbn-arxiv 7 https://ogb.stanford.edu/docs/nodeprop/#ogbn-mag 8 https://ogb.stanford.edu/docs/nodeprop/#ogbn-products
A dataset-specific grid search was performed over the other hyperparameters for each method, mentioned below. lr refers to the learning rate, nenc refers to the number of layers in the encoder MLP, ndec refers to the number of layers in the decoder MLP, λ refers to the noise multiplier, Cf refers to the clipping scaling factor, and K refers to the sampling degree.
ogbn-arxiv:
• Non-Private GCN: lr in {0.001, 0.002, 0.003}, nenc in {1, 2}, ndec in {1, 2}, Batch Size in {1000}, Activation in {ReLU}, K in {7, 10}.
• DP-GNN: lr (Adam) in {0.001, 0.002, 0.003}, lr (SGD) in {0.2, 0.5, 1.0}, nenc in {1, 2}, ndec in {1, 2}, Batch Size in {10000}, Activation in {Tanh}, λ in {1.0}, Cf in {1.0}, K in {7, 10}.
• Non-Private MLP: lr in {0.001, 0.002, 0.003}, nenc in {1, 2}, ndec in {1, 2}, Batch Size in {1000}, Activation in {ReLU}.
• DP-MLP: lr in {0.001, 0.002, 0.003}, nenc in {1, 2}, ndec in {1, 2}, Batch Size in {10000}, Activation in {Tanh}, λ in {1.0}, Cf in {1.0}.
ogbn-products:
• Non-Private GCN: lr in {0.001, 0.002, 0.003}, nenc in {1, 2}, ndec in {1, 2}, Batch Size in {1000, 4096}, Activation in {ReLU, Tanh}, K in {10}.
• DP-GNN: lr (Adam) in {0.001, 0.002, 0.003}, lr (SGD) in {0.01, 0.1, 1.0}, nenc in {1, 2}, ndec in {1, 2}, Batch Size in {1000, 4096, 10000}, Activation in {ReLU, Tanh}, λ in {0.8, 0.9, 1.0}, Cf in {1.0}, K in {10}.
• Non-Private MLP: lr in {0.001, 0.002, 0.003}, nenc in {1, 2}, ndec in {1, 2}, Batch Size in {1000, 4096, 10000}, Activation in {ReLU, Tanh}.
• DP-MLP: lr in {0.001, 0.002, 0.003}, nenc in {1, 2}, ndec in {1, 2}, Batch Size in {1000, 4096, 10000}, Activation in {ReLU, Tanh}, λ in {0.8, 0.9, 1.0}, Cf in {1.0}.
ogbn-mag:
• Non-Private GCN: lr in {0.001, 0.002, 0.003}, nenc in {1, 2}, ndec in {1, 2}, Batch Size in {1000, 4096, 5000, 10000}, Activation in {ReLU, Tanh}, K in {3, 5, 10}.
• DP-GNN: lr (Adam) in {0.001, 0.003, 0.01}, lr (SGD) in {0.1, 0.5, 0.8, 1.0}, nenc in {1, 2}, ndec in {1, 2}, Batch Size in {1000, 4096, 5000, 10000}, Activation in {ReLU, Tanh}, λ in {1.0, 0.8, 0.5}, Cf in {1.0, 2.0, 4.0}, K in {3, 5, 10}. • Non-Private MLP: lr in {0.001, 0.003, 0.01}, nenc in {1, 2}, ndec in {1, 2}, Batch Size in {1000, 4096, 5000, 10000}, Activation in {ReLU, Tanh}. • DP-MLP: lr in {0.001, 0.003, 0.01}, nenc in {1, 2}, ndec in {1, 2}, Batch Size in {1000,
4096, 5000, 10000}, Activation in {ReLU, Tanh}, λ in {1.0, 0.8, 0.5}, Cf in {1.0, 2.0, 4.0}.
Additionally, the best hyperparameters corresponding to each experiment to reproduce the results in the main paper are reported in Table 6.

heading: F CLASS-WISE ANALYSIS OF LEARNT MODELS
text: To better understand the performance of the private model as compared to 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 at a class-wise granularity. These results are summarized in Figure 3. We empirically observe that the performance of the private model degrades as the frequency of training data points for a particular class decreases. This indicates that the model is able to 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 et al., 2019; Fioretto et al., 2021) that differentially-private models generally perform disparately worse on under-represented classes.

Review summaries:
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.

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.  Its contributions are as follows: 1.	Propose the task of learning node-level differential private GNNs, 2.	Adapt DP-SGD to work on graphs, through extending amplified privacy guarantee, 3.	Evaluate proposed optimization algorithm on benchmark graph datasets. 

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.