ProGAP: Progressive Graph Neural Networks with Differential Privacy
  Guarantees
Graph Neural Networks (GNNs) have become a popular tool for learning on
graphs, but their widespread use raises privacy concerns as graph data can
contain personal or sensitive information. Differentially private GNN models
have been recently proposed to preserve privacy while still allowing for
effective learning over graph-structured datasets. However, achieving an ideal
balance between accuracy and privacy in GNNs remains challenging due to the
intrinsic structural connectivity of graphs. In this paper, we propose a new
differentially private GNN called ProGAP that uses a progressive training
scheme to improve such accuracy-privacy trade-offs. Combined with the
aggregation perturbation technique to ensure differential privacy, ProGAP
splits a GNN into a sequence of overlapping submodels that are trained
progressively, expanding from the first submodel to the complete model.
Specifically, each submodel is trained over the privately aggregated node
embeddings learned and cached by the previous submodels, leading to an
increased expressive power compared to previous approaches while limiting the
incurred privacy costs. We formally prove that ProGAP ensures edge-level and
node-level privacy guarantees for both training and inference stages, and
evaluate its performance on benchmark graph datasets. Experimental results
demonstrate that ProGAP can achieve up to 5-10% higher accuracy than existing
state-of-the-art differentially private GNNs. Our code is available at
https://github.com/sisaman/ProGAP.
Sina Sajadmanesh, Daniel Gatica-Perez
# ProGAP: Progressive Graph Neural Networks with Differential Privacy Guarantees

###### Abstract

Graph Neural Networks (GNNs) have become a popular tool for learning on graphs, but their widespread use raises privacy concerns as graph data can contain personal or sensitive information. Differentially private GNN models have been recently proposed to preserve privacy while still allowing for effective learning over graph-structured datasets. However, achieving an ideal balance between accuracy and privacy in GNNs remains challenging due to the intrinsic structural connectivity of graphs. In this paper, we propose a new differentially private GNN called ProGAP that uses a progressive training scheme to improve such accuracy-privacy trade-offs. Combined with the aggregation perturbation technique to ensure differential privacy, ProGAP splits a GNN into a sequence of overlapping submodels that are trained progressively, expanding from the first submodel to the complete model. Specifically, each submodel is trained over the privately aggregated node embeddings learned and cached by the previous submodels, leading to an increased expressive power compared to previous approaches while limiting the incurred privacy costs. We formally prove that ProGAP ensures edge-level and node-level privacy guarantees for both training and inference stages, and evaluate its performance on benchmark graph datasets. Experimental results demonstrate that ProGAP can achieve up to 5-10% higher accuracy than existing state-of-the-art differentially private GNNs.

Keywords:Graph Neural Network Differential Privacy Progressive Learning Node Classification.

## 1 Introduction

Graph Neural Networks (GNNs) have emerged as a powerful tool for learning from graph-structured data, and their popularity has surged due to their ability to achieve impressive performance in a wide range of applications, including social network analysis, drug discovery, recommendation systems, and traffic prediction [22, 5, 14, 48, 2]. GNNs excel at learning from the structural connectivity of graphs by iteratively updating node embeddings through information aggregation and transformation from neighboring nodes, making them well-suited for tasks such as node classification, graph classification, and link prediction [50, 16, 15, 25, 46, 7]. However, as with many data-driven approaches,
GNNs can expose individuals to privacy risks when applied to graph data containing sensitive information, such as social connections, medical records, and financial transactions [36, 42]. Recent studies have shown that various attacks, such as link stealing, membership inference, and node attribute inference, can successfully break the privacy of graph datasets [18, 19, 34, 44], posing a significant challenge for the practical use of GNNs in privacy-sensitive applications.

To address the privacy concerns associated with GNNs, researchers have recently studied _differential privacy (DP)_, a well-established mathematical framework that provides strong privacy guarantees, usually by adding random noise to the data [9, 10]. However, applying DP to GNNs is very challenging due to the complex structural connectivity of graphs, rendering traditional private learning methods, such as differentially private stochastic gradient descent (DP-SGD) [1], infeasible [3, 8, 39]. Recently, the _aggregation perturbation_ (AP) approach [39] has emerged as a state-of-the-art technique for ensuring DP in GNNs. Rather than perturbing the model gradients as done in the standard DP-SGD algorithm and its variants, this method perturbs the aggregate information obtained from the GNN neighborhood aggregation step. Consequently, such perturbations can obfuscate the presence of a single edge, which is called _edge-level privacy_, or a single node and all its adjacent edges, referred to as _node-level privacy_[37].

The key limitation of AP is its incompatibility with standard GNN architectures due to the high privacy costs it entails [39]. This is because conventional GNN models constantly query the aggregation functions with every update to the model parameters, which necessitates the re-perturbation of all aggregate outputs at every training iteration to ensure DP, leading to a significant increase in privacy costs. To mitigate this issue, Sajadmanesh _et al_. [39] proposed a method called GAP, which decouples the aggregation steps from the model parameters. In GAP, node features are recursively aggregated first, and then a classifier is learned over the resulting perturbed aggregations, enabling DP to be maintained without incurring excessive privacy costs. Due to having non-trainable aggregations, however, such decoupling approaches reduce the expressiveness of the GNN [12], leading to suboptimal accuracy-privacy trade-offs.

