Federated Social Recommendation with Graph Neural Network

In general, we have no constraints on the local graph neural networks. There can be arbitrary GNN models, such as GCN (Kipf and Welling, 2017), GAT (Veličković et al., 2017), and GraphSAGE (Hamilton et al., 2017), etc. This paper focuses on proposing a new FSRS framework. We directly adopt the GAT layer for learning node embedding and leave other GNN layers for future investigation. The GAT layer is designed by employing the self-attention mechanism (Vaswani et al., 2017). To learn the node embedding of $u_{n}$, we aggregate neighbor embeddings of $u_{n}$. However, since neighbors contribute unequally to the center node $u_{n}$, we should first learn a weight for each neighbor by employing an attention layer. Specifically, for a social pair $(u_{n},u_{p})$, their attention scores are formulated as:

where $o_{np}$ is a scalar denoting the attention weight, $\mathbf{W}_{1}\in\mathbb{R}^{d\times d}$ is a linear mapping matrix, and Attention is the attention layer. We define the attention layer as a single-layer feed-forward neural network. It is parameterized with a weight vector $a\in\mathbb{R}^{2d}$ and employs a LeakyReLU activation (Vaswani et al., 2017), which is formulated as:

where $\mathbf{a}^{\top}$ denotes the transpose of the attention layer parameter and $\|$ denotes the concatenation operation of two vectors. An illustration of the attention weight is in Fig. 2(a). The attention weight should be calculated for all the neighbors of the center node $u$, which forms a probability distribution by employing the softmax function:

where $\alpha_{np}$ is the final attention weights, exp denotes the exponential function. Note that $\alpha$ is calculated as the attention weights for user neighbors. We should learn attention weights for user-item pair $(u_{n},i_{k})$ in a similar way, which employs another linear mapping as in Eq. (1) and another attention parameters as in Eq. (4), as following:

where $\mathbf{W}_{2}\in\mathbb{R}^{d\times d}$ is the mapping matrix and $\mathbf{b}\in\mathbb{R}^{2d}$ is the weights for the user-item interaction attention layer. By employing the softmax to all the item neighbors, we derive the attention weights for item neighbors as:

where $\beta_{nk}$ denotes the attention weights for items normalized over all neighboring items, next, we present the relational aggregation for both user neighbors and item neighbors.

Inferring the center user embeddings requires aggregating both neighbor user nodes and neighbor item nodes with their associated attention weights, which are formulated as follows:

where $\mathbf{W}_{h}\in\mathbb{R}^{d\times d}$ is the linear mapping weight matrix, and $\mathbf{h}_{u}^{(n)},\mathbf{h}_{t}^{(n)}\in\mathbb{R}^{d}$ denotes the hidden embeddings for aggregating user neighbors and item neighbors, respectively. The general aggregation process is illustrated in Figure 2(b). Intuitively, we should aggregate hidden embeddings and the center node embedding to infer the embedding of $u_{n}$. However, social relation, user-item interactions and center node embedding are not equally contributed to the learning process (Yang et al., 2021). We should also handle the heterogeneity during the aggregation step. Therefore, we propose to use three relation vectors to preserve their semantics, i.e., $\mathbf{v}_{u},\mathbf{v}_{t},\mathbf{v}_{s}\in\mathbb{R}^{d}$ preserving the social semantics, user-item semantics and center node itself semantics respectively. To be more specific, we concatenate hidden embeddings with their relation vectors and employing the self-attention mechanism to learn the weights for aggregation:

where $\gamma_{u}$, $\gamma_{t}$ and $\gamma_{s}$ are the attention weights for hidden user neighbors embedding, hidden item neighbor embedding and center node itself embedding, respectively. $\mathbf{c}\in\mathbb{R}^{2d}$ is the weight vector for the attention layer. Given that, we infer the node embeddings of $u_{n}$ as:

where $\mathbf{e}_{u_{n}}^{*}$ is the local user embedding for prediction. The aggregation is illustrated in Fig. 3. As such, local clients preserve their user embeddings, which tackles the personalization problem. Next, we will use the learned embeddings and downloaded item embeddings to make a prediction.

To predict the local item ratings, we adopt the dot-product between the inferred user embedding and item embeddings. For a user $u$ and an item $t$ with embedding $\mathbf{e}^{*}_{u}$ and $\mathbf{e}_{t}$, respectively, the rating $\mathbf{R}_{ut}$ is:

