Privacy-preserving design of graph neural networks with applications to
  vertical federated learning
The paradigm of vertical federated learning (VFL), where institutions
collaboratively train machine learning models via combining each other's local
feature or label information, has achieved great success in applications to
financial risk management (FRM). The surging developments of graph
representation learning (GRL) have opened up new opportunities for FRM
applications under FL via efficiently utilizing the graph-structured data
generated from underlying transaction networks. Meanwhile, transaction
information is often considered highly sensitive. To prevent data leakage
during training, it is critical to develop FL protocols with formal privacy
guarantees. In this paper, we present an end-to-end GRL framework in the VFL
setting called VESPER, which is built upon a general privatization scheme
termed perturbed message passing (PMP) that allows the privatization of many
popular graph neural architectures.Based on PMP, we discuss the strengths and
weaknesses of specific design choices of concrete graph neural architectures
and provide solutions and improvements for both dense and sparse graphs.
Extensive empirical evaluations over both public datasets and an industry
dataset demonstrate that VESPER is capable of training high-performance GNN
models over both sparse and dense graphs under reasonable privacy budgets.
Ruofan Wu, Mingyang Zhang, Lingjuan Lyu, Xiaolong Xu, Xiuquan Hao, Xinyi Fu, Tengfei Liu, Tianyi Zhang, Weiqiang Wang
# Privacy-preserving design of graph neural networks with applications to vertical federated learning

###### Abstract

The paradigm of vertical federated learning (VFL), where institutions collaboratively train machine learning models via combining each other's local feature or label information, has achieved great success in applications to financial risk management (FRM). The surging developments of graph representation learning (GRL) have opened up new opportunities for FRM applications under FL via efficiently utilizing the graph-structured data generated from underlying transaction networks. Meanwhile, transaction information is often considered highly sensitive. To prevent data leakage during training, it is critical to develop FL protocols with _formal privacy guarantees_. In this paper, we present an end-to-end GRL framework in the VFL setting called VESPER, which is built upon a general privatization scheme termed _perturbed message passing (PMP)_ that allows the privatization of many popular graph neural architectures. Based on PMP, we discuss the strengths and weaknesses of specific design choices of concrete graph neural architectures and provide solutions and improvements for both dense and sparse graphs. Extensive empirical evaluations over both public datasets and an industry dataset demonstrate that VESPER is capable of training high-performance GNN models over both sparse and dense graphs under reasonable privacy budgets.

## 1 Introduction

In recent years, there has been an increasing interest in adopting modern machine learning paradigms to the area of financial risk management (FRM) [31]. The most crucial task in operational risk scenarios like fraud detection is identifying risky identities based on the behavioral data collected from the operating financial platform [4; 24]. For institutions like commercial banks and online payment platforms, the most important source of behavior information is the _transaction records_ between users, making _transaction networks_ (with users as nodes and transactions as edges) a direct and appropriate data model. To exploit the potential of transaction networks in a machine learning context, recent approaches [26; 47] have been exploring the adoption of graph representation learning (GRL) [16] as a principled way of incorporating structural information contained in transaction networks into the learning process. The family of graph neural networks in the message passing form [13; 48] offers a powerful yet scalable solution to GRL, and has become the prevailing practice in industry-scale graph learning [52].

Despite its convincing performance, high-quality network data are not always available for financial institutions. F It is, therefore, of great interest for institutions to learn GRL models _collaboratively_ while being coherent to regulatory structures at the same time. The technique of federated learning
(FL) [20, 49] provides a recipe for such scenarios, with participating institutions (hereafter abbreviated as _parties_) exchanging intermediate results instead of raw data. Depending on the specific form of collaboration, FL protocols are generally divided into horizontal federated learning (HFL), where participants aggregate their locally trained models to obtain a strong global model, and vertical federated learning (VFL) where participants are able to align the identifiers of modeling entities and train a model that efficiently combines feature or label information that are distributed among different parties. VFL is particularly useful when training a (supervised) model is not possible based on information of a single party, i.e., each party holds only feature or label data, and has attracted significant attention in applications to FRM [28]. While ordinary FL paradigms avoid the transmission of local raw data, they typically lack a formal guarantee of privacy [20, Chapter 4]. Moreover, recent studies have reported successful attacks targeting individual privacy against FL protocols [54, 50, 19, 9, 8]. As transaction records are widely considered extremely sensitive personal information, it is thus critical to establish FL applications in FRM with rigorous privacy guarantees.