In the face of these challenges, we present a novel differentially private GNN, called _"Progressive **G**NN with **A**ggregation **P**erturbation"_ (ProGAP). Our new method uses the same AP technique as in GAP to ensure DP. However, instead of decoupling the aggregation steps from the learnable modules, ProGAP adopts a multi-stage, progressive training paradigm to surmount the formidable privacy costs associated with AP. Specifically, ProGAP converts a \(K\)-layer GNN model into a sequence of overlapping submodels, where the \(i\)-th submodel comprises the first \(i\) layers of the model, followed by a lightweight supervision head layer with softmax activation that utilizes node labels to guide the submodel's training. Starting with the shallowest submodel, ProGAP then proceeds progressively to train deeper submodels, each of which is referred to as a training stage. At every stage, the learned node embeddings from the preceding stage are aggregated, perturbed, and then cached to save privacy budget, allowing ProGAP to learn
a new set of private node embeddings. Ultimately, the last stage's embeddings are used to generate final node-wise predictions.

The proposed progressive training approach overcomes the high privacy costs of AP by allowing the perturbations to be applied only once per stage rather than at every training iteration. ProGAP also maintains a higher level of expressive power compared to GAP, as the aggregation steps now operate on the learned embeddings from the preceding stages, which are more expressive than the raw node features. Moreover, we prove that ProGAP retains all the benefits of GAP, such as edge- and node-level privacy guarantees and zero-cost privacy at inference time. We evaluate ProGAP on five node classification datasets, including Facebook, Amazon, and Reddit, and demonstrate that it can achieve up to 10.4% and 5.5% higher accuracy compared to GAP under edge- and node-level DP with an epsilon of 1 and 8, respectively.

## 2 Related Work

Several recent studies have investigated differential privacy (DP) to provide formal privacy guarantees in various GNN learning settings. For example, Sajadmanesh and Gatica-Perez [38] propose a locally private GNN for a distributed learning environment, where node features and labels remain private, while the GNN training is federated by a central server with access to graph edges. Lin _et al_. [29] also introduce a locally private GNN, called Solitude, that preserves edge privacy in a decentralized graph, where each node keeps its own private connections. However, both of these approaches use local differential privacy [24], which operates under a different problem setting from our method.

Other approaches propose edge-level DP algorithms for GNNs. Wu _et al_. [44] developed an edge-level private method that modifies the input graph directly through randomized response or the Laplace mechanism, followed by training a GNN on the resulting noisy graph. In contrast, Kolluri _et al_. [27] propose LPGNet, which adopts a tailored neural network architecture. Instead of directly using the graph edges, they encode graph adjacency information in the form of low-sensitivity cluster vectors, which are then perturbed using the Laplace mechanism to preserve edge-level privacy. Unlike our approach, however, neither of these methods provides node-level privacy guarantees.

Olatunji _et al_. [33] propose the first node-level private GNN by adapting the framework of PATE [35]. In their approach, a student GNN model is trained on public graph data, with each node privately labeled using teacher GNN models that are trained exclusively for the corresponding query node. Nevertheless, their approach relies on public graph data and may not be applicable in all situations. Daigavane _et al_. [8] extend the standard DP-SGD algorithm and privacy amplification by subsampling to bounded-degree graph data to achieve node-level DP, but their method fails to provide inference privacy. Finally, Sajadmanesh _et al_. [39] propose GAP, a private GNN learning framework that provides both edge-level and node-level privacy guarantees using the aggregation perturbation approach. They decouple the aggregation steps from the neu
ral network model to manage the privacy costs of their method. Although our method leverages the same aggregation perturbation technique, we take a different approach to limit the privacy costs using a progressive training scheme.

The main concept behind progressive learning is to train the model on simpler tasks first and then gradually move towards more challenging tasks. It was originally introduced to stabilize the training of deep learning models and has been widely adopted in various computer vision applications, such as facial attribute editing [45], image super-resolution [43], image synthesis [23], and representation learning [28]. This technique has also been extended to federated learning, mainly to minimize the communication overhead between clients and the central server [4, 17, 41]. However, the potential benefit of progressive learning in DP applications has not been explored yet. In this paper, we are first to examine the advantages of progressive learning in the context of private GNNs.

## 3 Background

### Differential Privacy

Differential privacy (DP) is a widely accepted framework for measuring the privacy guarantees of algorithms that operate on sensitive data. The main idea of DP is to ensure that the output of an algorithm is not significantly affected by the presence or absence of any particular individual's data in the input. This means that even if an attacker has access to all but one individual's data, they cannot determine whether that individual's data was used in the computation. The formal definition of DP is as follows [10]:

Definition 1: Given \(\epsilon>0\) and \(\delta\in[0,1]\), a randomized algorithm \(\mathcal{A}\) satisfies \((\epsilon,\delta)\)-differential privacy, if for all adjacent datasets \(\mathcal{D}\) and \(\mathcal{D}^{\prime}\) differing by at most one record and for all possible subsets of \(\mathcal{A}\)'s outputs \(S\subseteq Range(\mathcal{A})\):

