Differentially Private Graph Neural Network with Importance-Grained
  Noise Adaption
Graph Neural Networks (GNNs) with differential privacy have been proposed to
preserve graph privacy when nodes represent personal and sensitive information.
However, the existing methods ignore that nodes with different importance may
yield diverse privacy demands, which may lead to over-protect some nodes and
decrease model utility. In this paper, we study the problem of
importance-grained privacy, where nodes contain personal data that need to be
kept private but are critical for training a GNN. We propose NAP-GNN, a
node-importance-grained privacy-preserving GNN algorithm with privacy
guarantees based on adaptive differential privacy to safeguard node
information. First, we propose a Topology-based Node Importance Estimation
(TNIE) method to infer unknown node importance with neighborhood and centrality
awareness. Second, an adaptive private aggregation method is proposed to
perturb neighborhood aggregation from node-importance-grain. Third, we propose
to privately train a graph learning algorithm on perturbed aggregations in
adaptive residual connection mode over multi-layers convolution for node-wise
tasks. Theoretically analysis shows that NAP-GNN satisfies privacy guarantees.
Empirical experiments over real-world graph datasets show that NAP-GNN achieves
a better trade-off between privacy and accuracy.
Yuxin Qi, Xi Lin, Jun Wu
# Differentially Private Graph Neural Network with

###### Abstract

Graph Neural Networks (GNNs) with differential privacy have been proposed to preserve graph privacy when nodes represent personal and sensitive information. However, the existing methods ignore that nodes with different importance may yield diverse privacy demands, which may lead to over-protect some nodes and decrease model utility. In this paper, we study the problem of importance-grained privacy, where nodes contain personal data that need to be kept private but are critical for training a GNN. We propose NAP-GNN, a node-importance-grained privacy-preserving GNN algorithm with privacy guarantees based on adaptive differential privacy to safeguard node information. First, we propose a Topology-based Node Importance Estimation (TNIE) method to infer unknown node importance with neighborhood and centrality awareness. Second, an adaptive private aggregation method is proposed to perturb neighborhood aggregation from node-importance-grain. Third, we propose to privately train a graph learning algorithm on perturbed aggregations in adaptive residual connection mode over multi-layers convolution for node-wise tasks. Theoretically analysis shows that NAP-GNN satisfies privacy guarantees. Empirical experiments over real-world graph datasets show that NAP-GNN achieves a better trade-off between privacy and accuracy.

## 1 Introduction

In recent years, graph neural networks have achieved outstanding performance in several domains, such as social analysis [14], financial anomaly detection [3], time series analysis [15], and molecule synthesis [1]. Through aggregating the feature information of neighboring nodes and fully mining and fusing the topological associations in graph data, graph neural networks yield state-of-art results in tasks such as link prediction [17], node classification [18], and sub-graph classification [14]. However, graph data in the real world usually contain private information. For example, in social network graphs, the edges between nodes indicate the existence of social attributes, such as being friends. Node features also carry sensitive information, such as the average online time of users per week and the average number of comments per week. To satisfy the privacy preservation demands of nodes, privacy-preserving GNN models have been proposed in [1]. The Locally Private Graph Neural Network (LPGNN) presented in [13] realizes the GNN model framework under local differential privacy guarantee. The features and labels of nodes can be protected. An edge-level differential privacy graph neural network (DP GNN) algorithm was proposed in [20] by perturbing the adjacency matrix of the graph. Some other researches attempt to address the privacy problem in GNN through federated [14] and split learning [16].

Although the existing DP GNN models enable privacy data protection, it does not consider the diverse privacy demand of nodes in the graph. Take node degree, for example. Nodes with different degree may yield different privacy protection needs. Most realistic graph data meet the power-law distribution [10]. The degree of most nodes is small, and few nodes have a relatively large degree. In the social media graph, suppose the nodes represent users, and the edges represent the following behaviors among users. The indegree of the nodes indicates how many followers they have, and the out-degree indicates how many other users they follow. Users with a larger number of followers have stronger social effects, and other users will notice their comments on social media and their friends list. Nodes with higher degrees require a more vital level of privacy protection.

However, existing works treat all nodes' privacy demands as the same and do not provide corresponding privacy guarantees for nodes with different privacy needs, which would lead to over-protecting some nodes, injecting over-needed noise, and decreasing model utility. Another drawback of existing methods protecting GNN through DP-SGD where noise is added on the parameter gradient is that the magnitude of injected noise and the privacy budget is accumulated during the training phase in proportion to epoch number.

To solve these problems, we propose a Node-Importance-Grained Adaptive Differential Private Graph Neural Network (NAP-GNN), which adds different extents of noise based on node importance and independent of the training epoch.
Our goal is to develop a fine-grained and adaptive differential privacy algorithm in GNN that flexibly distributes privacy budget according to known node importance and uses topology information in graphs. In this paper, we calculate the degree of a node as the sum of in-degree and out-degree. A supervised node importance estimation method, TNIE, is proposed to capture relations node neighbors and flexibly make centrality awareness adjustments. Then depending on the calculated node importance, we propose an importance-awareness fine-grained permutation method to realize node diverse privacy-preserving demand. An adaptive message passing method with residual connection is applied to improve model utility. We show theoretically that NAP-GNN satisfies the requirement of differential privacy. Experiments on real graph datasets show that the adaptive privacy budget allocation mechanism and adaptive residual aggregation of NAP-GNN can improve the utility of the model and outperforms existing approaches under a given privacy budget. The main contributions of this work are as follows.