where $\cdot$ denotes the dot-product operation. We use the local user-item rating values to optimize the prediction by employing the Root Mean Squared Error (RMSE) between the predicted score $\hat{\mathbf{R}}_{ut}$ and the ground-truth rating score $\mathbf{R}_{ut}$:

where $\mathcal{T}^{(u)}$ denotes the rated items of user $u$ and $\mathcal{L}_{u}$ is the local loss for user $u$. Recall that each user is associated with a client. This loss function will be used to calculate the gradient for clients. Then, the gradients are collected from multiple clients to the server for further updates. However, directly uploading gradients leads the user-item interaction data to be vulnerable (Chai et al., 2020; Wu et al., 2021b). It urges us to design a privacy protection mechanism regarding the gradients, which will be introduced next.

According to FedMF (Chai et al., 2020), the user’s rating information can be inferred if given the gradients of a user uploaded in two continuous steps. Though our case is more complicated than in FedMF, it is still problematic if directly optimizing the local data and uploading the gradients. Moreover, for embedding gradients, only items with ratings in a local client have non-zero gradients to upload to the server. FedMF (Chai et al., 2020) proposes using encryption for the gradients so that the server cannot inverse the encoding process. However, it requires generating the public key and secret key and introducing additional computation for encryption. Additionally, to solve the zero-gradient for non-rated items, FedGNN (Wu et al., 2021b) proposes to sample pseudo-interacted items and add Gaussian noise with the same mean and variance as the ground-truth items to their gradients. Another technique used broadly is the Local Differential Privacy (LDP) module (Erlingsson et al., 2014; Ribero et al., 2020; Qi et al., 2020). It adopts clipping the local gradients based on their L$\infty$-norm with a threshold $\delta$ and applies a LDP module with zero-mean Laplacian noise to the unified gradients to achieve privacy protection.

To be more specific, we instantiate the item embedding gradients, user embedding gradients and model gradients from client $n$ as $\mathbf{g}_{t}^{(n)}$, $\mathbf{g}_{u}^{(n)}$ and $\mathbf{g}_{m}^{(n)}$, respectively. Combining them gives the gradients as $\mathbf{g}^{(n)}=\{\mathbf{g}_{t}^{(n)},\mathbf{g}_{u}^{(n)},\mathbf{g}_{m}^{(n)}\}=\frac{\partial\mathcal{L}_{u}}{\partial\mathbf{\Theta}}$, where $\mathbf{\Theta}$ denotes all trainable parameters. Then, the LDP is formulated as:

where $\tilde{\mathbf{g}}^{(n)}$ is the randomized gradients, clip$(x,\delta)$ denotes limiting $x$ with the threshold $\delta$, and Laplacian$(0,\lambda)$ is the Laplacian noise with $0$ mean and $\lambda$ strength. However, a constant noise strength is inappropriate when dealing with gradients at different magnitudes. The gradient magnitude of different parameters varies during training. Hence, we propose to add dynamic noise based on the gradient, which is formulated as follows:

Based on existing work, we propose a new privacy protection module, which is advantageous as it can protect the training gradients and enhance the model with more robustness. In a local client, before calculating the training loss, we first sample $q$ items not in the neighbor items, which are the pseudo-items in Fig. 3, denoting as $\tilde{\mathcal{T}}^{(u)}=\{\tilde{t}^{(u)}_{1},\tilde{t}^{(u)}_{2},\dots,\tilde{t}^{(u)}_{q}\}$. Then, we use the local model to predict the ratings for these pseudo items. The predicted ratings are rounded to be the pseudo ratings. Hence, the loss in Eq. (12) is changed to:

Note that compared with Eq.(12), Eq.(15) is calculated from both the true interacted items and pseudo items. The ground-truth ratings for pseudo items are the rounded predicted score. The difference between the predicted score and the rounded one contributes to the gradients for those pseudo items. Here, we assume that $\mathbf{R}_{ut}\in\mathbb{N}$, while $\hat{\mathbf{R}}_{ut}\in\mathbb{R}$. The gradients derived from Eq. (15) contain both ground-truth rating information and the pseudo item rating information, which prevents the data leakage problem. Additionally, the pseudo labels of items provide additional rating information, which can alleviate the cold-start issue of the data. Intuitively, this technique works as a data augmentation method (Liu et al., 2021; Xia et al., 2020; Liu et al., 2020d). We sample those pseudo items and view the difference between rounded ratings with a predicted rating as the randomness, which enhances the robustness of the local model.

