Vertically Federated Graph Neural Network for Privacy-Preserving Node Classification

1 Introduction

Graph Neural Network (GNN) has gained increasing attentions from both academy and industry due to its ability to model high-dimensional feature information and high-order adjacent information on both homogeneous and heterogeneous graphs [Wu et al., 2019]. An important ingredient for high-performance GNN models is high-quality graph data including rich node features and complete adjacent information. However, in practice, such information could possibly be isolated by different data holders, which is the socalled data isolation problem. Such a data isolation problem Data holderA

∗Corresponding author

Data holderB

C

Figure 1: Problem description of vertically federated GNN.

presents a serious challenge for the development of Artificial Intelligence, which becomes a hot research topic recently.

Problem. Figure 1 shows a privacy-preserving node classification problem under vertically partitioned data setting. Here, we assume there are three data holders (A, B, and C) and they have four same nodes. The node features are vertically split, i.e., A has f1, f2, and f3, B has f4 and f5, and C has f6 and f7. Meanwhile, A, B, and C may have their own edges. For example, A has social relation between nodes while B and C have payment relation between nodes. We also assume A is the party who has the node labels. The problem is to build federated GNN models using the graph data of A, B, and C.

Related work. To date, many kinds of privacy-preserving machine learning models have been proposed, e.g., logistic regression [Chen et al., 2021], decision tree [Fang et al., 2021], and neural network [Wagh et al., 2019]. There are also several work on studying the privacy issues in GNN, e.g., graph publishing [Sajadmanesh and Gatica-Perez, 2020], GNN inference [He et al., 2020], and federated GNN when data are horizontally partitioned [Zheng et al., 2021; Wu et al., 2021]. Unlike previous privacy-preserving machine learning models that assume only samples (nodes) are held by different parties and they have no relationship, our task is more challenging because GNN relies on the relationships between samples, which are also private to data holders.

Naive solution. A direct way to build privacy-preserving GNN is employing advanced cryptographic algorithms, such as homomorphic encryption (HE) and secure multi party computation (MPC) [Mohassel and Zhang, 2017]. Such a pure cryptographic way can provide high security guarantees, however, it suffers high computation and communication costs, which limits their efficiency [Osia et al., 2019].

Our solution. We propose VFGNN, a vertically federated GNN learning paradigm for privacy-preserving node classification task. Motivated by the existing work in split learning [Vepakomma et al., 2018; Osia et al., 2019; Gu et al., 2018], we split the computation graph of GNN into two parts for privacy and efficiency concern, i.e., the private data related computations carried out by data holders and non-private data related computations conducted by a semi-honest server. Specifically, data holders first apply MPC techniques to compute the initial layer of the GNN using private node feature information collaboratively, which acts as the feature extractor module, and then perform neighborhood aggregation using private edge information individually, similar as the existing GNNs [Veliˇckovi´c et al., 2017], and finally get the local node embeddings. Next, we propose different combination strategies for a semi-honest server to combine local node embeddings from data holders and generate global node embeddings, based on which the server can conduct the successive non-private data related computations, e.g., the non-linear operations in deep network structures that are time-consuming for MPC techniques. Finally, the server returns the final hidden layer to the party who has labels to compute prediction and loss. Data holders and the server perform forward and back propagations to complete model training and prediction, during which the private data (i.e., features, edges, and labels) are always kept by data holders themselves. Moreover, we adopt differential privacy, on the exchanged information between server and data holders, to further protect potential information leakage from the server.

Contributions. We summarize our main contributions as:

• We propose a novel VFGNN learning paradigm, which not only can be generalized to most existing GNNs, but also enjoys good accuracy and efficiency.
• We propose different combination strategies for the server to combine local node embeddings from data holders.
• We evaluate our proposals on three real-world datasets, and the results demonstrate the effectiveness of VFGNN.

2 Preliminaries

2.1 SecurityModel

In this paper, we assume the adversary is honest-but-curious (semi-honest). That is, data holders and the server strictly follow the protocol, but they also use all intermediate computation results to infer as much information as possible. We also assume that the server does not collude with any data holders. This security setting is similar as most existing work [Mohassel and Zhang, 2017; Hardy et al., 2017].