\[\Pr[\mathcal{A}(\mathcal{D})\in S]\leq e^{\epsilon}\Pr[\mathcal{A}(\mathcal{ D}^{\prime})\in S]+\delta.\]

To adapt the definition of DP for graphs, two different notions of adjacency are defined: edge-level and node-level adjacency. In the former, two graphs are adjacent if they differ only in the presence of a single edge, whereas in the latter, the two graphs differ by a single node with its features, labels, and all attached edges. Accordingly, the definitions of edge-level and node-level DP are derived from these definitions [37]. Specifically, an algorithm \(\mathcal{A}\) provides edge-/node-level \((\epsilon,\delta)\)-DP if for every two edge-/node-level adjacent graph datasets \(\mathcal{G}\) and \(\mathcal{G}^{\prime}\) and any set of outputs \(S\subseteq Range(\mathcal{A})\), we have \(\Pr[\mathcal{A}(\mathcal{G})\in S]\leq e^{\epsilon}\Pr[\mathcal{A}(\mathcal{ G}^{\prime})\in S]+\delta\).

### Graph Neural Networks

Consider a graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) with a set of nodes \(\mathcal{V}=\{v_{1},\ldots,v_{N}\}\) and edges \(\mathcal{E}\) represented by an adjacency matrix \(\mathbf{A}\in\{0,1\}^{N\times N}\). Node features are represented by a matrix \(\mathbf{X}\in\mathbb{R}^{N\times d}\), where \(\mathbf{X}_{i}\) denotes the \(d\)-dimensional feature
vector of node \(v_{i}\). A common \(K\)-layer GNN is composed of \(K\) layers of graph convolution that are applied sequentially. Specifically, layer \(k\) takes as input the adjacency matrix \(\mathbf{A}\) and the node embeddings produced by layer \(k-1\), denoted by \(\mathbf{X}^{(k-1)}\), and outputs a new embedding for each node by aggregating the embeddings of its adjacent neighbors, followed by a neural network transformation. In its simplest form, the formal update rule for layer \(k\) can be written as follows:

\[\mathbf{X}^{(k)}=\text{MLP}\left(\text{Agg}(\mathbf{A},\mathbf{X}^{(k-1)}); \mathbf{\Theta}^{(k)}\right), \tag{1}\]

where Agg is a differentiable permutation-invariant _neighborhood aggregation function_ and MLP denotes a multilayer perceptron parameterized by \(\mathbf{\Theta}^{(k)}\) that takes the aggregated embeddings as input and produces a new embedding for each node. The aggregation function can take various forms, such as mean, sum, or max pooling. The input to the first layer is \(\mathbf{X}^{(0)}=\mathbf{X}\), i.e., the initial node features. The output of the final layer \(\mathbf{X}^{(K)}\) can then be used for downstream tasks, such as node classification or link prediction.

### Problem Definition

Consistent with prior work [8, 39], we focus on the node classification task. Consider a GNN-based node classification model \(\mathcal{M}(\mathbf{A},\mathbf{X};\mathbf{\Theta})\) parameterized by a set of parameters \(\mathbf{\Theta}\) that takes the adjacency matrix \(\mathbf{A}\) and the node features \(\mathbf{X}\), and outputs the corresponding predicted node labels \(\mathbf{\widehat{Y}}\):

\[\mathbf{\widehat{Y}}=\mathcal{M}(\mathbf{A},\mathbf{X};\mathbf{\Theta}). \tag{2}\]

We seek to minimize a standard classification loss function \(\mathcal{L}\), such as cross-entropy, with respect to the set of model parameters \(\mathbf{\Theta}\):

\[\arg\min_{\mathbf{\Theta}}\mathcal{L}(\mathcal{M}(\mathbf{A},\mathbf{X}; \mathbf{\Theta}),\mathbf{Y}), \tag{3}\]

where \(\mathbf{Y}\in\{0,1\}^{N\times C}\) is the ground-truth node labels with \(C\) being the number of classes. Given a graph dataset \(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X},\mathbf{Y})\), our goal is to ensure the privacy of \(\mathcal{G}\) at both the training (Eq. 3) and inference (Eq. 2) phases of the model \(\mathcal{M}\), using the differential privacy notions defined for graphs, i.e., edge-level and node-level DP. Note that preserving privacy during the inference stage is of utmost importance since the adjacency information of the graph is still used at inference time to generate the predicted labels, and thus sensitive information about the graph could potentially be leaked even with \(\mathbf{\Theta}\) being differentially private [39].

## 4 Proposed Method

In this section, we present our proposed ProGAP method, which leverages the aggregation perturbation (AP) technique [39] to ensure differential privacy but introduces a novel progressive learning scheme to restrain the privacy costs of AP incurred during training. The overview of ProGAP architecture is illustrated in Figure 1, and its forward propagation (inference) and training algorithms are presented in Algorithm 1 and Algorithm 2, respectively. In the following, we first describe our method in detail and then analyze its privacy guarantees.
### Model Architecture and Training

We start by considering a simple non-private sequential GNN model \(\mathcal{M}\) with \(K\) aggregation layers as the following:

