Sina Sajadmanesh

Ali Shahin Shamsabadi

Aurélien Bellet

Daniel Gatica-Perez

GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation

In this paper, we study the problem of learning Graph Neural Networks (GNNs) with Differential Privacy (DP). We propose a novel differentially private GNN based on Aggregation Perturbation (GAP), which adds stochastic noise to the GNN's aggregation function to statistically obfuscate the presence of a single edge (edge-level privacy) or a single node and all its adjacent edges (node-level privacy). Tailored to the specifics of private learning, GAP's new architecture is composed of three separate modules: (i) the encoder module, where we learn private node embeddings without relying on the edge information; (ii) the aggregation module, where we compute noisy aggregated node embeddings based on the graph structure; and (iii) the classification module, where we train a neural network on the private aggregations for node classification without further querying the graph edges. GAP's major advantage over previous approaches is that it can benefit from multi-hop neighborhood aggregations, and guarantees both edge-level and node-level DP not only for training, but also at inference with no additional costs beyond the training's privacy budget. We analyze GAP's formal privacy guarantees using Rényi DP and conduct empirical experiments over three real-world graph datasets. We demonstrate that GAP offers significantly better accuracy-privacy trade-offs than state-of-the-art DP-GNN approaches and naive MLP-based baselines. Our code is publicly available at https://github.com/sisaman/GAP.

Introduction

Real-world datasets are often represented by graphs, such as social [START_REF] Qiu | Deepinf: Social influence prediction with deep learning[END_REF], financial [START_REF] Wang | A review on graph neural network methods in financial applications[END_REF], transportation [START_REF] Diao | Dynamic spatial-temporal graph convolutional neural networks for traffic forecasting[END_REF], or biological [START_REF] Kearnes | Molecular graph convolutions: moving beyond fingerprints[END_REF] networks, modeling the relations (i.e., edges) between a collection of entities (i.e., nodes). Graph Neural Networks (GNNs) have achieved state-of-the-art performance in learning over such relational data in various graph-based machine learning tasks, such as node classification, link prediction, and graph classification [START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF][START_REF] Xu | How powerful are graph neural networks[END_REF][START_REF] Zhang | Link prediction based on graph neural networks[END_REF]. Due to their superior performance, GNNs are now widely used in many applications, such as recommendation systems, credit issuing, traffic forecasting, drug discovery, and medical diagnosis [START_REF] Cheung | Graph neural networks for covid-19 drug discovery[END_REF][START_REF] Gkalelis | Objectgraphs: Using objects and a graph convolutional network for the bottom-up recognition and explanation of events in video[END_REF][START_REF] Jiang | Graph neural network for traffic forecasting: A survey[END_REF][START_REF] Mohammadshahi | Graphto-graph transformer for transition-based dependency parsing[END_REF][START_REF] Ying | Graph convolutional neural networks for web-scale recommender systems[END_REF].

Privacy concerns. Despite their success, real-world deployments of GNNs raise privacy concerns when graphs contain personal data: for instance, social or financial networks involve sensitive information about individuals and their interactions.

Recent works [START_REF] He | Stealing links from graph neural networks[END_REF][START_REF] He | Node-level membership inference attacks against graph neural networks[END_REF][START_REF] Iyiola E Olatunji | Membership inference attack on graph neural networks[END_REF][START_REF] Wu | Linkteller: Recovering private edges from graph neural networks via influence analysis[END_REF] have extended the study of the privacy leakage of standard deep learning models to GNNs, showing the risk of information leakage regarding training data is even higher in GNNs, as they incorporate not only node features and labels but also the graph structure itself [START_REF] Duddu | Quantifying privacy leakage in graph embedding[END_REF]. Consequently, GNNs are vulnerable to various privacy attacks, such as node membership inference [START_REF] He | Node-level membership inference attacks against graph neural networks[END_REF][START_REF] Iyiola E Olatunji | Membership inference attack on graph neural networks[END_REF] and edge stealing [START_REF] He | Stealing links from graph neural networks[END_REF][START_REF] Wu | Linkteller: Recovering private edges from graph neural networks via influence analysis[END_REF]. For example, a GNN trained on a social network for friendship recommendation could reveal the existing relationships between the users via its predictions. As another example, a GNN trained on the social graph of COVID-19 patients can be used by government authorities to predict the spread of the disease, but an adversary may recover private information about the participating patients.

Problem and motivation. Motivated by these privacy concerns, we investigate the problem of designing privacypreserving GNNs for private, sensitive graphs. Our goal is to protect the sensitive graph structure and other accompanying data using the framework of Differential Privacy (DP) [START_REF] Dwork | Differential privacy: A survey of results[END_REF].In the context of graphs, two different variants of DP have been defined: edge-level and node-level DP [START_REF] Raskhodnikova | Differentially private analysis of graphs[END_REF]. Informally, an edge-level 𝜖-DP algorithm have roughly the same output (as measured by 𝜖) if one edge is removed from the input graph. This ensures that the algorithm's output does not reveal the existence of a particular edge in the graph. Correspondingly, node-level private algorithms conceal the presence of a particular node together with all its associated edges and attributes. Clearly, node-level DP is a stronger privacy definition, but it is harder to attain because it requires the algorithm's output distribution to hide much larger differences in the input graph.

Challenges.

As GNNs utilize the structural information in the graph data, protecting data privacy in such models is more At each layer, every node aggregates its neighbors' embedding vectors (initially node features, e.g. X A for node A), which is then updated using a neural net into a new vector (e.g., H A ). Removing an arbitrary edge (here, the edge from node B to F) excludes the source node (B) from the aggregation set of the destination node (F). At the first layer, this will only alter the destination node's embedding, but this change is propagated to the neighboring nodes in the next layer. Node embeddings that are affected by the removal of edge (B,F) are indicated in red.

challenging than in standard ones. As shown in Figure 1, one of these challenges is the interdependency between the node embeddings resulting from the GNN's data aggregation mechanism. Specifically, a 𝐾-layer GNN iteratively learns node embeddings by aggregating information from every node's 𝐾-hop neighborhood (i.e., from nodes that are at a distance at most 𝐾 in the graph). Hence, the embedding of a node is influenced not only by the node itself but also by all the nodes in its 𝐾-hop proximity. This fact voids the privacy guarantees of standard DP learning paradigms, such as DP-SGD [START_REF] Abadi | Deep learning with differential privacy[END_REF], as the training loss of GNNs can no longer be decomposed into individual samples. Furthermore, the number of interdependent embeddings grows exponentially with 𝐾, hindering the ability of a DP solution to hide the output differences effectively. Therefore, how to get more representational power from higher-order GNN aggregations while ensuring DP is an important challenge to address.

Another major challenge is to guarantee inference privacy, i.e., preserving the privacy of graph data not only for training but also at inference time, when the trained GNN model is queried to make predictions for test nodes. Unlike conventional deep learning models, where the training data is not reused at inference time, the inference about any node in a 𝐾-layer GNN requires aggregating data from its 𝐾-hop neighborhood, which can reveal information about the neighboring nodes. Therefore, private graph data can still be leaked at inference time, even with privately trained model parameters. As a result, it is critical to ensure that both the training and inference stages of a GNN satisfy DP. This is illustrated in Figure 2.

Our contributions. To address the above challenges, we propose GAP, a privacy-preserving GNN model satisfying edge-level privacy, which is also extensible to node-level privacy if combined with standard private learning algorithms such as DP-SGD. As perturbing an edge in the input graph can practically be viewed as changing a sample in a node's neighborhood aggregation set, GAP preserves edge privacy via aggregation perturbation: we add calibrated Gaussian noise to the output of the aggregation function, which can effectively hide the presence of a single edge (edge-level privacy) or a group of edges (node-level privacy). To avoid accumulating privacy costs at every model update, we propose a custom GNN architecture (Figure 3) comprising three individual components: (i) the encoder module, where we pre-train an encoder to extract lower-dimensional node features without relying on the graph structure; (ii) the aggregation module, where we use aggregation perturbation to privately compute multi-hop aggregated node embeddings using the graph edges and the encoded features; and (iii) the classification module, where we train a neural network on the aggregated data for node classification without further querying the graph edges. Aggregation perturbation allows us to benefit from higher- The encoded features are given to the aggregation module to compute private 𝐾-hop aggregations (here, 𝐾 = 2) using the graph's adjacency matrix (A). (3) The classification module is trained over the private aggregations for label prediction. order, multi-hop aggregations by composing individual noisy aggregations, yet the proposed architecture significantly reduces the privacy costs as the perturbed aggregations are computed once on lower-dimensional embeddings, and reused during training and inference. GAP also provides inference privacy, as the inference of any node relies on the perturbed aggregations, which hide information about neighboring nodes. Due to reusing cached aggregations, the inference step does not incur additional privacy costs beyond that of training.

MLP

Results.

We analyze GAP's formal privacy guarantees using Rényi Differential Privacy [START_REF] Mironov | Rényi differential privacy[END_REF], and empirically evaluate its accuracy-privacy performance on three medium to large-scale graph datasets, namely Facebook, Reddit, and Amazon. We demonstrate that GAP's accuracy surpasses the competing baselines' at (very) low privacy budgets under both edge-level DP (e.g., 𝜖 ≥ 0.1 on Reddit) and node-level DP (e.g., 𝜖 ≥ 1 on Reddit), and observe that it always performs on par or better than a naive (privately trained) MLP model which does not utilize the graph's structural information.