* We study a novel problem of node-importance-related privacy concerns in GNNs. To the best of our knowledge, this is the first work to analyze this issue.
* We propose a new algorithm named Node-Importance-Grained Adaptive Differential Private Graph Neural Network (NAP-GNN), which tackles different privacy requirements among nodes by assigning global budget.
* We present Topology-based Node Importance Estimation (TNIE), a supervised estimation method, to address unknown nodes' importance estimation problem considering neighborhood and centrality awareness from the topology perspective.
* The experimental results on four benchmark graph datasets demonstrate the availability and effectiveness of our proposed NAP-GNN method.

## 2 Problem Formulation

In this section, we first revisit the definition of differential privacy proposed by [14] and graph neural work. Then we define the problem of learning a GNN with node data privacy concerns related to node importance.

### Graph Neural Network

Let \(\mathcal{G}=\{V,E,A,X,Y\}\) be an unweighted undirected graph, where \(V\) and \(E\) denote the nodes set and edges set. The adjacency matrix \(A\in\{0,1\}^{N\times N}\) represents the link among edges, \(|N|\) denotes the node number. For \(\forall v_{i},v_{j}\in V\), if there exists an edge between \(v_{i},v_{j}\), then \(A_{ij}=1\), for else \(A_{ij}=0\). Node feature of \(v\in V\) is a \(d\)-dimension vector, and the N \(\times\)\(d\) matrix \(X\) represents the stack of all nodes' feature, where \(X_{v}\in X\) denotes the feature of \(v\). \(Y\in\{0,1\}^{N\times M}\) represents the label of nodes, and M is the class number.

The typical message-passing-based GNN consists of two phases: message aggregation and updating. In the message aggregation phase of \(i\)-th layer, every node share and receive neighbors embedding of the former \(i\)-1-th layer and output a new embedding after applying a transformation, which can be defined as:

\[E_{v}^{i}=f_{agg}(\{h_{u}^{i-1},u\in\mathcal{N}(v)\}). \tag{1}\]

\(\mathcal{N}(v)\) denotes the adjacent node set of node \(v\), and \(h_{u}^{i-1}\) represents the embedding output of node \(u\) at \(i\)-1-th layer. \(f_{agg}\) is the aggregation linear function like SUM, MEAN, MAX etc. \(E_{v}^{i}\) is the aggregate output of \(i\)-th layer after the aggregation transformation of all adjacent nodes. Update transformation is employed on the \(E_{v}^{i}\), which is shown as:

\[h_{v}^{i}=f_{upd}(E_{v}^{i},h_{v}^{i-1};\theta_{i}). \tag{2}\]

\(f_{upd}\) denotes the learnable function that takes the aggregate vector as input and outputs the embedding of node \(v\) at \(i\)-th layer. \(f_{upd}\) is determined by parameter \(\theta_{i}\). The input \(h_{v}^{0}\) of GNN's first layer is \(X_{v}\), and the last layer generates embedding vectors \(h_{v}^{L}\) for \(\forall v\in V\), which can be used in downstream tasks, \(L\) represents the total layer. In this paper, we focus on the node classification task. A softmax layer is employed on the final embedding vectors \(h_{v}^{L}\) to get the class probability \(C_{v}\) of node \(v\).

### Problem Definition

The goal of this paper is to preserve the adaptive privacy of the graph nodes from importance-grain in the training step of GNN through differential privacy. Different from previous work in [1], we aim to propose an epoch-independent method considering node importance from topology without losing much utility of GNN. Refer to the definition in [11], we first define the notion of Node-level adjacent graph in this paper as follows:

**Definition 1** (Node-level adjacent graph).: _Graphs \(\mathcal{G}\) and \(\mathcal{G}^{\prime}\) are node-level adjacent if at most one node's feature vector is different. Without loss of generality, let \(\mathcal{G}\) can be obtained by altering a node in \(\mathcal{G}^{\prime}\)._

Then we define the \(\epsilon\)-Node-level differential privacy as:

**Definition 2** (\(\epsilon\)-Node-level differential privacy).: _Let \(\mathcal{G}\) and \(\mathcal{G}^{\prime}\) be two node-level adjacent graph datasets, given \(\epsilon>0\), the random algorithm \(\mathcal{A}\) is \(\epsilon\)-Node-level differential privacy if for any set of outputs \(S\in\text{Range}(\mathcal{A})\), satisfies:_

\[\text{Pr}[\mathcal{A}(\mathcal{G})\in S]\leq e^{\epsilon}\text{Pr}[\mathcal{A }(\mathcal{G}^{\prime})\in S]. \tag{3}\]

Based on Definition 2, the global graph sensitivity can be defined as:

**Definition 3** (Global graph sensitivity).: _The global graph sensitivity of function \(f\) on two node-level adjacent graphs \(\mathcal{G}\) and \(\mathcal{G}^{\prime}\) is:_