2.2 Additive Secret Sharing

Additive Secret Sharing has two main procedures [Shamir, 1979]. To additively share Shr(·) an ℓ-bit value a for party i ∈ P = {1, ..., I}, party i generates {aj ∈ Z2ℓ , j ∈ P and j ̸= i} uniformly at random, sends aj to party j, and keeps ai = a-∑j aj mod 2ℓ . We use 〈a〉i = ai to denote the share of party i. To reconstruct Rec(·, ·) a shared value 〈a〉, each party i sends 〈a〉i to one who computes ∑i ai mod 2ℓ . For simplification, we denote additive sharing by 〈·〉. Addition in secret sharing can be done by participants locally. Multiplication in secret sharing usually relies on Beaver's triplet technique [Beaver, 1991].

2.3 Differential Privacy

Definition 1. (Differential Privacy [Dwork et al., 2014]). A randomized algorithmM that takes as input a dataset consisting of individuals is (ϵ, δ)-differentially private (DP) if for any pair of neighbouring data x, y that differ in a single entry, and any event E,

and if δ = 0, we say that M is ϵ-differentially private.

In [Dwork et al., 2014], the authors pointed out that the ℓ2-sensitivity of a function f measures the magnitude by which a single individual's data can change the function in the worst case.

Definition 2. (ℓ2-sensitivity [Dwork et al., 2014]). Suppose x and y are neighbouring inputs that differ in one entry. The ℓ2-sensitivity of a function f : D→Rd is:

Definition 3. (The Gaussian Mechanism [Dwork et al., 2014]) Given a function f : D → Rd over a dataset D, the Gaussian mechanism is defined as:

where Yi are i.i.d. random variables drawn from N(0, σ2∆2f 2 ) and σ = √2 ln(1.25/δ) ϵ .

Theorem 1. [Dwork et al., 2014] The Gaussian mechanism defined in Definition 3 preserves (ϵ, δ)-DP for each publication step.

3 The ProposedModel

3.1 Overview of VFGNN

As described in Section 1, for the sake of privacy and efficiency, we design a vertically federated GNN (VFGNN) learning paradigm by splitting the computational graph of GNN into two parts. That is, we keep the private data related computations to data holders for privacy concern, and delegate the non-private data related computations to a semihonest server for efficiency concern. In the context of GNN, the private data refers to node features, labels, and edges (node relations). To be specific, we divide the computational graph into the following three sub-Computational Graphs (CG), as is shown in Figure 2.

CG1: private feature and edge related computations. The first step of GNN is generating initial node embeddings using node's private features, e.g., user features in social networks. In vertically data split setting, each data holder has partial node features, as shown in Figure 1. We will present how data holders collaboratively learn initial node embeddings later. In the next step, data holders generate local node embeddings by aggregating multi-hop neighbors' information using different aggregator functions.

CG2: non-private data related computations. We delegate non-private data related computations to a semi-honest server for efficiency concern. First, the server combines the local node embeddings from data holders with different COMBINE strategies, and obtains the global node embeddings. Next, the server can perform the successive computations using plaintext data. Note that this part has many non-linear computations such as max-pooling and activation functions, which are not cryptographically friendly and need to be approximated [Mohassel and Zhang, 2017; Hardy et al., 2017]. Delegating these plaintext computations to server will not only improve our model accuracy, but also significantly improve our model efficiency. After this, the server gets a final hidden layer (zL) and sends it back to the data holder who has label to calculate the prediction, where L is the total number of layers of the deep neural network.

CG3: private label related computations. The data holder who has label can compute prediction using the final hidden layer it receives from the server. For node classification task, the Softmax activation function is used for the output layer [Kipf and Welling, 2016], which is defined as softmax(zc) = 1Z exp(zc) with c ∈ C be the node class and Z = ∑c exp(zc). In the following subsections, we will describe three impor-

tant components of VFGNN.

3.2 Generate Initial Node Embeddings

Initial node embeddings are generated by using node features. Under vertically partitioned data setting, each data holder has partial node features. There are two methods for data holders to generate initial node embeddings, i.e., individually and collaboratively, as shown in Figure 3.