Related Work

Graph neural networks. Deep learning on graphs has emerged in the past few years to tackle different kinds of graph-based learning tasks. A variety of GNN models and various architectures have been proposed, including Graph Convolutional Networks [START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF], Graph Attention Networks [START_REF] Veli Č Kovi Ć | Graph attention networks[END_REF], GraphSAGE [START_REF] William L Hamilton | Inductive representation learning on large graphs[END_REF], Graph Isomorphism Networks [START_REF] Xu | How powerful are graph neural networks[END_REF], Jumping Knowledge Networks [START_REF] Xu | Representation learning on graphs with jumping knowledge networks[END_REF], and Gated Graph Neural Networks [START_REF] Li | Gated graph sequence neural networks[END_REF]. For the latest advances and trends in GNNs, we refer the reader to the available surveys [START_REF] Sergi Abadal | Computing graph neural networks: A survey from algorithms to accelerators[END_REF][START_REF] William L Hamilton | Representation learning on graphs: Methods and applications[END_REF][START_REF] Wu | A comprehensive survey on graph neural networks[END_REF][START_REF] Zhang | Deep learning on graphs: A survey[END_REF][START_REF] Zhou | Graph neural networks: A review of methods and applications[END_REF].

Privacy attacks on GNNs. Several recent works have investigated the possibility of performing privacy attacks against GNNs and quantified the privacy leakage of publicly released GNN models or node embeddings trained on private graph datasets. Zhang et al. [START_REF] Zhang | Inference attacks against graph neural networks[END_REF] study the information leakage in graph embeddings and propose three different inference attacks against GNNs: inferring graph properties (such as number of nodes and edges), inferring whether a given subgraph is contained in the target graph, and graph reconstruction with similar statistics to the target graph. He et al. [START_REF] He | Stealing links from graph neural networks[END_REF] propose a series of black-box link stealing attacks on GNN models, and show that an adversary can accurately infer a link between any pair of nodes in a graph used to train the GNN. Zhang et al. [START_REF] Zhang | Graphmi: Extracting private graph data from graph neural networks[END_REF] study the connection between model inversion risk and edge influence, and show that edges with greater influence are more likely to be inferred. Wu et al. [START_REF] Wu | Linkteller: Recovering private edges from graph neural networks via influence analysis[END_REF] also study the link stealing attack via influence analysis, and propose an effective attack against GNNs based on the node influence information. The feasibility of the membership inference attack against GNNs has also been studied and several attacks with different threat models have been proposed in the literature [START_REF] Bang | Adapting membership inference attacks to gnn for graph classification: Approaches and implications[END_REF][START_REF] Duddu | Quantifying privacy leakage in graph embedding[END_REF][START_REF] He | Node-level membership inference attacks against graph neural networks[END_REF][START_REF] Iyiola E Olatunji | Membership inference attack on graph neural networks[END_REF]. Overall, these works underline the privacy risks of GNNs trained on sensitive graph data and confirm the vulnerability of these models to various privacy attacks.

Differentially private GNNs. Recently, there have been attempts to use DP to provide formal privacy guarantees in various GNN learning settings. Sajadmanesh and Gatica-Perez [START_REF] Sajadmanesh | Locally private graph neural networks[END_REF] propose a locally private GNN model by considering a distributed learning setting, where node features and labels are private but training the GNN is federated by a central server with access to graph edges. However, their method cannot be used in applications where the graph edges are private. Wu et al. [START_REF] Wu | Linkteller: Recovering private edges from graph neural networks via influence analysis[END_REF] propose an edge-level DP learning algorithm for GNNs by perturbing the input graph directly using either randomized response (called E R ) or the Laplace mechanism (called L G

). Then, a GNN is trained over the resulting noisy graph. However, their method cannot be extended trivially to the node-level privacy setting. Olatunji et al. [START_REF] Iyiola E Olatunji | Releasing graph neural networks with differential privacy guarantees[END_REF] consider a centralized learning setting and propose a node-level private GNN by adapting the framework of PATE [START_REF] Papernot | Semi-supervised knowledge transfer for deep learning from private training data[END_REF]. They train the student GNN model using public graph data, which is privately labeled using the teacher GNN models trained exclusively for each query node. However, their dependence on public graph data restricts the applicability of their method. Daigavane et al. [START_REF] Daigavane | Node-level differentially private graph neural networks[END_REF] also propose a node-level private approach for training 1-layer GNNs by extending the standard DP-SGD algorithm and privacy amplification by subsampling results to bounded-degree graph data. However, their approach fails to provide inference privacy and is limited to 1-layer GNNs and thus cannot leverage higher-order aggregations.

Comparison with existing methods. To our best knowledge, GAP is the first approach providing both edge-level or nodelevel privacy guarantees based on the application requirements. Unlike existing methods, our approach does not rely on public data, can leverage multi-hop aggregations beyond first-order neighbors, and guarantees inference privacy at no additional cost. In Section 7, we also show that GAP outperforms other baselines in terms of accuracy-privacy trade-off.

Background and Problem Formulation

Graph Neural Networks

GNNs aim to learn a representation for every node in the input graph by incorporating the initial node features and the graph structure (edges). The learned node representations, or embeddings, can then be used for the downstream machine learning task. In this paper, we focus on node classification, where the embeddings are used to predict the label of the graph nodes. Node-wise prediction problems can be tackled in either transductive or inductive setting. In the transductive setting, both training and testing are performed on the same graph, but different nodes are used for training and testing. Conversely, in the inductive setting, training and testing are performed on different graphs. This is illustrated in Figure 4.

Let G = (V, E, X, Y) be an unweighted directed graph dataset consisting of sets of nodes V and edges E represented by a binary adjacency matrix A ∈ {0, 1} 𝑁 ×𝑁 , where 𝑁 = |V | denotes the number of nodes, and A 𝑖, 𝑗 = 1 if there is a directed edge (𝑖, 𝑗) ∈ E from node 𝑖 to node 𝑗. Nodes are characterized by 𝑑-dimensional feature vectors stacked up in an 𝑁 × 𝑑 matrix X, where X 𝑣 denotes the feature vector of the 𝑣-th GNN Layer GNN Layer

GNN Layer

Figure 5: Typical 3-layer GNN for node classification. Each layer 𝑖 takes the adjacency matrix A and previous layer's node embedding matrix H (𝑖-1) (initially, node features X), and outputs a new embedding matrix H (𝑖) (ultimately, predicted class labels Y). Internally, the input embeddings H (𝑖-1) are aggregated based on the adjacency matrix A, and then fed to a neural network (U ) to generate new embeddings H (𝑖) . node. Y ∈ {0, 1} 𝑁 ×𝐶 represents the labels of the nodes, where Y 𝑣 is a 𝐶-dimensional one-hot vector denoting the label of the 𝑣-th node, and 𝐶 is the number of classes. Note that in the transductive learning setting, only a subset V 𝑇 ⊂ V of the nodes is labeled, and thus Y 𝑣 is a zero vector for all 𝑣 ∉ V 𝑇 .

A typical 𝐾-layer GNN consists of 𝐾 sequential graph convolution layers. Layer 𝑖 receives node embeddings from layer 𝑖 -1 and outputs a new embedding for each node by aggregating the current embeddings of its adjacent neighbors followed by a learnable transformation, as defined below:

H (𝑖) 𝑣 = upd agg {H (𝑖-1) 𝑢 : ∀𝑢 ∈ 𝔑 𝑣 } ; 𝚯 (𝑖) ,
where 𝔑 𝑣 = {𝑢 : A 𝑢,𝑣 ≠ 0} denotes the set of adjacent nodes to node 𝑣 (i.e., nodes with outbound edges toward 𝑣), and

H (𝑖-1)

𝑢

is the embedding of an adjacent node 𝑢 at layer 𝑖 -1. agg(•), is a (sub)differentiable, permutation invariant aggregator function, such as S , M , or M . Finally, upd(•) is a learnable function, such as a multi-layer perceptron (MLP), parameterized by 𝚯 (𝑖) that takes the aggregated vector and outputs the new embedding H (𝑖) 𝑣 . For convenience, we define the matrix-based version of agg(•) and upd(•) by stacking the corresponding vectors of all the nodes into a matrix as:

A (H, A) = [agg ({H 𝑢 : ∀𝑢 ∈ 𝔑 𝑣 }) : ∀𝑣 ∈ V] 𝑇 , U (M; 𝚯) = [upd (M 𝑣 ; 𝚯) : ∀𝑣 ∈ V] 𝑇 ,
where we omitted the layer indicator superscripts for simplicity. Initially, we have H (0) = X (i.e., node features) as the input to the GNN's first layer. The last layer generates an output embedding vector for each node, which can be used in different ways depending on the downstream task. For node classification, a softmax layer is applied to the final embeddings H (𝐾 ) to obtain the posterior class probabilities Y. The illustration of a typical 3-layer GNN is depicted in Figure 5.

