Blink: Link Local Differential Privacy in Graph Neural Networks via
  Bayesian Estimation
Graph neural networks (GNNs) have gained an increasing amount of popularity
due to their superior capability in learning node embeddings for various graph
inference tasks, but training them can raise privacy concerns. To address this,
we propose using link local differential privacy over decentralized nodes,
enabling collaboration with an untrusted server to train GNNs without revealing
the existence of any link. Our approach spends the privacy budget separately on
links and degrees of the graph for the server to better denoise the graph
topology using Bayesian estimation, alleviating the negative impact of LDP on
the accuracy of the trained GNNs. We bound the mean absolute error of the
inferred link probabilities against the ground truth graph topology. We then
propose two variants of our LDP mechanism complementing each other in different
privacy settings, one of which estimates fewer links under lower privacy
budgets to avoid false positive link estimates when the uncertainty is high,
while the other utilizes more information and performs better given relatively
higher privacy budgets. Furthermore, we propose a hybrid variant that combines
both strategies and is able to perform better across different privacy budgets.
Extensive experiments show that our approach outperforms existing methods in
terms of accuracy under varying privacy budgets.
Xiaochen Zhu, Vincent Y. F. Tan, Xiaokui Xiao
# Blink: Link Local Differential Privacy in Graph Neural Networks via Bayesian Estimation+

###### Abstract.

Graph neural networks (GNNs) have gained an increasing amount of popularity due to their superior capability in learning node embeddings for various graph inference tasks, but training them can raise privacy concerns. To address this, we propose using link local differential privacy over decentralized nodes, enabling collaboration with an untrusted server to train GNNs without revealing the existence of any link. Our approach spends the privacy budget separately on links and degrees of the graph for the server to better denoise the graph topology using Bayesian estimation, alleviating the negative impact of LDP on the accuracy of the trained GNNs. We bound the mean absolute error of the inferred link probabilities against the ground truth graph topology. We then propose two variants of our LDP mechanism complementing each other in different privacy settings, one of which estimates fewer links under lower privacy budgets to avoid false positive link estimates when the uncertainty is high, while the other utilizes more information and performs better given relatively higher privacy budgets. Furthermore, we propose a hybrid variant that combines both strategies and is able to perform better across different privacy budgets. Extensive experiments show that our approach outperforms existing methods in terms of accuracy under varying privacy budgets.

local differential privacy, graph neural networks +
Footnote †: This work is licensed under a Creative Commons Attribution 4.0 International License.
nodes, which data owners are often unwilling to disclose. Moreover, the issue of link LDP in GNNs over decentralized nodes as clients has yet to be sufficiently addressed in the literature, and there is currently a lack of effective mechanisms to balance privacy and utility. (Srivastava et al., 2017) first propose locally differentially private GNNs, but only providing protection for node features and labels, while assuming the server has full access to the graph topology. Current differential privacy techniques for protecting graph topology while training GNNs, such as those described in (Zhou et al., 2018; Zhang et al., 2019; Zhang et al., 2019), are limited by poor performance and are often outperformed by MLPs that are trained without link information at all (which naturally provides full link privacy). This issue with (Zhou et al., 2019) has been investigated in (Zhou et al., 2019), and we also demonstrate similar behaviors of other baselines in this paper. On a separate line of research, there have been recent works on privacy-preserving graph synthesis and analysis with link local privacy guarantees (Zhou et al., 2019; Zhang et al., 2019; Zhang et al., 2019). However, although some of these works do provide valid mechanisms to train GNNs with link LDP protections, these mechanisms are usually designed to estimate aggregate statistics of the graph, such as subgraph counts (Zhou et al., 2019), graph modularities and clustering coefficients (Zhou et al., 2019; Zhang et al., 2019), which are not useful for training GNNs. Hence, these works are not directly applicable to our setting, and we will later show in this paper that they perform poorly in terms of GNN test accuracy. As such, there is a clear need for novel approaches to alleviate the performance loss of GNNs caused by enforcing privacy guarantees and to achieve link privacy with acceptable utility.

**Challenges.** First, local DP is a stronger notion than central DP (CDP) where the magnitude of noise increases with the number of nodes. This creates an issue in real-world graph datasets where the number of vertices is typically large. Moreover, as shown in Figure 2, removing links leads to a significant drop in GNN performance, indicating that graph topology is crucial in training effective graph neural networks. This is because GNN training is very sensitive to link alterations as every single wrong link will lead to the aggregation of information of neighboring nodes which should have been irrelevant. When the server adopts local differential privacy, it only has access to graph topology that is perturbed to be noisy for privacy protection, thus making it very challenging to train any effective GNNs on it. Additionally, conventional LDP mechanisms such as randomized response (Zhou et al., 2019) flip too many bits in the adjacency matrix and renders the noisy graph too dense, thus making it difficult to train any useful GNNs. To conclude, it is challenging to alleviate the negative effects of local differential privacy on GNN performance.

**Contribution.** In this paper, we propose Blink (Bayesian estimation for **link** local privacy), a principled mechanism for link local differential privacy in GNNs. Our approach involves separately and independently injecting noise into each node's adjacency list and degree, which guarantees LDP due to the basic composition theorem of differential privacy (Koren, 2017). On the server side, our proposed mechanism uses Bayesian estimation to denoise the received noisy information in order to alleviate the negative effects on GNN performance of local differential privacy.

Receiving the noisy adjacency lists and degrees, the server first uses maximum likelihood estimation (MLE) in the \(\beta\)-model (Chen et al., 2017) to estimate the existence probability of each link based solely on the collected noisy degree sequence. Then, the server uses the estimated link probability as a prior and the noisy adjacency lists as evidence to evaluate posterior link probabilities where both pieces of information are taken into consideration. We theoretically explain the rationale behind our mechanism and provide an upper bound of the expected absolute error of the estimated link probabilites against the ground truth adjacency matrix. Finally, the posterior link probabilities are used to construct the denoised graph, and we propose three variants of such a construction--hard thresholding, soft thresholding, and a hybrid approach. Hard thresholding ignores links with a small posterior probability; it performs better when privacy budget is low and uncertainty is high because the lost noisy information would not significantly help with GNN training. The soft variant keeps all the inferred information and uses the posterior link probabilities as edge weights in the GNN model, and performs better than the hard variant when privacy budget is relatively higher thanks to the extra information. The hybrid approach combines both hard and soft variants and performs well for a wide range of privacy budgets. Extensive experiments demonstrate that all three variants of Blink outperform existing baseline mechanisms in terms of the test accuracy of trained GNNs. The hard and soft variants complement each other at different privacy budgets and the hybrid variant is able to consistently perform well across varying privacy budgets.

**Paper organization.** The rest of this paper is organized as follows. Section 2 introduces preliminaries for GNNs and LDP and Section 3 formally formulates our problem statement. We describe our proposed solution, Blink, in Section 4 and explain its rationale and properties theoretically. We report and discuss extensive experimental results with all Blink variants and other existing methods in Section 5. In Section 6, we conduct a literature review on related topics and give brief introduction to relevant prior work. At last, Section 7 concludes our work and discusses possible future research directions. The appendix includes complete proofs and experimental details.

## 2. Preliminaries

### Graph neural networks

We consider the problem of semi-supervised node classification (Zhou et al., 2019; Zhang et al., 2019; Zhang et al., 2019) on a simple undirected graph \(G=(V,A,X,Y)\). Vertex

Figure 2. Test accuracy of GCN (Zhou et al., 2019) and MLP (GCN after removing links) on various graph datasets. Significant performance degeneration caused by removing links indicates the importance of graph topology in GNN training.
set \(V=\{v_{i}:i\in\{1,2,\ldots,n\}\}\) is the set of all \(n\) nodes, consisting of labelled and unlabeled nodes. Let \(V_{L},V_{U}\) be the sets of labelled and unlabeled nodes, respectively, then \(V_{L}\cap V_{U}=\emptyset\) and \(V_{L}\cup V_{U}=V\). The adjacency matrix \(A\in\{0,1\}^{n\times n}\) represents all the links in the graph, where \(A_{i,j}=1\) if and only if a link exists between \(v_{i}\) and \(v_{j}\). The feature matrix of the graph is \(X\in\mathbb{R}^{n\times d}\), where \(d\) is the number of features on each node and for each \(i\), row vector \(X_{i}\) is the feature of node \(v_{i}\). Finally, \(Y\in\{0,1\}^{n\times c}\) is the label matrix where \(c\) is the number of classes. In the semi-supervised setting, if vertex \(v_{i}\in V_{L}\), then its label vector \(Y_{i}\) is a one-hot vector, i.e. \(Y_{i}\cdot\vec{1}\), where \(\vec{1}\) is an all-ones vector of compatible dimension. Otherwise, when the vertex is unlabeled, i.e., \(v_{i}\in V_{U}\), its label vector \(Y_{i}\) is the zero vector \(\vec{0}\).