The 'individually' method means that data holders generate initial node embeddings using their own node features, individually. For data holder i ∈ P, this can be done by hi0 = (xi )T · Wi , where xi and Wi are node features and weight matrix of data holder i. As the example in Figure 3 (a), A, B, and C generate their initial node embeddings using their own features separately. Although this method is simple and data holders do not need to communicate with each other, it cannot capture the relationship between features of data holders and thus causes information loss.

To solve the shortcoming of 'individually' method, we propose a 'collaboratively' method. It indicates that data holders generate initial node embeddings using their node features, collaboratively, and meanwhile keep their private features secure. Technically, this can be done by using cryptographic methods such as secret sharing and homomorphic encryption [Acar et al., 2018]. In this paper, we choose additive secret sharing due to its high efficiency.

3.3 Generate Local Node Embeddings

We generate local node embeddings by using multi-hop neighborhood aggregation on graphs, based on initial node embeddings. Note that, neighborhood aggregation should be done by data holders separately, rather than cooperatively, to protect the private edge information. This is because one may infer the neighboorhoold information of v given the neighborhood aggregation results of k-hop (hkv (i)) and k + 1-hop (hk+1 v (i)), if neighborhood aggregation is done by data holders jointly. For ∀v ∈ V at each data holder, neighborhood aggregation is the same as the traditional GNN. Take GraphSAGE [Hamilton et al., 2017] for example, it introduces aggregator functions to update hidden embeddings by sampling and aggregating features from a node's local neighborhood:

where we follow the same notations as GraphSAGE, and the aggregator functions AGG are of three types, i.e., Mean, LSTM, and Pooling. After it, data holders send local node embeddings to a semi-honest server for combination and further non-private data related computations.

3.4 Generate Global Node Embeddings

The server combines the local node embeddings from data holders and gets global node embeddings. The combination strategy (COMBINE) should be trainable and maintaining high representational capacity, and we design three of them.

Concat. The concat operator can fully preserve local node embeddings learnt from different data holders. That is, Line 14 in Algorithm 2 becomes

Algorithm 1 Information publishing mechanisms of data holders to server using differential privacy

Input: Local information of data holders x, dimension of local information d, noise multiplier σ, clipping value C. Output: Differentially private node embeddings.

• 1: Scale local information ¯x =min(1,C/‖x‖)x;
• 2: Draw i.i.d. samples from N(0, σ2C 2 ), which forms a d-dimension noise vector n;
• 3: # GaussianMechanism
• 4: Add noise ˜x = xK + n;
• 5: # James-Stein Estimator
• 6: Compute James-Stein Estimator

• 7: return ˜x or ˜xJS.

Mean. The mean operator takes the elementwise mean of the vectors in ({hKv (i), ∀i ∈ P}), assuming data holders contribute equally to the global node embeddings, i.e.,

Regression. The above two strategies treat data holders equally. In reality, the local node embeddings from different data holder may contribute diversely to the global node embeddings. We propose a Regression strategy to handle this kind of situation. Let ωi be the weight vector of local node embeddings from data holder i ∈ P, then

where ⊙ is element-wise multiplication.

These different combination operators can utilize local node embeddings in diverse ways, and we will empirically study their effects on model performances in experiments.

3.5 Enhancing Privacy by Adopting DP

Data holders directly send the local information, e.g., local node embeddings during forward propagation and gradient update during back propagation, to the server may cause potential information leakage [Lyu et al., 2020], and we propose to apply differential privacy to further enhance privacy. In this section, we introduce two DP based data publishing mechanisms, to further enhance the privacy of our proposed VFGNN. Such that with a single entry modification in the local information of data holders, there is a large probability that the server cannot distinguish the difference before or after the modification. We present the two mechanisms, i.e., Gaussian Mechanism and James-Stein Estimator, in Algorithm 1. We have described Gaussian mechanism in Section 2.3, we present James-Stein Estimator as follows.