Differential Privacy

Differential privacy (DP) [START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF] is the gold standard for formalizing the privacy guarantees of algorithms that process sensitive data. Informally, DP requires that the algorithm's output distribution be roughly the same regardless of the presence of an individual's data in the dataset. As such, an adversary having access to the data of all but the target individual cannot distinguish whether the target's record is among the input data. The formal definition of DP is as follows.

Definition 1 (Differential Privacy [START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF]). Given 𝜖 > 0 and 𝛿 > 0, a randomized algorithm A satisfies (𝜖, 𝛿)-differential privacy, if for all possible pairs of adjacent datasets 𝑋 and 𝑋 differing by at most one record, denoted as 𝑋 ∼ 𝑋 , and for any possible set of outputs 𝑆 ⊆ 𝑅𝑎𝑛𝑔𝑒(A), we have:

Pr[A (𝑋) ∈ 𝑆] ≤ 𝑒 𝜖 Pr[A (𝑋 ) ∈ 𝑆] + 𝛿.
Here, the parameter 𝜖 is called the privacy budget (or privacy cost) and is used to tune the privacy-utility trade-off of the algorithm: a lower privacy budget leads to stronger privacy guarantees but reduced utility. The parameter 𝛿 is informally treated as a failure probability, and is usually chosen to be very small. DP has the following important properties that help us design complex algorithms from simpler ones [START_REF] Dwork | Differential privacy: A survey of results[END_REF]:

• Robustness to post-processing: Any post-processing of the output of an (𝜖, 𝛿)-DP algorithm remains (𝜖, 𝛿)-DP. • Sequential composition: If an (𝜖, 𝛿)-DP algorithm is applied 𝑘 times on the same data, the result is at most (𝑘𝜖, 𝑘𝛿)-DP.

• Parallel composition: Executing an (𝜖, 𝛿)-DP algorithm on disjoint chunks of data yields an (𝜖, 𝛿)-DP algorithm.

In this paper, we use an alternative definition of DP, called Rényi Differential Privacy (RDP) [START_REF] Mironov | Rényi differential privacy[END_REF], which allows obtaining tighter sequential composition results: Definition 2 (Rényi Differential Privacy [START_REF] Mironov | Rényi differential privacy[END_REF]). A randomized algorithm A is (𝛼, 𝜖)-RDP for 𝛼 > 1, 𝜖 > 0 if for every adjacent datasets 𝑋 ∼ 𝑋 , we have 𝐷 𝛼 (A (𝑋) A (𝑋 )) ≤ 𝜖, where 𝐷 𝛼 (𝑃 𝑄) is the Rényi divergence of order 𝛼 between probability distributions 𝑃 and 𝑄 defined as:

𝐷 𝛼 (𝑃 𝑄) = 1 𝛼 -1 log E 𝑥∼𝑄 𝑃(𝑥) 𝑄(𝑥) 𝛼 .
As RDP is a generalization of DP, it can be easily converted back to standard (𝜖, 𝛿)-DP using the following proposition:

Proposition 1. If A is an (𝛼, 𝜖)-RDP algorithm, then it also satisfies (𝜖 + log(1/ 𝛿) /𝛼-1, 𝛿)-DP for any 𝛿 ∈ (0, 1).
A basic method to achieve RDP is the Gaussian mechanism, where Gaussian noise is added to the output of the algorithm we want to make private. Specifically, let 𝑓 : X → R 𝑑 be the non-private algorithm taking a dataset as input and outputting a 𝑑-dimensional vector. Let the sensitivity of 𝑓 be the maximum 𝐿 2 distance achievable when applying 𝑓 (•) to adjacent datasets 𝑋 and 𝑋 as Δ 𝑓 = max 𝑋 ∼𝑋 𝑓 (𝑋) -𝑓 (𝑋 ) 2 . Then, adding Gaussian noise with variance 𝜎 2 to 𝑓 as A (𝑋) = 𝑓 (𝑋) + N (𝜎 2 I 𝑑 ), with I 𝑑 being 𝑑 × 𝑑 identity matrix, yields an (𝛼, 𝜖)-RDP algorithm for all 𝛼 > 1 with 𝜖 = Δ 2 𝑓 𝛼 /2𝜎 2 [START_REF] Mironov | Rényi differential privacy[END_REF].

Problem Definition

Let Y = F (X, A; 𝚯) be a GNN-based node classification model with parameter set 𝚯 that takes node features X and the graph's adjacency matrix A as input, and outputs the corresponding predicted labels Y. To learn the model parameters 𝚯, we minimize a standard classification loss function (e.g., cross-entropy) with respect to 𝚯 as follows:

𝚯 ★ = arg min 𝚯 ∑ 𝑣 ∈V 𝑇 ℓ( Y 𝑣 , Y 𝑣 ), (1)
where ℓ(•, •) is the loss function, Y is the ground-truth labels, and V 𝑇 ⊆ V is the set of labeled training nodes. After training, in the transductive setting, the learned GNN is used to infer the labels of unlabeled nodes in G:

Y = F (X, A; 𝚯 ★ ), (2)
Otherwise, in the inductive setting, a new graph dataset G 𝑡𝑒𝑠𝑡 is given to the learned GNN for label inference. The goal of this paper is to preserve the privacy of graph datasets for both the training step (Eq. 1) and the inference step (Eq. 2) using differential privacy. Note that preserving privacy in the inference step is critical as the adjacency information is still used in this step for obtaining the predicted labels.

However, as graph datasets are different from standard tabular datasets due to the existence of links between data records, one needs to adapt the definition of DP to graphs. As the semantic interpretation of DP relies on the definition of adjacent datasets, we first define two different notions of adjacency in graphs, namely edge-level and node-level adjacent graph datasets [START_REF] Hay | Accurate estimation of the degree distribution of private networks[END_REF]: Definition 3 (Edge-level adjacent graphs). Two graphs G and G are edge-level adjacent if one can be obtained by removing a single edge from the other. Therefore, G and G differ by at most one edge.

Definition 4 (Node-level adjacent graphs). Two graphs G and G are node-level adjacent if one can be obtained by removing a single node (with its features, labels, and all attached edges) from the other. Therefore, G and G differ by at most one node.

Accordingly, the definition of edge-level and node-level DP follows from the above definitions: an algorithm A is edge-level (respectively, node-level) (𝜖, 𝛿)-DP if for every two edge-level (respectively, node-level) adjacent graph datasets G and G and any set of outputs 𝑆 ⊆ 𝑅𝑎𝑛𝑔𝑒(A), we have

Pr[A (G) ∈ 𝑆] ≤ 𝑒 𝜖 Pr[A (G ) ∈ 𝑆] + 𝛿.
Intuitively, edge-level DP protects edges (which could represent connections between people), while node-level DP protects nodes together with their adjacent edges (i.e., all information pertaining to an individual, including features, labels, and connections).

Proposed Method: GAP

In this section, we explain our proposed differentially private method, called GNN with Aggregation Perturbation (GAP), which guarantees both edge-level and node-level privacy for training and inference on sensitive graph data.

Overview

As mentioned in Section 1, the two primary challenges in the design of private GNNs come from the use of higher-order aggregations and the need to ensure inference privacy. To tackle these challenges, we propose a new architecture for GAP, which is different from the conventional GNN architectures presented in Section 3.1. The key distinction is that GAP decouples the graph-based aggregations from the neural network-based transformations, which is similar in spirit to the Inception model and scalable networks [START_REF] Fabrizio Frasca | Sign: Scalable inception graph neural networks[END_REF][START_REF] Szegedy | Going deeper with convolutions[END_REF][START_REF] Wu | Simplifying graph convolutional networks[END_REF]. As illustrated in Figure 3, GAP is composed of the following three components:

(i) Encoder Module (EM): This module encodes the input node features into a lower-dimensional representation without using the private graph structure.

(ii) Aggregation Module (AM): This module takes the encoded low-dimensional node features and recursively computes private multi-hop aggregations using the aggregation perturbation approach, i.e., by adding noise to the output of each aggregation step.

(iii) Classification Module (CM): This module takes the privately aggregated node features and predicts the corresponding labels without querying the edges any further.

GAP's privacy mechanism. Our proposed mechanism for preserving the privacy of graph edges in AM is the aggregation perturbation approach: we use the Gaussian mechanism to add stochastic noise to the output of the aggregation function proportional to its sensitivity. This approach is motivated by the fact that perturbing an edge in the input graph can practically be viewed as changing a sample in the neighborhood aggregation function of the edge's destination node. Therefore, by adding an appropriate amount of noise to the aggregation function, we can effectively hide the presence of a single edge, which ensures edge-level privacy, or a group of edges, which is necessary for node-level privacy. To fully guarantee nodelevel privacy, however, in addition to the edges, we need to also protect node features and labels, which is simply done by training EM and CM using standard DP learning algorithms such as DP-SGD. We discuss this point further in Section 5.