A GNN learns high-dimensional representations of all nodes in the graph by aggregating node embeddings of neighbor nodes and mapping the aggregated embedding through parameterized non-linear transformation. More formally, let \(x_{i}^{(k-1)}\) denote the node embedding of \(v_{i}\) in \((k-1)\)-th layer. The GNN learns the node embedding of \(v_{i}\) in the \(k\)-th layer by

\[x_{i}^{(k)}=\gamma^{(k)}(\text{Aggregate}(\{x_{j}^{(k-1)}:v_{j}\in\mathcal{N} (v_{i})\})) \tag{1}\]

where \(\mathcal{N}(v_{i})\) is the set of neighboring nodes of \(v_{i}\), Aggregate(\(\cdot\)) is a differentiable, permutation invariant aggregation function such as sum or mean, and \(\gamma(\cdot)\) is a differentiable transformation such as multi-layer perceptrons (MLPs). Note that the neighbor set \(\mathcal{N}(v_{i})\) may contain the node \(v_{i}\) itself, depending on the GNN architecture. When initialized, all node embeddings are the node feature, i.e., \(x_{i}^{(0)}=X_{i}\) for each \(v_{i}\in V\). At the last layer, the model outputs vectors of \(c\) dimension followed by a softmax layer to be compared against the ground truth so that the parameters in \(\gamma\) can be updated via back-propagation to minimize a pre-defined loss function such as cross-entropy loss.

### Local differential privacy

Differential privacy (DP) is the state-of-the-art mathematical framework to quantify and reduce information disclosure about individuals (K
exactly one edge in the graph. Therefore, if a mechanism satisfies \(\varepsilon\)-link LDP as defined in Definition 3.1, the influence of any single link on the released output is bounded and thus the link privacy is preserved.

After sending the privatized adjacency lists \(\mathcal{R}(A_{1}),\ldots,\mathcal{R}(A_{n})\) to the server, we also aim to design a server-side algorithm to denoise the received data which yields an estimated adjacency matrix \(\hat{A}\). Finally, the server uses \((V,X,Y,\hat{A})\) to train a GNN to perform node classification as described in Equation (1). Additionally, note that although we assume that the server has access to \(V,X,Y\), but it can be seen in Section 4 that our proposed method does not involve the server utilizing node features or labels to denoise the graph topology. Hence, our method is compatible with existing LDP mechanisms that provide protections for node features and labels, such as LPGNN (Zhu et al., 2017), and can serve as a convenient add-on to provide full local differential privacy on \(X,Y,A\).

## 4. Our Approach

To train GNNs with link local differential privacy over decentralized nodes, we propose Blink (**B**ayesian estimation for **link** local privacy), a new framework to inject noise to the graph topology on the client side to preserve privacy and to denoise the server side to train better GNN models. The key idea is to independently inject noise to the adjacency matrix and degree sequence such that the degree of each node can be utilized by the server to better denoise the graph structure. More specifically, as shown in Figure 3, the server uses the received noisy degree sequence as the prior and the noisy adjacency matrix as evidence to calculate posterior probabilities for each potential link. We now describe our method in more detail in the following subsections.

### Client-side noise injection

As suggested by previous studies (Zhu et al., 2017; Wang et al., 2018; Wang et al., 2018), simply randomly flipping the bits in adjacency lists will render the noisy graph too dense. Therefore, node degrees and graph density must be encoded in the private messages as well. Our main idea is to independently inject noise to the adjacency list and the degree of a node, and let the server estimate the ground truth adjacency matrix based on the gathered information. Based on this idea, we let the nodes send privatized adjacency lists and their degrees separately to the server, such that degree information can be preserved and utilized by the server to better denoise the graph topology. Specifically, for each node \(v_{i}\), we spend the total privacy budget \(\varepsilon\) separately on adjacency list \(A_{i}\) and its degree \(d_{i}\), controlled by degree privacy parameter \(\delta\in[0,1]\), such that we spend a privacy budget \(\varepsilon_{d}=\delta\varepsilon\) on degree and the remaining \(\varepsilon_{a}=(1-\delta)\varepsilon\) on adjacency list. This is possible because of the basic composition theorem of differential privacy (Koren et al., 2016). For real-valued degree \(d_{i}\), we use the widely-adopted Laplace mechanism (Koren et al., 2016) to inject unbiased noise drawn from Laplace(\(0,1/\varepsilon_{d}\)). And for bit sequence \(A_{i}\), we use randomized response (Zhu et al., 2017) to randomly flip each bit with probability \(1/(1+\exp(\varepsilon_{a}))\). This procedure is described in Algorithm 1. According to basic composition and the privacy guarantee of Laplace mechanism and randomized response, we have the following theorem, stating that Algorithm 1 achieves \(\varepsilon\)-link LDP. The detailed proof, together with the proofs of subsequent results, will be included in Appendix A.

```
0:\(A_{i}\in\{0,1\}^{n}\) - adjacency list of \(v_{i}\); \(\varepsilon\) - total privacy budget; \(\delta\) - degree privacy parameter
0:\(\left(\hat{A}_{i},\hat{d}_{i}\right)\) - the private adjacency list \(\hat{A}_{i}\in\{0,1\}^{n}\) and the private degree \(\tilde{d}_{i}\in\mathbb{R}\) of node \(v_{i}\).
1:functionLinkDP(\(A_{i},\varepsilon,\delta\)):\(\triangleright\) run by node \(v_{i}\)
2:\(\varepsilon_{d}\leftarrow\delta\varepsilon\)
3:\(\varepsilon_{a}\leftarrow(1-\delta)\varepsilon\)
4:for\(j\in\{1,2,\ldots,n\}\)do
5:\(\hat{A}_{ij}=\begin{cases}A_{ij},&\text{with probability }\exp(\varepsilon_{a})/(1+\exp( \varepsilon_{a}))\\ 1-A_{ij},&\text{with probability }1/(1+\exp(\varepsilon_{a}))\end{cases}\)
6:endfor
7:\(d_{i}\leftarrow\sum_{j=1}^{n}A_{ij}\)\(\triangleright\) degree of node \(v_{i}\)
8: sample \(l_{i}\sim\text{Laplace}(0,1/\varepsilon_{d})\)
9:\(\hat{d}_{i}\gets d_{i}+l_{i}\)\(\triangleright\) Laplace mechanism
10:return\(\left(\hat{A}_{i},\hat{d}_{i}\right)\)
11:endfunction
```

**Algorithm 1** Node-side \(\varepsilon\)-link LDP mechanism

### Server-side denoising

After receiving the noisy adjacency lists \(\tilde{A}_{1},\tilde{A}_{2},\ldots,\tilde{A}_{n}\) and degrees \(\tilde{d}_{1},\tilde{d}_{2},\ldots,\tilde{d}_{n}\) from the nodes, the server first assembles them into a noisy adjacency matrix \(\tilde{A}\in\{0,1\}^{n\times n}\) and noisy degree sequence \(\tilde{d}\in\mathbb{R}^{n}\). The server then uses \(\tilde{d}\) to estimate link probability to be used as prior, and uses \(\tilde{A}\) as the evidence to calculate the posterior probability for each potential link to exist in the ground truth graph. At last, the server constructs graph estimations based on the posterior link probabilities and use the estimated graph to train GNNs. These steps are described in greater details as follows.

#### 4.2.1. Estimation of link probability given degree sequence

Given noisy degree sequence \(\tilde{d}\), the server aims to estimate the probability of each link to exist, which is then used as prior probability in the next step. To estimate link probability, we adopt \(\beta\)-model, which is widely adopted in social network analysis (Bahdan et al., 2016; Wang et al., 2018; Wang et al., 2018) and closely related to the well-known Bradley-Terry-Luce (BTL) model for ranking (Bahdan et al., 2016; Wang et al., 2018; Wang et al., 2018; Wang et al., 2018). Given a vector \(\beta=(\beta_{1},\beta_{2},\ldots,\beta_{n})\in\mathbb{R}^{n}\), the model assumes that a random undirected simple graph of \(n\) vertices is drawn as follows: for each \(1\leq i<j\leq n\), an edge between node \(v_{i}\) and \(v_{j}\) exists with probability

\[p_{ij}=\frac{\exp(\beta_{i}+\beta_{j})}{1+\exp(\beta_{i}+\beta_{j})} \tag{4}\]

independently of all other edges. Hence, the probability of observing the (true) degree sequence \(d=(d_{1},\ldots,d_{n})\) from a random graph drawn according to the \(\beta\)-model is

\[L_{d}(\beta)=\frac{\exp(\sum_{i}\beta_{i}d_{i})}{\prod_{i<j}(1+\exp(\beta_{i}+ \beta_{j}))}. \tag{5}\]

As a result, one can estimate the value of \(\beta\) by maximizing the likelihood \(L_{d}(\beta)\) of observing \(d\). The maximum likelihood estimate (MLE) \(\hat{\beta}\) of \(\beta\) must satisfy the system of equations

\[d_{i}=\sum_{j\neq i}\frac{\exp(\hat{\beta}_{i}+\hat{\beta}_{j})}{1+\exp(\hat{ \beta}_{i}+\hat{\beta}_{j})},\qquad i=1,2,\ldots,n. \tag{6}\]

Chatterjee et al. (2016) show that with high probability, there exists a unique MLE solution \(\hat{\beta}\) as long as the ground truth sequence \((\beta_{i})\)
is bounded from above and below, and the authors also provide an efficient algorithm for computing the MLE when it exists. Consider the following function \(\phi_{d}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}\) where

