Vertical Federated Graph Neural Network for Recommender System
Conventional recommender systems are required to train the recommendation
model using a centralized database. However, due to data privacy concerns, this
is often impractical when multi-parties are involved in recommender system
training. Federated learning appears as an excellent solution to the data
isolation and privacy problem. Recently, Graph neural network (GNN) is becoming
a promising approach for federated recommender systems. However, a key
challenge is to conduct embedding propagation while preserving the privacy of
the graph structure. Few studies have been conducted on the federated GNN-based
recommender system. Our study proposes the first vertical federated GNN-based
recommender system, called VerFedGNN. We design a framework to transmit: (i)
the summation of neighbor embeddings using random projection, and (ii)
gradients of public parameter perturbed by ternary quantization mechanism.
Empirical studies show that VerFedGNN has competitive prediction accuracy with
existing privacy preserving GNN frameworks while enhanced privacy protection
for users' interaction information.
Peihua Mai, Yan Pang
# Vertical Federated Graph Neural Network for Recommender System

###### Abstract

Conventional recommender systems are required to train the recommendation model using a centralized database. However, due to data privacy concerns, this is often impractical when multi-parties are involved in recommender system training. Federated learning appears as an excellent solution to the data isolation and privacy problem. Recently, Graph neural network (GNN) is becoming a promising approach for federated recommender systems. However, a key challenge is to conduct embedding propagation while preserving the privacy of the graph structure. Few studies have been conducted on the federated GNN-based recommender system. Our study proposes the first vertical federated GNN-based recommender system, called VerFedGNN. We design a framework to transmit: (i) the summation of neighbor embeddings using random projection, and (ii) gradients of public parameter perturbed by ternary quantization mechanism. Empirical studies show that VerFedGNN has competitive prediction accuracy with existing privacy preserving GNN frameworks while enhanced privacy protection for users' interaction information.

Machine Learning, ICML

## 1 Introduction

Graph neural network (GNN) has become a new state-of-art approach for recommender systems. The core idea behind GNN is an information propagation mechanism, i.e., to iteratively aggregate feature information from neighbors in graphs. The neighborhood aggregation mechanism enables GNN to model the correlation among users, items, and related features. Compared with traditional supervised learning algorithms, GNN can model high-order connectivity through multiple layers of embedding propagation and thus capture the similarity of interacted users and items (Gao et al., 2022). Besides, the GNN-based model can effectively alleviate the problem of data sparsity by encoding semi-supervised signals over the graph (Jin et al., 2020). Benefiting from the above features, GNN-based models have shown promising results and outperformed previous methods on the public benchmark datasets (Berg et al., 2017; Wang et al., 2019;a).

Instead of training the model based on their own graphs, organizations could significantly improve the performance of their recommendation by sharing their user-item interaction data. However, such sharing might be restricted by commercial competition or privacy concerns, leading to the problem of data isolation. For example, the data protection agreement might prohibit the vendors from transferring users' personal data, including their purchase and clicking records, to a third party.

Federated learning (FL), a machine learning setting with data distributed in multiple clients, is a potential solution to the data isolation problem. It enables multiple parties to collaboratively train a model without sharing their local data (Peyre et al., 2019). A challenge in designing the federated GNN-based recommender system is how to perform neighborhood aggregation while keeping the graph topology information private. Indeed, each client should obtain the items their users have interacted with in other organizations to conduct embedding propagation. However, the user interaction data are supposed to keep confidential in each party, adding to the difficulty of federated implementation.

Few studies have been conducted on the federated implementation of GNN-based recommender systems. To our best knowledge, FedPerGNN is the first federated GNN-based recommender system on user-item graphs (Wu et al., 2022). However, their work considers a horizontal federated setting where each client shares the same items but with different users. This paper studies the vertical federated setting in which multiple collaborating recommenders offer different items to the same set of users. In addition, FedPerGNN expands the local user-item graphs with anonymous neighbouring user nodes to perform embedding propagation, which could leak users' interaction information (see Section 4.1).

To fill the gap, this paper proposes a vertical federated learning framework for the GNN-based recommender system
(VerFedGNN)1. Our method transmits (i) the neighbor embedding aggregation reduced by random projection, and (ii) gradients of public parameter perturbed by ternary quantization mechanism. The privacy analysis suggests that our approach could protect users' interaction data while leveraging the relation information from different parties. The empirical analysis demonstrates that VerFedGNN significantly enhance privacy protection for cross-graph interaction compared with existing privacy preserving GNN frameworks while maintaining competitive prediction accuracy.

