Towards Communication Efficient and Fair Federated Personalized Sequential Recommendation

Federated learning requires lots of transmissions of model parameters between servers and clients. However, we find not all communication is necessary. In the beginning stage, the global model performance is limited due to random initialization. Allowing all the clients to participate in all training rounds may be suboptimal since small clients may negatively affect the model performance in the beginning stage. Since for small clients, due to their limited data sizes or low learning rates, they may not contribute enough to improve the model. Instead, the updates by these small clients may even negatively affect the model aggregation.

To cope with this problem, an adaptive selector is adopted on the server-side to save training time and computing power, as well as to improve the performance. We introduce two criteria for selecting appropriate clients: (i) the number of data samples $|D_{i}|$ in client $c_{i}$ exceeds a threshold $\lambda_{1}$, or (ii) the training epoch $t_{i}$ of client $c_{i}$ exceeds a threshold $\lambda_{2}$. If a client $c_{i}$ satisfy either of the two criteria, we select it to participate in the training. In this way, the system can get rid of the interference from the updates from small clients in the beginning stage. Through adaptive client selection, the server can train the global model faster and achieve better performance.

We also propose client clustering to reduce the communication and computation complexity further. Each client is represented by short-term and long-term interest, as illustrated in Figure 2, which is represented by the concatenate of the recent interacted item embeddings. Specifically, we choose the recent $v_{1}$ items to represent the user’s short-term interest and the recent $v_{2}$ items to represent the user’s long-term interest. Obviously we have $v_{2}>v_{1}$. Then we calculate the average embeddings of the selected items. After that, we concatenate the long-term and short-term interests to form the client representation. Several clustering techniques can be adapted to cluster similar users, such as K-means [8] and Mean shift [9]. We sample clients proportionally from each cluster; thus, the sampled clients should be more representative than the randomly sampled.

Firstly, we review the FedAvg [10], which is a commonly used federation aggregation strategy. The formula is denoted as:

where $w_{t+1}$ is the model parameter in time $t+1$, and $n_{k}$ is the sample size for client $k$. According to the formula, a larger sample size would result in a more significant contribution to the global model for clients.

However, the FedAvg algorithm suffers from several problems. Though the overall model performance may be satisfactory, the local model performance for each client may not be promising. The main reason is that the data for clients are Non-IID, then the local datasets are usually heterogeneous between clients in terms of size and distribution. Therefore, it is unfair for some clients since they may have a small data sample size and are largely ignored in the parameter aggregation process.

To tackle the heterogeneous problem, we design a weighting strategy to encourage a more fair distribution in this work. Firstly, we propose a fairness-aware parameter aggregation method to deal with the varying model performance among clients. To start with, we represent the performance for client $k$ as $p_{k}$. For federated recommendation scenarios, commonly adopted evaluation metrics are Hit Rate (HR) and Normalized Discounted Cumulative Gain (NDCG). Thus we use the sum of evaluation metrics to represent the performance, denoted as:

Then we normalize it:

After that, we apply an activation function. The activation function should satisfy decreasing in range $[0,1]$. In this work, the activation function is $f(x)=(\frac{1}{2})^{x}$.

Then we normalize it again,

where the ${p_{k}^{\prime}}$ is the fairness-aware factor.

Secondly, we alleviate the impact of the data sample size. For the unfairness caused by the imbalance sample size, one way to eliminate this effect is to reduce the impact of the parameter of data sampling size. In this way, the aggregation formula is denoted as:

We set the weight parameter as $q_{k}$. Intuitively, it is denoted as:

Then we use an activation function. The activation function should satisfies increasing in range $[0,1]$. In this work, the activation function is $f(x)=\sqrt{x}$.

Then we have:

Lastly, we combine these two factors and form the final parameter aggregation function:

where $w_{t+1}$ is the global model at time $t+1$, $\alpha$ and $\beta$ are two hyper-parameters.

Prior researches show that FL could be used to train a high-performing global model for federated recommendation [11, 12]. The trained model, however, is more of generality but lacks personalization. Therefore, we fine-tune the global model with the client’s local data to make personalized recommendations. We aggregate the global and fine-tuned model to balance generality and personalization. Thus the client could benefit from the personalization process. We denote the process as:

where $\gamma$ is a hyper-parameter. The model could adaptively balance the generalizable and personalization by adjusting the hyper-parameters. Additionally, note we only transmit the embedding layer in the training process, as the skeleton network, while letting the remaining part of the network be trained localized.

We have conducted experiments using real-world datasets to evaluate our proposed method. A detailed description of the total number of user clicks, the number of items and clicks, and the average number of clicks is listed in Table I. These datasets vary in domains, platforms, and sparsity. Here we give the detailed description of the datasets.

$\bullet$ Amazon: A series of datasets introduced in [13], comprising large corpora of product reviews crawled from Amazon.com. Top-level product categories on Amazon are treated as separate datasets. We consider two categories, Beauty and Video. This dataset is notable for its high sparsity and variability.