\[\phi_{d}(x)_{t}=\log(d_{t})\,-\log\left(\sum_{j\neq t}\frac{1}{\exp(-x_{j})+ \exp(x_{t})}\right). \tag{7}\]

Chatterjee et al. (2017) prove that the MLE solution is a fixed point of the function \(\phi\) and hence can be found iteratively using Algorithm 2.

Therefore, if the degree sequence \(d\) were to be released to and observed by the server, the server could then model the graph using the \(\beta\)-model and estimate link probabilities via MLE. However, actual degree sequence \(d\) must be kept private to the server for the privacy guarantee. As per Algorithm 1, \(d\) is privatized through Laplace mechanism and only the noisy \(\tilde{d}\) can be observed by the server. Although the server cannot directly maximize the likelihood \(L_{d}(\beta)\) of observing \(d\), the following theorem shows that the observable log-likelihood \(\ell_{\tilde{d}}(\beta)=\log(L_{\tilde{d}}(\tilde{\beta}))\) is a lower bound of the unobservable \(\ell_{d}(\beta)=\log(L_{d}(\tilde{\beta}))\) (up to a gap).

**Theorem 4.2**.: _For any \(\beta\in\mathbb{R}^{n}\) that is bounded from above and below, let \(M=\max_{1\leq i\leq n}\|\tilde{\rho}_{i}\|\). For any given constant \(a\), with probability at least \(1-1/a^{2}\), we have \(\ell_{\tilde{d}}(\beta)\geq\ell_{\tilde{d}}(\beta)-a\sqrt{n}M/\ell_{d}^{2}\), where the probability is measured over the randomness of Laplace mechanism of \(\tilde{d}\)._

_Remark 4.3_.: Maximizing the observable but noisy log-likelihood \(\ell_{\tilde{d}}(\beta)\) can maximize the unobservable target log-likelihood \(\ell_{\tilde{d}}(\beta)\) to a certain extent (a gap of \(\Theta(\sqrt{n}M/\ell_{d}^{2})\)). Similar to (6), the solution \(\hat{\beta}\) that maximizes log-likelihood \(\ell_{\tilde{d}}(\beta)\) satisfies the following system of equations

\[\tilde{d}_{t}=\sum_{j\neq t}\frac{\exp(\hat{\rho}_{t}+\hat{\beta}_{j})}{1+ \exp(\hat{\rho}_{t}+\hat{\beta}_{j})},\qquad i=1,2,\ldots,n, \tag{8}\]

and it will be a fixed point of function \(\phi_{\tilde{d}}\). However, Eq. (8) has a solution only if \(\tilde{d}_{t}\in(0,n-1)\) for all \(i=1,2,\ldots,n\). Therefore, the server first clips the values of \(\tilde{d}\) to \(\tilde{d}^{+}\in[1,n-2]^{n}\) and then calls the function \(\textsc{MELinkProbability}(\tilde{d}^{+})\) from Algorithm 2 to find the link probabilities that maximize \(\ell_{\tilde{d}^{+}}(\beta)\). This step is described in Lines 2 and 3 of Algorithm 3.

```
0:\(\tilde{A}\in\{0,1\}^{n\times n}\) - privileged adjacency matrix and degree sequence, where for \(1\leq i\leq n\), \((\tilde{A}_{i},\tilde{d}_{t})=\textsc{LmxLDP}(A_{t},\varepsilon,\delta)\) executed by node \(q_{ij}\); \(\varepsilon\) - total privacy budget; \(\delta\) - degree privacy parameter
0:\(P\in[0,1]^{n\times n}\) - the posterior probabilities for each link to exist
1:functionDenskip(\(\tilde{A},\tilde{d},\varepsilon,\delta\)):
2:\(\tilde{d}^{*}\gets\tilde{A}_{\textsc{clip}}(\textsc{min}=1,\textsc{max}= n-2)\)
3:\(p\leftarrow\textsc{MELinkProbability}(\tilde{d}^{+})\)\(\triangleright\) prior
4:for\((i,j)\in\{1,2,\ldots,n\}^{2}\)do
5:\(q_{ij}\leftarrow\Pr\{(\tilde{A}_{ij},\tilde{A}_{ji})|(A_{ij},A_{ji})=(1,1)\}\) \(\triangleright\) evidence likelihood
6:\(q^{*}_{ij}\leftarrow\Pr\{(\tilde{A}_{ij},\tilde{A}_{ji})|(A_{ij},A_{ji})=(0,0 )\}\) \(\triangleright\) evidence likelihood
7:\(P_{ij}\leftarrow\frac{q_{ij}P_{ij}}{q_{ij}p_{ij}+q^{*}_{ij}(1-p_{ij})}\)\(\triangleright\) Bayesian posterior probability
8:endfor
9:return\(P\)
10:endfunction
```

**Algorithm 3** Server-side estimation of posterior link probabilities

#### 4.2.2. Estimation of posterior link probabilities

The noisy degree sequence \(\tilde{d}\) enables the server to estimate the link probabilities to be used as a prior, such that the server can use the received noisy adjacency matrix as evidence to evaluate posterior probability. For each potential link between \(q_{i},q_{j}\in V\), the server receives two bits \(\tilde{A}_{ij}\) and \(\tilde{A}_{ji}\) related to its existence. Because the privacy budget \(\varepsilon_{a}\) in RR (Algorithm 1) is known to the server, the server can use the flip probability \(p_{\textsc{flip}}=1/(1+\exp(\varepsilon_{a}))\) to calculate the likelihood of observing the received bits \((\tilde{A}_{ij},\tilde{A}_{ji})\) conditioned on whether a link exists between \(q_{i}\) and \(q_{j}\) in the actual graph. More specifically, we have

\[q_{ij} =\begin{cases}p_{\textsc{flip}}^{2},&(\tilde{A}_{ij},\tilde{A}_{ji })=(0,0)\\ p_{\textsc{flip}}(1-p_{\textsc{flip}}),&(\tilde{A}_{ij},\tilde{A}_{ji})=(0,1) \vee(\tilde{A}_{ij},\tilde{A}_{ji})=(1,0)\ ;\\ (1-p_{\textsc{flip}})^{2},&(\tilde{A}_{ij},\tilde{A}_{ji})=(1,1)\end{cases}\] \[q^{*}_{ij} =\begin{cases}(1-p_{\textsc{flip}})^{2},&(\tilde{A}_{ij},\tilde{A}_{ ji})=(0,0)\\ p_{\textsc{flip}}(1-p_{\textsc{flip}}),&(\tilde{A}_{ij},\tilde{A}_{ji})=(0,1)\vee( \tilde{A}_{ij},\tilde{A}_{ji})=(1,0)\.\\ p_{\textsc{flip}}^{2},&(\tilde{A}_{ij},\tilde{A}_{ji})=(1,1)\end{cases}\]