Differential privacy (DP) [11] is the state-of-the-art approach to address information disclosure that injects algorithm-specific random noise to fuse the participation of any individual. The adoption of DP as the privacy model for FL is now under active development, with most of the applications appearing in HFL over independently identically distributed (i.i.d.) data through the lens of optimization [20]. However, discussions on applying DP over VFL remain nascent [3, 53, 39]. The situation becomes even more complicated in VFL over graph-structured data, since the right notions of (differential) privacy on graphs are semantically different from that in the i.i.d. case [35, 22]. So far, as we have noticed, the only work that provides meaningful DP guarantee under VFL over graphs is the GAP model [39], which requires three stages of training. Meanwhile, a notable aspect of GRL is that the structure of the underlying graph, i.e., whether the graph is dense or sparse, might have a significant influence on the performance of the graph neural model especially when the aggregation process involves noisy perturbations. This phenomenon was overlooked in previous studies.

In this paper, we discuss private FL over graph-structured data under the task of node classification in the vertical setup with edge DP [35] chosen as the privacy model. We first develop a general privatization scheme termed _perturbed message passing (PMP)_ that produces message-passing procedures over graphs that are guaranteed to satisfy edge DP constraints. Next, we discuss the influence of the underlying graph's degree profiles on the utility of specific design choices of PMP, using two representative graph aggregation schemes, namely GIN [48] and GCN [23], and develop further improvements of PMP that better handles sparse graphs under the GCN aggregation scheme. Finally, we integrate the developments of PMP and its variants into a VFL architecture called VESPER based on the SplitNN framework [14], and conducted extensive empirical evaluations over both public and industrial datasets covering dense and sparse graphs. We summarize our contributions as follows:

* We propose PMP, a general framework for designing differentially private message-passing procedures. PMP enables the privatization of many popular graph neural network architectures. The privacy guarantee of PMP is formally analyzed with new privacy amplification results under uniform neighborhood sampling.
* We discuss two representative design choices under the PMP framework, GIN and GCN, and discover the fact that the utility of the privatized GNN model may be affected by the _degree profile_ of the input graph. To better accommodate varying graph structures, we develop the truncated message passing framework under the base model of GCN through properly tuning the hyper-parameter that reduces noise scale at the cost of learning less structural information, which is beneficial when the input graph is _sparse_.
* We derive an end-to-end VFL learning framework operating over graph-structured data called VESPER, which is efficient in computation and communication. A thorough experimental study demonstrates that VESPER achieves better privacy-utility trade-off over previously proposed models and is capable of training high-performance GNN models over both sparse and dense graphs under reasonable privacy budgets.
## 2 Methodology

### Preliminaries

We focus on the node classification task over a static, undirected graph \(G=(V,E)\) with node size \(N=|V|\), node feature \(X=\{x_{v}\}_{v\in V}\) and node labels \(Y=\{y_{v}\}_{v\in V_{T}}\) where \(V_{T}\subseteq V\) is the set of training nodes with \(N_{T}=|V_{T}|\). Throughout this article, we will assume the graph of interest to be degree bounded, i.e.,

\[\max_{G}\max_{v\in G}d_{v}\leq D \tag{1}\]

for some \(D>1\). In this paper, we will be interested in the setup where the graph data \(G\) and label information are distributed over two distinct parties. Specifically, suppose there are two parties, A (Alice) and B (Bob), where A holds the graph data \(G\) as well as the node feature \(X\) and B holds the label collection \(Y\), both indexed by node identifiers that are known to both sides (i.e., \(V_{T}\) is known to both party A and party B). We consider a representative federated learning paradigm that A and B collaboratively train a graph representation learning model via utilizing the panoply of graph neural networks [13], which could be regarded as a special case of vertical federated learning (VFL) [49]. Under VFL protocols, party A and party B iteratively exchange intermediate outputs depending on the specific training algorithm chosen. A main concern in VFL [20, Chapter 4] is, therefore, whether the exchanging process satisfies formal _privacy_ guarantees. Before elaborating on privacy protection issues, we first state the threat model in our context.

**Threat model** We adopt the following threat model in this paper: In the training stage, label party B is curious about the adjacency information (i.e., the existence of some edges) in the data party A. The data party A is assumed to be benign, with both parties strictly obeying the chosen VFL protocol. 1 In other words, the goal of privacy protection is to prevent the _semi-honest_ adversary (party B) from inferring the edge membership that is only known to party A.

Footnote 1: The assumption of a harmless party A might be relaxed to a curious onlooker that tries to infer party B’s label information. We discuss related extensions in section D.

Differential privacy [11] is now the _de facto_ choice of privacy protection paradigm against membership inference adversaries. As an appropriate solution concept in the current setup, we introduce the edge-level differential privacy model (hereafter abbreviated as Edge DP).