$\bullet$ Wikipedia: This dataset contains one month of edits on Wikipedia [14]. The editors who made at least 5 edits and the 1,000 most edited pages are filtered out as users and items for recommendation. This dataset contains 157,474 interactions in total.

We aim to explore the performance of federated learning in a deep learning model for sequential recommendations. We use the GRU4REC [1] as the backbone sequential recommendation model. The model combines RNNs to model user sequences for the sequential recommendation. We compare our proposed CF-FedSR algorithm with the popular FedAvg [10] method. FedAvg is a classical federated learning algorithm that allows many clients to train a global model collaboratively. Recall that CF-FedSR is designed to improve FedAvg in communication efficiency, fairness, and personalization. Also, we compare them with centralized training settings.

We use the following two metrics to evaluate the performance of our proposed algorithms and existing algorithms.
1) Hit Rate (HR). To calculate the proportion of predicted items that are accurate. In this work, we evaluate the top-5 and top-10 items for comparison.
2) Normalized Discounted Cumulative Gain (NDCG). To calculate the ranking position of correctly predicted items. When the rank list is predicted correctly, the NDCG is high. If predicted item ranks exceed the recommended limit (5 or 10 in our settings), the NDCG value is zero.

For performance evaluation, we use the leave-one-out strategy, following [2, 15]. For each user, we held out their latest interaction for the test set, the second last for validation and the remaining data for training.

Also, we adopt a commonly used negative sampling method to reduce heavy computation, in accordance to [2, 15]. Specifically, we randomly sample 100 negative items, and rank these items together with the ground-truth item.

The number of users used in each round of model training is 128, and the total number of the epoch is 200. The ratio of dropout is 0.3. Adam [16] is selected as the optimizer, and the default learning rate is 0.001. We tune hyper-parameters using the validation set, and terminate training if validation performance doesn’t improve for five successive epochs. Unless stated otherwise, we use the same hyper-parameters of FedAvg and CF-FedSR. We report the average performance scores over the five repetitions.

Our evaluation target is to compare the recommendation performance in a federated context, thus we don’t compare it to other centralized algorithms since they’re not well suited to federated settings.

We have compared different methods’ performances in Table II. We have the following observations:

$\bullet$ Our proposed CF-FedSR significantly outperforms the state-of-the-art federated recommender systems in all datasets. Compared with FedAvg, CF-FedSR achieves on average 7.92% and 10.32% relative improvements on HR and NDCG, respectively. Several advantages of CF-FedSR support its superiority: (1) client selection and sampling helps to find more representative and useful clients to participate in training; (2) fairness aware aggregation algorithm help to bridge the gap between clients with various data distribution and facilitate the training.

$\bullet$ The centralized models perform better than those decentralized models. Compared with CF-FedSR, centralized models achieves in average 10.25% and 15.20% relative improvements in HR and NDCG, respectively. There are two reasons: (1) centralized models models are better as they can directly train the model without noise or pseudo-labeled items. In the meantime, the federated learning framework achieves better privacy-preserving ability than centralized training because clients do not reveal raw data to the server. It could be viewed as the tradeoff of the recommendation performance to privacy. (2) though FL theoretically would have similar performance with the centralized settings. However, due to the data heterogeneous, distributed systems are harder to train since they lack the capacity to model the global data structures.

We evaluate the converge speed together with the model performance in Table III. We observe that the CF-FedSR converges much more quickly than FedAvg. Thus the communication cost is saved by transmitting less round. The reason is that we adopt several techniques to reduce communication loss. We strictly limit the participation of small clients at the beginning stage of training, which prevents the inference from these small clients. Additionally, we carefully select representative clients to participate through clustering, making the system converge faster. In a nutshell, CF-FedSR can enhance the model performance while boosting communication efficiency.

Recall that we define the fairness as the variance among clients in Section II. A lower value of variance means the system is more fair. The experimental results is shown in Figure 4. The result demonstrate that our proposed method could decrease the variance and boost the model performance in the meanwhile, showing the effectiveness of our proposed method. The superiority of our proposed method come from our specially designed adaptive aggregation algorithm.

Table V illustrates the analysis of the effect of embedding on the Beauty dataset. We repeat the experiment with default parameters and with different values for the number of embedding size, i.e. with $d\in\{10,20,50,100\}$. We find that performance is continually improved with the increase of embedding size. Presumably, this is because higher dimension of item embedding could bring more information from different aspect. However, a larger embedding size would have a higher communication cost. Thus it is a tradeoff between the communication cost and the model performance.

This experiment demonstrates the sensitivity of CF-FedSR to the number of clusters hyper-parameter. We ran CF-FedSR using the default parameters in subsection 5.1 but with different values for the number of clusters, i.e. with $k\in\{3,5,10\}$. The result of this experiment is presented in Table VI. We observe that its performance improves and then drops when the number of cluster increases from 3 to 10.