\[\Delta_{g\mathcal{G}}=\text{max}||f(\mathcal{G})-f(\mathcal{G}^{\prime})||_{1} \tag{4}\]

## 3 Proposed Method:NAP-GNN

In this section, we present our proposed **N**ode-Importance-Grained **A**daptive **I**pivate **G**raph **N**eural **N**etwork (NAP-GNN). First, the overall flow of NAP-GNN is provided. Then we show the algorithm design and key components of NAP-GNN in detail.
### Overall Flow of NAP-GNN

Figure 1 shows the overall flow of NAP-GNN, which consists of three components: _Topology-based Node Importance Estimation Module_, _Node-Importance-Grained Permutation Module_ and _Adaptive Residual Multi-Layer Aggregation Module_. The key mechanism of NAP-GNN is to preserve the graph data privacy considering node importance, which is achieved in a fine-grain permutation module. We use the Laplacian mechanism to add noise on the aggregation vector in a customized way, motivated by the fact that altering a feature vector can be viewed as adding or mincing extra noise.

The propagation layer is essential to graph neural network utility. Compared to fully propagating all neighbors embedding, we propose to use an adaptive conversion between noised aggregation embedding and residual connection, letting different nodes employ customized propagation layers.

### Topology-based Node Importance Estimation

To estimate topology-based node importance in a given graph, we propose a TNIE method considering the _Neighborhood Awareness_ and _Centrality Awareness_ motivated by [13]. Neighborhood Awareness refers to the idea that the importance of a node is influenced by its neighboring nodes, so the neighboring nodes' importance is a good representation of the current node's importance. Centrality Awareness means that nodes with higher centrality are more important than nodes with lower centrality.

The effect of neighboring nodes includes two aspects: node original feature and connectivity. To model this relationship, TNIE first uses a score computing network to map the original node features to a \(r\)-dimensional space:

\[f_{u}^{0}=ScoreComputing(\mathbf{x_{u}};u\in V), \tag{5}\]

where \(u\) is a node in \(\mathcal{G}\). Score computing network can be any neural network that takes node original feature as input and output encoded feature. In this paper, we use Multi-Layer Perception (MLP). Then through intermediate embedding propagation, TNIE realizes weighted aggregation from node \(u\) and its neighbors for the \(t\)-th layer (\(t=1,2,...T\)):

\[f_{u}^{t}=\sum_{v\in N(u)}\frac{1}{\sqrt{D_{u}}}\frac{1}{\sqrt{D_{v}}}f_{v}^{ t-1}, \tag{6}\]

where \(D_{u}\) denotes degree of \(u\). After \(T\) layers aggregation, \(\forall u\in V\) gets neighborhood awareness-based embedding \(f_{u}^{T}\).

The degree is a common proxy for node centrality. The degree of node has an impact on node importance estimation. Instead of initial degree \(log(D_{u}+\alpha)\) of node \(u\), where \(\alpha\) is a small parameter, TNIE adopts a shifting degree \(\lambda(log(D_{u}+\alpha))+\phi)\) to allow the possible discrepancy between degree and importance rank, where \(\lambda\) and \(\phi\) are learnable parameters. Then the shifting degree is used to adjust the neighborhood awareness-based embedding \(h_{u}^{T}\) of node \(u\) from centrality awareness consideration, which is as follows:

\[s(u)^{*}=\sigma((\lambda(log(D_{u}+\alpha))+\phi)\cdot f_{u}^{T}), \tag{7}\]

where \(\sigma\) is a non-linear activation function, \(s(u)^{*}\) denotes estimated importance score.

To estimate unknown nodes' importance score, TNIE uses mean squared error between the given importance score \(\mathcal{NI}(u)\) and estimated score \(s(u)^{*}\) for node \(u\in V_{t}\subset V\) to train the TNIE model. The loss function is:

\[\frac{1}{|V_{t}|}\sum_{u\in V_{t}}\left(s(u)^{*}-\mathcal{NI}(u)\right)^{2} \tag{8}\]

### Node-Importance-Grained Adaptive Laplace Mechanism

The goal of the Node-Importance-Grained Permutation Module is to privately release nodes' first aggregation embedding using adaptive noise proportion to sensitivity and node importance. Motivated by the fact that perturbing a node \(u\)'s edges in the graph can be seen as changing neighborhood aggregation of \(u\)'s adjacent nodes \(\forall v\in N(u)\), we realize Node-Importance-Grained Permutation Module by adding appropriate noise on the first layer's aggregation function. Specially, we use the sum aggregation function as the first layer, which is equivalent to the multiplication of the adjacent matrix and the input row-normalized feature. The permutation process can be presented as follows:

\[\overline{\mathcal{H}^{0}}(A,V,X)=\{\overline{H_{u}^{0}}\}_{u\in V}\ s.t.\ \overline{H_{u}^{0}}=\sum_{j=1}^{|N|}a_{uj}\mathbf{x_{j}}+Lap(\frac{\Delta \mathcal{H}^{0}}{\epsilon_{u}}), \tag{9}\]