The server in FeSoG collects the gradients uploaded from clients to update both the model parameters and embeddings, which collaboratively optimize the model. Recall that the gradients from client $n$ is $\tilde{\mathbf{g}}^{(n)}$ and the parameters is $\mathbf{\Theta}$, which includes $\mathbf{\Theta}_{m}$, $\mathbf{\Theta}_{t}$ and $\mathbf{\Theta}_{u}$ indicating model parameters, item embedding and user embedding, separately. In each round, the server builds a connection with a batch (e.g., 128) of clients, denoted as $\mathcal{N}$. It first sends the current model parameters $\mathbf{\Theta}_{m}$ and embeddings $\mathbf{\Theta}_{e}$ to those clients. Then, it aggregates local gradients from those clients as follows:

where $\mathcal{R}_{n}$ is the total number interaction for calculating the gradients, including both the real interactions and pseudo interactions. $\mathcal{R}_{n}^{t}$ and $\mathcal{R}_{n}^{u}$ indicate interactions involving item $t$ and user $u$, separately. Intuitively, $\bar{\mathbf{g}}_{m}$, $\bar{\mathbf{g}}_{t}$, $\bar{\mathbf{g}}_{u}$ are weighted average of the gradients from clients. After aggregation, the server updates the parameter $\mathbf{\Theta}$ with gradient descent as:

where $\eta$ is the learning rate. This learning process is operated multiple rounds until convergence.

The pseudo-code of the algorithm of FeSoG is presented in Algorithm 1. The input are consist of the training hyper-parameters such as the embedding size $d$ and learning $\eta$. Additionally, the client data should also be given, i.e. the clients local graphs $\{\mathcal{G}_{n}|_{n=1}^{N}\}$. Though the target is to predict item ratings, we output the parameters $\mathbf{\Theta}$ and the local inferred embeddings $\{\mathbf{e}_{u_{n}}^{*}|_{n=1}^{N}\}$, which is sufficient for clients to predict ratings. In the algorithm, the line 1 to the line 1 is the loop operated on the server, which sends parameters to clients and collects their gradients for updating. The function ClientUpdate() is the operation on local devices. It downloads the parameters to infer the local user embeddings (line 1). Then, the pseudo items are sampled (line 1). Pseudo-labelling and LDP are combined  (line 1 to line 1) to protect the gradients from privacy leakage. This function returns the gradients and the number of interactions (line 1) for the server to collect.

In this paper, we adopt three commonly used social recommendation datasets to conduct experimental analyses, which are Ciao, Epinions (Tang et al., 2012b, a, 2013) and Filmtrust (Guo et al., 2013). Ciao and Epinions²²2https://www.cse.msu.edu/~tangjili/datasetcode/truststudy.htm (Tang et al., 2012b, a, 2013) are crawled from shopping website. Both datasets contain user rating scores on items and trust links between users as social relations. Each user can give an integer score in $\{1,2,3,4,5\}$ to rate an item, where $1$ indicates least like while $5$ represents most. Filmtrust³³3https://guoguibing.github.io/librec/datasets.html (Guo et al., 2013) is built from online film rating website and the trust relationship between users. The rating scale ranges from 1 to 8. Social relations are also the trust links between users in these datasets. Data statistics are shown in Table 3. In our FSRS scenario, each user is treated as a local client, and the user’s interactions are local privacy data on the device. The global graph information is transferred from user embeddings.

We adopt three types of baselines for comparison: traditional Matrix Factorization (MF) based methods for social recommendation, recent GNN-based methods for social recommendation, and federated learning frameworks. MF-based and GNN-based methods are based on centralized learning, which is unable to protect user privacy. Federated learning methods are not able to handle the fusion of local social information and rating information.

MF-based methods

• •

  SoRec (Ma et al., 2008): It co-factorizes user-item rating matrix and user-user social matrix.

• •

  SoReg (Ma et al., 2011): It develops a social regularization with social links to regularize on matrix factorization.

• •

  SocialMF (Jamali and Ester, 2010): Compared with SoReg, social matrix factorization also considers social trust propagation.

• •

  CUNE (Zhang et al., 2017): Collaborative user network embedding assumes users hold implicit social links from each other, and it tries to extract semantic and reliable social information by graph embedding method.