Theorem2. (James-Stein Estimator and its adaptivity [Balle and Wang, 2018]). Suppose d is the dimension of local information x. When d ≥ 3, substituting w in ˜xBayes with its maximum likelihood estimate under x ∼ N(0,w2 I), ˜x|x ∼ N(x, σ2C 2 I), and ˜xBayes = argmin˜x‖˜x - x‖2 produces James-Stein Estimator ˜xJS = (1 - (d-2)σ2C2 ‖˜x‖2 ) ˜x. Moreover, it has an Mean Squared Error (MSE) of

The MSE of Gaussian Mechanism ˜x to exact x is E‖˜x - x‖2 = dσ2C 2 , while the MSE of James-Stein Estimator is reduced with a factor of (1 - (d-2)2 d2 σ2C2 w2+σ2C2 ). Both methods preserve (ϵ, δ)-DP while James-Stein estimator shows reductions in MSE, thus improves utility. By the definition of Gaussian mechanism (Definition 3), we have the privacy loss for both information publishing mechanisms in Algorithm 1. By combining it with Moment Accountant (MA) [Abadi et al., 2016], we present the overall privacy for T iterations.

Theorem 3. Suppose each iteration of Algorithm 1 is (ϵ, δ)-DP. There exist constants c1 and c2 so that given the sampling probability q and the number of iterations T, and ϵ < c1q√T , Algorithm 1 over T iteration is (ϵ′ , δ)-DP, with ϵ′ = c2q√Tϵ.

Proof. By Definition 3 and Theorem 1, to ensure one iteration (ϵ, δ)-DP, we set σ = √2 ln(1.25/δ) ϵ . By Theorem 1 in [Abadi et al., 2016], with σ = √2 ln(1.25/δ) ϵ and the appropriate choice of ϵ, q, T, such that ϵ < c1q√T, the privacy loss over T iterations is ϵ′ = c1q√T log(1/δ) σ = c2q√Tϵ.

3.6 Putting Together

By combining CG1-CG3, we complete the forward propagation of VFGNN. To describe the procedures in details, without loss of generality, we take GraphSAGE [Hamilton et al., 2017] for example and present its forward propagation process in Algorithm 2. VFGNN can be learnt by gradient descent through minimizing the cross-entropy error over all labeled training examples. As can be seen, in VFGNN, both private data and model are hold by data holders themselves, thus data privacy can be better guaranteed.

4 Experiments

We conduct experiments to answer the following questions. Q1: whether VFGNN outperforms the GNN models that are trained on the isolated data. Q2: how does VFGNN behave comparing with the traditional insecure model trained on the plaintext mixed data. Q3: how does VFGNN perform comparing with the naive solution in Section 1. Q4: are our proposed combination strategies effective to VFGNN. Q5: what is the effect of the number of data holders on VFGNN. Q6: what is the effect of differential privacy on VFGNN.

4.1 Experimental Setup

Datasets. We use four benchmark datasets, i.e., Cora, Pubmed, Citeseer [Sen et al., 2008], and arXiv [Hu et al., 2020]. We use exactly the same dataset partition of training, validate, and test following the prior work [Kipf and Welling, 2016; Hu et al., 2020]. Besides, in data isolated GNN setting, both node features and edges are hold by different parties. For all the experiments, we use five-fold cross validation and adopt average accuracy as the evaluation metric.

Comparison methods. We compare VFGNN with GraphSAGE models [Hamilton et al., 2017] that are trained using isolated data and mixed plaintext data to answer Q1 and Q2.

Algorithm 2 Privacy-preserving GraphSAGE for node label prediction (forward propagation)

Input: Data holder ∀i ∈ P; Graph G(V, E i ) and node features {xiv , ∀v ∈ V}; depth K; aggregator functions AGGk, ∀k ∈ {1, ...,K}; weight matrices Wki , ∀k ∈ {1, ...,K}; max layer L; weight matrices Wl, ∀l ∈ {0, ...,L}; non-linearity σ; neighborhood functions N i : v → 2V ; node labels on data holder p ∈ P and c ∈ C Output: Node label predictions {ˆ yvc, ∀v ∈ V, ∀c ∈ C}