**Definition 1** (Edge-level differential privacy(Edge DP)).: For a (randomized) graph-input mechanism \(\mathcal{M}\) that maps graphs to some output space \(\mathcal{S}\) and two non-negative numbers \(\epsilon\) and \(\delta\), the mechanism is \((\epsilon,\delta)\)-Edge DP if for any subset \(S\) (or more rigorously defined as Borel measurable sets) of the output space, the following holds uniformly for any two possible adjacent graphs \((G,G^{\prime})\):

\[\mathbb{P}[\mathcal{M}(G)\in S]\leq e^{\epsilon}\mathbb{P}[ \mathcal{M}(G^{\prime})\in S]+\delta, \tag{2}\]

where we define two graphs \(G\) and \(G^{\prime}\) as being adjacent if \(G\) could be edited into \(G^{\prime}\) via adding or removing a single edge.

Regarding the capability of the adversary adopted in this paper, a VFL protocol satisfying Edge DP with a reasonable \(\epsilon\) level implies that based on all the exchanged intermediate outputs between party A and party B, any membership inference algorithm may not be able to make any sophisticated guess about the existence of some specific edge in a probabilistic sense, thereby offering strong privacy protection. Most contemporary differentially private machine learning algorithms involve sequentially applying DP procedures to intermediate learning steps [1], with the privacy level of

Figure 1: A concise pictorial description of the VESPER framework. We use solid arrows to depict the dataflow of forward computations and use dashed arrows to depict the dataflow of backward computations.
the entire training procedure obtained via composition theorems [11; 21]. In this paper, we choose the composition framework of analytical moment accountant (AMA) [44] that exploits the idea of Renyi DP [33], which we introduce below in our graph learning context:

**Definition 2** (Edge-level Renyi -differential privacy(Edge RDP)).: Sharing notations with definition 1, the mechanism \(\mathcal{M}\) is \((\alpha,\epsilon(\alpha))\)-Renyi differentially private with some \(\alpha>1\) and \(\epsilon(\alpha)\geq 0\), if for any two possible adjacent graphs \((G,G^{\prime})\), the \(\alpha\)-Renyi divergence of the induced probability distribution of random variables \(\mathcal{M}(G)\) and \(\mathcal{M}(G^{\prime})\) is bounded by \(\epsilon(\alpha)\):

\[D_{\alpha}\left(\mathcal{M}(G)||\mathcal{M}(G^{\prime})\right)\leq\epsilon( \alpha), \tag{3}\]

with the definition of \(\alpha\)-Renyi divergence \(D_{\alpha}\left(\cdot||\cdot\right)\) presented in appendix A.

To develop privacy-preserving learning algorithms under the AMA framework, we first design mechanisms that satisfy RDP guarantee in each step, then use standard composition results of RDP [33] to obtain the privacy level of the learning procedure. Finally, we apply the conversion rule in [2] to convert it back to \((\epsilon,\delta)\)-DP for reporting.

**Message passing GNNs with stochastic training** The backbone of our privacy-preserving training framework is the graph neural network model in the message passing form [13]. We define the GNN of interest to be a map from the space of graphs to a node embedding matrix with embedding dimension \(d\): \(f:\mathcal{G}\mapsto\mathbb{R}^{N\times d}\), or \(H:=\{h_{v}\}_{v\in V}=f(G)\). For an \(L\)-layer GNN, let \(h_{v}^{(0)}=g(x_{v})\) be the input encoding of node \(v\), which could be either \(x_{v}\) or some encoding based on \(x_{v}\). We assume the following recursive update rule for \(1\leq l\leq L\) and \(v\in V\):

\[h_{v}^{(l)}=\sigma\left(\widetilde{h}_{v}^{(l)}\right),\quad\widetilde{h}_{v}^ {(l)}=\omega_{v}W_{1}^{(l)}h_{v}^{(l-1)}+\sum_{u\in N(v)}\beta_{uv}W_{2}^{(l)}h _{u}^{(l-1)}, \tag{4}\]