Challenges addressed. Our GAP method can benefit from multi-hop aggregations by composing individual noisy aggregation steps. As the sensitivity of a single-step aggregation is easily determined, AM applies the Gaussian mechanism immediately after each aggregation step, avoiding the growing interdependency between node embeddings. GAP also provides inference privacy as the inference of a node relies on the aggregated data from its neighbors, which is privately computed by AM. As the subsequent CM only post-processes these private aggregations, GAP ensures inference-time privacy. This is explained in more details in Section 5.

In the rest of this section, we first discuss each of the GAP's components thoroughly and then describe the inference mechanism.

Encoder Module

GAP uses a multi-layer perceptron (MLP) model as an encoder to transform the original node features into an intermediate representation given to AM. The main goal of this module is to reduce the dimensionality of AM's input, as the magnitude of the Gaussian noise injected into the aggregations grows with data dimensionality. Therefore, reducing the dimensionality helps achieve better aggregation utility under DP.

Note that in order to save the privacy budget spent in AM, we do not train the encoder end-to-end with CM. Instead, we attach a linear softmax layer to the encoder MLP for label prediction, and then pre-train this model separately using node features and labels. Specifically, we use the following model:

Y = softmax (MLP enc (X; 𝚯 enc ) • W) , (3)
where MLP enc is the encoder MLP with parameter set 𝚯 enc , W is the weight matrix of the linear softmax layer, X is the original node features, and Y is the corresponding posterior class probabilities. In order to train this model, we minimize the cross-entropy (or any other classification-related) loss function ℓ(•, •) with respect to the model parameters 𝚯 = {𝚯 enc , W}:

𝚯 ★ = arg min 𝚯 ∑ 𝑣 ∈V 𝑇 ℓ( Y 𝑣 , Y 𝑣 ), (4)
where Y is the ground-truth labels and V 𝑇 ⊆ V is the set of training nodes. After pre-training, we use the encoder MLP to extract low-dimensional node features, X (0) , for AM:

X (0) = MLP enc (X; 𝚯 ★ enc ). (5)
Remark. As will be discussed in Section 4.3, this encoder pretraining approach significantly reduces the model's privacy costs as the private aggregations in AM no longer need to be updated with the encoder's parameters. Besides, compared to the original features, this approach provides better node features to AM as the encoded representations incorporate label information as well.

Aggregation Module

The goal of AM is to privately release multi-hop aggregated node features using the aggregation perturbation method. Algorithm 1 presents our mechanism, the Private Multi-hop Aggregation (PMA). It relies on the S aggregation function, which is simply equivalent to the multiplication of the adjacency matrix A by the input feature matrix X, as A (X, A) = A 𝑇 • X. The PMA mechanism takes X(0) , the row-normalized version of the encoder's extracted features as:

X(0) 𝑣 = X (0) 𝑣 / X (0) 𝑣 2 , ∀𝑣 ∈ V. (6)
It then outputs a set of 𝐾 normalized, privately aggregated node features X(1) to X(𝐾) corresponding to different hops from 1 to 𝐾. Specifically, given 𝜎 > 0, the PMA mechanism performs the following steps to recursively compute and perturb the aggregations in 𝑘-th hop from (𝑘 -1)-th:

1. Aggregation: First, we compute 𝑘-th non-private aggregations using the normalized aggregations at step 𝑘 -1:

X (𝑘) = A 𝑇 • X(𝑘-1) . (7)
2. Perturbation: Next, we perturb the aggregations using the Gaussian mechanism, i.e., by adding noise with variance 𝜎 2 to every row of X (𝑘) independently:

X (𝑘) 𝑣 = X (𝑘) 𝑣 + N (𝜎 2 I), ∀𝑣 ∈ V. (8)
3. Normalization: Finally, it is essential to bound the effect of each feature vector on the subsequent aggregations. Therefore, we again row-normalize the private aggregated features, such that the L2-norm of each row is 1:

X(𝑘) 𝑣 = X (𝑘) 𝑣 /|| X (𝑘) 𝑣 || 2 , ∀𝑣 ∈ V. (9)
Remark. The recursive computation of aggregations in the PMA mechanism has one advantage: each aggregation step acts as a denoising mechanism, averaging out the DP noise added in the previous step (to some extent). Therefore, part of the injected noise is dampened by the PMA mechanism itself, leading to better aggregation utility. This noise-reducing effect of GNN aggregations is also observed in prior work [START_REF] Sajadmanesh | Locally private graph neural networks[END_REF].

Effect of EM.

Note that EM plays a critical role in improving AM's privacy-utility trade-off: First, it increases the utility of noisy aggregations by reducing the dimensionality of AM's input, resulting in less noise added to the aggregations. Second, its pre-training strategy makes AM agnostic to model training, which remarkably reduces the total privacy costs as the PMA mechanism is called only once and its output is cached to be reused for entire training and inference. Technically, this implies that with 𝑇 training iterations, the Gaussian mechanism is composed only 𝐾 times, which would otherwise be 𝐾𝑇 in the case of end-to-end training. Since 𝐾 is small (1 ≤ 𝐾 ≤ 5) compared to 𝑇 (in the order of hundreds), this leads to a substantial reduction in the privacy budget.

Classification Module

Given the list of private aggregated features { X(0) , . . . , X(𝐾) } provided by AM, the goal of CM is to predict node labels

Algorithm 1: Private Multi-hop Aggregation

Input :Graph G = ( V, E) with adjacency matrix A; initial normalized features X(0) ; max hop 𝐾 ; noise variance 𝜎 2 ; Output :Private aggregated node feature matrices X(1) , . . . , X(𝐾 ) without further relying on the graph edges. To this end, for each 𝑘 ∈ {0, 1, . . . , 𝐾 }, we first obtain the 𝑘-hop representation H (𝑘) using a corresponding base MLP, denoted as MLP (𝑘) base :

1 for 𝑘 ∈ {1, . . . , 𝐾 } do 2 X (𝑘) ← A 𝑇 • X(𝑘-1) // aggregate 3 X (𝑘) ← X (𝑘) + N ( 𝜎 2 I) // perturb 4 for 𝑣 ∈ V do 5 X(𝑘) 𝑣 ← X (𝑘) 𝑣 / | | X (𝑘) 𝑣 | | 2 //
H (𝑘) = MLP (𝑘) base ( X(𝑘) ; 𝚯 (𝑘) base ), (10)
where 𝚯 (𝑘) base is the parameters of MLP (𝑘) base . Next, we combine these representations to get an integrated node embedding H:

H = C {H (0) , H (1) , . . . , H (𝐾 ) }; 𝚯 comb , (11)
where C is any differentiable combination strategy, with common choices being summation, concatenation, or attention, potentially with parameter set 𝚯 comb . Finally, we feed the integrated representation into a head MLP, denoted as MLP head , to get posterior class probabilities for the nodes:

Y = MLP head (H; 𝚯 head ), (12)
where 𝚯 head denotes the parameters of MLP head . To train CM, we minimize a similar loss function as Eq. 4 but with respect to CM's parameters: 𝚯 = {𝚯 (0) base , . . . , 𝚯 (𝐾 ) base , 𝚯 comb , 𝚯 head }. The overall training procedure of GAP is presented in Algorithm 2.

Remark. CM independently processes the information encoded in the graph-agnostic node features X(0) and the private, graph-based aggregated features X(1) to X(𝐾) , combining them together to get an integrated node representation. Therefore, even if the DP noise overwhelms the signal in the higher-level aggregations, the information in the lower-level aggregations and/or the graph-agnostic features is still preserved and exploited for classification. As a result, regardless of the privacy budget, GAP is expected to always perform on par or better than pure MLP-based models that do not rely on the graph structure. We will empirically demonstrate this point in our experiments.

Inference Mechanism

GAP is compatible with both the transductive and the inductive inference, as discussed below.

Algorithm 2: GAP Training

Input :Graph G = ( V, E) with adjacency matrix A; node features X; node labels Y; max hop 𝐾 ; noise variance 𝜎 2 ; Output :Trained model parameters {𝚯 ★ enc , 𝚯 ★ (0) base , . . . , 𝚯 ★ (𝐾 ) base , 𝚯 ★ comb , 𝚯 ★ head };

1 Pre-train EM (Eq. 3) to obtain 𝚯 ★ enc . 2 Use the pre-trained encoder (Eq. 5) to obtain encoded features X (0) . 3 Row-normalize the encoded features (Eq. 6) to obtain X(0) . 4 Use Algorithm 1 to obtain private aggregations X(1) , . . . , X(𝐾 ) .

5 Train CM (Eq. 10-12) to get 𝚯 ★ (0) base , . . . , 𝚯 4b). In this case, we first extract low-dimensional node features for the new graph using the pre-trained encoder and then feed them to AM to obtain the private aggregations. Finally, we input the private aggregations to the trained CM to get the node labels.

Privacy Analysis

Edge-Level Privacy

In the following, we provide a formal analysis of GAP's edge-level privacy guarantees at training and inference stages.

Training privacy. The following arguments establish the DP guarantees of the PMA mechanism and the GAP training algorithm. The detailed proofs can be found in Appendix A. Proposition 2 shows that the privacy cost grows with the number of hops (𝐾), but is independent of the number of training steps thanks to our GAP architecture.

Theorem 1. Given the maximum hop

Inference privacy.