\[\mathbf{X}^{(0)} =\mathrm{MLP}^{(0)}_{base}\left(\mathbf{X};\mathbf{\Theta}^{(0)}_{ base}\right), \tag{4}\] \[\mathbf{X}^{(k)} =\mathrm{MLP}^{(k)}_{base}\left(\mathbf{A}_{\text{GG}}(\mathbf{A},\mathbf{X}^{(k-1)});\mathbf{\Theta}^{(k)}_{base}\right),\quad\forall k\in\{1, \ldots,K\},\] (5) \[\mathbf{\widehat{Y}} =\mathrm{MLP}_{head}\left(\mathbf{X}^{(K)};\mathbf{\Theta}_{ head}\right), \tag{6}\]

where \(\mathbf{X}^{(k)}\) is the node embeddings generated at layer \(k\) by \(\mathrm{MLP}^{(k)}_{base}\) having parameters \(\mathbf{\Theta}^{(k)}_{base}\), and \(\mathrm{MLP}_{head}\) is a multi-layer perceptron parameterized by \(\mathbf{\Theta}_{head}\) with the softmax activation function that maps the final embeddings \(\mathbf{X}^{(K)}\) to the predicted class probabilities \(\mathbf{\widehat{Y}}\).

To make this model differentially private, we follow the aggregation perturbation technique proposed by Sajadmanesh_et al_. [39] and add noise to the output of the aggregation function. Specifically, we replace the original aggregation function Agg in Eq. 5 with a _Normalize-Aggregate-Perturb_ mechanism defined as:

\[\mathrm{NAP}\left(\mathbf{A},\mathbf{X};\sigma\right)=\left[\sum_{j=1}^{N} \frac{\mathbf{X}_{i}}{\|\mathbf{X}_{i}\|_{2}}\mathbf{A}_{j,i}+\mathcal{N}( \mathbf{0},\sigma^{2}\mathbf{I}_{d})\mid\forall i\in\{1,\ldots,N\}\right], \tag{7}\]

where \(N\) is the number of nodes, \(d\) is the dimension of the input node embeddings, and \(\sigma\) is the standard deviation of the Gaussian noise. Concretely, the

Figure 1: An example ProGAP architecture with three stages. MLP and JK represent multi-layer perceptron and Jumping Knowledge [47] modules, respectively. NAP denotes the normalize-aggregate-perturb module used to ensure the privacy of the adjacency matrix, with its output cached immediately after computation to save privacy budget. Training is done progressively, starting with the first stage and then expanding to the second and third stages, each using its own head MLP. The final prediction is obtained by the head MLP of the last stage.
NAP mechanism row-normalizes the input embeddings to limit the contribution of each node to the aggregated output, then applies the sum aggregation function followed by adding Gaussian noise to the results.

It can be easily shown that the resulting model provides edge-level DP as every query to the adjacency matrix \(\mathbf{A}\) is immediately perturbed with noise. However, training such a model comes at the cost of a significant increase in the privacy budget, which is proportional to the number of queries to the adjacency matrix. Concretely, with \(T\) training iterations, the NAP mechanism is queried \(KT\) times (at each forward pass and each layer), leading to an excessive accumulated privacy cost of \(O(\sqrt{KT})\).

To reduce this cost, we propose a progressive training approach as the following: We first split the model \(\mathcal{M}\) into \(K+1\) overlapping submodels, where submodel \(\mathcal{M}_{s}\), \(s\in\{0,1,\ldots,K\}\), is defined as:

\[\widetilde{\mathbf{X}}^{(s)} =\mathrm{NAP}\left(\mathbf{A},\mathbf{X}^{(s-1)};\sigma\right), \tag{8}\] \[\mathbf{X}^{(s)} =\mathrm{MLP}^{(s)}_{base}\left(\widetilde{\mathbf{X}}^{(s)}; \mathbf{\Theta}^{(s)}_{base}\right),\] (9) \[\widehat{\mathbf{Y}}^{(s)} =\mathrm{MLP}^{(s)}_{head}\left(\mathrm{JK}^{(s)}(\bigcup_{k=0}^ {s}\{\mathbf{X}^{(k)}\};\mathbf{\Theta}^{(s)}_{jump});\mathbf{\Theta}^{(s)}_ {head}\right), \tag{10}\]

where \(\widetilde{\mathbf{X}}^{(s)}\) is the noisy aggregate embeddings of \(\mathcal{M}_{s}\), with \(\widetilde{\mathbf{X}}^{(0)}=\mathbf{X}\). \(\mathrm{JK}^{(s)}\) is a Jumping Knowledge module [47] with parameters \(\mathbf{\Theta}^{(s)}_{jump}\) that combines the embeddings generated by submodels \(\mathcal{M}_{0}\) to \(\mathcal{M}_{s}\), and \(\mathrm{MLP}^{(s)}_{head}\) is a lightweight, 1-layer head MLP with parameters \(\mathbf{\Theta}^{(s)}_{head}\) used to train \(\mathcal{M}_{s}\). Finally, \(\widehat{\mathbf{Y}}^{(s)}\) is the output predictions of \(\mathcal{M}_{s}\). Then, we progressively train the model in \(K+1\) stages, starting from the shallowest submodel \(\mathcal{M}_{0}\) and gradually expanding to
the deepest submodel \(\mathcal{M}_{K}\) (which is equivalent to the full model \(\mathcal{M}\)) as explained by Algorithm 2. For the final inference after training, we simply use the labels predicted by the last submodel \(\mathcal{M}_{K}\), i.e., \(\widehat{\mathbf{Y}}=\widehat{\mathbf{Y}}^{(K)}\).