where \(H_{u}^{0}=\sum_{j=1}^{|N|}a_{uj}\mathbf{x_{j}}\) denotes the sum aggregation process of node \(u\), \(a_{uj}\in A\), \(\mathbf{x_{j}}\) is the row-normalized feature of node \(j\), \(Lap(\frac{\Delta\mathcal{H}^{0}}{\epsilon_{u}})\) is the perturbed noise, \(\Delta\mathcal{H}^{0}\) denotes the sensitivity of aggregation function, \(\epsilon_{u}\) is the privacy budget.

Figure 1: Overview of NAP-GNN’s architecture
**Lemma 1**.: _Let \(\mathcal{G}=\{A,V,X\}\) and \(\mathcal{G}=^{\prime}=\{A^{\prime},V^{\prime},X^{\prime}\}\) be two adjacent graph dataset. Then the global graph sensitivity of first sum aggregation layer \(\Delta\mathcal{H}^{0}\leq 2D_{max}\), where \(D_{max}\) is maximum node degree._

Proof.: Assume adjacent graph dataset \(\mathcal{G}\) and \(\mathcal{G}^{\prime}\) differs in node \(k\). Then we have:

\[\Delta\mathcal{H}^{0} =\max_{u\in V}||\sum\mathcal{H}^{0}(A,V,X)-\sum\mathcal{H}^{0}(A ^{\prime},V^{\prime},X^{\prime})||_{1} \tag{10}\] \[=\max\sum_{u\in V}||\sum_{j=1}^{|N|}(a_{uj}\textbf{x}_{j}-a^{ \prime}_{uj}\textbf{x}^{\prime}_{j})||_{1}\]

\(A\) and \(A^{\prime}\) are two adjacent matrix. Without loss of generality, in \(\mathcal{G}^{\prime}\), we assume that node \(k\) is removed from \(\mathcal{G}\). Therefore, for nodes \(i\) and \(j\), we have \(a^{\prime}_{ij}=0,\ if\ i=k\ or\ j=k\), otherwise \(a^{\prime}_{ij}=a_{ij}\). Then we can get the following inequality:

\[\Delta\mathcal{H}^{0} =||\sum_{j=1}^{|N|}a_{kj}\textbf{x}_{j}+\sum_{i=1}^{|N|}a_{ik} \textbf{x}_{k}||_{1}\leq\sum_{j=1}^{|N|}a_{kj}+\sum_{i=1}^{|N|}a_{ik} \tag{11}\] \[\leq D_{out_{k}}+D_{in_{k}}\leq 2D_{max},\]

which concludes the proof. 

Denote the _Node Importance_ of node \(u\) as \(\mathcal{NI}(u)\), the rank of importance as \(\mathcal{R}\)-\(\mathcal{NI}(u)\). \(\mathcal{C}(u)\) represents the privacy protection level of node \(u\). For node \(m\) and \(n\), if \(\mathcal{NI}(m)>\mathcal{NI}(n)\), then \(\mathcal{C}(m)>\mathcal{C}(n)\). Let \(\epsilon_{\mathcal{A}}\) denotes the total privacy cost of first aggregation layer, then the assigned privacy budget \(\epsilon_{u}\) of node \(u\) is proportional to \(\mathcal{C}(u)\), which is \(\epsilon_{u}=\epsilon_{\mathcal{A}}\cdot\beta_{u}\), where \(\beta_{u}\) is a weight coefficient that quantifies the impact of node importance in the privacy protection level.

Many real-world graph datasets follow power-law distribution. When node degree distribution is extremely imbalance, the maximum node degree is obviously higher than most nodes, Laplace-based noise generation mechanism may yield high noise. To tackle this challenge, we propose to leverage the potential wasted privacy budget generated by node degree difference of adjacent graph nodes.

For arbitrary node \(u\in V\), it receives potential reusable privacy budget from neighboring node \(k\in N(u)\). Total reusable privacy ratio of \(k\) is \(D_{max}-D_{k}\), for each neighbor node of \(k\), the assigned ratio \(r(u,k)\) is

\[r(u,k)=\frac{\mathcal{R}\mathcal{NI}(u)}{\sum_{j\in N(k)}\mathcal{R}\mathcal{NI }(j)}, \tag{12}\]

which is proportion to node importance rank. Then the weight coefficient of \(u\) is the minimum of all reusable budget ratio:

\[\beta_{u}=\min_{k\in N(u)}\{\frac{\mathcal{R}\mathcal{NI}(u)}{ \sum_{j\in N(k)}\mathcal{R}\mathcal{NI}(j)}(D_{max}-D_{k})+1,\frac{D_{max}}{D_ {k}}\}. \tag{13}\]

### Adaptive Residual Multi-Layer Aggregation

The Adaptive Residual Multi-Layer Aggregation Module takes the node-importance-grained perturbed aggregation vectors as input and outputs the embedding vectors, which are generated through aggregating the multi-hops neighbors embedding with adaptive residual. Compared with equally receiving all neighbors embedding, the adaptive residual aggregation module allows each node to learn from different neighbors with different weights.