A major advantage of GAP is that querying the model at inference time preserves DP without consuming additional privacy budget. This is true for both the transductive and the inductive settings:

• Transductive setting: In this setting, the inference is performed by feeding the privately trained CM with the cached aggregations of the test nodes, which have already been computed privately at training time. As this computation does not query the private graph structure and only postprocesses the previous DP operations, due to the robustness of DP to post-processing, GAP provides inference privacy with no additional cost.

•

Node-Level Privacy

Equipped with aggregation perturbation, the proposed GAP architecture guarantees edge-level privacy by default. However, it is readily extensible to provide node-level privacy guarantees as well, providing that we have bounded-degree graphs, i.e., the degree of each node should be bounded above by a constant 𝐷. This allows to bound the sensitivity of the aggregation function in the PMA mechanism when adding/removing a node, as in this case each node can influence at most 𝐷 other nodes. If the input graph has nodes with very high degrees, we can use neighbor sampling (as proposed in [START_REF] Daigavane | Node-level differentially private graph neural networks[END_REF]) to randomly sample at most 𝐷 neighbors per node.

For bounded-degree graphs, adding or removing a node corresponds (in the worst case) to adding or removing 𝐷 edges. Therefore, our PMA mechanism also ensures nodelevel privacy, albeit with increased privacy costs compared to the edge-level setting (see Theorem 2 below).

However, since the node features and labels are also private under node-level DP, both EM and CM need to be trained privately as they access node features/labels. To this end, we can simply use standard DP-SGD [START_REF] Abadi | Deep learning with differential privacy[END_REF] or any other differentially private learning algorithm for pre-training the encoder as well as training CM with DP. In other words, steps 1 and 5 of Algorithm 2 must be done with DP instead of regular non-private training. This way, since each of the three GAP modules become node-level private, the entire GAP model, as an adaptive composition of several node-level private mechanisms, satisfies node-level DP. The formal node-level privacy Note that in Proposition 3, we cannot optimize 𝛼 in closed form as we do not know the precise form of 𝜖 1 (𝛼) and 𝜖 5 (𝛼). However, in our experiments, we numerically optimize the choice of 𝛼 on a per-case basis.

Inference privacy. The arguments stated for edge-level inference privacy also hold for node-level privacy. Note that in the inductive setting, the test graph should also have bounded degree for the node-level inference privacy guarantees to hold.

Discussion

Choice of aggregation function. In this paper, we used S as the default choice of aggregation function. Although other choices of aggregation functions are also possible, we empirically found that S is the most efficient choice to privatize, as its sensitivity does not depend on the size of the aggregation set (i.e., number of neighbors), which is itself a quantity that should be computed privately. For example, the calculation of both M and GCN [START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF] aggregation functions depend on the node degrees, and thus requires additional privacy budget to be spent on perturbing node degrees. In any case, S is recognized as one of the most expressive aggregation functions in the GNN literature [START_REF] Corso | Principal neighbourhood aggregation for graph nets[END_REF][START_REF] Xu | How powerful are graph neural networks[END_REF].

Normalization instead of clipping. The PMA mechanism uses normalization to bound the effect of each individual feature on the S aggregation function. While clipping is more common in the private learning literature (e.g., gradient clipping in DP-SGD [START_REF] Abadi | Deep learning with differential privacy[END_REF]), we empirically found that normalization is a better choice for aggregation perturbation: CM is then trained on normalized data, which tends to facilitate learning. Normalizing the node embeddings is actually commonly done in non-private GNNs as well to stabilize training [START_REF] William L Hamilton | Inductive representation learning on large graphs[END_REF][START_REF] You | Design space for graph neural networks[END_REF].

Limitations. As the PMA mechanism adds random noise to the aggregation function, its utility naturally depends on the size of the node's aggregation set, i.e., the node's degree. Specifically, with a certain amount of noise, the more inbound neighbors a node has, the more accurate its noisy aggregated vector will be. This implies that graphs with higher average degree per node can tolerate larger noise in the aggregation function, and thus GAP can achieve a better privacy-accuracy trade-off on such graphs. Conversely, GAP's performance will suffer if the average degree of the graph is too low, requiring higher privacy budgets to achieve acceptable accuracy. Note however that this is an expected behavior: nodes with fewer inbound neighbors are more easily influenced by a change in their neighborhood compared to nodes with higher degrees, and thus the privacy of low-degree nodes is harder to preserve than high-degree ones. Furthermore, this limitation is not specific to GAP: it is shared by all DP algorithms, whose performance generally suffer from lack of sufficient data.

Edge-level vs. node-level privacy. While GAP can work in either edge-level or node-level privacy settings, it must be emphasized that the former setting is suitable only for the use cases where the node-level information (e.g, features or labels) is not sensitive or is publicly available (e.g., the vertically partitioned graph setting described in [START_REF] Wu | Linkteller: Recovering private edges from graph neural networks via influence analysis[END_REF]). Whenever nodelevel information is private as well (e.g., user profiles in a social network), however, edge-level privacy fails to provide appropriate privacy protection, and thus node-level privacy setting has to be enforced.

Experiments

In this section, we conduct extensive experiments to empirically evaluate GAP's privacy-accuracy performance and its resilience under privacy attacks. As GAP's privacy guarantees are the same under both transductive and inductive settings, we only focus on the former, which has also more pertinent use cases (e.g., social networks).

Datasets

We evaluate the proposed method on three publicly available node classification datasets, which are medium to large scale in terms of the number of nodes and edges:

Facebook [START_REF] Traud | Social structure of facebook networks[END_REF]. This dataset contains the anonymized Facebook social network between UIUC students collected in September 2005. Nodes represent Facebook users and edges indicate friendship. Each node (user) has the following attributes: student/faculty status, gender, major, minor, and housing status, and the task is to predict the class year of users.

Reddit [START_REF] William L Hamilton | Inductive representation learning on large graphs[END_REF]. This dataset consist of a set of posts from the Reddit social network, where each node represents a post and an edge indicates if the same user commented on both posts. Node features are extracted based on the embedding of the post contents, and the task is to predict the community (subreddit) that a post belongs to.

Amazon [START_REF] Chiang | Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks[END_REF]. The largest dataset used in this paper represents Amazon product co-purchasing network, where nodes represent products sold on Amazon and an edge indicates if two products are purchased together. Node features are bag-of-words vectors of the product description followed by PCA, and the task is to predict the category of the products.

We preprocess the datasets by limiting the classes to those having 1k, 10k, and 100k nodes on Facebook, Reddit, and Amazon, respectively. We then randomly split the remaining nodes into training, validation, and test sets with 75/10/15% ratios, respectively. Table 1 summarizes the statistics of the datasets after preprocessing.

Competing Methods

Edge-level private methods. The following methods are evaluated under edge-level privacy:

• GAP-EDP: Our proposed edge-level DP algorithm.

• SAGE-EDP: This is the method of Wu et al. [START_REF] Wu | Linkteller: Recovering private edges from graph neural networks via influence analysis[END_REF] that uses the graph perturbation approach, with the popular Graph-SAGE architecture [START_REF] William L Hamilton | Inductive representation learning on large graphs[END_REF] as its backbone GNN model. We perturb the graph's adjacency matrix using the Asymmetric Randomized Response (ARR) [START_REF] Imola | Communication-Efficient triangle counting under local differential privacy[END_REF], which performs better than E R [START_REF] Wu | Linkteller: Recovering private edges from graph neural networks via influence analysis[END_REF] by limiting the output sparsity. • MLP: A simple MLP model that does not use the graph edges, and thus provides perfect edge-level privacy (𝜖 = 0).

Node-level private methods. We compare the following nodelevel private algorithms:

• GAP-NDP: Our proposed node-level DP approach.

• SAGE-NDP: This is the method of Daigavane et al. [START_REF] Daigavane | Node-level differentially private graph neural networks[END_REF] that adapts the standard DP-SGD method for 1-layer GNNs, with the same GraphSAGE architecture as its backbone model. Since this method does not inherently ensure inference privacy, as suggested by its authors, we add noise to the aggregation function based on its node-level sensitivity at test time and account for the additional privacy cost. • MLP-DP: Similar to MLP, but trained with DP-SGD so as to provide node-level DP without using the graph edges. We do not consider the approach of [START_REF] Iyiola E Olatunji | Releasing graph neural networks with differential privacy guarantees[END_REF] as it requires public graph data and is thus not directly comparable to the others.

Non-private methods. To quantify the accuracy loss of private approaches, we use the following non-private methods (𝜖 = ∞):

• GAP-∞: a non-private counterpart of the GAP method, where we do not perturb the aggregations. • SAGE-∞: a non-private GraphSAGE model.

Experimental Setup