_The key point in this training strategy is that we immediately save the outputs of NAP modules on their first query and reuse them throughout the training._ More specifically, at each stage \(s\), the perturbed aggregate embedding matrix \(\widetilde{\mathbf{X}}^{(s)}\) computed in the first forward pass of \(\mathcal{M}_{s}\) (via Eq. 8) is stored in the cache and reused in all further queries. This caching mechanism allows us to reduce the privacy costs of the model by a factor of \(T\), as the NAP module in this case is only queried \(K\) times (once per stage) instead of \(KT\) times. At the same time, the aggregations \(\widetilde{\mathbf{X}}^{(s)}\) are computed over the embeddings \(\mathbf{X}^{(s-1)}\) that are already learned in the preceding stage \(s-1\), which provide more expressive power than the raw node features as they also encode information from the adjacency matrix and node labels, and thus lead to better performance.

Remark 1: The proposed ProGAP model can also be trained in a layerwise fashion, i.e., by training each layer \(\text{MLP}_{base}^{(k)}\) individually, while keeping the parameters of the preceding layers frozen and using the same caching mechanism. Note that this is different from the proposed progressive approach, in which all the parameters from layer 0 to layer \(s\), i.e., \(\mathbf{\Theta}_{base}^{(0)},\ldots,\mathbf{\Theta}_{base}^{(s)}\) are trained together in each stage \(s\). In Section 6, we show that such a progressive training strategy leads to better performance than layerwise training.

```
Input : Adjacency matrix \(\mathbf{A}\); node features \(\mathbf{X}\); node labels \(\mathbf{Y}\); model depth \(K\); noise standard deviation \(\sigma\); Output : Trained model parameters \(\mathfrak{P}_{K}^{*}\)
1 initialize \(\mathbf{\Theta}_{base}^{(0)},\mathbf{\Theta}_{jump}^{(0)},\mathbf{\Theta}_{ head}^{(0)}\) randomly
2\(\mathfrak{P}_{0}\leftarrow\{\mathbf{\Theta}_{base}^{(0)},\mathbf{\Theta}_{ jump}^{(0)},\mathbf{\Theta}_{head}^{(0)}\}\)
3for\(s\in\{0,\ldots,K\}\)do
4\(\mathfrak{P}_{s}^{*}\leftarrow\arg\min_{\mathfrak{P}}\mathcal{L}\Big{(} \mathcal{M}_{s}\left(\mathbf{A},\mathbf{X};\sigma,\mathfrak{P}_{s}\right), \mathbf{Y}\Big{)}\)
5if\(s<K\)then
6 initialize \(\mathbf{\Theta}_{base}^{(s+1)},\mathbf{\Theta}_{jump}^{(s+1)},\mathbf{ \Theta}_{head}^{(s+1)}\) randomly
7\(\mathfrak{P}_{s+1}\leftarrow\mathfrak{P}_{s}^{*}\cup\{\mathbf{\Theta}_{base}^ {(s+1)},\mathbf{\Theta}_{jump}^{(s+1)},\mathbf{\Theta}_{head}^{(s+1)}\}\setminus \{\mathbf{\Theta}_{jump}^{*(s)},\mathbf{\Theta}_{head}^{*(s)}\}\)
8
9 end for
10
11 end for return\(\mathfrak{P}_{K}^{*}\)
```

**Algorithm 2**ProGAP Training

### Privacy Analysis

With the following theorem, we show that the proposed training strategy provides edge-level DP. The proof is provided in Appendix 0.A.2.
Theorem 4.1: _Given the maximum stage \(K\geq 0\) and noise variance \(\sigma^{2}\), for any \(\delta\in(0,1)\) Algorithm 2 satisfies edge-level \((\epsilon,\delta)\)-DP with \(\epsilon=\frac{K}{2\sigma^{2}}+\sqrt{2K\log{(1/\delta)}/\sigma}\)._

To ensure node-level DP, however, we must train every submodel using DP-SGD or its variants, as in this case node features and labels are also private and can be leaked with non-private training. Theorem 4.2 establishes the node-level DP guarantee of ProGAP's training algorithm when combined with DP-SGD:

Theorem 4.2: _Given the number of nodes \(N\), batch-size \(B<N\), number of per-stage training iterations \(T\), gradient clipping threshold \(C>0\), maximum stage \(K\geq 0\), maximum cut-off degree \(D\geq 1\), noise variance for aggregation perturbation \(\sigma^{2}_{AP}>0\), and noise variance for gradient perturbation \(\sigma^{2}_{GP}>0\), Algorithm 2 satisfies node-level \((\epsilon,\delta)\)-DP for any \(\delta\in(0,1)\) with:_