with \(\mathbf{\omega}:=\{\omega_{v}\}_{v\in V}\in\mathbb{R}^{N}\) and \(\mathbf{\beta}:=\{\beta_{uv}\}_{u,v\in V\times V}\in\mathbb{R}^{N\times N}\) be model-dependent coefficients, \(\sigma\) a parameter-free nonlinear function, and \(\mathbf{W}=(W_{1}^{(1)},\dots,W_{1}^{(L)},W_{2}^{(1)},\dots,W_{2}^{(L)})\) be the collection of learnable parameters. For any matrix \(W\), we denote \(\|W\|_{\text{op}}\) as the operator norm of the matrix (i.e., its largest singular value). In this paper, we assess two representative instantiations of the protocol (4) which are the GIN model [48] with with \(\omega_{v}\equiv\beta_{uv}\equiv 1,\forall u,v\in V\) and the GCN model [23] with \(\omega_{v}=\frac{1}{d_{v}+1}\) and \(\beta_{uv}=\frac{1}{\sqrt{d_{u}+1}\sqrt{d_{v}+1}}\). For simplicity we additionally let the nonlinearity be the ReLU function and set \(W_{1}^{(l)}=W_{2}^{(l)}=W^{(l)},1\leq l\leq L\).

Applying message passing updates (4) may become computationally prohibitive for large input graphs, which are frequently encountered in industrial scenarios. To enable scalable GRL, the prevailing practice is to use graph sampling methods [15] and adopt **stochastic training of graph neural networks**. In this paper, we investigate the simple and effective sampling scheme of uniform neighborhood sampling [15; 7], with the maximum number of neighbors sampled in each layer to be the maximum degree \(D\). Asides from their computational benefits, it has been observed [1; 32] that stochastic training with a low sampling ratio over large datasets is crucial to training high-utility differentially private machine learning models with reasonably small privacy budgets, which has also been recently verified in the case of differentially private graph learning [7; 39].

### Perturbed message passing

A notable fact about the message-passing protocol (4) is that it uses the aggregation strategy of _weighted summation_, thereby allowing standard additive perturbation mechanisms like the Laplace mechanism or Gaussian mechanism that are prevailing in the design of differentially private algorithms [11]. Motivated by this fact, we propose a straightforward solution to privatize message-passing GNNs in a _layer-wise_ fashion named _perturbed message passing (PMP)_, which adds layer-wide Gaussian noise with an additional normalization step that controls sensitivity. We present the pseudo-code of PMP with neighborhood sampling in algorithm 1. Next we discuss the privacy guarantee of algorithm 1. To state our main result, we first define the right notion of sensitivity in our context:

**Definition 3** (Edge sensitivity).: Denote \(G^{\prime}\) as the adjacent graph via removing the edge \((u^{*},v^{*})\) from \(G\), and let \(\widetilde{h}_{v}\) and \(\widetilde{h}^{\prime}_{v}\) be the outputs of node \(v\) generated via some \(1\)-layer GNN protocol under graph \(G\) and \(G^{\prime}\) without nonlinearity, then we define the (\(\ell_{2}\)-) _edge sensitivity_ as:

\[\mathcal{S}=\max_{G,G^{\prime}}\sqrt{\sum_{v\in V}\|\widetilde{h}_{v}- \widetilde{h}^{\prime}_{v}\|_{2}^{2}}. \tag{5}\]
The following theorem quantifies the privacy guarantee of algorithm 1:

**Theorem 2.1** (RDP guarantee).: _Let \(\mathbf{H}_{L}\) be the released outputs with input a minitach of \(B\) subgraphs produced by uniform neighborhood sampling for \(L\) layers with a maximum number of \(D\) neighbors sampled in each layer. Define \(\epsilon(\alpha):=\frac{\alpha\sum_{L}^{L}\mathcal{S}_{2}^{2}}{2\theta^{2}}\), then \(\mathbf{H}_{L}\) is \((\alpha,\epsilon_{\gamma}(\alpha)\)-RDP for any \(\alpha>1\), where \(\gamma=1-\frac{\binom{N_{T}-\frac{2(DL-1)}{D-1}}{\binom{B}{B}}}{\binom{B}{B}}\) and_

\[\epsilon_{\gamma}(\alpha)\leq\frac{1}{\alpha-1}\log\left(1+ \gamma^{2}\binom{\alpha}{2}\min\left(4\left(e^{\epsilon(2)}-1\right),\epsilon( 2)\min\left(2,\left(e^{\epsilon(\infty)-1}\right)^{2}\right)\right)\right. \tag{6}\] \[+\left.\sum_{j=3}^{\infty}\gamma^{j}\binom{\alpha}{j}e^{(j-1) \epsilon(j)}\min\left(2,\left(e^{\epsilon(\infty)-1}\right)^{j}\right)\right)\]

Theorem 2.1 provides a principled way of analyzing the privacy of privatized GNN models using algorithm 1, which boils down to computing the edge sensitivity of the underlying message passing protocol. However, sensitivity computations are usually conducted in a _worst-case_ manner, resulting in unnecessarily large noise levels and significant utility loss. Therefore, it is valuable to explore the utility of concrete PMP models and their relationships with the underlying input graph. To begin our expositions, we analyze the GIN model in the following section.

```
0: Graph \(G=(V,E)\), input encodings \(\{h_{v}^{(0)}\}_{v\in V}\), number of message passing rounds \(L\), GNN spec \((\omega,\mathbf{\beta},\sigma)\), noise scale \(\theta\), GNN parameter \(\mathbf{W}\), batch size \(B\), maximum degree \(D\).
1: Sample a random batch of root nodes \(v_{1},\ldots,v_{B}\).
2: Apply an \(L\)-layer neighborhood sampler with each layer sampling at most \(D\) nodes with roots \(v_{1},\ldots,v_{B}\), obtaining a batch of \(B\) subgraphs \((G_{v_{1}}^{(L)},\ldots,G_{v_{B}}^{(L)})\).
3: Combine \((G_{v_{1}}^{(L)},\ldots,G_{v_{B}}^{(L)})\) into a subgraph \(G_{B}^{(L)}\). Additionally, overload the notation \(N(v)\) for the neighborhood of node \(v\) with respect to \(G_{v_{B}}^{(L)}\).
4: Set \(h_{v}^{(0)}=\frac{h_{v}^{(0)}}{\left\|h_{v}^{(0)}\right\|_{2}}\) for \(\forall v\in G_{v_{B}}^{(L)}\))
5:for\(l\in\{1,\ldots,L\}\)do
6:for\(v\in G_{v_{B}}^{(L)}\)do
7: Compute the linear update \(\widetilde{h}_{v}^{(l)}=\omega_{v}W_{1}^{(l)}h_{v}^{(l-1)}+\sum_{u\in N(v)} \beta_{uv}W_{2}^{(l)}h_{u}^{(l-1)}\).
8: Do additive perturbation, \(h_{v}^{(l)}=\sigma(\widetilde{h}_{v}^{(l)}+N(0,\theta^{2}))\)
9: Normalize \(h_{v}^{(l}=\frac{h_{v}^{(l)}}{\left\|h_{v}^{(l)}\right\|_{2}}\) return A list of all layers' embedding matrices \(\mathbf{H}_{L}=(H^{(1)},\ldots,H^{(L)})\), with \(H^{(l)}=\{h_{v}^{(l)}\}_{v\in G_{v_{B}}^{(L)}},1\leq l\leq L\).
```

**Algorithm 1** PMP with neighborhood sampling

### Analysis of GIN and the challenge of sparse graphs

We start with the following proposition:

**Proposition 1**.: _Under the GIN model, the edge sensitivity is bounded from above by \(\mathcal{S}_{l}^{\text{GIN}}\leq\sqrt{2}\|W^{(l)}\|_{\text{op}}\) for each \(1\leq l\leq L\)._

**Advantage of layer-wise perturbations** According to proposition 1, the edge sensitivity of GIN is independent of the input graph's maximum degree upper bound \(D\), which is essentially a direct consequence of the fact that for a \(1\) layer message passing procedure, adding or removing one edge would affect up to two nodes' output embeddings. As a consequence, the privacy cost scales linearly with the number of message-passing layers in the Renyi DP framework, thereby offering a better privacy-utility trade-off than algorithms that do the do the perturbation only in the final layer [53], whose privacy cost may scale exponentially with \(D\).
**Effectiveness and challenges of summation pooling** It has been observed in previous works [39] that aggregation perturbation with sum pooling works well on graphs with a large average degree. Intuitively, this phenomenon could be understood as keeping a high "signal-to-noise ratio (SNR)" during the aggregation process: For nodes with large degrees, the noise scale becomes relatively small with respect to the summation of incoming messages. Therefore if high-degree nodes are prevalent in the underlying graph, the utility loss during aggregation is reasonably controlled for most nodes. However, realistic graph data might not have large average degrees. For example, transaction networks in FRM scenarios are usually sparse, including many nodes with degrees smaller than \(5\) or even being singular (i.e., of degree \(0\)). Consequently, the SNR of sparse networks makes it harder for summation pooling to maintain decent utility, which will be further verified in section 3.

### Improvements of PMP in the GCN model

As discussed in the previous section, the degree profile of the input graph may affect the utility of PMP-privatized GNNs when the underlying aggregation follows the summation pooling scheme. It is therefore of interest to explore aggregation schemes that are more appropriate when the input graph is sparse. On first thought, we may expect aggregation schemes like mean pooling or GCN pooling to have smaller sensitivities. However, such sensitivity reduction does NOT hold in a worst-case analysis: Just think of nodes with degree \(1\), then it is not hard to check that mean pooling or GCN pooling behaves similarly to summation pooling. The primary issue with worst-case analysis is that the resulting sensitivity is determined by extremely _low-degree_ nodes. Inspired by this phenomenon, we seek improvements by first deriving lower sensitivity with an extra requirement on a _degree lower bound_, and then relax the requirement via introducing a modified protocol. We start with the following observation:

**Proposition 2**.: _Assume all the possible input graphs have a minimum degree larger or equal to \(D_{\text{min}}\), or_

\[\min_{G}\min_{v\in G}d_{v}\geq D_{\text{min}}>1. \tag{7}\]

_Then for the GCN model, the edge sensitivity of the \(l\)-th layer \(\mathcal{S}_{l}^{\text{GCN}}\) is bounded from above by a function \(\eta_{l}(D_{\text{min}})\), defined as:_

\[\eta_{l}(D_{\text{min}})=\sqrt{2}\left(\frac{1-1/D_{\text{min}}}{2D_{\text{min }}}+\frac{1}{D_{\text{min}}(D_{\text{min}}+1)}+\frac{1}{D_{\text{min}}+1} \right)\|W^{(l)}\|_{\text{op}}. \tag{8}\]

Proposition 2 implies that the edge sensitivity of the GCN model shrinks significantly if the underlying graph has a reasonably large minimum degree, which will result in a significantly reduced noise scale that improves utility. However, the minimum degree assumption (7) is impractical since most of the realistic graph data have a large number of nodes with small degrees. To circumvent the impracticality of assumption (7) while still being able to reduce the noise scale in the GCN model, we propose a modification to the basic message passing algorithm 1 called _truncated message passing_. The idea of truncated message passing is to block all the incoming messages unless the receiver node's neighborhood is large than or equal to \(D_{\text{min}}\), which is treated as a hyperparameter. For nodes with degrees lower than \(D_{\text{min}}\), the output embedding is instead produced by an MLP with perturbation that does not involve any edge information. A detailed version is provided in algorithm 2 in appendix F. Consequently, it is straightforward to show that the differential privacy guarantee of the resulting algorithm operating on any graph matches the privacy level of perturbed GCN (produced by algorithm 1) operating only on graphs with minimum degree assumption.

**How to choose \(D_{\text{min}}\)?** To maintain the same privacy level under the truncated message passing algorithm, one may reduce the noise scale \(\theta\) at the cost of raising the minimum degree hyperparameter \(D_{\text{min}}\). On the one hand, reducing the noise scale significantly improves the utility of the message-passing procedure. On the other hand, raising \(D_{\text{min}}\) might prevent a non-ignorable proportion of nodes from learning structural information. Therefore, properly adjusting \(D_{\text{min}}\) may help achieve a better privacy-utility trade-off in the GCN model. In practice, one may choose \(D_{\text{min}}\) based on prior knowledge about the degree distribution of the underlying graph or via inspecting a private release of its degree distribution, which could be done efficiently using the Laplace mechanism [11].

### VESPER: an end-to-end learning framework

In previous sections, we have established the PMP framework for differentially private graph representation learning. Now under the vertically federated learning setup described in section 2.1,
we propose an end-to-end architecture inspired by the SplitNN paradigm [14] based on the PMP framework, named **V**E**rtically private **S**plit GNN with **PER**turbed message passing(**V**ESPER**). The VESPER architecture contains three main components: Encoder, Private representation extractor (PRE), and Decoder.

**Encoder** The encoder module maps input node features into a \(d\)-dimensional representation vector, with an ad-hoc choice being an MLP. Note that for node features with additional structural patterns (i.e., sequence data), we may use a more tailored encoder architecture as long as it does not involve edge information. The encoder model is physically stored in party A.

**Private representation extractor** The PRE module takes its input the node embeddings produced by the encoder and a batch of \(B\) subgraphs produced by a neighborhood sampler. The output representation of PRE is computed using some specific type of PMP mechanism such as PMP-GIN or PMP-GCN. The PRE module is physically stored in party A. The output of PRE is a tensor of shape \(B\times d\times L\), with \(d\) and \(L\) being the dimension of graph representation and the number of message passing layers respectively. The outputs will be transmitted from party A to party B.

**Decoder** The decoder module is physically stored in party B, which decodes the received node embeddings produced by PRE into the final prediction of VESPER with its structure depending on the downstream tasks (i.e., classification, regression, ranking, etc.). We test two types of decoder architectures in our implementation of VESPER. The first one proceeds via concatenating the node embeddings of all layers followed by an MLP, which we call the CONCAT decoder. The second one treats the node embeddings as a sequence of \(L\) node embeddings and uses a GRU network to combine them, similar to the idea used in GNN architectures like GaAN [25] and GeniePath [30] which we term the GRU decoder.

The VFL training protocol closely resembles the SplitNN protocol [14], where in each step, forward computation results (i.e., the outputs of the PRE module) are transmitted from party A to party B. After party B finishes the forward computation using the decoded outputs and label information, party B first update its local decoder module via back-propagation, and then sends (partial) gradients that are intermediate results of the backward computation to party A for updating party A's local parameters (i.e., parameters of the encoder module and PRE module). A pictorial illustration of the VESPER architecture is presented in figure 1. We will discuss some practical issues in implementing VESPER in appendix E.1.

## 3 Experiments

In this section we present empirical evaluations of the VESPER framework via investigate its privacy-utility trade-off and resistance to empirical membership inference attacks. Due to limited space, a complete report will be postponed to appendix C.

### Datasets

We use three large-scale graph datasets, with their summary statistics listed in table 2. Specifically, we use two public datasets ogbn-products and Reddit, with their detailed descriptions postponed to appendix C.1. We additionally used an industrial dataset called **the Finance dataset** which is generated from transaction records collected from one of the world's leading online payment systems. The underlying graph is generated by treating users as nodes, and two nodes are connected if at least one transaction occurred between corresponding users within a predefined time period. The business goal is to identify risky users which is cast into an algorithmic problem of node classification with a binary label. The node features are obtained via statistical summaries of corresponding users' behavior on the platform during a specific time period. The training and testing datasets are constructed under two distinct time windows with no overlap.

**A differentially private analysis of degree profiles** While all three datasets are large in scale (i.e., with the number of nodes exceeding \(100,000\)), they differ significantly in their degree distributions. For a better illustration, we conduct a differentially private analysis of degree distribution (with \((0.1,0)\)-differential privacy) detailed in appendix C.2. According to the analysis, we find that both the ogbn-products and the Reddit contain a large portion of high-degree nodes (as illustrated by the spiking bar at the \(\geq 50\) category), while the Finance dataset exhibits a concentration on the lower-degree nodes. As discussed in section 2.2, it is expected that the Finance dataset is more challenging for (private) message passing under sum pooling.
### Baselines

We compare the proposed VESPER framework with three types of baselines, with each one being able to implement in the vertically federated setting. **MLP without edge information** we use MLP over node features directly is the most trivial solution to the learning task as it totally ignores edge information. **Non-private GNN counterparts** we compare with ordinary GCN and GIN models without privacy guarantees, or equivalently set the \(\epsilon\) parameter in the VESPER framework to be infinity. **GNN models with privacy guarantees** we consider two alternative approaches to private GRL, namely the VFGNN model [53] and the GAP model [39]. We found the privacy analysis in the corresponding papers to be somewhat incoherent with the privacy model in our paper and we conducted new analysis of their privacy properties, detailed in appendix C.3.

### Experimental setup

Due to limited space, we postpone the description of our training configurations to appendix C.4 and elaborate more on the **privacy configurations**: All the privacy reports are based on the \((\epsilon,\delta)\)-differential privacy model, with \(\delta\) being the reciprocal of the number of edges. To adequately inspect the privacy-utility trade-off, we aim to evaluate all the models with differential privacy guarantees under the total privacy costs (privacy budgets) \(\epsilon\in\{1,2,4,8,16,32\}\), with the privacy costs accounted during the entire training period. We treat the setting where \(\epsilon\in\{1,2\}\) as of _high privacy_, \(\epsilon\in\{4,8\}\) as of _moderate privacy_, and the rest as of _low privacy_. For VESPER and VFGNN, we add spectral normalization to each GNN layer. For the privacy accountant, we base our implementation upon AMA implementation available in the dp-accounting library and use an adjusted sampling probability according to theorem 2.1. For each required privacy level, we compute the minimum scale of Gaussian noise via conducting a binary search over the adjusted AMA, with associating spectral norms of weight matrices fixed at one in all layers.

**Evaluation metrics** We adopt classification accuracy (ACC) as the evaluation metric for the ogbn-products and Reddit datasets, and ROC-AUC score (AUC) as the evaluation metric for the Finance dataset.

\begin{table}
\begin{tabular}{l c c c} \hline \hline  & \multicolumn{3}{c}{Non-private approaches} \\ \hline Model & ogbn-products & Reddit & Finance \\ \hline MLP & \(61.66_{\text{softmax}}\) & \(71.67_{\text{softmax}}\) & \(71.39_{\text{softmax}}\) \\ GNN & \(78.54_{\text{softmax}}\) & \(94.85_{\text{softmax}}\) & \(79.75_{\text{softmax}}\) \\ GCN & \(78.25_{\text{softmax}}\) & \(94.56_{\text{softmax}}\) & \(80.13_{\text{softmax}}\) \\ \hline \hline Model & ogbn-products & \multicolumn{3}{c}{Reddit} \\ \hline \hline \end{tabular} 
\begin{tabular}{l c c c c c c c c c c c c} \hline \hline Model & ogbn-products & \multicolumn{3}{c}{Reddit} \\ \hline Model & ogbn-products
### Performance and privacy-utility trade-off

According to our empirical experience, obtaining reasonable performance in the _high privacy_ regime is difficult, especially for baseline algorithms. Therefore, we report two sets of results: Firstly, we thoroughly investigate the privacy-utility trade-off regarding the proposed VESPER framework under both GIN and GCN aggregation schemes and plot the results in figure 2. Secondly, we report comparisons of VESPER against private and non-private baselines with only moderate to large privacy budgets and summarize the results in table 1. The results demonstrate that the proposed VESPER framework exhibits competitive privacy-utility trade-off under both GIN and GCN aggregators. Moreover, a comparison of GIN and GCN aggregator suggests that summation pooling excels when the underlying graph is dense (i.e., ogbn-products and Reddit), while introducing the truncated message passing mechanism helps achieving better results over sparse graphs (i.e., Finance). Finally, VESPER demonstrates a better privacy-utility trade-off compared to other private GNN baselines.

### Protection against membership inference attacks

We launch a membership inference attack (MIA) [37] to empirically investigate the resilience of VESPER against practical privacy risks that targets the membership of nodes instead of edges, which is regarded as a stronger attack than edge MIA. We provide a detailed description of the attack setup in appendix C.7. The attack is conducted over trained models under privacy budgets \(\epsilon\in\{1,2,4,8,16,32,\infty\}\), where \(\epsilon=\infty\) indicated no privacy protection is adopted. We use ROC-AUC (AUC) to evaluate the attack performance. We report the attack performances in Figure 4. From the results, we observe that when privacy protection is disabled (\(\epsilon=\infty\)), the attacks show non-negligible effectiveness, especially on obgn-products and Reddit datasets. Generally, with the privacy budget getting smaller (privacy getting stronger), the attack performances sharply decline. With an appropriate privacy budget, the attacks on all three datasets are successfully defended with AUC reduced to around 0.5 (random guess baseline).

**Additional experiments** We will report a series of ablation studies that assess the effect of maximum degree \(D\), minimum degree \(D_{\text{min}}\) for PMP-GCN and batch size in appendix C.8.

## 4 Related Works

### Graph representation learning in the federated setting

The majority of GRL research in the federated setting is based on the horizontal setup, with each party holding its own local graph data [45; 17; 38]. The adoption of VFL paradigms to GRL is relatively few, VFGNN [53] uses additive secret sharing to combine feature information held by different parties, followed by a straightforward adaptation of the SplitNN framework [14] with the underlying neural model being graph neural networks. In [5; 46], the authors discussed VFL setups where node features and graph topology belong to different parties. We refer to the recent survey [27] for a more detailed overview.

### Graph representation learning with differential privacy guarantees

The most straightforward way to integrate DP techniques into GRL is via adopting private optimization algorithms like DP-SGD[1]. However, meaningful notions of differential privacy over graph data (i.e., the edge model [35] and node model [22]) are semantically different from that of i.i.d. data, and require refined privacy analysis which is sometimes ignored in the privacy analysis in previous works [53; 45; 36]. In [7], the authors analyzed the DP-SGD algorithm in the node DP model. The GAP model [39] proposed a three-stage training procedure and analyzed its privacy guarantee in both edge DP and node DP models. However, we noticed that the privacy analysis in [39] did not properly address the effect of sampling, resulting in an overly optimistic performance. Considering only edge DP, randomized response (RR) [46] that flips each entry of the underlying graph's adjacent matrix guarantees privacy (in a stronger _local_ sense), but makes reasonable privacy-utility trade-off extremely hard to obtain in practice.

## 5 Conclusion and discussions

We present the VESPER framework as a differentially private solution to node classification in the VFL setup using graph representation learning techniques. The core algorithmic component of VESPER is the PMP scheme that allows efficient learning under both dense and sparse graph
data. We demonstrate the practicality and effectiveness of the proposed framework by establishing theoretical DP guarantees as well as investigating its ability for privacy protection and privacy-utility trade-off empirically. We will discuss possible extensions and future directions of the VESPER framework in appendix D.