Here, \(q_{ij}\) is the likelihood of observing \((\tilde{A}_{ij},\tilde{A}_{ji})\) given the existence of the link \((v_{i},v_{j})\), and \(q^{*}_{ij}\) is the likelihood of observing \((\tilde{A}_{ij},\tilde{A}_{ji})\) given the non-existence of the link \((v_{i},v_{j})\). Hence, together with the link probability (without taking evidence into consideration) \(p_{ij}\) estimated solely from noisy degree sequence, one can apply Bayes rule to evaluate the posterior probability, i.e. for each \(1\leq i\neq j\leq n\),

\[P_{ij}=\Pr\{(A_{ij},A_{ji})=(1,1)|(\tilde{A}_{ij},\tilde{A}_{ji})|\}=\frac{q_{ij}P _{ij}}{q_{ij}p_{ij}+q^{*}_{ij}(1-p_{ij})}.\]

For each \(1\leq i\neq j\leq n\), \(P_{ij}\) is the posterior probability that a link exists between \(v_{i}\) and \(v_{j}\) conditioned on the evidence \((\tilde{A}_{ij},\tilde{A}_{ji})\). We will show the accuracy of this estimation of graph topology in Section 4.3 by bounding the mean absolute error between \(P\) and ground truth \(A\).

#### 4.2.3. Graph estimation given posterior link probabilities

After obtaining \(P\), we propose three different variants of Blink for the server to construct graph estimations used for GNN training.

Blink-Hard.The simplest and most straightforward approach is to only keep links whose posterior probability of its existence triumphs that of its absence, i.e. keep a link between \(v_{i}\) and \(v_{j}\) in the estimated graph \(\tilde{A}\) if and only if \(P_{ij}>0.5\).
It is clear that hard-thresholding loses a lot of information contained in \(P\) by simply rounding all entries to \(0\) or \(1\). However, when privacy budget is low and uncertainty is high, the information provided by the nodes are usually too noisy to be useful for GNN training, and may even corrupt the GNN model (Zhu et al., 2017). Therefore, Blink-Hard is expected to perform better when privacy budget is low, while when privacy budget grows, it is likely to be outperformed by other variants of Blink.

Blink-Soft.Instead of hard-thresholding, the server can keep all the information in \(P\) instead by using them as edge weights. In this way, the GNN formulation in (1) is modified as follows to adopt weighted aggregation:

\[x_{i}^{(k)}=\gamma^{(k)}\left(\text{Aggregate}(\{P_{ij}\cdot x_{j}^{(k-1)}:y_{ j}\in V\})\right), \tag{9}\]

where \(\text{Aggregate}(\cdot)\) is a permutation invariant aggregation function such as sum or mean. Detailed modifications of specific GNN architectures will be included in Appendix B.

The soft variant utilizes extra information of \(P\) compared to Blink-Hard, and hence, is expected to achieve better performance as long as the information is not too noisy to be useful. Therefore, we form a hypothesis that Blink-Soft and Blink-Hard complement each other and the former is preferred when privacy budget is relatively higher while the latter is preferred at lower privacy budgets.

Blink-Hybrid.At last, we combine both the hard and soft variants such that the server can eliminate unhelpful noisy information while utilizing more confident information in \(\|P\|_{1,1}\) via weighted aggregation. The server first takes the highest \(\|P\|_{1,1}\) entries of \(P\) and filters out the remaining by setting them as zeros. This is to only keep the top \(\|P\|_{1,1}\) possible links in the graph as \(\|P\|_{1,1}\) is an estimation of the graph density \(\|A\|_{1,1}\) (suggested by Theorem 4.4 and Corollary 4.6). This step is inspired by the idea of only keeping the top \(|E|\) links from DpGCN (Zhu et al., 2017). Then, the server utilizes the remaining entries in \(P\) by using them as edge weights and trains the GNN as in Equation (9). Blink-Hybrid is expected to incorporate the advantages of both Blink-Hard and Blink-Soft and perform well for all privacy levels.

### Theoretical analysis for utility

We have described our proposed approach, namely, Blink, in detail in previous sections. While its privacy guarantee has been shown in Theorem 4.1, we now theoretically demonstrate its utility guarantees.

Choice of utility metric.To quantify the utility of Blink, we first need to identify a metric to be bounded that is able to reflect the quality of the estimated graph, \(P\). In the related literature, many metrics have been used to demonstrate the utility of differentially private mechanisms for graph analysis. For example, Hidano and Murakami (2017) show that their estimated graph topology preserves the graph density; Imola et al. (2018) bound the error in triangle count and \(k\)-star count; Ye et al. (2019) evaluate the error in any arbitrary aggregate graph statistic, as long as the aggregate statistic can be estimated without bias from both degree and neighbor lists, such as clustering coefficient and modularity. However, none of these metrics can reflect the quality of the estimated graph topology directly and represent the performance of the GNN trained on the estimated graph because they only involve aggregate and high-level graph statistics. In contrast, the performance of GNNs for node classification is very sensitive to link information from a microscopic or local perspective, as node information propagates along links and any perturbation of links will lead to aggregation of other nodes' information that should have been irrelevant, or missing the information of neighboring nodes. This is one of the reasons that many prior works involving privacy-preserving GNNs for node classification (Zhu et al., 2017; Wang et al., 2017; Zhu et al., 2017) only provide empirical evidence of the utility of their approaches. Although there is no metric that can directly reflect the performance of the trained GNNs, the closer the estimated adjacency matrix \(P\) is to the ground truth \(A\), the better the GNNs trained on \(P\) are expected to perform, and the closer the trained GNNs would perform compared to those trained with accurate graph topology. Therefore, we evaluate the utility of Blink as a statistical estimator of the ground truth adjacency matrix \(A\) by bounding the expectation of the \(\ell_{1}\)-distance between \(P\) and \(A\), i.e. \(\text{E}[\|P-A\|_{1,1}]\). If \(P\) is a binary matrix similar to \(A\), this metric measures the number of edges in the ground truth graph that are missing or falsely added in the estimated graph; if \(P\) is a matrix of link probabilities, this metric measures to what extent the links in \(A\) are perturbed. It can be seen that this metric, just like GNN performance, is sensitive to link perturbations from a local perspective, and it is able to reflect the overall quality of the estimated graph topology. This metric is also closely related to the mean absolute error (MAE) between \(P\) and \(A\), defined as \(\frac{1}{n^{2}}\sum_{i,j}|P_{ij}-A_{ij}|\), which is a commonly used metric in empirical evaluation. Therefore, we use the expectation of \(\ell_{1}\)-distance between \(P\) and \(A\) as the utility metric to quantify the utility of Blink, and we present an upper bound of it in the following Theorem 4.4.