\[\epsilon\leq\min_{\alpha>1} \frac{(K+1)T}{\alpha-1}\log\Bigg{\{}\bigg{(}1-\frac{B}{N}\bigg{)} ^{\alpha-1}\left(\alpha\frac{B}{N}-\frac{B}{N}+1\right)\] \[+\binom{\alpha}{2}\left(\frac{B}{N}\right)^{2}\left(1-\frac{B}{N }\right)^{\alpha-2}e^{\frac{C^{2}}{\sigma^{2}_{GP}}}\] \[+\sum_{l=3}^{\alpha}\binom{\alpha}{l}\left(1-\frac{B}{N}\right) ^{\alpha-l}\left(\frac{B}{N}\right)^{l}e^{(l-1)(\frac{C^{2}l}{2\sigma^{2}_{GP} })}\Bigg{\}}\] \[+\frac{DK\alpha}{2\sigma^{2}_{AP}}+\frac{\log(1/\delta)}{\alpha-1},\]

_providing that the optimization in line 4 of Algorithm 2 is done using DP-SGD._

The proof is deferred to Appendix 0.A.3. Note that to decrease the node-level sensitivity of the NAP mechanism (i.e., the impact of adding/removing a node on the output of the NAP mechanism), we assume an upper bound \(D\) on node degrees, and randomly sample edges from the graph to ensure that each node has no more than \(D\) outgoing edges. This is a standard technique to ensure bounded-degree graphs [8, 39].

In addition to training privacy, ProGAP also guarantees privacy during inference at both edge and node levels without any further privacy costs. This is because the entire noisy aggregate matrices \(\widehat{\mathbf{X}}^{(i)}\) corresponding to all the nodes -both training and test ones- are already computed and cached during training and reused for inference (i.e., lines 4 and 5 of Algorithm 1 is not executed at inference time). As a result, the inference for a node no longer depends on its private neighborhood and is done by post-processing differentially private outputs, which does not incur any additional privacy costs.

## 5 Experimental Setup

We test our proposed method on node-wise classification tasks and evaluate its effectiveness in terms of classification accuracy and privacy guarantees.
### Datasets

We conduct experiments on three real-world datasets that have been used in previous work [33, 39, 8], namely Facebook [40], Reddit [16], and Amazon [6], and also two new datasets: Facebook-100 [40] and WeNet [30, 13]. The Facebook dataset is a collection of anonymized social network data from UIUC students, where nodes represent users, edges indicate friendships, and the task is to predict students' class year. The Reddit dataset comprises a set of Reddit posts as nodes, where edges represent if the same user commented on both posts, and the goal is to predict the posts' subreddit. The Amazon dataset is a product co-purchasing network, with nodes representing products and edges indicating if two products are purchased together, and the objective is to predict product category. Facebook-100 is an extended version of the Facebook dataset combining the social network of 100 different American universities. WeNet is a mobile sensing dataset collected from university students in four different countries. Nodes represent eating events, which are linked based on the similarity of location and Wi-Fi sensor readings. Node features are extracted based on cellular and application sensors, and the goal is to predict the country of the events.A summary of the datasets is provided in Table 1.

### Baselines

We compare our ProGAP method against GAP [39], which is the closest related work to ours. We use GAP's official implementation on GitHub1 and follow the same experimental setup as reported in the original paper. We do not include other available differentially private GNN approaches as they either: (i) are outperformed by GAP (e.g., [44, 8]) or (ii) have different problem settings (e.g., [34, 38]) that make them not directly comparable to our method.