Footnote 1: Source code: [https://github.com/maiph123/VerticalGNN](https://github.com/maiph123/VerticalGNN)

Our main contributions involves the following:

* To the best of our knowledge, we are the first to study the GNN-based recommender system in vertical federated learning. We also provide a rigorous theoretical analysis of the privacy protection and communication cost. The experiment results show that the performance of our proposed federated algorithm is comparable to that in a centralized setting.
* We design a method to communicate projected neighborhood aggregation and quantization-based gradients for embedding propagation across subgraphs. Our method outperforms existing framework in terms of accuracy and privacy. The proposed framework could be generalized to the horizontal federated setting.
* We propose a de-anonymization attack against existing federated GNN framework that infers cross-graph interaction data. The attack is simulated to evaluate its performance against different privacy preserving GNN approaches.

## 2 Literature Review

**Graph Neural Network (GNN) for Recommendation:** There has been a surge of studies on designing GNN-based recommender systems in recent years. Graph convolutional matrix completion (GC-MC) employs a graph auto-encoder to model the direct interaction between users and items (Berg et al., 2017). To model high-order user-item connectivities, neural graph collaborative filtering (NGCF) stacks multiple embedding propagation layers that aggregate embeddings from neighbouring nodes (Wang et al., 2019). LightGCN simplifies the design of NGCF by demonstrating that two operations, feature transformation and nonlinear activation, are redundant in the GCN model (He et al., 2020). PinSage develops an industrial application of GCN-based recommender systems for Pinterest image recommendation (Ying et al., 2018). To achieve high scalability, it samples a neighborhood of nodes based on a random walk and performs localized aggregation for the node.

**Federated Graph Neural Network:** Recent research has made progress in federated graph neural network. Most of the work either performs neighborhood aggregation individually (Zhou et al., 2020; Liu et al., 2021), or assumes that the graph topology could be shared to other parties (Chen et al., 2021). It's a non-trivial task to incorporate the cross-client connection while preserving the relation information between nodes. To protect the graph topology information, a direct method is to apply differential privacy on the adjacency matrix (Zhang et al., 2021), which requires a tradeoff between privacy protection and model performance. In FedSage+, a missing neighbour generator is trained to mend the local subgraph with generated cross-subgraph neighbors (Zhang et al., 2021). To our best knowledge, FedPerGNN is the first work that develops horizontal federated GNN-based recommender system with user-item graphs (Wu et al., 2022). Each client expands the local user-item graphs with anonymous neighbouring user node to learn high-order interaction information.

This paper considers the unexplored area, i.e., graph learning for recommender systems in a vertical federated setting. We show that applying local graph expansion could leak user interaction information from other parties, and develop a GNN-based recommender system that leverages the neighbourhood information across different subgraphs in a privacy-preserving way.

## 3 Problem Formulation and Background

### Problem Statement

We assume that \(P\) parties collaboratively train a recommender system, where each party holds a set of common users but non-overlapping items. Denote \(\mathcal{U}=\{u_{1},u_{2},...,u_{N}\}\) as the set of common users and \(\mathcal{V}_{p}=\{v_{1},v_{2},...,v_{M_{p}}\}\) as the set of items for party \(p\). The total item size \(M_{p}\), \(p\in[1,P]\) is shared across parties. Assume that user \(u\) has \(N_{u}\) neighboring items \(\mathcal{N}(u)=\{v_{1},v_{2},...,v_{N_{u}}\}\), and item \(v\) has \(N_{v}\) neighboring users \(\mathcal{N}(v)=\{u_{1},u_{2},...,u_{N_{v}}\}\). Denote \(\mathcal{N}_{p}(u)=\{v_{1},v_{2},...,v_{N_{v}^{n}}\}\) as the neighboring items for user \(u\) in party \(p\). The related items and users form a local subgraph \(\mathcal{G}_{p}\) in party \(p\). Denote \(r_{uv}\) as the rating user \(u\) gives to item \(v\). Our objective is to generate a rating prediction that minimizes the squared discrepancy between actual ratings and estimate.

### Graph Neural Network (GNN)

**General Framework:** We adopt a general GNN (Wu et al., 2022) framework as the underlying model for our recommender system. In the initial step, each user and item is offered an ID embedding of size \(D\), denoted by \(e_{u}^{0},e_{v}^{0}\in R^{D}\) respectively. The embeddings are passed through \(K\) mes
age propagation layers:

\[\begin{split} n_{u}^{k}&=Agg_{k}(\{e_{v}^{k},\forall v \in\mathcal{N}(u)\})\\ e_{u}^{k+1}&=Update_{k}(e_{u}^{k},n_{u}^{k})\\ n_{v}^{k}&=Agg_{k}(\{e_{u}^{k},\forall u\in\mathcal{ N}(v)\})\\ e_{v}^{k+1}&=Update_{k}(e_{v}^{k},n_{v}^{k})\end{split} \tag{1}\]

where \(e_{u}^{k}\) and \(e_{v}^{k}\) denote the embeddings at the \(k^{th}\) layer for user \(u\) and item \(v\), and \(Agg_{k}\) and \(Update_{k}\) represent the aggregation and update operations, respectively. The final representation for users (items) are given by the combination of embeddings at each layer:

\[\begin{split} h_{u}&=\sum_{k=0}^{K}a_{k}e_{u}^{k}; \ h_{v}=\sum_{k=0}^{K}a_{k}e_{v}^{k}\end{split} \tag{3}\]

where \(h_{u}\) and \(h_{v}\) denote the final representation for user \(u\) and item \(v\) respectively, \(K\) denotes the number of embedding propagation layers, and \(a_{k}\) denotes the trainable parameter implying the weight of each layer.

The rating prediction is defined as the inner product of user and item representation

\[\begin{split}\hat{r}_{uv}&=h_{u}^{T}h_{v}\end{split} \tag{4}\]

The loss function is computed as:

\[\begin{split}\mathcal{L}&=\sum_{(u,v)}(\hat{r}_{uv }-r_{uv})^{2}+\frac{1}{N}\sum_{u}\|e_{u}^{0}\|_{2}^{2}+\frac{1}{M}\sum_{v}\|e_ {v}^{0}\|_{2}^{2}\end{split} \tag{5}\]

where \((u,v)\) denotes pair of interacted user and item, and \(N\) and \(M\) denote the number of users and items respectively.

**Aggregation and Update Operations:** This paper discusses three typical GNN frameworks: Graph convolutional network (GCN) (Kipf and Welling, 2016), graph attention networks (GAT) (Velickovic et al., 2017), and gated graph neural network (GGNN) (Li et al., 2015). We illustrate their aggregation and update operations for user embedding as an example.

* **GCN** approximates the eigendecomposition of graph Laplacian with layer-wise propagation rule: \[\begin{split} Agg_{k}:&\ n_{u}^{k}=\sum_{v\in \mathcal{N}(u)}\frac{1}{\sqrt{N_{u}N_{v}}}e_{v}^{k}\\ Update_{k}:&\ e_{u}^{k+1}=\sigma(W^{k}(e_{u}^{k}+n_{u}^{k})) \end{split}\] (6)
* **GAT** leverages self-attention layers to assign different importances to neighboring nodes: \[\begin{split} Agg_{k}:&\ n_{u}^{k}=\sum_{v\in \mathcal{N}(u)}b_{uv}^{k}e_{v}^{k}\\ Update_{k}:&\ e_{u}^{k+1}=\sigma(W^{k}(b_{uu}^{k}e_{u}^{k} +n_{u}^{k}))\end{split}\] (7) where \(b_{uu}^{k}\) and \(b_{uv}^{k}\) are the importance coefficients computed by the attention mechanism: \[\begin{split} b_{uv}^{k}&=\frac{exp(\tilde{b}_{uv}^{k })}{\sum_{v^{\prime}\in\mathcal{N}(u)\cup u}exp(\tilde{b}_{uv^{\prime}}^{k})} \end{split}\] (8) where \(b_{uv}^{k}=Att(e_{u}^{k},e_{v}^{k})\) is computed by an attention function.
* **GGNN** updates the embeddings with a gated recurrent unit (GRU): \[\begin{split} Agg_{k}:&\ n_{u}^{k}=\sum_{v\in \mathcal{N}(u)}\frac{1}{N_{u}}e_{v}^{k}\\ Update_{k}:&\ e_{u}^{k+1}=GRU(e_{u}^{k},n_{u}^{k}) \end{split}\] (9)

### Differential Privacy

We adopt the standard definition of \((\epsilon,\delta)\)-differential privacy (Dwork et al., 2014) for our analysis.

**Definition 3.1**.: A randomized function \(M(x)\) is \((\epsilon,\delta)\)-differentially private if for all \(x\), \(y\) such that \(\|x-y\|_{1}\leq 1\) and any measurable subset \(S\subseteq\text{Range}(M)\),

\[\begin{split} P(M(x)\in S)\leq e^{\epsilon}P(M(y)\in S)+\delta \end{split} \tag{10}\]

This paper assumes an untrusted server and requires that the local gradients from each party satisfy \((\epsilon,\delta)\)-local differential privacy (Duchi et al., 2013).

## 4 Proposed Method

### De-anonymization Attack

A straightforward cross-graph propagation solution is to use anonymous neighborhood embeddings from other graphs (Wu et al., 2022). Adapting to the vertical setting, each party sends the encrypted ids of each item's related users to the server, and the server provides each party with the embeddings of their neighboring items via user matching.

One privacy concern of this approach suffers leakage of interaction information, as is shown by the de-anonymization attack below. We assume that each organization is accessible to the set of available items from other parties.

Suppose that party A wants to obtain their users' interaction with party B. Party A could create a set of adversarial users that have registered on other platforms. Each fake user rates only one item in party B. The interaction information could be recovered by matching the embeddings for adversarial and honest users. Denote \(v_{i}\in\mathcal{N}(u)\) as the \(i^{th}\) item in user \(u\)'s neighborhood from party B, \(\mathcal{N}_{adv}\) as the set of items given by all fake users, and \(v_{j}\in\mathcal{N}_{adv}\) as the item rated by \(j^{th}\) adversarial user. The inferred \(i^{th}\) item for user \(u\) is:

\[\begin{split}\hat{v}_{i}&=\arg\min_{v^{\prime}\in \mathcal{N}_{adv}}\|e_{v}^{\prime 0}-e_{v_{i}}^{0}\|_{1}\end{split} \tag{11}\]
where \(\|\cdot\|\) computes the \(l_{1}\)-norm of inner vectors.

The above attack suggest that revealing the individual embedding for each item is susceptible to privacy leakage. Following, we introduce a new method to obtain embeddings at the aggregated level.

### Federated Graph Neural Network

In the proposed framework, the collaborating parties jointly conduct model training with a central server. Each client \(cl_{p}\) is associated with a party \(p\). Item embeddings \(e_{v}^{0}\) should be maintained privately on each client, while other public parameters are initialized and stored at the server. At the initial step, Private Set Intersection (PSI) is adopted to conduct secure user alignment (Pinkas et al., 2014). Algorithm 1 outlines the process to perform VerFedGNN. Figure 1 gives the overall framework of our VerFedGNN, and we will illustrate the key components in the following.

### Neighborhood Aggregation

Instead of sending the individual embeddings of missing neighbors, each party performs embedding aggregation locally for each common user before the transmission. Each party outputs a list of \(N\times D\) aggregation matrices \([X_{p}^{0},X_{p}^{1},...,X_{p}^{K-1}]\), with each row of \(X_{p}^{k}\) given by \(E_{p}(n_{u}^{k})\). Below details the local neighborhood aggregation for the three GNN frameworks:

**GCN** requires \(N_{u}\) to perform local aggregation, while sharing \(N_{u}\) could reveal how many items user \(u\) has interacted with in other parties. To preserve the privacy of \(N_{u}^{p}\), we develop an estimator from party \(p\)'s view in replacement of \(N_{u}\):

\[E_{p}(N_{u})=\frac{\sum_{i}M_{i}}{M_{p}}\cdot N_{u}^{p} \tag{12}\]

where \(M_{i}\) denotes the number of items in party \(i\). The estimator is utilized to perform embedding aggregation:

\[E_{p}(n_{u}^{k})=\sum_{v\in\mathcal{N}_{p}(u)}\frac{1}{\sqrt{E_{p}(N_{u})N_{v} }}e_{v}^{k} \tag{13}\]

**GAT** calculates importance coefficient \(b_{uv}^{k}\) using all item embeddings for \(v\in\mathcal{N}_{u}\), incurring further privacy concern and communication cost. Therefore, we adapt equation 8 to obtain \(E_{p}(b_{uv}^{k})\):

\[E_{p}(b_{uv}^{k})=\frac{exp(\bar{b}_{uv}^{k})}{exp(\bar{b}_{uu}^{k}+\sum_{v^{ \prime}\in\mathcal{N}_{u}}exp(\bar{b}_{uv^{\prime}}^{k})\cdot\sum_{i}M_{i}/M_{ p})} \tag{14}\]

The neighbor items are aggregated locally using:

\[E_{p}(n_{u}^{k})=\sum_{v\in\mathcal{N}_{p}(u)}b_{uv}^{k}e_{v}^{k} \tag{15}\]

Figure 1: Overall framework of VerFedGNN
**GGNN** slightly adapt \(Agg_{k}\) in equation 9 to perform aggregation:

\[E_{p}(n_{u}^{k})=\sum_{v\in\mathcal{N}_{p}(u)}\frac{1}{N_{u}^{p}}e_{v}^{k} \tag{16}\]

Refer to Appendix A for embedding update with the aggregated neighborhood.

### Random Projection

Though neighborhood aggregation reduces the information leakage, users might still be susceptible to de-anonymization attack when they rated few items in other parties. We adopt random projection (Lindenstrauss, 1984) to perform multiplicative data perturbation for two reasons: (1) random projection allows to reduce dimensionality and reconstruct matrix without prior knowledge of the data; (2) random projection preserve the pairwise distance between points with small error (Ghojogh et al., 2021). Below we define a Gaussian random projection matrix.

**Definition 4.1**.: For \(q\ll N_{u}\), a Gaussian random projection matrix \(\Phi\in\mathbb{R}^{q\times N_{u}}\) has elements drawn independently from Gaussian distribution with mean 0 and variance \(1/q\).

Each active party sends a list of \(q\times D\) projected matrices to other participants:

\[Y_{p}^{k}=\Phi X_{p}^{k} \tag{17}\]

for \(k\in[0,K-1]\). The recipient recover the perturbed aggregation matrices \(\hat{X}_{p}^{k},\ k\in[0,K-1]\):

\[\hat{X}_{p}^{k}=\Phi^{T}Y_{p}^{k} \tag{18}\]

### Privacy-preserving Parameter Update

The gradients of public parameters could leak sensitive information about the users. For example, if two users rated the same items, the gradients for their embeddings would be similar. Therefore, a participant could infer subscribers' interaction history by comparing their embeddings with adversarial users. We introduce a ternary quantization scheme (Wang and Basar, 2022) to address this issue.

**Definition 4.2**.: The ternary quantization scheme quantizes a vector \(x=[x_{1},x_{2},...,x_{d}]^{T}\in\mathbb{R}^{d}\) as follows:

\[Q(x)=[q_{1},q_{2},...,q_{d}],\ \ q_{i}=r\text{sign}(x_{i})b_{i},\ \ \forall 1\leq i\leq d \tag{19}\]

where \(r\) is a parameter such that \(\|x\|_{\infty}\leq r\), sign represents the sign of a value, and \(b_{i}\) are independent variables following the distribution

\[\left\{\begin{array}{l}P(b_{i}=1|x)=|x_{i}|/r\\ P(b_{i}=0|x)=1-|x_{i}|/r\end{array}\right. \tag{20}\]

The ternary quantization scheme is adopted in place of Gaussian or Laplace noise for two reasons: (1) The scale of Gaussian or Laplace noise is determined by the sensitivity that could be significant for high dimensional data. For GNN model with large size, directly adding the calibrated noises would greatly distort the direction of gradients. On the other hand, the quantization scheme ensures that the sign of each element in the gradient is not reversed by the stochastic mechanism. (2) For user embeddings, the gradients is a \(N_{u}\times D\) matrix with communication cost proportional to user size. Under the quantization scheme, parties could send a much smaller sparse matrix indexed by the non-zero binary elements.

### Partial Participants

We consider the case where in each iteration, only a portion of clients participates in model training. The challenge is that both the embedding update and gradient computation contain components summed over all clients to capture the complete graph structure. To address this issue, we develop an estimator of the total summation based on the subsets of components received.

Denote \(c_{i}\) as the component send by party \(i\), and \(\mathcal{A}_{t}\) as the set of participating clients in iteration \(t\). The estimation \(E(C)\) is given by:

\[E(C)=\frac{\sum_{i}M_{i}}{\sum_{i\in\mathcal{A}_{t}}M_{i}}\sum_{i}c_{i} \tag{21}\]

Specifically, the component \(c_{i}\) is \(E_{p}(n_{u}^{k}),\ k\in[0,K-1]\) for embedding update, and local gradients for gradient computation, respectively.

## 5 Theoretical Performance Analysis

### Privacy Analysis

The privacy of the algorithm is analyzed for two communication stages: (i) neighborhood exchange, and (ii) gradient transmission. We assume honest-but-curious (Yang et al., 2019) participants for the analysis, i.e., the participant will not deviate from the defined training protocol but attempt to learn information from legitimately received messages.

**Neighborhood exchange:** Suppose that an attacker would like to infer the original aggregation matrix \(X_{p}^{k}\) given \(Y_{p}^{k}\). The model can be analyzed as an underdetermined system of linear equations with more unknowns than equations \(y=\Phi x\), where \(x\) is a column vector in \(X_{p}^{k}\) and \(y\) is the corresponding column in \(Y_{p}^{k}\). We start with the definition of \(l\)-secure (Du et al., 2004).

**Definition 5.1**.: A matrix \(\Phi\) is \(l\)-secure if a submatrix \(\Phi_{k}\) formed by removing any \(l\) columns from \(\Phi\) has full row rank.
**Lemma 5.2**.: _Let \(\Psi\) be an \(l\times N\) matrix, where each row is a nonzero linear combination of row vectors in \(\Phi\). If \(\Phi\) l-secure, the linear equations system \(y=\Psi x\) involves at least \(2l\) variables if these \(l\) vectors are linearly independent._

**Theorem 5.3**.: _For \(2q\leq m+1\), let \(\Phi\) be a \(q\times m\) matrix with entries independently chosen from Gaussian distribution. For a linear system of equations \(y=\Phi x\), it's impossible to solve the exact value of any element in \(x\)._

The proof is given in Appendix B and C. As long as we select \(q\leq(m+1)/2\), the privacy of aggregation matrix is protected in the sense that the attacker cannot identify the exact value of any elements in the original data.

Next, we consider the possibility to infer users' interaction history from the reconstructed aggregation matrix. Appendix E demonstrates the NP-hardness of finding a subset of items that match the aggregated embeddings.

**Gradient transmission:** The gradient transmitted to server is perturbed by the ternary quantization scheme. The following theorem shows that the ternary quantization can achieve \((0,\frac{1}{r})\) differential privacy.

**Theorem 5.4**.: _The ternary quantization scheme given by Definition 4.2 achieves \((0,\frac{1}{r})\)-differential privacy for individual party's gradients in every iteration._

Proof.: The privacy guarantee has been proved by (Wang and Basar, 2022) in Theorem 3. 

_Remark 5.5_.: The ternary quantization still achieves \((0,\frac{1}{r})\)-differential privacy when the \(l_{1}\) norm in Definition 3.1 is replaced with any \(l_{p}\) norm with \(p\geq 1\) (see Appendix D).

### Utility Analysis

The federated algorithm involves two sources of error: (i) random projection and reconstruction of aggregation matrix, and (ii) stochastic ternary quantization mechanism. We will discuss the concerns one at a time.

**Random projection and matrix reconstruction:** The reconstructed matrix \(X_{p}^{k},\ k\in[0,K-1],\ p\in[1,P-1]\) doesn't deviate much from the original matrix with the following bounded MSE.

**Theorem 5.6**.: _Let \(\Phi\) be a random matrix defined in Definition 4.1. For any \(X\in\mathbb{R}^{N_{u}\times D}\),_

\[\mathbb{E}_{\Phi}[\|\Phi^{T}\Phi X-X\|_{F}^{2}]=\frac{(m+1)}{p}\|X\|_{F}^{2} \tag{22}\]

_where \(\|\cdot\|\) represents the Frobenius norm of inner matrix._

Refer to Appendix F for the proof of Theorem 5.6.

**Ternary quantization mechanism:** In Appendix G we provide an convergence analysis for the gradient perturbed mechanism.

### Communication Analysis

The communication cost is analyzed in terms of the total message size transferred between parties. We assume that the participation rate \(\alpha\), the number of participating clients divided by that of total clients in an iteration, remains unchanged throughout the training. Suppose that each number in embedding matrix and public parameters requires \(s_{1}\) bits, and that in quantized gradients requires \(s_{2}\) bits, respectively.

Downloading public parameters requires to transfer \(\mathcal{O}(\alpha pKD(D+N_{u})Ts_{1})\) bits. It takes \(\mathcal{O}(\alpha pqDKs_{1})\) bits for each party to communicate neighborhood aggregation matrix per iteration, which adds up to \(\mathcal{O}(\alpha^{2}p^{2}qDKTs_{1})\) in total.

For gradient transmission, each party is expected to have \(\mathcal{O}(|\xi|_{1}/r)\) nonzero entries in their upload matrix, where \(|\xi|_{1}\) denotes the \(l_{1}\) norm of public parameters. It takes \(\mathcal{O}(\alpha p|\xi|_{1}Ts_{2}/r)\) bits to upload quantized gradients from clients to the server,

Summing up the above processes, the algorithm involves \(\mathcal{O}(\alpha pT(KD(D+N_{u})s_{1}+\alpha pqDKs_{1}+|\xi|_{1}s_{2}/r))\) bits of communication cost.

## 6 Experiment

### Dataset and Experiment Settings

**Dataset:** We use two benchmark datasets for recommendation, MovieLens-1M2 (ML-1M) and BookCrossing3. For BookCrossing we randomly select \(6000\) users and \(3000\) items. The items are divided into non-overlapping groups to simulate the vertical federated setting.

Footnote 2: [https://grouplens.org/datasets/movielens/1m/](https://grouplens.org/datasets/movielens/1m/)

Footnote 3: [http://www2.informatik.uni-freiburg.de/cziegler/BX/](http://www2.informatik.uni-freiburg.de/cziegler/BX/)

**Implementation and Hyper-parameter Setting:** Appendix H details the implementation and hyperparameters.

### Experiment Result

#### 6.2.1 Comparison with Different Methods

We compare our proposed method with several centralized and federated recommender system, including: matrix factorization (MF) (Koren et al., 2009), central implementation of GNN (CentralGNN), federated GNN with graph expansion (FedPerGNN) (Wu et al., 2022), adaption of FedSage and FedSage+ to GNN-based recommender system (Zhang et al., 2021). We implement the GNN-related methods using the three GNN frameworks introduced in section 3.2. We compare the methods along four dimensions in table 1: (i) high-order interaction: modeling of high-order connectivity with graph propagation; (ii) gradient protection:
sending perturbed or encrypted gradients instead of raw gradients; (iii) cross graph neighborhood: usage of missing links across parties or subgraphs.

Table 2 summarizes the performance in terms of RMSE for different methods. For VerFedGNN, we use privacy budget \(\frac{1}{r}=\frac{1}{3}\), reduced dimension \(q=N_{u}/5\), and participation rate \(\alpha=1\). It can be observed that our proposed method achieves lower RMSE than other federated GNN algorithms in most scenarios, and clearly outperform MF by an average of \(4.7\%\) and \(18.7\%\) respectively for ML-1M an BookCrossing dataset. The RMSE in VerFedGNN slightly increases over the central implementation, with average percentage difference \(\leq 1.8\%\).

#### 6.2.2 Hyper-parameter Studies

We use GCN as an example to study the impact of hyper-parameters on the performace of VerFedGNN.

**Participation rate:** The participation rate is changed from \(0.2\) to \(1\), with results presented in figure 2. Using GCN model, the percentage differences over the fully participation case are within \(0.15\%\) for ML-1M and \(0.7\%\) for BookCrossing when \(\alpha\) reaches to \(0.5\). The other two models gives RMSE \(\leq 0.92\) for ML-1M and \(\leq 1.2\) for BookCrossing when \(\alpha>0.5\).

**Privacy budget:** A smaller the privacy budget \(\frac{1}{r}\) suggests that the transmitted gradients leak less user information. Figure 3 presents the tradeoff between privacy budget \(\frac{1}{r}\) and model performance. GGNN model is most sensitive to the change in privacy budget, while GAT model remains effective against the increase in \(\frac{1}{r}\).

**Dimension Reduction:** We further analyze the effectiveness of our model with varying dimension reduction ratio \(q/N_{u}\). As is shown in figure 4, GCN and GAT are more robust to the change in neighborhood dimension \(q\), with error increase by \(0.5\%\) for ML-1M and \(1.5\%\) for BookCrossing when \(N_{u}/q\) increases to \(100\).

#### 6.2.3 De-anonymization Attack

To verify the effectiveness of our model against de-anonymization attack, we simulate this attack to compare the inference accuracy of VerFedGNN with the other two methods using cross graph neighborhood: FedPerGNN and FedSage+. For FedSage+, we match the generated embeddings of honest and adversarial users using equation 11. The attack for VerFedGNN utilized the recovered aggregation embeddings. Specifically, we find the subset of adversarial item embeddings leading to smallest \(l_{1}\) distance with each users' neighborhood aggregation. Refer to appendix I for more illustrations.

Table 3 reports the attack accuracy for the three federated algorithm using GCN model. The experiment is conducted under three cases regarding the proportion of items rated by the adversarial users \(p_{ad}\). One important observation is that our algorithm greatly reduces the attack accuracy compared with the two baseline methods. FedPerGNN results in highest F1 and precision of \(100\%\) as the attacker could match the embeddings exactly with adversarial users.

#### 6.2.4 Communication Cost

Figure 5 presents the communication cost measured in the size of bits to be transferred in each iteration. We find that the communication cost is nearly proportional to user size

Figure 4: RMSE by inverse dimension reduction ratio \(N_{u}/q\).

Figure 3: RMSE with varying privacy budget \(\frac{1}{r}\).

Figure 2: RMSE with varying participation rate \(\alpha\).
\(N_{u}\) and participation rate \(\alpha\). Besides, random projecting the neighborhood aggregation matrix with \(q=\frac{1}{5}N_{u}\) saves the communication bits by \(50.6\%\) with gradient quantization, and applying the quantization scheme reduces the communication cost by over \(30\%\) when \(N_{u}/q\geq 4\).

#### 6.2.5 Other Studies

For other studies, we simulate the de-anonymization attack against VerFedGNN under the case with and without dimension reduction, and evaluate the model performance when Laplace noise is employed in place of ternary quantization scheme (see Appendix J).

## 7 Conclusion

This paper proposes VerFedGNN, a framework for GNN-based recommender systems in a vertical federated setting. The cross-graph interactions are transferred in form of neighborhood aggregation matrix perturbed by random projection. We adopt ternary quantization scheme to protect the privacy of public gradients. Our approach could learn the relation information across different graphs while preserving users' interaction data. Empirical studies on two benchmark datasets show that: (1) VerFedGNN achieves comparative prediction performance with SOTA privacy preserving GNN models. (2) The neighborhood aggregation combined with random projection significantly reduces the attack accuracy compared with existing cross-graph propagation methods. (3) Optimizing dimension reduction ratio \(N_{u}/q\) and participation rate \(\alpha\) could lower the communication cost while maintaining accuracy.

This work opens up new possibilities for the federated GCN-based recommendation. Firstly, it's interesting to develop a scalable federated framework with up to millions of users. Secondly, the framework could be extended to other federated scenarios, such as transfer federated recommender systems with few overlapping nodes (Yang et al., 2020).

\begin{table}
\begin{tabular}{l c c c c c} \hline \hline  & MF & CentralGNN & FedPerGNN & FedSage & FedSage+ & VerFedGNN \\ \hline High-order interaction & \(\times\) & \(\surd\) & \(\surd\) & \(\surd\) & \(\surd\) & \(\surd\) \\ Gradient protection & \(\times\) & \(\times\) & \(\surd\) & \(\times\) & \(\times\) & \(\surd\) \\ Cross graph neighborhood & \(\times\) & \(\times\) & \(\surd\) & \(\times\) & \(\surd\) & \(\surd\) \\ Data storage & Central & Central & Local & Local & Local & Local \\ \hline \hline \end{tabular}
\end{table}
Table 1: Comparison of different approaches

\begin{table}
\begin{tabular}{l l c c c} \hline \hline  & Model & ML-1M & BookCrossing \\ \hline MF & MF & \(0.9578\)\(\pm\)0.0016 & \(1.9972\)\(\pm\)0.0063 \\ \hline \multirow{3}{*}{CentralGNN} & GCN & \(0.9108\)\(\pm\)0.0007 & \(1.5820\)\(\pm\)0.0050 \\  & GAT & \(0.9062\)\(\pm\)0.0029 & \(1.5478\)\(\pm\)0.0071 \\  & GGNN & \(0.9046\)\(\pm\)0.0045 & \(1.6562\)\(\pm\)0.0040 \\ \hline \multirow{3}{*}{FedPerGNN} & GCN & \(0.9282\)\(\pm\)0.0012 & \(1.6892\)\(\pm\)0.0068 \\  & GAT & \(0.9282\)\(\pm\)0.0017 & \(1.6256\)\(\pm\)0.0048 \\  & GGNN & \(0.9236\)\(\pm\)0.0023 & \(1.6962\)\(\pm\)0.0050 \\ \hline \multirow{3}{*}{FedSage} & GCN & \(0.9268\)\(\pm\)0.0012 & \(1.6916\)\(\pm\)0.0118 \\  & GAT & \(0.9242\)\(\pm\)0.0041 & \(1.6256\)\(\pm\)0.0048 \\  & GGNN & \(0.9268\)\(\pm\)0.0008 & \(2.6596\)\(\pm\)0.0133 \\ \hline \multirow{3}{*}{FedSage+} & GCN & \(0.9194\)\(\pm\)0.0041 & \(1.6335\)\(\pm\)0.0065 \\  & GAT & \(0.9146\)\(\pm\)0.0033 & \(1.6078\)\(\pm\)0.0039 \\  & GGNN & \(0.9180\)\(\pm\)0.0002 & \(1.8788\)\(\pm\)0.0401 \\ \hline \multirow{3}{*}{VerFedGNN} & GCN & \(\mathbf{0.9152\)\(\pm\)**0.0013**} & \(\mathbf{1.5906\)\(\pm\)**0.0030**} \\  & GAT & \(\mathbf{0.9146\)\(\pm\)**0.0010**} & \(\mathbf{1.5830\)\(\pm\)**0.0131**} \\ \cline{1-1}  & GGNN & \(\mathbf{0.9076\)\(\pm\)**0.0024**} & \(\mathbf{1.6962\)\(\pm\)**0.0050**} \\ \hline \hline \end{tabular}
\end{table}
Table 2: Performance of different methods. The values denote the \(mean\pm standard\ deviation\) of the performance.

Figure 5: Communication cost by user size and dimension for GCN

\begin{table}
\begin{tabular}{l l c c c} \hline \hline \(p_{ad}\) & Methods & Precision & Recall & F1 \\ \hline \multirow{3}{*}{0.2} & FedPerGNN & \(1.00\)\(\pm\)0.00 & \(0.21\)\(\pm\)0.01 & \(0.34\)\(\pm\)0.01 \\  & FedSage+ & \(0.14\)\(\pm\)0.00 & \(0.03\)\(\pm\)0.01 & \(0.05\)\(\pm\)0.01 \\  & VerFedGNN & \(0.01\)\(\pm\)0.00 & \(0.01\)\(\pm\)0.00 & \(0.01\)\(\pm\)0.00 \\ \hline \multirow{3}{*}{0.5} & FedPerGNN & \(1.00\)\(\pm\)0.00 & \(0.49\)\(\pm\)0.03 & \(0.66\)\(\pm\)0.02 \\  & FedSage+ & \(0.22\)\(\pm\)0.03 & \(0.08\)\(\pm\)0.00 & \(0.11\)\(\pm\)0.00 \\  & VerFedGNN & \(0.02\)\(\pm\)0.01 & \(0.01\)\(\pm\)0.00 & \(0.01\)\(\pm\)0.00 \\ \hline \multirow{3}{*}{0.8} & FedPerGNN & \(1.00\)\(\pm\)0.00 & \(0.81\)\(\pm\)0.01 & \(0.90\)\(\pm\)0.01 \\  & FedSage+ & \(0.26\)\(\pm\)0.02 & \(0.10\)\(\pm\)0.01 & \(0.14\)\(\pm\)0.01 \\ \cline{1-1}  & VerFedGNN & \(0.02\)\(\pm\)0.00 & \(0.01\)\(\pm\)0.00 & \(0.02\)\(\pm\)0.00 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Attack accuracy for three federated algorithms using GCN model on ML-1M.