To keep edges and node labels private, we perturb them before the message passing and updating steps. Edge Randomization [20] is selected as the edge preprocessing method because it can preserve the adjacency matrix's sparse structure. To reduce the impact of adding or removing edges on the graph, we propose a degree-preserving Edge Randomization method, in which an unbiased sample method is used at the end with the sampling probability of:

\[p_{u}^{sample}=\frac{2D_{u}}{D_{u}+N-Ns+D_{u}s} \tag{14}\]

for node \(u\), where \(D_{u}\) is the degree of \(u\) before permutation, \(s\) is a parameter of Edge Randomization satisfying \(s\geq\frac{2}{e^{sB}+1}\), \(\epsilon_{B}\) is the privacy budget. The expectation of sampled node degree \(\mathbb{E}(\overline{D^{\prime}_{u}})\) equals \(\mathbb{E}(D_{u})\) for \(\forall u\in V\). We exploit Random Response [17] to encode node \(i\)'s labels for it outperforms other oracles in low dimensions. The transformation distribution is:

\[p(y^{\prime}_{i}|y_{i})=\begin{cases}\frac{e^{\epsilon_{C}}}{e^{ \epsilon_{C}}+M-1},if\ y^{\prime}_{i}=y_{i}\\ \frac{1}{e^{\epsilon_{C}}+M-1},\ otherwise,\end{cases} \tag{15}\]

where \(\epsilon_{C}\) is the privacy budget, \(M\) is class number.

For the aggregation process, motivated by [17], a node-wise adaptive embedding aggregation and the residual connection are applied to balance the smoothness of different perturbed vectors between neighbors and the node itself. The Adaptive Message Passing (AMP) process includes three steps: feature aggregation, residual weight computing, and linear combination, which can be presented as:

\[\textbf{AMP}(u,k,1):M_{u}^{k-1}=\tilde{A}H_{u}^{k-1}, \tag{16}\]

\[\textbf{AMP}(u,k,2):\gamma_{u}=\max(1-\tau.\frac{1}{||M_{u}^{k-1}-\overline{H_{ u}^{0}}||_{2}},0), \tag{17}\]

\[\textbf{AMP}(u,k,3):H_{u}^{k}=(1-\gamma_{u})\overline{H_{u}^{0}}+\gamma_{u}M_{u }^{k-1}. \tag{18}\]

Equation (16) shows the feature aggregation step for node \(u\) at layer \(k\in\{1,2,...K\}\), where \(\tilde{A}=\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{8}}\), \(\tilde{A}=\overline{A^{\prime}}+I\) is the sampled noise adjacent matrix with self loop, \(D\) is the degree matrix, \(H_{u}^{0}=\overline{H_{u}^{0}}\). Residual weight \(\beta_{u}\) of node \(u\) is computed through equation (17) depending on the deviation of adaptive perturbed embedding \(\overline{H_{u}^{0}}\) and feature aggregation of neighbors \(M_{u}^{k}\), \(\tau\) is a parameter that controls the smoothing. Finally, the aggregation embedding of \(u\) at layer \(k+1\) is the linear combination of \(\overline{H_{u}^{0}}\) and \(M_{u}^{k}\) weighted by \(\beta_{u}\) in (18).

## 4 Theoretical Analysis

In this section, we give the theoretical analysis of NAP-GNN. The complete process of NAP-GNN is shown in Algorithm 1.
**Theorem 1**.: _Algorithm 1 preserves \(\epsilon_{A}\)-DP in the computation of first differential private aggregation layer \(\mathcal{H}^{0}\)._

Proof.: All nodes' aggregation embedding in \(\mathcal{G}\) are perturbed, therefore we have:

\[Pr(\overline{\mathcal{H}^{0}}(A,V,X))=\prod_{i=1}^{N}exp(\frac{\epsilon_{i}}{ \Delta\mathcal{H}^{0}}||\sum_{j=1}^{N}a_{ij}\textbf{x}_{j}-\overline{H_{i}^{0} }||_{1}). \tag{19}\]

\(\Delta\mathcal{H}^{0}\) is set to \(2D_{max}\) in Algorithm 1. Assume adjacent graph dataset \(\mathcal{G}\) and \(\mathcal{G}^{\prime}\) differs in node \(k\). We have:

\[\begin{split}&\frac{Pr(\overline{\mathcal{H}^{0}}(A,V,X))}{Pr( \overline{\mathcal{H}^{0}}(A^{\prime},V^{\prime},X^{\prime}))}\\ &\leq\prod_{i=1}^{N}exp(\frac{\epsilon_{i}}{\Delta\mathcal{H}^{0 }}||\sum_{j=1}^{N}a_{ij}\textbf{x}_{j}-\sum_{j=1}^{N}a^{\prime}_{ij}\textbf{ x}^{\prime}_{j}||_{1})\\ &=exp(\sum_{i=1}^{N}\sum_{j=1}^{N}\frac{\epsilon_{i}}{\Delta \mathcal{H}^{0}}||a_{ij}\textbf{x}_{j}-a^{\prime}_{ij}\textbf{x}^{\prime}_{j }||_{1})\\ &=exp(\sum_{j\in N(k)}a_{kj}\frac{\epsilon_{k}}{\Delta\mathcal{H} ^{0}}+\sum_{i\in N(k)}a_{ik}\frac{\epsilon_{i}}{\Delta\mathcal{H}^{0}}). \end{split} \tag{20}\]