Footnote 1: [https://github.com/sisaman/GAP](https://github.com/sisaman/GAP)

### Implementation Details

We use PyTorch Geometric [11] for implementing the models, \(\mathsf{autodp}^{2}\) for privacy accounting, and Opacus [49] for DP training. We follow the same experimental setup as GAP [39], and randomly split the nodes in all the datasets into

\begin{table}
\begin{tabular}{l r r r r r} \hline \hline Dataset & \# Nodes & \# Edges & \# Features & \# Classes & Med. Degree \\ \hline Facebook & 26,406 & 2,117,924 & 501 & 6 & 62 \\ Reddit & 116,713 & 46,233,380 & 602 & 8 & 209 \\ Amazon & 1,790,731 & 80,966,832 & 100 & 10 & 22 \\ Facebook-100 & 1,120,280 & 86,304,478 & 537 & 6 & 57 \\ WeNet & 37,576 & 22,684,206 & 44 & 4 & 286 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Dataset Statistics.
training, validation, and test sets with 75/10/15% ratio, respectively. We vary \(\epsilon\) within \(\{0.25,0.5,1,2,4,\infty\}\) for the edge-level privacy (\(\epsilon=\infty\) corresponds to the non-private setting) and within \(\{2,4,8,16,32\}\) for the node-level privacy setting. For each \(\epsilon\) value, we tune the following hyperparameters based on the mean validation set accuracy computed over 10 runs: \(\text{MLP}_{base}\) layers in \(\{1,2\}\), model depth \(K\) in \(\{1,2,3,4,5\}\), and learning rate in \(\{0.01,0.05\}\). The value of \(\delta\) is fixed per each dataset to be smaller than the inverse number of private units (i.e., edges for edge-level privacy, nodes for node-level privacy). For all cases, we set the number of \(\text{MLP}_{head}\) layers to 1 and use concatenation for the JK modules. Additionally, we set the number of hidden units to 16 and use the SeLU activation function [26]. We use batch normalization except for the node-level setting, for which we use group normalization with one group. Under the edge-level setting, we train the models with full-sized batches for 100 epochs using the Adam optimizer and perform early stopping based on the validation set accuracy. For the node-level setting, we use randomized neighbor sampling to bound the maximum degree \(D\) to 50 for Amazon, 100 for Facebook and Facebook-100, and 400 for Reddit and WeNet. We use DP-Adam [15] with a clipping threshold of 1.0. We tune the number of per-stage epochs in \(\{5,10\}\) and set the batch size to 256, 1024, 2048, 4096, and 4096 for Facebook, Reddit, Amazon, Facebook-100, and WeNet, respectively. Finally, we report the average test accuracy over 10 runs with 95% confidence intervals calculated by bootstrapping with 1000 samples. We open-source our implementation on GitHub.3

Footnote 3: It will be made public upon acceptance.

## 6 Results and Discussion

### Accuracy-Privacy Trade-off

Table 2 presents the test accuracy of ProGAP against GAP at three different privacy levels: non-private with \(\epsilon=\infty\), edge-level privacy with \(\epsilon=1\), and node-level privacy with \(\epsilon=8\). The results are reported as mean accuracy \(\pm\) 95% confidence interval. We observe that ProGAP outperforms GAP in almost all cases, and often by a substantial margin. Specifically, in the non-private setting,

\begin{table}
\begin{tabular}{l l l l l l l} \hline \hline Privacy & \multirow{2}{*}{Method} & \multirow{2}{*}{\(\epsilon\)} & \multirow{2}{*}{Facebook} & \multirow{2}{*}{Reddit} & \multirow{2}{*}{Amazon} & \multirow{2}{*}{Facebook-100} & \multirow{2}{*}{Wenet} \\ Level & & & & & & \\ \hline Non- & ProGAP & \(\infty\) & **84.5 \(\pm\) 0.24** & 99.3 \(\pm\) 0.03 & **93.3 \(\pm\) 0.04** & **74.4 \(\pm\) 0.14** & **73.9 \(\pm\) 0.25** \\ Private & GAP & \(\infty\) & 80.5 \(\pm\) 0.42 & **99.5 \(\pm\) 0.01** & 92.0 \(\pm\) 0.10 & 66.4 \(\pm\) 0.35 & 69.7 \(\pm\) 0.14 \\ \hline Edge & ProGAP & 1.0 & **77.2 \(\pm\) 0.33** & **97.8 \(\pm\) 0.05** & **84.2 \(\pm\) 0.07** & **56.9 \(\pm\) 0.30** & **68.8 \(\pm\) 0.23** \\ Level & GAP & 1.0 & 69.4 \(\pm\) 0.39 & 97.5 \(\pm\) 0.06 & 78.8 \(\pm\) 0.26 & 46.5 \(\pm\) 0.58 & 62.4 \(\pm\) 0.28 \\ \hline Node & ProGAP & 8.0 & **69.3 \(\pm\) 0.33** & **94.0 \(\pm\) 0.04** & **79.1 \(\pm\) 0.10** & **48.5 \(\pm\) 0.36** & **61.0 \(\pm\) 0.34** \\ Level & GAP & 8.0 & 63.9 \(\pm\) 0.49 & 93.9 \(\pm\) 0.09 & 77.6 \(\pm\) 0.07 & 43.0 \(\pm\) 0.20 & 58.2 \(\pm\) 0.39 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Comparison of Experimental Results (Mean Accuracy \(\pm\) 95% CI)
ProGAP achieves significantly higher test accuracies on all datasets except Reddit, on which GAP performs only slightly better. Under both the edge-level and node-level privacy settings, however, ProGAP consistently outperforms GAP on all datasets, with the largest performance gap of 10.4% and 5.5% accuracy points, respectively, which are both observed on Facebook-100.

To examine the performance of the methods at different privacy budgets, we varied \(\epsilon\) between 0.25 to 4 for edge-level privacy and 2 to 32 for node-level private algorithms. We then recorded the accuracy of each method for each privacy budget. The outcome for both edge-level and node-level privacy settings is depicted in Figure 2.4 Notably, we observe that ProGAP achieves higher accuracies than GAP across all \(\epsilon\) values tested and approaches the non-private accuracy more quickly under both privacy settings. This is because in ProGAP each aggregation step is computed on the node embeddings learned in the previous stage, providing greater expressive power than GAP, which recursively computes the aggregations on the initial node representations.

Footnote 4: The results on the Facebook dataset are omitted due to space limitation.

### Convergence Analysis

We examine the convergence of ProGAP to further understand its behavior under the two privacy settings. We report the training and validation accuracy of ProGAP per training step under edge-level privacy with \(\epsilon=1\) and node-level privacy with \(\epsilon=8\). For all datasets, ProGAP is trained for 100 and 10 epochs per stage under edge and node-level privacy, respectively. We fix \(K=5\) in all settings. The results are shown in Figure 3. We observe that both training and validation accuracies increase as ProGAP moves from stage 0 to 5, with diminishing returns for more stages, which indicates the higher importance of the nearby neighbors to each node, since the receptive field of nodes grows with the number of stages. Moreover, we observe negligible discrepancies between training and validation accuracy when the model converges, which suggests higher

Figure 2: Accuracy-privacy trade-off of edge-level (top) and node-level (bottom) private methods. The dotted line represents the accuracy of the non-private ProGAP.
resilience to privacy attacks, such as membership inference, which typically rely on large generalization gaps. This result is in line with previous work showing the effectiveness of DP against privacy attacks [20, 21, 32, 39].

### Effect of the Model Depth

We explore how the performance of ProGAP is influenced by modifying the model depth \(K\), or equivalently, the number of stages \(K+1\). We experiment with different values of \(K\) ranging from \(1\) to \(5\) and evaluate ProGAP's accuracy under varying privacy budgets of \(\epsilon\in\{0.25,1,4\}\) for edge-level DP and \(\epsilon\in\{2,8,32\}\) for node-level privacy. The results are demonstrated in Figure 4. We observe that ProGAP can generally gain advantages from increasing the depth, but there is a compromise depending on the privacy budget: deeper models lead to better accuracy under higher privacy budgets, while lower privacy budgets require shallower models to achieve optimal performance. This is because ProGAP can leverage data from more remote nodes with a higher value of \(K\), which can boost the final accuracy, but it also increases the amount of noise in the aggregations, which has a detrimental effect on the model's accuracy. When the privacy budget is lower and the amount of noise is greater, ProGAP has the best performance at smaller values of \(K\). But as the privacy budget grows, the magnitude of the noise is lowered, enabling the models to take advantage of greater \(K\) values.

### Progressive vs. Layerwise Training

We compare the performance of ProGAP using two different training strategies: progressive training and layerwise training. Similar to Table 2, we report the test accuracy of both strategies at three different privacy levels: non-private with \(\epsilon=\infty\), edge-level privacy with \(\epsilon=1\), and node-level privacy with \(\epsilon=8\). The results are presented in Table 3. Overall, we observe that the progressive training yields higher accuracies than the layerwise strategy in most cases, which as mentioned in Section 4, is due to the higher capacity of the progressive approach.

Figure 3: Convergence of ProGAP with \(K=5\) under edge-level (top) and node-level (bottom) privacy, with \(\epsilon=1\) and \(\epsilon=8\), respectively.
## 7 Conclusion

In this paper, we introduced ProGAP, a novel differentially private GNN that improves the challenging accuracy-privacy trade-off in learning from graph data. Our approach uses a progressive training scheme that splits the GNN into a sequence of overlapping submodels, each of which is trained over privately aggregated node embeddings learned and cached by the previous submodels. By combining this technique with the aggregation perturbation method, we formally proved that ProGAP can ensure edge-level and node-level privacy guarantees for both training and inference stages. Empirical evaluations on benchmark graph datasets demonstrated that ProGAP can achieve state-of-the-art accuracy by outperforming existing methods. Future work could include exploring new architectures or training strategies to further improve the accuracy-privacy trade-off of differentially private GNNs, especially in the more challenging node-level privacy setting.

Figure 4: Effect of the model depth on ProGAP’s accuracy under edge-level (top) and node-level (bottom) privacy.

\begin{table}
\begin{tabular}{l c c c c c c c} \hline \hline Privacy & \(\epsilon\) & Training & \multirow{2}{*}{Facebook} & \multirow{2}{*}{Reddit} & \multirow{2}{*}{Amazon} & \multirow{2}{*}{Facebook-100} & \multirow{2}{*}{Wenet} \\ Level & & & Strategy & & & & \\ \hline Non- & \multirow{2}{*}{\(\infty\)} & PR & 84.5 \(\pm\) 0.24 & **99.3 \(\pm\) 0.03** & **93.3 \(\pm\) 0.04** & **74.4 \(\pm\) 0.14** & **73.9 \(\pm\) 0.25** \\ Private & \(\infty\) & LW & **85.6 \(\pm\) 0.29** & 99.3 \(\pm\) 0.03 & 92.9 \(\pm\) 0.04 & 74.0 \(\pm\) 0.16 & 71.9 \(\pm\) 0.19 \\ \hline Edge & \multirow{2}{*}{1.0} & PR & **77.2 \(\pm\) 0.33** & 97.8 \(\pm\) 0.05 & **84.2 \(\pm\) 0.07** & **56.9 \(\pm\) 0.30** & **68.8 \(\pm\) 0.23** \\ Level & & LW & 76.8 \(\pm\) 0.22 & **98.0 \(\pm\) 0.06** & 83.4 \(\pm\) 0.08 & 55.7 \(\pm\) 0.25 & 67.7 \(\pm\) 0.25 \\ \hline Node & \multirow{2}{*}{8.0} & PR & **69.3 \(\pm\) 0.33** & **94.0 \(\pm\) 0.04** & **79.1 \(\pm\) 0.10** & 48.5 \(\pm\) 0.36 & **61.0 \(\pm\) 0.34** \\ Level & & LW & 68.7 \(\pm\) 0.48 & 94.0 \(\pm\) 0.07 & 78.8 \(\pm\) 0.05 & **49.2 \(\pm\) 0.57** & 59.3 \(\pm\) 0.42 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Accuracy Comparison of Progressive (PR) and Layerwise (LW) Training
## Acknowledgments

This work was supported by the European Commission's H2020 Program ICT-48-2020, AI4Media Project, under grant number 951911. It was also supported by the European Commission's H2020 WeNet Project, under grant number 823783.