Theorem 4.4 ().: _Assume that \(\beta\) found by MLE in Algorithm 3 is the optimal solution that maximizes \(\ell_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*} _{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{ \tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}}^{*}_{ \tilde{d}^{*}_{\tilde{d}}^{*}_{\tilde{d}^{*}_{\tilde{d}}^{*}_{\tilde{d}}^{*}_{ \tilde{d}^{*}_{\tilde{d}}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}}^{*}_{ \tilde{d}}^{*}_{\tilde{d}^{*}_{\tilde{d}}^{*}_{\tilde{d}^{*}_{\tilde{d}}^{*}_{ \tilde{d}^{*}_{\tilde{d}}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}}^{*}_{ \tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}}^{*}_{\tilde{d}^{*}_{\tilde{d}}^{*}_{ \tilde{d}^{*}_{\tilde{d}}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{ \tilde{d}}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}}^{*}_{\tilde{d}^{*}_{ \tilde{d}}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{ \tilde{d}}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{ \tilde{d}}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{ \tilde{d}}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{ \tilde{d}}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{ \tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{ \tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{ \tilde{d}^{*}_{\tilde{d}}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{ \tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{ \tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}}^{*}_{\tilde{d}^{*}_{ \tilde{d}^{*}_{\tilde{d}}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{ \tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{ \tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}}^{*}_{ \tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{ \tilde{d}}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{ \tilde{d}^{*}_{\tilde{d}^{d}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{ \tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}}_{\tilde{d}^{*}_{\tilde{d}}^{*}_{ \tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}}^{*}_{ \tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d} }^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}}^{*}_{\tilde{d} ^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{ \tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d}^{*}_{\tilde{d} ^{*}_{\tilde{d}^{*}_{\tilde{d}}^{*}_{\tilde{d}^{*}_{\tilde
**Corollary 4.6**.: _For a sparse graph where \(\|A\|_{1,1}=O(n)\), the expected mean absolute error (MAE) of \(P\) against \(A\) is bounded by \(O(1/n+1/(n\varepsilon))\)._

Empirical bound tightness.To empirically evaluate the estimation accuracy of the posterior link probabilities \(P\) against the ground truth graph topology \(A\), and to inspect the tightness of our upper bound on the estimation error given in Theorem 4.4, we report the average mean absolute error (MAE) and its theoretical upper bound (as given in Theorem 4.4) between \(P\) and \(A\) on four well-known graph datasets in Figure 4. Figure 4 shows that in all datasets, the MAE between \(P\) and the ground truth \(A\) is very small, and decrease to almost zero (on the order of \(10^{-6}\) when \(\varepsilon=8\)) as the privacy budget \(\varepsilon\) increases. This demonstrates that the inferred link probability matrix \(P\) is a close estimation of the unseen private adjacency matrix \(A\), and thus can be used for GNN training. Furthermore, Figure 4 reports that the upper bound of the expected MAE given by Theorem 4.4 is very close to the empirical average MAE when the total privacy budget \(\varepsilon\) is small. However, empirical results also suggest that the bound given in Theorem 4.4 is not tight when \(\varepsilon\) is large, as our upper bound converges to \(2\|A\|_{1,1}\) instead of \(0\) when \(\varepsilon\to\infty\), while the empirical estimation error converges to zero when \(\varepsilon\) grows larger. This has inspired us to prove Theorem 4.7 below, which states that the estimated graph from noisy messages will be identical to the actual one when \(\varepsilon\to\infty\).

**Theorem 4.7**.: _As \(P\) is a random function of the total link privacy parameter \(\varepsilon\), we write \(P=P_{\varepsilon}\). Then, we have \(\lim_{\varepsilon\to\infty}P_{\varepsilon}=A\), i.e., when \(\varepsilon\to\infty\), the estimated graph from noisy messages converges to the ground truth._

_Remark 4.8_ (Implications of Theorem 4.7).: Theorem 4.7 demonstrates that when \(\varepsilon\) goes to infinity, the estimated graph from noisy messages will converge to the ground truth graph and hence the trained GNN will also have the same performance as its theoretical upper bound - the performance of a GNN trained with the accurate graph topology. This is a desirable property of any differentially private mechanisms, yet not enjoyed by all existing ones. For example, LDPGen (Zhu et al., 2017) clusters structurally similar nodes together and generates a synthetic graph based on noisy degree vectors via the Chung-Lu model (Chung et al., 2018). Even when no noise is injected, the generated graph is not guaranteed to be identical to the ground truth graph since only accurate degree vectors are used to construct the graph. Theorem 4.7 shows that Blink is able to achieve this desirable property, and together with Theorem 4.4, which has been shown to be quite tight when \(\varepsilon\) is small, we show that the estimation error of Blink is well controlled for all \(\varepsilon\), as demonstrated empirically in Figure 4.

_Remark 4.9_.: Note that Theorem 4.4, Corollary 4.6 and Theorem 4.7 are not violations to privacy. They indicate how good the server can estimate the ground truth, conditioned on the fact that the input information is theoretically guaranteed to satisfy \(\varepsilon\)-link LDP (as shown in Theorem 4.1). These are known as privacy-utility bounds, and it is standard practice in local differential privacy literature for the server to denoise the received noisy information to aggregate useful information.

_Remark 4.10_ (Limitations).: Note that Theorems 4.4 and 4.7 only capture the estimation errors of \(P\), and are not direct indicators of the performance of the GNNs trained on \(P\). As discussed in the beginning of this section, there is no metric that can directly reflect the performance of the trained GNNs. However, in general, the closer the estimated adjacency matrix \(P\) is to the ground truth \(A\), the better the GNNs trained on \(P\) are expected to perform. Still, Theorem 4.4 and 4.7 alone are not sufficient to demonstrate the superior performance of the proposed approach, Blink, over existing approaches. For example, for L-DrGCN (to be introduced in Section 5.1), the mechanism only retains around the same number of links in the estimated graph as the ground truth graph, and hence the estimation error is approximately bounded by \(2\|A\|_{1,1}\), similar to what we have proved in Theorem 4.4. This is also the case for degree-preserving randomized response proposed in (Kolmogorov et al., 2017). Therefore, we provide extensive empirical evaluations of the performance of Blink in Section 5 and show that Blink outperforms existing approaches in terms of utility at the same level of privacy.

### Technical novelty

The split of privacy budget to be separately used for degree information and adjacency lists has appeared in the literature (Kolmogorov et al., 2017; Kolmogorov et al., 2017). However, in both works, the noisy degrees and adjacency lists are denoised or calibrated such that a target aggregate statistic can be estimated more accurately. Hidano and Murakami (2017) uses the noisy degree to sample from the noisy adjacency lists such that the overall graph density can be preserved. (Kolmogorov et al., 2017) combines two estimators of the target aggregate statistic, one from noisy degrees and the other from noisy adjacency lists, and calibrates for a better estimation for the target aggregate statistic, such as clustering coefficient and modularity. As discussed previously, guarantees on

Figure 4. Average mean absolute error (MAE) of the inferred link probabilities \(P\) against ground truth \(A\) (\(\delta\) set to \(0.1\)).
the estimation error of these aggregate statistics are not sufficient to train useful GNNs due to their sensitivity to link perturbations. In contrast, our approach, Biink, utilizes the noisy degree information to estimate the posterior link probabilities conditioned on the evidence of noisy RR outputs _for all possible links_, via Bayesian estimation. To the best of our knowledge, this is a novel approach that has not been explored in the literature.

## 5. Experiments

### Experimental settings

EnvironmentTo demonstrate the privacy-utility trade-off of our proposed mechanism, we ran extensive experiments on real-world graph datasets with state-of-the-art GNN models.2 The experiments are conducted on a machine running Ubuntu 20.04 LTS, equipped with two Intel(r) Xeon(r) Gold 6326 CPUs, 256GB of RAM and an NVIDIA(r) A100 80GB GPU. We implement our mechanism and other baseline mechanisms using the PyTorch3 and PyTorch Geometric4 frameworks. To speed up execution, we use NVIDIA's TF32 tensor cores (Fan et al., 2017) in hyperparameter search at the slight cost of precision. All experiments other than hyperparameter grid search are done using the more precise FP32 format to maintain precision.

Footnote 2: Our code can be found at [https://github.com/ahcchdt/blink_gmn](https://github.com/ahcchdt/blink_gmn).

Footnote 3: Available at [https://pytorch.org](https://pytorch.org)

**Datasets.** We evaluate Blink and other mechanisms on real-world graph datasets. The description of the datasets is as followed:

* _Cora_ and _CiteSeer_(Xeon et al., 2017) are two well-known citation networks commonly used for benchmarking, where each node represents a document and links represent citation relationships. Each node has a feature vector of bag-of-words and a label for category.
* _LastFM_(Nishu et al., 2018) is a social network collected from music streaming service LastFM, where each node represents a user and links between them represent friendships. Each node also has a feature vector indicating the artists liked by the corresponding user and a label indicating the home country of the user.
* _Facebook_(Nishu et al., 2018) is a social network collected from Facebook, where each node represents a verified Facebook page and links indicate mutual likes. Each node is associated with a feature vector extracted from site description and a label indicating the cite category. This graph is significantly larger and more dense than the previous datasets, and hence represents the scalability and performance on larger graphs of our proposed method.

Table 1 summarizes the statistics of datasets used in experiments.

**Baselines.** To better present the performance of Blink, we implement the following baseline mechanisms for comparison.

1. Randomized response (RR) (Nishu et al., 2018) is included to demonstrate the effectiveness of our server-side denoising algorithm, where the server directly uses the RR result of adjacency matrix as the estimated graph without calibration.
2. Wu et al. (Wu et al., 2018) propose DrGCN as a mechanism to achieve \(\varepsilon\)-central DP to protect graph links. It adds Laplacian noise to all entries of \(A\) and keeps the top \(\|A\|_{1,1}\) entries to be estimated links. However, in LDP setting, \(\|A\|_{1,1}\) is kept private to the server and cannot be directly utilized. Following the same idea, we propose a LDP variant of it, namely L-DrGCN, where each node adds Laplacian noise to entries of its own adjacency list and sends the noisy adjacency matrix \(\tilde{A}\) to the server. The server first estimates the number of links by \(\|\tilde{A}\|_{1,1}\) and keeps the top \(\|\tilde{A}\|_{1,1}\) entries as estimated links.
3. Solitude is proposed in (Zhou et al., 2018) as a LDP mechanism to protect features, labels and links of the training graphs. The link LDP setting of theirs is identical to ours, and we only use the link privacy component of their mechanism. In Solitude, each node perturbs its adjacency list via randomized response, and the server collects noisy matrix \(\tilde{A}\). However, RR result is usually too dense to be useful for GNN training. Hence, Solitude learns a more sparse adjacency matrix by replacing the original GNN learning objective with \[\min_{\tilde{A},\theta}\mathcal{L}(\hat{A}|\theta)+\lambda_{1}\|\hat{A}-\hat{ A}\|_{F}+\lambda_{2}\|\hat{A}\|_{1,1},\] (10) where \(\theta\) is the GNN trainable parameters and \(\mathcal{L}(\hat{A}|\theta)\) is the original GNN training loss under parameters \(\theta\) and graph topology \(\hat{A}\). To optimize for Equation (10), Solitude uses alternating optimization to optimize for both variables.
4. Hidano and Murakami (Hidano and Murakami, 2018) propose DPRR (degree-preserving randomized response) to achieve \(\varepsilon\)-link local differential privacy to train GNNs for graph classification tasks. The algorithm denoises the randomized response noisy output by sampling from links reported by RR such that the density of the sampled graph is an unbiased estimation to the ground truth density. We implement DPRR as a baseline to compare with Blink variants.
5. We also implement and include baselines designed for privacy-preserving graph synthesis and analysis. Qin et al. (Qin et al., 2018) propose LDPGen, a mechanism to generate synthetic graphs by collecting link information from decentralized nodes with link LDP guarantees, similar to ours. The key idea of the mechanism is to cluster structurally similar nodes together (via K-means (Beng et al., 2017)) and use noisy degree vectors reported by nodes to generate a synthetic graph via the Chung-Lu model of random graphs (Beng et al., 2017).
6. Imola et al. (Imola et al., 2018) propose locally differentially private mechanisms for graph analysis tasks, namely, triangle counting and \(k\)-star counting. Their main idea is to use the randomized response mechanism to collect noisy adjacency lists from nodes, and then derive an estimator to estimate the target graph statistics from the noisy adjacency lists. We adopt the first part of their mechanisms, i.e., random response, to derive noisy graph topology to be used for GNNs. The RR mechanism used in (Imola et al., 2018) only involves injecting noise to the lower triangular part of the adjacency matrix, i.e., node \(v_{i}\) only perturbs \(a_{i,1},\ldots,a_{i,i-1}\) and sends these bits, to force the noisy adjacency matrix to be symmetric. Hence, we denote this baseline as SymRR.

More discussions of these baseline methods and other related works can be found in Section 6.

\begin{table}
\begin{tabular}{l c c c c} \hline \hline Dataset & \#Nodes & \#Features & \#Classes & \#Edges \\ \hline Cora(Xeon et al., 2017) & 2708 & 1433 & 7 & 5278 \\ CitsSeer(Xeon et al., 2017) & 3327 & 3703 & 6 & 4552 \\ LastFM(Nishu et al., 2018) & 7624 & 128 & 18 & 27806 \\ Facebook(Nishu et al., 2018) & 22470 & 128 & 4 & 171002 \\ \hline \hline \end{tabular}
\end{table}
Table 1. Statistics of the graph datasets used in experiments
Experimental setup.For all models and datasets, we randomly split the nodes into train/validation/test nodes with the ratio of 2:1:1. To better demonstrate the performance of Blink and other baseline methods, we apply them with multiple state-of-the-art GNN architectures including graph convolutional networks (GCN) (Gendle et al., 2016), GraphSAGE (Gendle et al., 2017) and graph attention networks (GAT) (Kumar et al., 2018) (details of the model configurations can be found in Appendix B.1). Note that we do not conduct experiment on Blink-Soft or Solitude with the GAT architecture because it is not reasonable to let all nodes attend over all others (Kumar et al., 2018) (even in a weighted manner). To compare the performance of DP mechanisms, we also experiment on all datasets with non-private GNNs, whose performance will serve as a theoretical upper bound of all DP mechanisms. Moreover, following (Kumar et al., 2018), we also include the performance of multi-layer perceptrons (MLPs) for each dataset, which is trained after removing all links from the graph and is considered fully link private. We experiment all mechanisms under all architectures and datasets with \(\varepsilon\in\{1,2,\ldots,8\}\). To showcase the full potential of our proposed method, for each combination of dataset, GNN architecture, privacy budget and mechanism, we run grid search and select the hyperparameters with the best average performance on validation data over 5 trials, and report the mean and standard deviation of model accuracy (or equivalently, micro F1-score, since each node belongs to exactly one class) on test data over 30 trials for statistical significance. Similar to previous works (Zhu et al., 2018; Wang et al., 2018), we do not consider the potential privacy loss during hyperparameter search. The hyperparameter spaces for all mechanisms used in grid search are described in detail in Appendix B.2.

### Experimental results and discussions

#### 5.2.1. Privacy-utility of the proposed Blink mechanisms

We report the average test accuracy of all three variants of Blink and other baseline methods over all datasets and GNN architectures in Figure 5. For all methods, the test accuracy increases as the total privacy budget increases, indicating the privacy-utility trade-off commonly found in differential privacy mechanisms. At all privacy budgets, L-DpGCN outperforms RR because the former one takes

Figure 5. Performance of Blink and other mechanisms. X-axis represents \(\varepsilon\) and y-axis represents test accuracy (%).
the graph density into consideration and preserves the number of links in the estimated graph, while the latter mechanism produces too many edges after randomly flipping the bits in the adjacency matrix which renders the graph too dense. This is consistent with Remark 4.5 where we show the huge improvement in estimation error for Blink over RR. We notice that the performance of SymRR and our implementation of Solitude is on par with RR, which makes sense because SymRR is essentially RR only applied to the lower triangular part of the adjacency matrix while Solitude de-noises graph topology based on RR outputs. Note that Lin et al. [27] did not made the implementation of Solitude publicly available by the time this paper was written, and the authors only performed experiments at large privacy budgets where \(\epsilon\geq 7\), while our results under similar privacy budgets agree with or outperform theirs presented in the paper. Additionally, the performance of LDPGen is worse than other mechanisms, which is expected because it is designed for graph synthesis and not for GNN training. The performance of LDPGen on GNNs also does not improve as the privacy budget increases, which is also expected because at all privacy budgets, the synthetic graph generated by LDPGen is always generated by a random graph model given noisy degree vectors. This has been discussed in Remark 4.8.

It is evident from Figure 5 that at all levels of \(\varepsilon\), the Blink variants generally outperform all baseline methods, because they also take individual degrees into consideration when estimating the prior probabilities, and utilize its confidence in links via hard thresholding, soft weighted aggregation or both. Noticeably, only Blink variants (especially Blink-Hard and Blink-Hybrid) can consistently perform on par with the fully link private MLP baselines, which is due to the fact that these variants can eliminate noisy and non-confident link predictions at low privacy budget and high uncertainty. Additionally, among the three GNN architectures, the baseline methods can perform better on GraphSAGE with accuracy closer to MLP. This is because GraphSAGE convolutional layers have a separate weight matrix to transform the embedding of the root node and hence can learn not to be distracted by the embeddings of false positive neighbors. See Appendix B.1 for details on GNN architectures. At last, for \(\epsilon\in[4,8]\) which is widely adopted in LDP settings in real-world industry practice [3, 13], Blink variants on different GNN architectures outperform the MLP and baselines significantly in most cases, indicating their utility under real-world scenarios. Also, when \(\epsilon\geq 6\), Blink variants achieve test accuracy on par with the theoretical upper bound on all datasets and architectures. In the following paragraphs, we describe with greater detail the performance and trade-off among the Blink variants.

Performance of Blink-Hard.As demonstrated in Figure 5, one main advantage of Blink-Hard is that it is almost never outperformed by MLP trained only on node features, which is not the case for the baseline methods. Existing approaches [21, 44] of achieving (central or local) link privacy on graphs aim to preserve the graph density in the estimated graph, i.e. try to make \(\|\hat{A}\|_{1,1}\approx\|A\|_{1,1}\), however, when \(\epsilon\) is small, it is against the promise of differential privacy to identify the same number of links from the estimated graph from the actual graph. As Kolluri et al. [25] point out, 100% of the selected top \(|E|\) links estimated by DrGCN [44] at \(\epsilon=1\) are false positive, corrupting the GNN results when aggregating neighbor embeddings. By only keeping links whose posterior link probability of existence exceeds 0.5, Blink-Hard takes an alternative approach of understanding graph density at tight privacy budgets and high uncertainty. As shown in Figure 6, \(\|\hat{A}\|_{1,1}\) estimated by Blink-Hard is much lower than the ground truth density \(\|A\|_{1,1}\) when \(\epsilon\) is small, and gradually increases to a similar level with \(\|A\|_{1,1}\) as \(\varepsilon\) increases. In this way, Blink-Hard eliminates information that is too noisy to be useful at low privacy budgets, thus reducing false positive link estimations and avoiding them from corrupting the GNN model. As shown in Figure 6, among the much fewer link estimations given by Blink-Hard, the true positive rates are much higher than DrGCN as reported in [25]. Therefore, Blink-Hard consistently outperforms the fully link-private MLP and other baselines.

Figure 6. Density of estimated \(\hat{A}\) against ground truth \(A\) in Blink-Hard.

Figure 7. GCN test accuracy on LastFM with all three variants at \(\epsilon\in(1,8)\). This is a closer look on the results in Figure 5 on LastFM with GCN.
Performance of Blink-Soft.Although Blink-Hard outperforms MLP and baseline mechanisms, the elimination and rounding of link probabilities lead to a significant amount of information loss. Blink-Soft aims to improve over the hard variant at moderate privacy budgets by utilizing the extra information while it is not too noisy. As described in Section 4.2.3, Blink-Soft utilizes the inferred link probabilities by using them as weights in the GNN aggregation step (see Appendix B.1 for more details), which has enabled the GNN to be fed with more information and perform better as long as the extra information is useful. As reflected in Figure 5 and Figure 7, Blink-Soft is able to outperform Blink-Hard at moderate privacy budgets (i.e., \(\varepsilon\in[4,6]\)) under almost all dataset and GNN architecture combinations. For higher privacy budgets, as both variants perform very well and are on par with the non-private upper bound, the performance gap is not significant. However, at lower privacy budgets where \(\varepsilon\in[1,3]\), Blink-Soft sometimes performs much worse than Blink-Hard and the fully private MLP baseline, for example, on LastFM with GCN model which we take a closer look in Figure 7. This is caused by the low information-to-noise ratio of the inferred link probabilities at low privacy budgets. Here, we confirm the hypothesis proposed in Section 4.2.3 that Blink-Hard and Blink-Soft complement each other where the hard variant performs better at low privacy budget while the soft variant performs better at higher privacy budgets.

Performance of Blink-Hybrid.The hybrid variant is proposed to combine the previous two aiming to enjoy the benefits of both variants across all privacy settings. As shown in Figure 5, at low privacy budgets, Blink-Hybrid successfully outperforms Blink-Soft by a significant margin and achieves test accuracy on par with Blink-Hard (thus, not outperformed by MLP), due to its elimination of noisy and useless information, avoiding false positive links from poisoning the model. At higher privacy budgets, Blink-Hybrid is often able to perform better than the hard variant, thanks to keeping the link probabilities as aggregation weights. For example, for the configuration of LastFM with GCN in Figure 5 which we take a closer look in Figure 7, Blink-Hard achieves accuracy close to Blink-Hard at \(\varepsilon\in[1,3]\) while performs on par with Blink-Soft at \(\varepsilon\in[4,8]\), achieving the best of both worlds. Although Blink-Hybrid is seldom able to outperform both the hard and the soft variants, it can enjoy both the benefits of Blink-Hard at low privacy budgets and the benefits of Blink-Soft at higher privacy budgets.

#### 5.2.2. On the effects of \(\delta\)

The degree privacy budget parameter, \(\delta\), is an important hyperparameter that makes a difference on the performance of the trained GNNs. In previous experiments, we choose the value of \(\delta\) by grid search and use the one that is associated with the best validation accuracy. To better understand the effects of different choices of \(\delta\) values on the GNN performance, we report the test accuracy of graph convolutional network on CiteSeer with Blink-Soft over varying \(\delta\) values at \(\varepsilon\in\{1,8\}\) in Figure 8. It can be seen that at different privacy budgets, there are different implications for the values of \(\delta\). At small privacy budget, i.e., \(\varepsilon=1\), we notice that the GNN performance increases as \(\delta\) value increases, while at larger privacy budget, e.g., \(\varepsilon=8\), it is clear that lower \(\delta\) values result in better performance. This is because at very tight privacy budgets, the noisy adjacency matrix given by randomized response will be too noisy to be useful, hence, the prior probabilities estimated from the noisy degree sequence will be more important. Therefore, it is optimal to allocate more privacy budget towards degrees. At much higher privacy budgets, the flip probability in randomized response becomes so small that the noisy adjacency matrix itself is sufficient to provide the necessary information to effectively train the GNN, hence, it is preferred to allocate more privacy budget to the adjacency lists. If we denote \(\delta^{*}(\varepsilon)\) as the optimal \(\delta\) at total privacy budget \(\varepsilon\) that achieves the best performing GNNs (for instance, we have \(\delta^{*}(1)=0.9\) and \(\delta^{*}(8)=0.1\) in Figure 8), we propose a conjecture that \(\delta^{*}\) decreases as \(\varepsilon\) increases, i.e., \(\delta^{*\prime}(\varepsilon)<0\), and our experiments resonate with this conjecture.

#### 5.2.3. Ablation studies

Naturally, one would be curious about which component, the prior or the evidence, of the proposed Blink mechanisms, contributes more to the final link estimations \(P\). To answer this question, we conduct ablation studies on the proposed methods. Figure 9 reports the MAE of the estimated link probabilities \(P\) against the ground truth \(A\) under Blink, its prior component and its evidence components. Blink with prior component only is equivalent to taking \(\delta=1\) where the flip probability of RR becomes \(1/2\) and hence the noisy adjacency matrix does not provide any information as evidence. Blink with evidence only is the case where the prior probabilities are set to be all \(1/2\) to provide no extra information.

Figure 8. GCN test accuracy on CiteSeer with Blink-Soft at \(\varepsilon\in\{1,8\}\).

Figure 9. The MAE of the estimated link probabilities \(P\) against ground truth \(A\) for full Blink, Blink with prior component only and Blink with evidence component only on CiteSeer. The latter figure is a closer look at the prior component whose trend is unclear in the former figure.
First, as shown in Figure 9, all mechanisms, the complete and partial ones, have their MAE decreasing as privacy budgets increase. More importantly, it can be seen that at tighter privacy budgets, the prior-only mechanism produces better estimations than its evidence-only counterpart, indicating that the prior contributes more to the final estimation at tighter privacy budgets. When \(\varepsilon\) grows (i.e., \(\varepsilon\geq 7\) in Figure 9), the noisy adjacency matrix becomes less noisy so the evidence-only method starts to produce better estimations, playing a more important role than the prior. This agrees with the findings in Section 5.2.2 that it is optimal to allocate more privacy budget to degrees (i.e., the prior component) at smaller \(\varepsilon\) and vise versa. It is important to note that at all privacy budgets, the full Blink method significantly outperforms both single-component methods, indicating that our proposed method effectively utilizes both components to make better estimations and both components are irreplaceable in Blink.

## 6. Related Work

Graph neural networks.Recent years have witnessed an emerging amount of work on graph neural networks for many tasks on graph, such as node classification, link classification and graph classification. Many novel GNN models have been proposed, including GCN (Kipf and Welling, 2015), GraphSAGE (Kipf and Welling, 2015), GAT (Kipf and Welling, 2015) and Graph Isomorphism Networks (Kipf and Welling, 2015). As our proposed mechanism estimates the graph topology and then feed it into GNN models without interfering the model architecture, we will not survey recent advances in GNNs here in great detail, but refer the audience to available surveys (Kipf and Welling, 2015; Kipf and Welling, 2015; Kipf and Welling, 2015) for detailed discussions of GNN models, performance and applications.

Differentially private GNNs.There have been recent attempts in the literature of incorporating the notion of differential privacy to GNNs. Wu et al. (Wu et al., 2015) study the adversarial link inference attacks on GNNs and proposes DrGCN, a central DP mechanism to protect edge-level privacy, which can be easily modified to adopt stronger LDP guarantee. Daigavane et al. (Daigavane et al., 2016) attempt to extend the well-celebrated DP-SGD (Deng et al., 2015) algorithm on neural networks to GNNs and achieve stronger node-level central differential privacy. More recently, Kolluri et al. (Kolluri et al., 2016) propose new GNN architecture to achieve edge-level central DP, where they separate the edge structure and only use MLPs to model both node features and graph structure information. Following a similar intuition, Sajadmanesh et al. (Sajadmanesh et al., 2016) propose a new mechanism where the aggregation step is decoupled from the GNN and executed as a pre-processing step to save privacy budget. When combined with DP-SGD, Sajadmanesh et al. (Sajadmanesh et al., 2016) achieve stronger node-level central DP on the altered GNN architecture.

For local differential privacy, Sajadmanesh and Gatica-Perez (Sajadmanesh et al., 2016) propose a LDP mechanism to protect node features but not the graph topology. Lin et al. (Lin et al., 2017) extend on (Sajadmanesh et al., 2016) and propose Soutput to also protect edge information in a LDP setting. The link LDP notion of (Lin et al., 2017) is identical to that of ours. However, their link DP mechanism is not principled and their estimated graph structure is learned by minimizing a loss function \(\|\hat{A}-\hat{A}\|_{1,1}+\lambda\|\hat{A}\|_{F}\) to encourage the model to choose less dense graphs. Hidano and Murakami (Hidano and Murakami, 2017) propose link LDP mechanism for graph classification tasks, and takes a similar approach to ours, by separately injecting noise to adjacency matrix and degrees. However, Hidano and Murakami (Hidano and Murakami, 2017) aim to preserve node degrees in the estimated graph like DrGCN, which is not suitable to node classification tasks and performs worse than our method as shown in Section 5.

Privacy-preserving graph synthesis.Privacy-preserving graph publication is also closely related to what we have studied, where one aims to publish a sanitized and privacy-preserving graph given an input graph. Blocki et al. (Blocki et al., 2015) utilize the Johnson-Lindenstrauss Transform to achieve graph publication with edge differential privacy. Qin et al. (Qin et al., 2016) consider local edge differential privacy where an untrusted data curator collects information from each individual user about their adjacency lists and construct a representative synthetic graph of the underlying ground truth graph with edge LDP guarantee. This is achieved by incrementally clustering structurally similar users together. More recently, Yang et al. (Yang et al., 2017) achieve differentially private graph generation by noise injection to a graph generative adversarial network (GAN) such that the output of the GAN model is privacy-preserving. It is worth noting that in the settings of (Blocki et al., 2015; Wu et al., 2015), a privacy-preserving synthetic graph is generated in a centralized way, i.e., the curator has access to the ground truth graph and perturbs it for a privacy-preserving publication, which is a weaker threat model than ours. Qin et al. (Qin et al., 2016) consider threat models similar to ours with local differential privacy where the curator does not need to have access to the actual graph, but there's no theoretical upper bound on the distance from the synthetic graph to the ground truth graph, which we provide in Theorem 4.4.

Privacy-preserving graph analysis.There exist prior works in the literature proposed for graph analysis tasks with local differential privacy. Imola et al. (Imola et al., 2017) propose mechanisms to derive estimators for triangle count and \(k\)-star count in graphs with link LDP. Ye et al. (Ye et al., 2017) propose a general framework for graph analysis with local differential privacy, to estimate an arbitrary aggregate graph statistic, such as clustering coefficient or modularity. This approach combines two estimators of the target aggregate statistic, one from noisy neighbor lists and one from noisy degrees, and derives a better estimator for the target statistic. However, this approach does not produce an estimated graph topology that can be used for GNN training. Hence, we do not include this as a baseline in our experiments in Section 5.

Link inference attacks in GNNs.As the popularization of GNNs in research and practice in recent years, there has garnered an increasing amount of attention on their privacy and security in the research community, and several privacy attacks on GNNs have been proposed for an attacker to infer links in the training graph. He et al. (He et al., 2017) propose multiple link stealing attacks for an adversary to infer links in the training graph given black-box access to the trained GNN model, guided by the heuristic that two nodes are more likely to be linked if they share more similar attributes or embeddings. Wu et al. (Wu et al., 2015) consider a scenario where a server with full access to graph topology trains a GNN by querying node features and labels from node clients (who do not host graph topology), and demonstrate that the nodes can infer the links from the server by designing adversarial queries via influence analysis. Zhang et al. (Zhang et al., 2017) propose graph reconstruction attacks where an adversary examines the trained graph embeddings and aims to reconstruct a graph similar to the ground truth graph used in GNN
training. All these attacks share the same threat model where the GNN is trained with complete and accurate information and an adversary aims to infer links by examining the trained model. Our proposed solution, Blink, naturally defends this kind of attacks at its source as a local differential privacy mechanism with a more severe threat model, where even the server who trains the GNN does not have non-private access to any links in the training graph.

**Estimate of link probability given degree sequence.** The model and estimation of random graphs given degree sequence is a common topic in network science and probability theory. Chatterjee et al. (2019) discuss the maximum likelihood estimate of parameters in \(\beta\)-model, which is closely related to BTL model for ranking (Blink, 2018; Dwork et al., 2019). Parameters in BTL model can be estimated via MM algorithms (Krishnan et al., 2019) or MLE (Zhu et al., 2019). Alternatively, configuration model (Krishnan et al., 2019) can also be used to model random graphs given degree sequence, which generates multi-graphs that allows multiple edges between two vertices. In configuration model, the expected number of edges between two nodes \(v_{i}\) and \(v_{j}\) conditioned on the degree sequence \(d\) is given by \(d_{i}d_{j}/(\sum d_{i}-1)\). When this value \(\ll 1\), it can be considered a probability that there's (at least one) edge between \(v_{i}\) and \(v_{j}\). We also attempt Blink with configuration model instead of \(\beta\)-model, but the link probabilities fail to be consistently below 1.

## 7. Conclusion

Overall, the presented framework, Blink, is a step towards making GNNs locally privacy-preserving while retaining their accuracy. It separately injects noise to adjacency lists and node degrees, and uses the latter as prior and the former as evidence to evaluate posterior link probabilities to estimate the ground truth graph. We propose three variants of Blink based on different approaches of constructing the graph estimation from the inferred link probabilities. Theoretical and empirical evidence support the state-of-the-art performance of Blink against existing link LDP approaches.

The area of differentially private GNNs is still novel with many open challenges and potential directions. There are a few future research directions and improvements for the presented paper. First, one may want to improve the bound in Theorem 4.4, which would require careful inspection of \(\hat{\beta}\) found by MLE. Also, an interesting future direction of research is to design algorithms such that each node can optimally decide its own privacy parameter \(\delta\), to avoid the use of hyperparameter search of \(\delta\) which may potentially lead to information leakage (Zhu et al., 2019). We also leave the investigation of such potential risk to future work. Additionally, one could consider exploring different models for graph generation from the posterior link probabilities, or extend the proposed framework to other types of graphs such as directed or weighted graphs. Furthermore, exploring the scalability of Blink for large-scale graph data is an important future direction. At last, one may also want to incorporate other LDP mechanisms that protect features and labels (such as (Zhu et al., 2019)) into Blink to provide complete local privacy protection over decentralized nodes.

## Acknowledgements

This work is supported by the Singapore Ministry of Education Academic Research Fund (AcRF) Tier 3 under MOE's official grant number MOE2017-T3-1-007 and AcRF Tier 1 under grant numbers A-8000980-00-0 and A-8000189-01-00.