• 1: # CG1: private feature and edge related computations
• 2: Data holders: jointly calculate initial node embeddings h0v (i) ← xiv , ∀i ∈ P, ∀v ∈ V
• 4: for k = 1 to K do
• 3: for i ∈ P in parallel do
• 5: for v ∈ V do
• 7: end for
• 6: Data holder: calculates hkN(v) (i) ← AGGk({hk-1 u (i), ∀u ∈ N i (v)})
• 8: Data holder: calculates hkv (i) ← σ(Wki · CONCAT (hk-1 v (i), hkN(v) (i))
• 9: end for
• 10: Data holder: calculates local node embeddings hKv (i) ← hKv (i)/||hKv (i)||2, ∀v ∈ V and sends (publishes) it to server using differential privacy
• 11: end for
• 12: # CG2: non-private data related computations
• 13: for v ∈ V do
• 15: Server: forward propagation based on the global node embeddings zL = σ(WL-1 · σ(...σ(W0 · hKv )))
• 14: Server: combines the local node embeddings from data holders hKv =COMBINE ({hKv (i), ∀i ∈ P})
• 16: Server: sends zL to data holder p
• 17: end for
• 18: # CG3: private label related computations
• 19: Data holder p: makes prediction by ˆ yvc ← softmax(WL · zL), ∀v ∈ V, ∀c ∈ C

We also compare VFGNN with the naive solution described in Section 1 to answer Q3. To answer Q4, we vary the proportion of the data (features and edges) hold by A and B, and change VFGNN with different combination strategies. We vary the number of data holders in VFGNN to answer Q5, and vary the parameters of differential privacy to answer Q6. For all these models, we choose Mean operator as the aggregator function.

Parameter settings. For all the models, we use TanH as the active function of neighbor propagation, and Sigmoid as the active function of hidden layers. For the deep neural network on server, we set the dropout rate to 0.5 and network structure as (d, d, |C|), where d ∈ {32, 64, 128} is the dimension of node embeddings and |C| the nubmer of classes. We vary ϵ ∈ {1, 2, 4, 8, 16, 32, 64,∞}, set δ = 1e-4 and the clip value C = 1 to study the effects of differential privacy on our model. Since we have many comparison and ablation models, and they achieve the best performance with different parameters, we cannot report all the best parameters. Instead, we report the range of the best parameters. We vary the propagation depth K ∈ {2, 3, 4, 5}, L2 regularization in {10-2 -10-4 }, and learning rate in {10-2 -10-3 }. We tune parameters based on the validate dataset and evaluate model performance on the test dataset.

4.2 Comparison Results and Analysis

To answer Q1-Q3, we assume there are two data holders (A and B) who have equal number of node features and edges, i.e., the proportion of data held by A and B is 5:5, and compare our models with GraphSAGEs that are trained on isolated data individually and on mixed plaintext data. We also set ϵ = ∞ during comparison and will study its effects later. We summarize the results in Table 2, where VFGNN C, VFGNN M, and VFGNN R denote VFGNN with Concat, Mean, and Regression combination strategies.

Result1: answer to Q1. We first compare VFGNNs with the GraphSAGEs that are trained on isolated feature and edge data, i.e., GraphSAGEA and GraphSAGEB. From Table 2, we find that, VFGNNs with different combination strategies significantly outperforms GraphSAGEA and GraphSAGEB on all the three datasets. Take Citeseer for example, our VFGNN R improves GraphSAGEA and GraphSAGEB by as high as 28.10% and 51.64%, in terms of accuracy.

Analysis of Result1. The reason of result1 is straightforward. GraphSAGEA and GraphSAGEB can only use partial feature and edge information held by A and B. In contrast, VFGNNs provide a solution for A and B to jointly train GNNs without compromising their own data. By doing this, VFGNNs can use the information from the data of both A and B simultaneously, and therefore achieve better performance.

Result2: answer to Q2. We then compare VFGNNs with GraphSAGE that is trained on the mixed plaintext data, i.e., GraphSAGEA+B. It can be seen from Table 2 that VFGNNs have comparable performance with GraphSAGEA+B, e.g., 0.8090 vs. 0.8150 on Cora dataset and 0.6950 vs. 0.7001 on Citeseer dataset.

Analysis of Result2. It is easy to explain why our proposal has comparable performance with the model that are trained on the mixed plaintext data. First, we propose a secret sharing based protocol for A and B to generate the initial node embeddings from their node features, which are the same as those generated by using mixed plaintext features. Second, although A and B generate local node embeddings by using their own edge data to do neighbor aggregation separately (for security concern), we propose different combination strategies to combine their local node embeddings. Eventually, the edge information from both A and B is used for training the classification model. Therefore, VFGNN achieves comparable performance with GraphSAGEA+B.

Result3: answer to Q3. In VFGNN, we delegate the nonprivate data related computations to server. One would be curious about what if these computations are also performed by data holders using existing secure neural network protocols, i.e., SecureML [Mohassel and Zhang, 2017]. To answer this question, we compare VFGNN with the secure GNN model that is implemented using SecureML, which we call as SecureGNN, where we use 3-degree Taylor expansion to approximate TanH and Sigmoid. The accuracy and running time per epoch (in seconds) of VFGNN vs. SecureGNN on Pubmed are 0.8090 vs. 0.7970 and 18.65 vs. 166.81, respectively, where we use local area network.

Analysis of Result3. From the above comparison results, we find that our proposed VFGNN learning paradigm not only achieves better accuracy, but also has much better efficiency. This is because the non-private data related computations involve many non-linear functions that are not cryptographically friendly, which have to be approximately calculated using time-consuming MPC techniques in SecureML.

4.3 Ablation Study

We now study the effects of different combination operators and different number of data holders on VFGNN.

Result4: answer to Q4. Different combination operators can utilize local node embeddings in diverse ways and make our proposed VFGNN adaptable to different scenarios, we study this by varying the proportion (Prop.) of data (node features and edges) hold by A and B in {9: 1, 8: 2, 7: 3}. The results on Cora dataset are shown in Table 3.

Analysis of Result4. From Table 3, we find that with the proportion of data hold by A and B being even, i.e., from {9: 1} to {7: 3}, the performances of most strategies tend to decrease. This is because the neighbor aggregation is done by data holders individually, and with a bigger proportion of data hold by a single holder, it is easier for this party to generate better local node embeddings. Moreover, we also find that Mean operator works well when data are evenly split, and Regression operator is good at handling the situations where data holders have different quatity of data, since it treats the local node embeddings from each data holder differently, and assigns weights to them intelligently.

Result5: answer to Q5. We vary the number of data holders in {2, 3, 4} and study the performance of VFGNN. We report the results in Table 4, where we use the Cora dataset and assume data holders have even feature and edge data.

Analysis of Result5. From Table 4, we find that, as the number of data holders increases, the accuracy of all the models decreases. This is because the neighborhood aggregation in VFGNN is done by each holder individually for privacy concern, and each data holder will have less edge data when there are more data holders, since they split the original edge information evenly. Therefore, when more participants are involved, more information will be lost during the neighborhood aggregation procedure.

Result6: answer to Q6. We present the privacy loss of each iteration in Table 5 and the over all privacy in Theorem 3. We vary ϵ and set δ = 1e-4 to study the effects of DP on VFGNN. We report the results in Table 5, where we use Cora dataset, use MEAN as the combination operator, and assume data holders have even feature and edge data.

Analysis of Result6. From Table 5, we can see that the accuracy of VFGNN increases with ϵ. In other words, there is a trade-off between accuracy and privacy. The smaller ϵ, the more noise will be added into the local node embeddings, which causes stronger privacy guarantee but lower accuracy. We also find James-Stein estimator consistently works better than Gaussian mechanism, since it can reduce MSE, as we have analyzed in Section 3.5.

5 Conclusion

We propose VFGNN, a vertically federated GNN learning paradigm for privacy-preserving node classification task. We finish this by splitting the computation graph of GNN. We leave the private data related computations on data holders and delegate the rest computations to a server. Experiments on real world datasets demonstrate that our model significantly outperforms the GNNs by using the isolated data and has comparable performance with the traditional GNN by using the mixed plaintext data insecurely.

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China (No. 62172362) and "Leading Goose" R&D Program of Zhejiang (No. 2022C01126).