Model implementation details. For our GAP models (GAP-EDP, GAP-NDP, and GAP-∞), we set the number of MLP enc , MLP base , and MLP head layers to be 2, 1, and 1, respectively. We use concatenation as the C function (Eq. 11) and tune the number of hops 𝐾 in {1, 2, . . . , 5}. For the GraphSAGE models (SAGE-EDP, SAGE-NDP, and SAGE-∞), we use the S aggregation function and tune the number of messagepassing layers in {1, 2, . . . , 5}, except for SAGE-NDP that only supports one message-passing layer. We use a 2-layer and a 1-layer MLP as preprocessing and post-processing before and after the message-passing layers, respectively. For the MLP baselines (MLP and MLP-DP), we set the number of layers to 3. In addition, for both the GAP-NDP and SAGE-NDP methods, we use randomized neighbor sampling to bound the maximum degree 𝐷 and search for the best 𝐷 within {100, 200, 300, 400}. For all methods, we set the number of hidden units to 16 (including the dimension of GAP's encoded representation) and use the SeLU activation function [START_REF] Klambauer | Self-normalizing neural networks[END_REF] at every layer. Batch-normalization is used for all methods except the node-level private ones (GAP-NDP, SAGE-NDP, and MLP-DP), for which batch-normalization is not supported.

Training and evaluation details. We train the non-private and edge-level private methods using the Adam optimizer over 100 epochs with full-sized batches. For the node-level private algorithms (GAP-NDP, SAGE-NDP, MLP-DP), we use DP-Adam [START_REF] Gylberth | Differentially private optimization algorithms for deep neural networks[END_REF] with maximum gradient norm set to 1, and train each model for 10 epochs with a batch size of 256, 2048, 4096 on Facebook, Reddit, and Amazon, respectively. For our GAP models (GAP-∞, GAP-EDP, and GAP-NDP), we use the same parameter setting for training both the encoder and classification modules. We train all the methods with a learning rate of 0.01 and repeat each combination of possible hyperparameter values 10 times. We pick the best performing model based on validation accuracy, and report the average test accuracy with 95% confidence interval calculated by bootstrapping with 1000 samples.

Privacy accounting and calibration. Privacy budget accounting is done via the Analytical Moments Accountant [START_REF] Wang | Subsampled renyi differential privacy and analytical moments accountant[END_REF]. We numerically calibrate the noise scale (i.e., the noise standard deviation 𝜎 divided by the sensitivity) of PMA (for GAP-EDP and GAP-NDP), ARR (for SAGE-EDP), DP-SGD (for GAP-NDP, SAGE-NDP, and MLP-DP) and the Gaussian mechanism (for inference privacy in SAGE-NDP) to achieve the desired (𝜖, 𝛿)-DP. We report results for several values of 𝜖, while 𝛿 is set to be smaller than the inverse number of private entities (i.e., edges for edge-level privacy, nodes for node-level privacy). For both GAP-NDP and SAGE-NDP, we use the same noise scale for perturbing the gradients (in DP-SGD) and the aggregations (in PMA and Gaussian mechanisms). Software and hardware. All the models are implemented in PyTorch [START_REF] Paszke | Pytorch: An imperative style, high-performance deep learning library[END_REF] using PyTorch-Geometric (PyG) [START_REF] Fey | Fast graph representation learning with PyTorch Geometric[END_REF]. We use

Experimental Results

Trade-offs between Privacy and Accuracy

We first compare the accuracy of our proposed methods against the non-private, edge-level private, and node-level private baselines. We fix the privacy budget to 𝜖 = 8 for the node-level private methods and 𝜖 = 4 for the edge-level private ones (except for MLP, which does not use the graph structure and thus achieves 𝜖 = 0). The results are presented in Table 2. We observe that in the non-private setting, the proposed GAP architecture is competitive with SAGE, with only a slight decrease in accuracy on Facebook and Amazon. Under both edge-level and node-level privacy settings, however, our proposed methods GAP-EDP and GAP-NDP significantly outperform their competitors. Particularly, under edge-level privacy, GAP-EDP's accuracy is roughly 26, 14, and 15 points higher than the best competitor over Facebook, Reddit, and Amazon, respectively. Under node-level privacy, our proposed GAP-NDP method outperforms the best performing competitor by approximately 13, 13, and 4 accuracy points, respectively. Next, to investigate how different methods perform under different privacy budgets, we vary 𝜖 from 0.1 to 8 for edgelevel private methods and from 1 to 16 for node-level private algorithms and report the accuracy of the methods under each privacy budget. The result for both edge-level and node-level privacy settings is depicted in Figure 6.

Under edge-level privacy (Figure 6, left side), we observe that GAP-EDP consistently outperforms its direct competitor, SAGE-EDP, especially at lower privacy costs. The relative gap between GAP-EDP and SAGE-EDP is influenced by the average degree of the dataset. For example, on Facebook and https://github.com/yuxiangw/autodp Reddit with higher average degrees, SAGE-EDP requires a high privacy budget of 𝜖 ≥ 8 to achieve reasonable accuracy, but on Amazon, which has the lowest average degree, it cannot even beat the MLP baseline. In comparison, the accuracy of GAP-EDP approaches the non-private GAP-∞ at much lower privacy budgets, and always performs better than a vanilla MLP. This is because SAGE-EDP perturbs the adjacency matrix, which is extremely high-dimensional and sparse, while GAP-EDP perturbs the aggregated node embeddings, which has much lower dimensions and is not sparse compared to the adjacency matrix. The amount of accuracy loss with respect to the non-private method also depends on the average degree of the graph. For example, on Reddit at 𝜖 = 2, GAP-∞'s accuracy is only 1 point higher than GAP-EDP's, while on Amazon at 𝜖 = 8, GAP-EDP's accuracy fall behind GAP-∞ by around 5 points. These observations are in line with our discussion of Section 6.

We can observe similar trends under node-level privacy (Figure 6, right side). We see that our GAP-NDP method always performs on par or better than the MLP-DP baseline, and also significantly outperforms SAGE-NDP under all the considered privacy budgets. We attribute this to two factors: first, SAGE-NDP is limited to 1-layer models and thus cannot exploit higher-order aggregations; second, the naive noisy aggregation patch for supporting inference privacy severely hurts the performance of SAGE-NDP. As expected, since the node-level private GAP-NDP hides more information (e.g., node features, labels, and all the adjacent edges to a node) than the edge-level private GAP-EDP, it requires larger privacy budgets to achieve a reasonable accuracy. Still, the accuracy loss with respect to the non-private method is higher in the node-level private method as we have further information loss due to neighborhood sampling (to bound the graph's maximum degree) and gradient clipping (to bound the sensitivity in DP-SGD/Adam).

Resilience Against Privacy Attacks

As mentioned above, the node-level private methods require a higher privacy budget than the edge-level private ones as they attempt to hide much more information. In order to assess the practical implications of choosing rather large privacy budgets (e.g., 𝜖 = 8 in Table 2), we empirically measure the privacy guarantees of GAP-NDP and other node-level private methods by conducting node-level membership inference attack [START_REF] He | Node-level membership inference attacks against graph neural networks[END_REF][START_REF] Iyiola E Olatunji | Membership inference attack on graph neural networks[END_REF] as the most relevant adapted privacy attack to GNNs.

Attack overview. The attack is modeled as a binary classification task, where the goal is to infer whether an arbitrary node 𝑣 is a member of the training set V 𝑇 of the target GNN. The key intuition is that due to overfitting, GNNs give more confident probability scores to training nodes than to test ones, which can be exploited by the attacker to distinguish members of the training set. Having access to a shadow graph dataset coming from the same distribution as the target graph, the attacker first trains a shadow GNN to mimic the behavior of the target GNN, but for which the membership ground truth is known. Then, the attacker trains an attack model over the probability scores of the shadow graph nodes and their corresponding membership labels. Finally, the attacker uses the trained attack model to infer the membership of the target graph nodes.

Attack settings. We follow the TSTF (train on subgraph, test on full graph) approach of [START_REF] Iyiola E Olatunji | Membership inference attack on graph neural networks[END_REF] for the node-level membership inference attack. Specifically, we consider a strong adversary with access to a shadow graph dataset with 1000 nodes per class, which are sampled uniformly at random from the target dataset. For the shadow model, we use the same architecture and hyperparameters as the target model (described in Section 7.3). Similar to prior work [START_REF] Iyiola E Olatunji | Membership inference attack on graph neural networks[END_REF], we use a 3-layer MLP with 64 hidden units as the attack model, and use the area under the receiver operating characteristic curve (AUC) averaged over 10 runs as the evaluation metric.

Results. Table 3 reports the mean AUC of the attack on different node-level private methods trained with the same setting as in Figure 6 (right). As we see, the attack is quite effective on the non-private methods (𝜖 = ∞), especially on Facebook and Amazon datasets. The success of the attack on each method mainly depends on its generalization gap (the difference between the training and test accuracy): the higher the generalization gap, the more confident the model is on the training nodes and the easier it is to distinguish them from the test nodes. Hence, the lower attack performance on the nonprivate SAGE method is due to its lower generalization gap compared to the other methods. Nevertheless, for all private GNN methods, we observe that DP with privacy budgets as large as 𝜖 = 16 can effectively defend against the attack, reducing the AUC to about 50% (random baseline) on all datasets. This result is in line with the work of [START_REF] Jagielski | Auditing differentially private machine learning: How private is private sgd[END_REF][START_REF] Jayaraman | Evaluating differentially private machine learning in practice[END_REF][START_REF] Nasr | Adversary instantiation: Lower bounds for differentially private machine learning[END_REF],

showing that DP with large privacy budgets can still effectively mitigate realistic membership inference attacks.

Ablation Studies

Effectiveness of the encoder module (EM). In this experiment, we investigate the effect of EM on the accuracy/privacy performance of the proposed methods, GAP-EDP and GAP-NDP. We compare the case in which EM is used as usual with the case where we remove EM and just input the original node features to the aggregation module. The results under different privacy budgets are given in Figure 7. We can observe that in all cases, the accuracy of GAP-EDP and GAP-NDP is higher with EM than without it. For example, leveraging EM results in a gain of around 20, 2, and 5 accuracy points for GAP-EDP with 𝜖 = 1 on Facebook, Reddit, and Amazon datasets, respectively. GAP-NDP with EM also benefits from a gain of more than 10, 10, and 5 points with 𝜖 = 4 on Facebook, Reedit, and Amazon datasets, respectively. As discussed in Section 4.2, the improved performance with EM is mainly due to the reduced dimensionality of the aggregation module's input, which leads to adding less noise to the aggregations. Also, the effect of EM is more significant on GAP-NDP, as the amount of noise injected into the aggregations is generally larger for node-level privacy, hence dimensionality reduction becomes more critical to mitigate the impact of noise.

Effect of the number of hops. In this experiment, we investigate how changing the number of hops 𝐾 affects the accuracy/privacy performance of our proposed methods, GAP-EDP and GAP-NDP. We vary 𝐾 within {1, 2, 3, 4, 5} and report the accuracy under different privacy budgets: 𝜖 ∈ {1, 4} for GAP-EDP and 𝜖 ∈ {8, 16} for GAP-NDP. The result is depicted in Figure 8. We observe that both of our methods can effectively benefit from allowing multiple hops, but there is a trade-off in increasing the number of hops. As we increment 𝐾, the accuracy of both GAP-EDP and GAP-NDP method increase up to a point and then steady or decrease in almost all cases. The reason is that with a larger 𝐾 the model is able to utilize information from more distant nodes (all the nodes within the 𝐾-hop neighborhood of a node) for prediction, can increase the final accuracy. However, as more hops are involved, the amount of noise in the aggregations is also increased, which adversely affects the model's accuracy. We can see that with the lower privacy budgets where the noise is more severe, both GAP-EDP and GAP-NDP achieve their peak accuracy at smaller 𝐾 values. But as the privacy budget increases, the magnitude of the noise is reduced, enabling the models to benefit from larger 𝐾 values.

Effect of the maximum degree. We now analyze the effect of 𝐷 on the performance of our node-level private method. We vary 𝐷 from 10 to 400 and report GAP-NDP's accuracy under two different privacy budgets 𝜖 ∈ {4, 16}. Figure 9 shows that the accuracy keeps growing with 𝐷 on Reddit (which has a high average degree), while on Facebook and Amazon (lower average degrees) the accuracy increases with 𝐷 up to a peak point, and drops afterwards. This is due to the trade-off between having more samples for aggregation and the amount of noise injected: the larger 𝐷, the fewer neighbors are excluded from the aggregations (i.e., less information loss), but on the other hand, the larger the sensitivity of the aggregation function, leading to more noise injection. We also observe that the accuracy gain as a result of increasing 𝐷 gets bigger as the privacy budget is increased from 5 to 20, since a higher privacy budget compensates for the higher sensitivity by reducing the amount of noise.

Conclusion

In this paper, we presented GAP, a privacy-preserving GNN architecture that ensures both edge-level and node-level differential privacy for training and inference over sensitive graph data. We used aggregation perturbation, where the Gaussian mechanism is applied to the output of the GNN's aggregation function, as a fundamental technique to achieve DP in our approach. We proposed a new GNN architecture tailored to the specifics of private learning over graphs, aiming to achieve better privacy-accuracy trade-offs while tackling the intricate challenges involved in the design of differentially private GNNs. Experimental results over real-world graph datasets showed that our approach achieves favorable privacy/accuracy trade-offs and significantly outperforms existing methods. Promising future directions include: (i) investigating robust aggregation functions that provide specific benefits for private learning; (ii) exploiting the redundancy of information in recursive aggregations to achieve tighter composition when the number of hops 𝐾 gets large, which might prove useful for specific applications; (iii) extending the framework to other tasks and scenarios, such as link-wise prediction or learning over dynamic graphs; and (iv) conducting an extended theoretical analysis of differentially private GNNs, such as proving utility bounds and characterizing their expressiveness.

FFigure 1 :

 1 Figure1: Schema of an unfolded 2-layer GNN taking an example graph as input. At each layer, every node aggregates its neighbors' embedding vectors (initially node features, e.g. X A for node A), which is then updated using a neural net into a new vector (e.g., H A ). Removing an arbitrary edge (here, the edge from node B to F) excludes the source node (B) from the aggregation set of the destination node (F). At the first layer, this will only alter the destination node's embedding, but this change is propagated to the neighboring nodes in the next layer. Node embeddings that are affected by the removal of edge (B,F) are indicated in red.

CacheFigure 3 :

 3 Figure 3: Overview of GAP's architecture: (1) The encoder is trained using only node features (X) and labels (Y). (2)The encoded features are given to the aggregation module to compute private 𝐾-hop aggregations (here, 𝐾 = 2) using the graph's adjacency matrix (A). (3) The classification module is trained over the private aggregations for label prediction.

Figure 4 :

 4 Figure 4: (a) Transductive learning: training and inference steps are conducted on the same graph, but different nodes are used for training and testing. Here, the blue nodes (A, D, and E) are used for training and the red nodes (B, C, and F) for inference. (b) Inductive learning: training and inference steps are performed on different graphs. Here, the left and right graphs are used for training and inference, respectively.

Theorem 2 .Proposition 3 .

 23 analysis of GAP's training and inference is provided below. Training privacy. The node-level privacy guarantees of the PMA mechanism and the GAP training algorithm are as follows. Detailed proofs are deferred to Appendix A. Given the maximum degree 𝐷 ≥ 1, maximum hop 𝐾 ≥ 1, and noise variance 𝜎 2 , Algorithm 1 (PMA mechanism) satisfies node-level (𝛼, 𝐷𝐾 𝛼 /2𝜎 2 )-RDP for any 𝛼 > 1. For any 𝛼 > 1, let encoder pre-training (Step 1 of Algorithm 2) and CM training (Step 5 of Algorithm 2) satisfy (𝛼, 𝜖 1 (𝛼))-RDP and (𝛼, 𝜖 5 (𝛼))-RDP, respectively. Then, for any 0 < 𝛿 < 1, maximum hop 𝐾 ≥ 1, maximum degree 𝐷 ≥ 1, and noise variance 𝜎 2 , Algorithm 2 satisfies node-level (𝜖, 𝛿)-DP with 𝜖 = 𝜖 1 (𝛼) + 𝜖 5 (𝛼) + 𝐷𝐾 𝛼 /2𝜎 2 + log(1/ 𝛿) /𝛼-1.

Figure 6 :

 6 Figure 6: Accuracy vs. privacy cost (𝜖) of edge-level private algorithms (left) and node-level private methods (right).

Figure 7 :

 7 Figure 7: Effect of the encoder module (EM) on the accuracy/privacy performance of the edge-level private GAP-EDP (top) and the node-level private GAP-NDP (bottom).

Figure 8 :

 8 Figure 8: Effect of the number of hops 𝐾 on the accuracy/privacy performance of the edge-level private GAP-EDP (top) and the node-level private GAP-NDP (bottom).

Figure 9 :

 9 Figure 9: Effect of the degree bound 𝐷 on the accuracy/privacy performance of the node-level private GAP-NDP method.

  normalize

	6	end
	7 end
	8 return X(1) , . . . , X(𝐾 )

  Inductive setting: In this case, first the new graph's node features are given to the encoder to obtain low-dimensional features, which are fed to AM to compute private aggregations. Then, the private aggregations are given to CM to obtain the final predictions. The only part where the private graph structure is queried is the AM, in which the PMA mechanism is applied to the new graph data, and thus the output is private. Furthermore, since the training and test graphs are disjoint, this application of the PMA mechanism is subject to the parallel composition of differentially private mechanisms, and thus it does not increase the privacy costs beyond that of training's. The other parts, the encoder and CM, perform graph-agnostic computations and only post-process previous DP outputs, leading to GAP ensuring inference privacy without extra privacy costs.

Table 1 :

 1 Overview of dataset statistics.

	D	N	E	D	F	C
	F	26,406	2,117,924	62	501	6
	R	116,713	46,233,380	209	602	8
	A	1,790,731	80,966,832	22	100	10

Table 2 :

 2 Test accuracy of different methods on the three datasets. The best performing method in each category -noneprivate, edge-level DP and node-level DP -is highlighted.

		M	𝜖	F	R	A
		GAP-∞	∞	80.0 ± 0.48	99.4 ± 0.02	91.2 ± 0.07
	N	SAGE-∞	∞	83.2 ± 0.68	99.1 ± 0.01	92.7 ± 0.09
	DP	GAP-EDP	4	76.3 ± 0.21 98.7 ± 0.03 83.8 ± 0.26
		SAGE-EDP	4	50.4 ± 0.69 84.6 ± 1.63 68.3 ± 0.99
	E	MLP	0	50.8 ± 0.17 82.4 ± 0.10 71.1 ± 0.18
	DP	GAP-NDP	8	63.2 ± 0.35 94.0 ± 0.14 77.4 ± 0.07
		SAGE-NDP	8	37.2 ± 0.96 60.5 ± 1.10 27.5 ± 0.83
	N	MLP-DP	8	50.2 ± 0.25 81.5 ± 0.12 73.6 ± 0.05
	the autodp library which implements analytical moments
	accountant, and utilize Opacus [51] for training the node-level
	private models with differential privacy. Experiments are
	conducted on Sun Grid Engine with NVIDIA GeForce RTX
	3090 and NVIDIA Tesla V100 GPUs, Intel Xeon 6238 CPUs,
	and 32 GB RAM.

Table 3 :

 3 Mean AUC of node membership inference attack. 𝜖 = 2 𝜖 = 4 𝜖 = 8 𝜖 = 16 𝜖 = ∞

	D	M 𝜖 = 1 GAP-NDP 50.16 50.25 50.61 51.11 52.66 81.67
	F	SAGE-NDP 50.25 50.20 50.23 50.17 50.20 62.49
		MLP-DP	50.32 50.72 52.13 53.44 54.77 81.57
		GAP-NDP 50.04 50.39 51.20 52.23 52.54 54.97
	R	SAGE-NDP 49.97 49.97 49.95 50.00 49.98 50.05
		MLP-DP	51.25 53.09 55.13 56.72 58.32 71.35
		GAP-NDP 50.06 50.23 50.54 51.53 51.72 66.68
	A	SAGE-NDP 49.93 49.93 49.93 49.92 49.97 59.41
		MLP-DP	50.30 50.58 51.43 52.31 53.34 72.97

Acknowledgments

This work was supported by the European Commission's Horizon 2020 Program ICT-48-2020, under grant number 951911, AI4Media project. It was also supported by the French National Research Agency (ANR) through grant ANR-20-CE23-0015 (Project PRIDE). Ali Shahin Shamsabadi acknowledges support from The Alan Turing Institute.

Availability

Our open-source implementation is publicly available on GitHub at https://github.com/sisaman/GAP.

A Deferred Theoretical Arguments

A.1 Proof of Theorem 1

To prove Theorem 1, we first establish the following lemma. Lemma 1. Let A (X, A) = A 𝑇 • X be the summation aggregation function. Assume that the input feature matrix X is row-normalized, such that ∀𝑣 ∈ V : X 𝑣 2 = 1. Then, the edge-level sensitivity of the aggregation function is Δ A = 1.

Proof. Let A and A be the adjacency matrices of two arbitrary edge-level adjacent graphs. Therefore, there exist two nodes 𝑢 and 𝑣 such that:

Without loss of generality, we can assume that A 𝑣,𝑢 = 1 and A 𝑣,𝑢 = 0. The goal is to bound the following quantity:

Let M = A (X, A) be the aggregation function output on A, and

be the 𝑖-th row of M corresponding to the aggregated vector for the 𝑖-th node. Analogously, let M = A (X, A ). Then:

2 )

which concludes the proof.

We can now prove Theorem 1.

Proof. The PMA mechanism applies the Gaussian mechanism on the output of the summation aggregation function A (X, A) = A 𝑇 • X. Based on Lemma 1, the edge-level sensitivity of A (•) is 1. Therefore, according to Corollary 3 of [START_REF] Mironov | Rényi differential privacy[END_REF], each individual application of the Gaussian mechanism is (𝛼, 𝛼 /2𝜎 2 )-RDP. As PMA can be seen as an adaptive composition of 𝐾 such mechanisms, based on Proposition 1 of [START_REF] Mironov | Rényi differential privacy[END_REF], the total privacy cost is (𝛼, 𝐾 𝛼 /2𝜎 2 )-RDP.

A.2 Proof of Proposition 2

Proof. Under edge-level DP, only the adjacency information is protected. In Algorithm 2, the only step where the graph's adjacency is used is the application of the PMA mechanism (step 4), which according to Theorem 1 is (𝛼, 𝐾 𝛼 /2𝜎 2 )-RDP.

Since EM does not use the graph's edges and the classification module only post-process the private aggregated features without accessing the edges again, the total privacy cost remains (𝛼, 𝐾 𝛼 /2𝜎

A.3 Proof of Theorem 2

We first prove Lemma 2 and Lemma 3, and then prove Theorem 2.

Lemma 2. Given any graph

be the summation aggregation function over the neighborhood 𝔑 𝑣 of any arbitrary node 𝑣 ∈ V. Assume that the input feature matrix X is row-normalized, such that ∀𝑣 ∈ V :

Then, the node-level sensitivity of agg(.) is Δ agg = 1.

Proof. Consider a node-level adjacent graph G = (V , E , X ) formed by adding a single node 𝑞 to G. Hence, we have V = V ∪ {𝑞}, and X 𝑣 = X 𝑣 for every node 𝑣 ∈ V. Let A and A be the adjacency matrices of G and G respectively. The goal is to bound the following:

where 𝔑 𝑣 = {𝑢 : A 𝑢,𝑣 = 1} and 𝔑 𝑣 = {𝑢 : A 𝑢,𝑣 = 1} are the adjacent nodes to 𝑣 in G and G , respectively. Fixing any arbitrary node 𝑣 ∈ V, we have the following two cases:

1. If 𝑞 ∈ 𝔑 𝑣 , then we have 𝔑 𝑣 = 𝔑 𝑣 \ {𝑞}. Therefore:

2. If 𝑞 ∉ 𝔑 𝑣 , then we have 𝔑 𝑣 = 𝔑 𝑣 . Therefore:

Eq. 14 follows from the above two cases.

Lemma 3.

Given any graph G = (V, E, X) with adjacency matrix A and maximum degree bounded above by some constant 𝐷 > 0, assume that the feature matrix X is row-normalized, such that ∀𝑣 ∈ V :

𝑢 ∈𝔑 𝑣 X 𝑢 be the summation aggregation function over the neighborhood 𝔑 𝑣 of any arbitrary node 𝑣 ∈ V, and A (X, A) be a noisy aggregation mechanism which applies the Gaussian mechanism independently on the aggregated vector of every individual node as:

Proof. According to Lemma 2, the node-level sensitivity of agg ({X 𝑢 : ∀𝑢 ∈ 𝔑 𝑣 }) is 1, and thus each individual noisy aggregation query is (𝛼, 𝛼 /2𝜎 2 )-RDP. Although A is composed of 𝑁 = |V | such queries in total (one noisy aggregation per node), as G's maximum degree is bounded above by 𝐷, the embedding X 𝑢 of each node 𝑢 only contributes to maximum 𝐷 out of 𝑁 queries. As these 𝑁 queries are chosen non-adaptively and the noise of the Gaussian mechanism is independently drawn for each query, the maximum privacy cost of A (.) is equivalent to 𝐷 compositions of (𝛼, 𝛼 /2𝜎 2 )-RDP mechanisms, which based on Proposition 1 of [START_REF] Mironov | Rényi differential privacy[END_REF] is (𝐷𝛼, 𝛼 /2𝜎 2 )-RDP. Now, we prove Theorem 2.

Proof. At each step of the PMA mechanism, the Gaussian mechanism is applied on every output row of the summation aggregation function A (X, A) = A 𝑇 • X. Based on Lemma 3, this mechanism is (𝛼, 𝛼𝐷 /2𝜎 2 )-RDP. As PMA can be seen as an adaptive composition of 𝐾 such mechanisms, based on Proposition 1 of [START_REF] Mironov | Rényi differential privacy[END_REF], the total privacy cost is (𝛼, 𝛼𝐷𝐾 /2𝜎 2 )-RDP.

A.4 Proof of Proposition 3

Proof. Under node-level DP, all the information pertaining to an individual node, including its features, label, and edges, are private. The first step of Algorithm 2 privately processes the node features and labels so as to satisfy (𝛼, 𝜖 1 (𝛼))-RDP.

Steps 2 and 3 of the algorithm, however, expose the private node features, but then they are processed by steps 4 and 5, which are (𝛼, 𝐷𝐾 𝛼 /2𝜎 2 )-RDP (according to Theorem 2) and (𝛼, 𝜖 5 (𝛼))-RDP, respectively. As a result, Algorithm 2 can be seen as an adaptive composition of an (𝛼, 𝜖 1 (𝛼))-RDP mechanism, an (𝛼, 𝐷𝐾 𝛼 /2𝜎 2 )-RDP mechanism, and an (𝛼, 𝜖 5 (𝛼))-RDP mechanism. Therefore, based on Proposition 1 of [START_REF] Mironov | Rényi differential privacy[END_REF], the total node-level privacy cost of Algorithm 2 is (𝛼, 𝜖 1 (𝛼) + 𝐷𝐾 𝛼 /2𝜎 2 + 𝜖 5 (𝛼))-RDP, which ensures (𝜖 1 (𝛼) +