GNN-based methods

• •

  GCMC+SN (Berg et al., 2017): GCMC is a graph neural network based method. User nodes are initialized as vectors learned by node2vec (Grover and Leskovec, 2016) from the social graph to obtain social information. The dense representation learned upon the social graph can include more information than the random initialized feature.

• •

  GraphRec (Fan et al., 2019): Graph recommendation uses graph neural network to learn user embedding and item embedding from their neighbors and uses several fully connected layers as the rating predictor.

• •

  ConsisRec (Yang et al., 2021): It is the state-of-the-art method in social recommendation. ConsisRec modifies graph neural network to mitigate the inconsistency problems in social recommendation.

Federated learning methods

• •

  FedMF (Chai et al., 2020): It separates the matrix factorization computation to different users and uses an encryption method to avoid information leakage.

• •

  FedGNN (Wu et al., 2021b): Federated graph neural network is the state-of-the-art federated recommendation method. It adopts local differential privacy methods to protect user’s interaction with items.

To evaluate the performance and compare, we adopt Mean Absolute Error (MAE) and Root Mean Square Error (RMSE) to measure the model performance because they are the most commonly used metrics in social recommendation. Smaller values of both two metrics indicate better performance in the test data. The two metrics are calculated as follows:

where $\mathbf{R}_{nt}$ and $\hat{\mathbf{R}}_{nt}$ are the true rating value and predicted rating value of user $n$ for item $t$, respectively. $N$ is the total number of users for testing. $\mathcal{T}^{(n)}$ denotes the rated items for user $n$. Again, the evaluation is conducted on devices locally since the server has no access to the local privacy data. The lower MAE and RMSR both indicate better performance.

The ratings in each dataset are randomly split into training set ($60\%$), validation set ($20\%$), and test set ($20\%$). Hyper-parameters are tuned based on the validation performance. Then, we report the final performance on the test dataset. In all experiments, we initialize the parameters with standard Gaussian distribution. For the LDP technique used in FeSoG, the gradient clipping threshold is set to $0.3$, and the strength of Laplacian noise is set to 0.1. Other hyperparameters are tuned based on grid searching. The number of pseudo interacted items $p$ is search in $\{10,50,100,500,1000\}$. Embedding size $d$ is tuned from $\{4,8,16,32,64\}$. User batch size in each training round is searched in $\{16,32,64,128,256\}$. Learning rate $\eta$ is searched in $\{0.1,0.05,0.01\}$. Training is stopped if RMSE on the validation set does not improve for $5$ successive validations.

In this section, we analyze the impact of user batch size. Intuitively, choosing a small user batch size increases the communication rounds for the server to train a model. However, it is unclear how it affects the prediction performance. We report the performance of FedGNN and FeSoG with respect to RMSE and MAE across three datasets, which is illustrated in Fig. 4 and Fig. 5, respectively. We have the following observations:

• •

  FeSoG performs better than FedGNN. On all three datasets, the RMSE of FeSoG is consistently lower than FedGNN, which results from its powerful embedding ability of relational local GNN.

• •

  The performance of FeSoG becomes better with the increase of user batch size across datasets. With a larger user batch size, the server can obtain a more accurate global information estimation, which leads to a better performance. However, in practice, aggregating more users at each training step would lead to more computational cost and more time to converge.

Pseudo items are sampled to protect the gradients from privacy leakage. Sampling more pseudo items requires more computational cost as more ratings should be predicted. However, it is unclear how many samples should be selected to achieve satisfying results. Hence, we conduct experiments on three datasets to study the impacts of the number of sampled pseudo items. We also compare FedGNN, which samples a set of negative items and assigns them with random gradients. The influence of the number of pseudo items on three datasets with respect to RMSE and MAE is reported in Fig. 6 and Fig. 7. Besides the performance value, we also present the computational cost with respect to the number of sampled pseudo items. We have the following observations:

• •

  FeSoG yields better performance compared with FedGNN. On Ciao and Epinions datasets, the performance of FeSoG and FedGNN gets worse with the increase of pseudo items. However, the value of FeSoG is much lower than FedGNN. It suggests that our pseudo item sampling and the pseudo labeling techniques are robust. Therefore, we can conclude that the pseudo item sampling in FeSoG can protect privacy data and enhance the training process.