Let \(f(k)=\sum_{j\in N(k)}a_{kj}\epsilon_{k}+\sum_{i\in N(k)}a_{ik}\epsilon_{i}\). Then we have:

\[\begin{split}& f(k)=D_{k}\epsilon_{k}+\sum_{i\in N(k)}\epsilon _{i}=\epsilon_{A}(D_{k}\beta_{k}+\sum_{i\in N(k)}\beta_{i})\\ &\leq\epsilon_{A}(D_{k}\beta_{k}+\sum_{i\in N(k)}(\frac{\mathcal{ R\_NI}(u)}{\sum_{j\in N(k)}\mathcal{R\_NI}(j)}(D_{max}-D_{k}+1))\\ &\leq\epsilon_{A}(D_{k}\frac{D_{max}}{D_{k}}+D_{max}-D_{k}+D_{k} )\leq 2\epsilon_{A}D_{max}.\end{split} \tag{21}\]

Substitute equation (21) into (20), we can get:

\[\frac{Pr(\overline{\mathcal{H}^{0}}(A,V,X))}{Pr(\overline{\mathcal{H}^{0}}(A ^{\prime},V^{\prime},X^{\prime}))}\leq exp(\frac{2\epsilon_{A}D_{max}}{\Delta \mathcal{H}^{0}})=exp(\epsilon_{A}). \tag{22}\]

Theorem 1 is proved. 

Since the first aggregation function is linear, the generated embedding is unbiased, as follows:

**Proposition 1**.: _The sum aggregator function defined in (9) for the first layer is unbiased._

Now we analyze the unbiased property of degree-preserving edge sampling:

**Proposition 2**.: _Let \(\overline{A}\) denote the noised adjacent matrix obtained by Edge Randomization, \(D_{u}\) is the degree of node \(u\) in the original graph, \(\overline{D_{u}^{\prime}}\) denotes the degree after sampling. Then \(\mathbb{E}(\overline{D_{u}^{\prime}})=\mathbb{E}(D_{u})\)._

Proof.: In the original adjacent matrix \(A\), there are \(D_{u}\) 1s and \((N-D_{u})\) 0s for node \(u\). The expectation of \(u\)'s degree after Edge Randomization is:

\[\begin{split}\mathbb{E}(\overline{D_{u}})&=D_{u}s+D _{u}(1-s)+0.5(N-D_{u})(1-s)\\ &=0.5D_{u}+0.5N-0.5Ns+0.5D_{u}s,\end{split} \tag{23}\]

where \(s\) is the Bernoulli sample probability [20]. Then we can have \(\mathbb{E}(\overline{D_{u}^{\prime}})=\mathbb{E}(\overline{D_{u}})*p_{u}^{sample }=\mathbb{E}(D_{u})\). 

**Theorem 2**.: _Algorithm 1 preserves \((\epsilon_{A}+\epsilon_{B}+\epsilon_{C})\)-DP._

Proof.: From theorem 1, we know that the first aggregation layer satisfies \(\epsilon_{A}\)-DP. Adjacent matrix perturbation guarantees \(\epsilon_{B}\)-DP for \(\epsilon_{B}\geq(\ln\frac{2}{s}-1),s\in(0,1]\)[20]. Random response mechanism on node label guarantees \(\epsilon_{C}\)-DP under equation (15).

Node-level DP preserves all information of one node, including feature, edges and label. Differential aggregation layer \(\mathcal{H}^{0}\) process node feature and edge privately. The following Adaptive Residual Multi-Layer Aggregation Module do not expose node features and edges for it only post-processing the noised aggregation embedding and perturbed adjacent matrix without access private features and links. Training phase also guarantees DP because node label is perturbed former. The total privacy cost is \((\epsilon_{A}+\epsilon_{B}+\epsilon_{C})\)-DP.
## 5 Experimental Evaluation

In this section, we provide experiments on the proposed method and evaluate it under different parameter settings.

### Experiment Settings

#### 5.1.1 Datasets

Four publicly available datasets are used, Cora, Citeseer [11], Lastfm [12] and Facebook [13]. Cora and Citeseer are typical citation networks, representing two sparse graphs. Lastfm and Facebook are social networks, representing large scale and dense graphs compared with Cora and Citeseer. Detailed information of datasets is shown in Table 2.

#### 5.1.2 Compared Methods

We compare with the following methods: DP-GNN [12] that apply DP-Adam on 1-layer GNN. We also compare with MLP-DP, for MLP does not use graph topology. It is trained with DP-Adam to provide node-level protection. What's more, we compare two types of variants by privacy cost distribution methods: equal and adaptive. Two state-of-art GNN architectures, GCN and GraphSAGE, are used to substitute the proposed adaptive residual multi-layer aggregation module. We compare the performance of node importance estimation between node degree and TNIE through substitute \(\mathcal{NI}(i)\) with \(D_{i}\). Degree-preserving edge sample is removed from NAP-GNN as competitors.

#### 5.1.3 Training and Evaluation Settings

We randomly split the nodes in the dataset into training, test, and validation sets in the ratio of 50%, 25%, and 25%. Since the original Lastfm is highly imbalanced, we choose the top 10 classes that have most samples. The compared methods, GCN and GraphSAGE, are two convolutional layers with hidden dimension 128, RELU activation function, and a dropout layer with a probability of 0.2. We use the same noise scale on all noise-added perturbation modules. All models are trained based on Adam optimizer [13] with a maximum epoch of 1500. The initial value of the learning rate is 1e-3, and the decay mechanism is used with patience of 20 and a decay rate of 0.5. We measure the model performance by training 10 consecutive rounds on the test set and taking the average value with a 95% confidence interval under bootstrapping with 2000 samples. All experiments are implemented by using Pytorch and PyTorch-Geometric (PyG).

### Results and Analysis

#### 5.1.1 Evaluation on Adaptive Budget over Different \(\epsilon\)

We first compare the difference in accuracy between the proposed NAP-GNN and competitors under different privacy budgets. The results are shown in Table 1 and Figure 2. It can be observed that the adaptive DP mechanism achieves higher accuracy than equally distributing the total privacy budget under the same method in most cases. The performance gap between the two differential privacy

\begin{table}
\begin{tabular}{c|c c|c c|c c|c c} \hline \hline Dataset & \multicolumn{2}{c|}{Cora} & \multicolumn{2}{c|}{Citeseer} & \multicolumn{2}{c|}{Lastfm} & \multicolumn{2}{c}{Facebook} \\ \hline Privacy Level & Low & High & Low & High & Low & High & Low & High \\ \hline MLP-DP & 38.3\(\pm\)0.92 & 30.7\(\pm\)1.5 & 36.5\(\pm\)1.59 & 26.4\(\pm\)2.52 & 41.7\(\pm\)1.39 & 26.1\(\pm\)1.34 & 53.2\(\pm\)0.35 & 43.4\(\pm\)0.51 \\ DP-GNN & 64.2\(\pm\)1.17 & 55.7\(\pm\)2.80 & 54.5\(\pm\)0.85 & 42.1\(\pm\)4.25 & 72.1\(\pm\)0.43 & 63.3\(\pm\)1.73 & 73.4\(\pm\)0.69 & 59.8\(\pm\)0.93 \\ \hline GCN-DP\({}_{equa}\) & 75.4\(\pm\)0.45 & 62.6\(\pm\)0.65 & 63.1\(\pm\)0.21 & 42.1\(\pm\)0.62 & 77.2\(\pm\)0.49 & 57.7\(\pm\)0.47 & 82.5\(\pm\)0.31 & 61.1\(\pm\)0.17 \\ GCN-DP\({}_{adap}\) & 77.2\(\pm\)0.42 & 58.3\(\pm\)0.35 & 64.1\(\pm\)0.39 & 42.2\(\pm\)0.39 & 79.5\(\pm\)0.58 & 59.2\(\pm\)0.43 & 86.1\(\pm\)0.21 & 62.0\(\pm\)0.15 \\ SAGE-DP\({}_{equa}\) & 63.8\(\pm\)0.33 & 44.1\(\pm\)0.63 & 46.1\(\pm\)1.19 & 31.3\(\pm\)0.45 & 72.9\(\pm\)0.24 & 50.1\(\pm\)0.36 & 85.7\(\pm\)1.31 & 51.3\(\pm\)1.18 \\ SAGE-DP\({}_{adap}\) & 67.2\(\pm\)0.27 & 44.3\(\pm\)0.36 & 58.9\(\pm\)0.50 & 31.5\(\pm\)0.48 & 73.3\(\pm\)0.50 & 51.6\(\pm\)0.69 & 86.0\(\pm\)1.44 & 50.1\(\pm\)0.91 \\ \(\text{Ours}_{equa}\) & 83.1\(\pm\)0.11 & 63.4\(\pm\)0.26 & 64.5\(\pm\)0.21 & 42.4\(\pm\)0.17 & 84.5\(\pm\)0.10 & 65.3\(\pm\)0.15 & 89.8\(\pm\)0.07 & 65.5\(\pm\)1.10 \\
**Ours** & **33.5\(\pm\)1.84** & **64.9\(\pm\)1.75** & **65.0\(\pm\)0.16** & **44.6\(\pm\)0.26** & **86.3\(\pm\)0.84** & **65.9\(\pm\)0.15** & **91.3\(\pm\)0.64** & **67.8\(\pm\)0.17** \\ \hline Ours\({}_{deg}\) & 79.6\(\pm\)0.18 & 64.1\(\pm\)0.44 & 64.9\(\pm\)1.12 & 44.2\(\pm\)0.28 & 85.7\(\pm\)0.19 & 63.4\(\pm\)0.14 & 91.1\(\pm\)0.03 & 64.8\(\pm\)0.37 \\ Ours\({}_{-edgeSam}\) & 81.5\(\pm\)0.15 & 64.5\(\pm\)1.30 & 63.8\(\pm\)1.14 & 43.9\(\pm\)2.07 & 85.4\(\pm\)1.87 & 64.9\(\pm\)0.14 & 90.0\(\pm\)1.07 & 67.1\(\pm\)0.09 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Performance of Compared Methods on Cora, Citeseer, Lastfm and Facebook. Test accuracy(%) over two privacy level (for MLP-DP, set \(\epsilon=10\) for high privacy cost and \(\epsilon=20\) for low cost; for other models, set \(\epsilon=7\) for high cost and \(\epsilon=12\) for low cost, ) is reported. ‘equa’, ‘adap’, ‘deg’ and ‘-edgeSam’ is short for ‘equal’, ‘adaptive’, ‘degree’ and ‘without edge sample’, respectively.

\begin{table}
\begin{tabular}{c c c c c} \hline \hline Datasets & Nodes & Edges & Features & Avg\_Deg \\ \hline Cora & 2708 & 5278 & 1433 & 3.89 \\ Citeseer & 3327 & 4552 & 3703 & 3.73 \\ Lastfm & 7083 & 25814 & 7842 & 8.28 \\ Facebook & 22470 & 170912 & 4717 & 15.21 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Detailed Statistic of Used Datasets

Figure 2: Evaluation on Different Privacy Budget.
the average degree graph. Under the same global privacy budget, we also compare different noise scale ratios between differential private aggregation layer \(\mathcal{H}^{0}\), the degree-preserving adjacent matrix \(\overline{A}\) and noised label \(\overline{Y}\). With noise on \(\overline{A}\) be constant, we add more noise on \(\mathcal{H}^{0}\) (decline \(\epsilon_{A}\)), which is less \(\epsilon\) on \(\mathcal{H}^{0}\). Compared with the equal distribution method, the accuracy improvement of accuracy represents adaptive DP on \(\mathcal{H}^{0}\) can mitigate the noise waste problem caused by node over-protecting. The scheme that assigns less \(\epsilon\) on \(\mathcal{H}^{0}\) converges faster. As \(\epsilon\) increases (noise decreases), the model's utility tends to be the same for the two compared schemes.

#### 5.2.2 Evaluation on Node Importance Estimation

We investigate the effectiveness of the importance estimation module. We compare the case where TNIE is used as usual and the case where node degree is regarded as the importance score. The accuracy gap of method _Ours\({}_{deg}\)_ in line 10 and _Ours_ in line 9 of Table 1 demonstrates that the performance of the model with TNIE is better. This is because node degree only reflects the neighbor number and does not consider interactions between the adjacent nodes and the node feature.

#### 5.2.3 Evaluation on Degree-Preserving Edge Sampling

We compare the usual NAP-GNN with the case that edge sampling is removed and directly inputs noised adjacent matrix to the next module. The result is shown in line 11 in Table 1. We can see that in all cases, the accuracy of NAP-GNN is higher with edge sampling than without it.

#### 5.2.4 Evaluation on Maximum Degree \(D_{max}\) of Graph

We analyze the impact of the maximum node degree of the graph on model performance. The performance variation of the adaptive differential privacy mechanism is shown in Figure 3(a)-(d). The accuracy of the model increases to a peak and then decreases as \(D_{max}\) increases. The maximum degree of the sub-graphs taken at the peak differs on data with different degree average value. When \(D_{max}\) increases, the neighbor information that nodes can aggregate grows, but at the same time, more noise is received, thus affecting the accuracy of the model. Meanwhile, the Laplace mechanism is affected by data sensitivity. When \(D_{max}\) increases, the data sensitivity increases, and thus the noise added to each node on average increases, reducing the utility of the model.

#### 5.2.5 Evaluation on Multi-Adaptive-Layer \(K\)

We investigate the effect of different hops on the model performance. The results are shown in Figure 3(e)-(g). As can be seen, both NAP-GNN and its competitors can aggregate more information from neighbors when \(K\) increases. However, there is a trade-off between \(K\) and accuracy. When the value of \(K\) increases, the accuracy of both NAP-GNN and its competitors increases first, then reaches a peak and decreases. This is because when more layers of neighbor information are aggregated, the noise data collected from the neighbors also increase, affecting the behavior of the model. Besides, when \(\epsilon\) is small, the noise scale of the joined data is larger, and the model needs higher \(K\) to reach the peak.

## 6 Conclusion

In this paper, we propose a novel adaptive differential private graph neural network from node-importance-grain. We use adaptive aggregation perturbation, where the node-importance-grained Laplace mechanism is applied to the first aggregation function, and adaptive residual multi-layer aggregation, where embedding vectors are generated through multi-hops with the adaptive residual connection. Moreover, we present a new node importance estimation method named TNIE from graph topology considering neighborhood and centrality awareness. Experimental results over real-world graph datasets show that our NAP-GNN can achieve better privacy and accuracy trade-off and outperforms existing methods. In the future, we would like to investigate the rationale behind the trade-off between graph properties and noise scale from theoretical and algorithmic views, which would improve model utility and promote differentially private graph neural networks in practice.

Figure 3: Evaluation on Maximum Degree \(D_{max}\) of Graph (a-d) and Hop \(K\) of Multi-Adaptive-Layer (e-g).