• •

  If increasing the number of pseudo items, the error value all increases for both FedGNN and FeSoG on Ciao and Epinions datasets, which results from more noise caused by pseudo items. However, on the Filmtrust dataset, the error value of FedGNN first increases and then drops. This is because FedGNN generates gradients of pseudo items from the same Gaussian distribution, and at the same time Filmtrust dataset only has $1957$ items. So when sampling more than $500$ pseudo items, the gradient of pseudo items from different users would counteract with each other to reduce noise impact. FeSoG generates gradients of pseudo items by user-specific labelling, which does not have this characteristic.

• •

  We should find a trade-off between pseudo-item sampling and model performance. As illustrated in Fig. 6 and Fig. 7, if increasing the number of pseudo items, the extra computational cost increases linearly and the server would be harder to infer the true interacted items. At the same time, prediction accuracy would become worse. So we should find a suitable pseudo item number to balance privacy protection and model performance. For example, $100$ pseudo items for Ciao dataset would be an appropriate setting because the model performance does not deteriorate much when the number of pseudo items is lower than $100$.

This section studies the performance with respect to the embedding size. The values of RMSE and MAE on three datasets are reported in Fig. 8 and Fig. 9, respectively. For comparison, we also select two representative baselines, which are FedGNN and FedMF. We have the following observations:

• •

  The proposed FeSoG consistently outperforms other federated recommender system methods across all embedding sizes. This observation suggests that FeSoG can learn informative structures from local graphs. Compared with FedMF, FedGNN demonstrates a much better performance, which justifies the necessity to employ GNN for graph embedding.

• •

  FeSoG has lower fluctuations as embedding sizes change compared with the other two baselines. It indicates that FeSoG is more robust than FedGNN on different embedding sizes, demonstrating the effectiveness of using pseudo-item protection to enhance the training.

• •

  Furthermore, suitable embedding sizes are crucial for different datasets to achieve satisfying performance. All federated learning methods follow the same trend and obtain the best performance in either $d=16$ or $d=32$. With a smaller embedding size (e.g., $d=4$), the model has insufficient representation ability. However, with large embedding sizes (e.g., $d=64$), it may cause the overfitting issue due to limited data.

Learning rate affects the number of communication rounds for the convergence of a federated learning framework. Intuitively, fewer communication steps can decrease the number of communication times between the server and clients, which implies less risks of information leakage. We investigate the impact of learning rate with respect to the training loss of FeSoG and report the results in Fig. 10. The learning rather is selected from $\{0.1,0.05,0.01\}$. We have the following observations:

• •

  The training of FeSoG is smooth. The loss on three datasets all converges smoothly when increasing the number of communications steps. It suggests that the federated learning framework can effectively transfer informative gradients for the FeSoG to converge.

• •

  Different datasets prefer different learning rates. For example, on the Epinions dataset, the best learning rate $\eta=0.1$. While both Ciao and Filmtrust datasets converge the fastest when the learning rate $\eta=0.05$. Learning rate has a critical influence on different datasets.

This section studies the correlations between model performance and the LDP module. It contains two parameters: gradient clip threshold $\delta$ and Laplace noise strength $\lambda$, as shown in Eq. (14). Intuitively, this module alters gradients by injecting noise to gradients to protect the user’s privacy. The injected gradients contribute to the training because the server also aggregates them for updating. Therefore, we conduct experiments to study the model performance with respect to the variations of these two parameters, which is shown in Fig. 11 and Fig. 12 for RMSE and MAE, respectively. We have the following observations:

• •

  With a fixed $\lambda$, FeSoG performs better when increasing $\delta$. The reason is that a large $\delta$ tends to clip less gradients. Therefore, the aggregated gradient information would be more accurate to reflect the true gradients.

• •

  With fixed $\delta$, FeSoG performs worse when increasing $\lambda$. It is because a larger $\lambda$ injects more substantial Laplace noise to the model gradient. Hence, the gradient learned from data would be overwhelmed by generated noises. Thus, a smaller $\lambda$ is preferred.

• •

  There is a trade-off in selecting optimal values. Although larger $\delta$ or smaller $\lambda$ lead to better performance, it would increase the risk of privacy leakage. If $\delta$ is infinitely large and $\lambda$ is $0$, the server can revert the interactions by checking uploaded gradients from clients. Therefore, we should choose an optimal pair to achieve acceptable performance with a small enough privacy budget.