ReFRS: Resource-efficient Federated Recommender System for Dynamic and Diversified User Preferences

A RS gathers information about the preferences of its users for a set of items e.g., movies, songs, books, jokes, gadgets, applications, websites, etc. The information can be collected either explicitly (typically from the ratings of users) or implicitly (typically by monitoring the users’ actions, such as the songs they hear, the applications they download, or the websites they visit). RS may also use demographic information such as age, nationality, and gender, as well as social information, like followers, followed, tweets, and posts, that is commonly used in Web 2.0, to predict users’ interests. As a general rule, recommender systems are programs that attempt to predict an individual or business’ interest in an item based on information about the item, the user, and their interactions with the item.

In the mid-1990s, researchers began to focus on recommendation problems based on explicit ratings, and recommender systems emerged as an independent research area (Adomavicius and Tuzhilin, 2005; Goldberg et al., 1992). The most common recommendation techniques are collaborative filtering (CF) (Schafer et al., 2007), the content-based approach (CB) (Pazzani and Billsus, 2007) and knowledge-based approach (KB) (Burke, 2000). In addition to its strengths and weaknesses, each recommendation method has advantages and disadvantages; e.g., CF suffers from sparseness, scalability, and cold-start problems (Adomavicius and Tuzhilin, 2005; Schafer et al., 2007), while CB offers overspecialized recommendations (Adomavicius and Tuzhilin, 2005; Goldberg et al., 1992). Many advanced recommendation approaches have been proposed to solve these problems, including social network-based recommender systems (He and Chu, 2010), fuzzy recommender systems (Zhang et al., 2013), context-aware recommender systems (Adomavicius and Tuzhilin, 2011), group recommender systems (Masthoff, 2011), session based recommender systems (Qiu et al., 2020) and sequential recommender systems (Tang and Wang, 2018).

In Sequential Recommender Systems (SRS), each user is associated with a number of interaction sequences with some items. Its goal is to recommend each user the most probable next item by considering that user’s general tastes as well as short-term intention (Tang and Wang, 2018). Most of the early research on SRS adopts the Markov Chain (MC) (Mobasher et al., 2002; Rendle et al., 2010; Shani et al., 2005) method to model sequential behavior by estimating an item-item transition probability, and predicting the next item. The introduction of neural networks paved way for learning based RS, with the adoption of Gated Recurrent Units (GRU) (Hidasi et al., 2015) to the session-based recommendation. Modifications of GRU based methods soon followed, by adopting pair-wise loss functions (Hidasi et al., 2016), memory networks (Huang et al., 2019, 2018), hierarchical structures (Quadrana et al., 2017), copy mechanism (Ren et al., 2019) and reinforcement learning (Zhou et al., 2020), etc.

Recently generative model have generated increased interest in SRS, that captures user behavior and time dependencies in those preferences. One such approach is developed by SVAE (Sachdeva et al., 2019), which utilizes variational autoencoders for modeling a user’s preferences by incorporating latent variables and temporal dependencies. It models latent dependencies by using recurrent neural networks, before feeding them into the VAE model for prediction. Another popular approch is To generate high-quality latent variables, ACVAE (Xie et al., 2021) adopts the Adversarial Variational Bayes (AVB) (Mescheder et al., 2017) framework. Then, it applies a contrastive loss (Inoue and Goto, 2020) to compare the latent variables between different users. Contrary to the use of multi-user single models in these proposed models, ReFRS follows a federated setting, where each user only has access to their own data. As part of the embedding model, ReFRS takes in a window of recently interacted items and learns their temporal representation using a generative model. The vector quantization (VQ) layer and the multi-head attention between the encoder latents and the quantized latent help preserve the salient temporal features and interaction dependencies.

FL is an online architecture where under the coordination of a central aggregator, multiple clients can collaborate to solve machine learning (ML). FL allows the training to be carried out on a local device, in a decentralized fashion, to ensure the data privacy of each device (Zhang et al., 2021b). The main contribution of FL is preserving user privacy while allowing multiple users to collaborate. FL architecture can be divided into three categories, horizontal FL, vertical FL and federated transfer learning (Yang et al., 2019). Horizontal FL is suitable for a scenario where the items that are interacted by the users overlap but not the users themselves (Bonawitz et al., 2017; Smith et al., 2017). In Vertical FL, the items being interacted with only overlap a little (if any). However, the users (or user interactions) have a high degree of overlap (Cheng et al., 2021). Finally, in federated transfer learning, both the users and the user-item interactions rarely overlap. In this case, rather than segmenting the data, we adopt transfer learning for the lack of data or tags (Liu et al., 2020). Model aggregation is one of the main components in FL, which trains the global model by summarizing the model parameters from all participating clients (Zhang et al., 2021b).

RSs are primarily data-driven systems, where the common case is that the more data it uses, the better it performs. However, due to privacy and security constraints, directly sharing user data between parties is undesired (Tan et al., 2020). FRS builds up a stronger recommender model without compromising user privacy or data security. Recently, Ammad et al. (Ammad-Ud-Din et al., 2019) introduced the first FL-based collaborating filtering (CF) method, that utilizes stochastic gradient descent (SGD) to update the local model and the FedAvg mechanism is adopted to update the global model. Improving on data security and potential leakages in (Ammad-Ud-Din et al., 2019), (Chai et al., 2020) introduces FedMF, which enhances the distributed matrix factorization (MF) framework to the FL setting and apply homomorphic encryption on the gradient information before sharing the information. FedMeta (Chen et al., 2018) is a federated meta-learning framework, where a parameterized algorithm is shared as compared to a global model using FedAvg, adopted in a typical FL setting. SFSL (Niu et al., 2020) observe that clients interact with a subspace of items rather than complete feature space. To cater effective utilization of bandwidth and ensure model anonymity, they design a secure federated sub-model learning mechanism coupled with a private set union protocol. FedFast (Muhammad et al., 2020) accelerates federated recommendation tasks by applying an active aggregation method that propagates the updated models to similar clients. However, FedFast (Muhammad et al., 2020) relies on user grouping based upon profile similarity. This similarity is computed by sharing user’s personal demographic information with the central server, leaving users vulnerable to identity leakage (Kendzierskyj et al., 2019).

Some clustering based FL approaches have been proposed that support users’ behavioral heterogeneity without sharing/leaking any user data. Iterative Federated Cluster Algorithm (IFCA) (Ghosh et al., 2020) attempts to minimize the loss function of each FL client while also assigning the client to a cluster. Two variants are proposed for model aggregation in IFCA, i.e., model and gradient averaging. IFCA applies random initialization and multiple restarts to cluster clients and reach optimal results. However, IFCA estimates each client’s cluster by iteratively finding the best performing model parameters on the local device. Consequently, this will incur additional communication and computational costs on resource-constrained user devices like cellphones or tablets. A more recent clustering-based FL approach, DistFL (Liu et al., 2021), extracts and compares distribution knowledge from uploaded models to perform clustering based on the data generated from uploaded models, but its practicality is also constrained by the high communication overhead. Furthermore, in IFCA, each user device participating in federated clustering has to be synchronously on the same training step. In the real world, this is infeasible, especially in recommendation systems where user devices are constantly connecting and disconnecting from the server.

Let a set of $n$ users $\mathcal{U}$ interact independently with a set of $m$ items $\mathcal{I}$, and each $i\in\mathcal{I}$ has features $\mathbf{F}_{i}\in\mathbb{R}^{d}$, where $d$ is the number of dimensions. Each user $u\in\mathcal{U}$ accumulates various sessions $\mathcal{S}_{u}=\{s_{1},s_{2},...\}$ on her/his local machine over time, where a session $s=\{i_{1},i_{2},...i_{w}\}$ is a sequence of $w$ interacted items in a short time period. Note that we use numbered subscripts for items mainly to indicate their orders in a sequence. Our sequential recommendation task is session-based, where the model predicts the next item $i_{w+1}$ for every given $s\in\mathcal{S}_{u}$. Due to multi-faceted user preferences, the distribution of $\mathcal{S}_{u}$ is highly skewed across users. Also, compared with the centralized setting where all users’ data is available, in FRS, each user has a highly limited amount of interactions for learning her/his preference. To fully capture such data heterogeneity, we perform asynchronous clustering to help generate aggregated global models, so as to achieve better personalized recommendation accuracy in an effective and efficient way.

ReFRS follows the standard FL client-server architecture, as illustrated in Section 1. Each client corresponds to a personal device that holds a single user’s interaction data and trains a lightweight recommender model. A client hosts an interaction sampler, an embedding model and a recommender model. The server identifies client groups based on their model parameters and keeps a copy of the aggregated recommender model for each group. Overall the server is responsible for: 1) identifying, grouping and asynchronously updating client groups based on their parameter similarity; 2) aggregating and disseminating model parameters within each user cluster. The detailed designs of both the client and server are presented in Section 4 and Section 5.

In the federated setting, each client holds only its own user’s interaction sequences $\mathcal{S}_{u}$. These sequences are first broken down into smaller sessions in order to train the user model. To simulate sequential behavior, these sessions are fed to the embedding model as batches. Since the same item may recur over time in a sequential system, it is important to take note of how this item co-occurs with its neighbors over time (Chorney et al., 2010). This results in different representations of an item in different sessions, reflecting changes in the user’s behavior. For this reason we define an interaction window $s=\{i_{1},i_{2},...i_{|w|}\}$, which represents the interaction history of an item $i_{w+1}$. Taking into account that $s=\{i_{1},i_{2},..,i_{w}\}$ consists of $w$ items and leads to the $(w+1)^{th}$ item, we model the input to our embedding model using sequential feature vectors $\mathbf{x}_{w}=[\mathbf{F}_{i_{1}};\mathbf{F}_{i_{2}};..;\mathbf{F}_{i_{w}}]$ of items in $s$, used to estimate the latent representation $\mathbf{z}_{w+1}\in\mathbb{R}^{d}$ of item $i_{w+1}$.

An example of aforementioned sequence sampling is given in Figure 2. User 1 interacts with multiple music tracks over a period of time. In order to get the user interaction behavior for Track 4 at time interval $t_{7}$, we define $w$ (of size 4 for the purpose of this example) and stack the feature vectors of tracks falling under the window $w$. Note that the generation of Track 4’s embedding is conditioned on $\mathbf{x}_{s}$ (i.e., stacked features of Tracks 7, 1, 1, and 8 in this case). The embedding of items in such sampling is influenced by their sequential context and temporal positioning. As such, the same item will have a different temporal embedding when different temporal contexts are given. The main advantage of our approach is that it captures the user’s interest in an item $i_{a}$ at time $t$ when it is followed by sampled items $\{(i_{b},i_{c},i_{d},..),(i_{x},i_{y},i_{z},..),...\}$, grouped temporally. This change of user interest and variation in grouping persist in SRS setting, so it is beneficial to encode each item based on the latest context, when predicting the next item. In our work we define the best $w=16$ after experimentation (using $w=4,8,16$ and $32$). In the first session (i.e. batch), 16 interactions are sampled as $s_{i_{1}}=(i_{-15},i_{-14},...i_{0})$ for $i_{1}$, $s_{i_{1}}=(i_{-14},i_{-13},...i_{1})$ for $i_{2}$, and so on.

Given a session, the embedding model learns informative item representations by incorporating the dynamic context carried by other recently interacted items. In other words, we need to learn a compact vector representation (i.e., embedding) $\mathbf{z}$ of item $i_{n}$ from the interaction window $w$. The window groups semantically similar items together to capture the temporal and contextual relationships between the interacted items. As a result of this representation, item-sequence relationships should be effectively captured and items that are contextually and temporally similar should be grouped together. Since an item can be repeatedly interacted with over time, it is important to fully incorporate such dynamic context into an item’s embedding. Hence, in ReFRS, instead of using a fixed embedding for every item, each item’s embedding is dynamically conditioned on its predecessors within the same session. In order to meet these requirements, we propose to utilize the sequential variational autoencoders (VAE) (Shao et al., 2021) to capture the relationship among the input feature vector. The VAE will try to capture the dependencies among the temporally stacked item sequence (as described in Section 4.1), by enforcing a probabilistic prior to the latent space of the autoencoder (Zhu et al., 2020). That is, instead of mapping the session $s$ to a point in the embedding space, VAE maps it to a normal distribution, making the representation $\mathbf{z}$ learned from similar sources close, compact and smooth to interpolate between. VAE uses Kullback-Leibler (KL) divergence to measure the information discrepancy between the approximated true posterior $p(\mathbf{x}|z)$ of the latent variables and the variational posterior $q(\mathbf{z}|s)$:

where $q(\mathbf{z}_{w+1}|\mathbf{x}_{s})$ denotes posteriors approximated by the neural network encoder, and $p(\mathbf{x}_{s}|\mathbf{z}_{w+1})$ is the reconstruction approximated by the decoder, which is also a neural network.

However, in federated settings where there is only one user’s data (a small amount of data that grows slowly), the training objective of VAE (i.e., KL divergence) quickly reaches local maxima (Lucas et al., 2019). As a result, the continuous latent representation learned by VAE suffers from issues like high variance and posterior collapse (Dai et al., 2020). Furthermore, the continuous vector representation produced by VAE requires a large embedding representation to accurately represent the feature vector. However, the limited memory of the end-device, makes storing large embedding vectors counterproductive.

We propose to use the vector quantization (VQ) (Jin et al., 2020) technique to discretize the latent variable space into numerous sub-spaces, and further adopt self-supervision to drive the learning of discrete latent variables. This technique effectively projects each interaction window $w$ in a separate sub-space. VQ transforms continuous vectors into finite sets of ”code” vectors. In essence, it works the same way as k-nearest neighbors (KNN), in that a sample is mapped to a centroid code vector with the minimum Euclidean distance. The resultant discrete latent representations are also more constricted and space-efficient.

As shown in Figure 3, an encoder layer converts the input $\mathbf{x}$ into latents $\mathbf{z}_{e}$ and the VQ layer then convert $\mathbf{z}_{e}$ into discrete latents $\mathbf{z}$ by calculating nearest neighbour look-up. Before feeding $\mathbf{z}$ to the decoder, we perform multi-head attention (Vaswani et al., 2017) on $\mathbf{z}_{e}$ and $\mathbf{z}$, yielding $\mathbf{z}_{a}$, which is converted back in $\mathbf{x}$ by the decoder. As a result, the model can jointly attend to information from different representation from the latent sub-spaces at different positions.

The discrete latents, fed into the attention network are the sampled distributions indexed by an embedding table (van den Oord et al., 2017). Overall the embedding model can be viewed as a VAE where $\log p(\mathbf{x}_{s})$ is bounded by the evidence lower bound (ELBO) (Yang, 2017), as given in Eq. (3):

where $\mathbf{z}_{encode}(\mathbf{x}_{s})$ denotes the output from the encoder given by $\mathbf{x}_{s}$, which is discretized by mapping to the nearest element of embedding $\mathbf{e}_{j}$, with $j$ given as:

where each embedding vector $\mathbf{e}_{j}$ is drawn from the VQ’s embedding table (a.k.a. codebook) consisting of $J$ discrete values. The objective function of our embedding model is then to minimize the flipped ELBO (Jin et al., 2020) assuming degenerate approximate posteriors:

In Eq.(5), the first term is the reconstruction loss from the decoder. While both the second and third terms use $l_{2}$ error to move $\mathbf{e}$ towards $\mathbf{z}_{encode}(\mathbf{x})$, in the second term we adopt the stop-gradient operator $sg(\cdot)$ (Jin et al., 2020) to encourage the encoder output to commit as much as possible to its closest codebook vector. $\beta$ is a hyperparameter controlling the effect of the third term. Note that, once we obtain a well-trained embedding model, its parameters will stay fixed and we use the learned encoder $\mathbf{z}_{encode}(\cdot)$ followed by the vector quantization described in Eq.(4) to directly generate the temporal embeddings for observed items. With embeddings generated for all items in $s$, we further use a sequential recommender model to capture the dynamic preferences of the user. Note that, every time an item is visited, its feature vector is obtained from the server and a unique embedding is calculated based on its temporal position. As a result, all item embeddings are private and specific to the device.

Both models for item embedding and next-item recommendation are trained independently. We follow the commonly used recommendation strategy here, i.e., predicting the next most likely item to be interacted with. Given our primary contribution was obtaining meaningful temporal embeddings, we test its effectiveness by feeding learned embedding to state-of-the-art sequential recommender models. The sequence representation ${h}$ (where, ${h}_{w+1}=\{\mathbf{z}_{1}\oplus\mathbf{z}_{2}\oplus...\mathbf{z}_{w}\}$) and the item embedding matrix $\textbf{V}=\{\mathbf{z}_{1},\mathbf{z}_{2},...\}$ are used to compute the predictive score as:

In our work we use GRU4Rec (Hidasi et al., 2016) and SASRec (Kang and McAuley, 2018) since they are the most widely adopted SRSs. In addition the learning mechanism proposed by these frameworks i.e., GRU and the transformer, are widely adopted in different variations by other state-of-the-art SRSs.

In FRSs where the main objective is to provide users with suggested items based on their historical interactions with a collection of items, the issue of non-i.i.d. data arises. For example, music streaming clients may be interested in different categories of music due to personal interests, demographics, moods etc. Thus, leveraging the heterogeneity in user behavior is of utmost interest. FL facilitates aggregating models for learning user preferences while maintaining each user’s privacy, however by straightforwardly treating interactions from all the users as i.i.d., it inevitably harms the personalization characteristics of a recommender model.

In light of this, we tackle the dilemma of interaction scarcity at the user level and non-i.i.d. data at the server level by investigating communities consisting of similar users. Intuitively, it would be beneficial to perform model aggregation within each of the user groups, such that each client model can be enhanced using only the knowledge from users with similar preferences. Though similar users can be easily identified via their interaction records or personal attributes, it will void the privacy guarantees provided by FRSs. So, we propose a semantic sampler that utilizes the shared model parameters to generate user clusters. More precisely, the semantic sampler treats the encoder model parameters of each client as its respective features, and embeds them into a low-dimensional vector representation via a stand-alone VAE model. The input to this VAE are the shared encoder model parameters (obtained in Section 4.2) of each client, obtained from encoder layer. By obtaining low-dimensional vectors withholding client-wise similarity information, we are able to avoid heavy computation cost of directly clustering the high-dimensional model parameters.

Using VAE, latent variables of a client $u$ are drawn from a prior $p(\mathbf{e}_{u})$, where $\mathbf{e}_{u}$ is the embedding vector of the client’s shared model parameters $\mathbf{m}_{u}$. Here $\mathbf{m}_{u}$ are flattened encoder layer parameters of client $u$. VAE defines a joint probability distribution $p(\mathbf{m}_{u}|\mathbf{e}_{u})$ over the input data and latent variables, with the goal of inferring the latent variables (i.e., client’s model embedding) given observed data (i.e., the client’s model parameters):

where the optimization goal can be formulated analogously to Eq.(1) using Kullback-Leibler (KL) divergence:

As such, the server is able to compute low-dimensional vector representations $\mathbf{z}_{u}$ using model parameters shared by clients. In addition to reduced dimensionality, the VAE also maps similar models closer in the embedding space.

The semantic sampler computes a low-dimensional vector representation of each client’s model parameters, as soon as they arrive at the server side. Note that in Section 5.1, vector embeddings are computed in such a way that semantically similar models will have close representations in the vector space and dissimilar clients will be mapped far apart. Such placement of model parameters in the embedding space fulfils both clustering properties (Bateni et al., 2017; Hung et al., 2017), i.e. intra-cluster maximization and inter-cluster minimization. Making use of $k$-Means (Jin and Han, 2010) algorithm to compute effective clusters, we group together similar client models. However, directly applying $k$-Means clustering incurs the following overheads: 1) the optimal value of $k$ is unknown; 2) it needs to be recomputed every time a new client has to be added; and 3) it is inefficient to synchronously update for each incoming client model.

Our asynchronous clustering module effectively addresses these challenges via a dynamic setting. After the first global epoch, using a small pool of sampled initial clients, the server trains the VAE-based semantic sampler and also generates initial client embeddings. With these initial embeddings, we run the Elbow method (Syakur et al., 2018) that uses $k$-Means clustering on the dataset, and then compute an average silhouette score (De Amorim and Hennig, 2015) for all the clusters. Subsequently, the server obtains the incoming client’s model embeddings by feeding its model parameters to the trained semantic sampler. For the subsequent epochs, we compute the Euclidean distance between cluster centroids and the embedded vector to efficiently assign/update the clustering outcome. Since the computation of the optimal clustering coefficient $k$ and the assignment of an incoming client model to an existing group are performed asynchronously to the model aggregation, the communication bandwidth of the federated server is not affected. This live computation of client's cluster, given in Algorithm 1, simultaneously supports model scalability and efficiency.

Finally, the asynchronous capability of the server allows us to update the semantic sampler model and recompute the effective number of clusters. This is achieved completely independently without incurring any overhead on communication bandwidth between the server and the clients. The dynamic nature of ReFRS architecture enables any clustering algorithm to be substituted.

Each client model at the server side is assigned a specific cluster by the clustering unit. The aggregator is responsible for aggregating all the model parameters on each individual cluster and sending the respective aggregated model to the client upon request. When the server receives a client’s model parameters, it processes them as explained in Section 5.2. Once the cluster id is obtained, the model parameter and cluster id is fed as input to the aggregator.

Model parameters, received by the server are aggregated via lines 3-5 of Algorithm 2 and distributed back to the respective clients. In order to asynchronously update clusters on the server side, we keep a copy of the last shared client models. The server updates the clusters after every two global epochs.

As a result of its strong privacy guarantees, DP has been widely adopted in FL settings as a privacy mechanism. If some information from a dataset is publicly available, DP can address the privacy leakage of data belonging to an individual. To provide privacy, most DP mechanisms add an independent random noise component to available data (Kim et al., 2021). By working only on the final parameters, it is possible to protect the privacy of training data. Unfortunately, it may not be possible to directly determine how these parameters are dependent on the training data; if the parameters are overly noisy, the worst-case analysis would undermine the usefulness of the learned model. We take the sophisticated approach of attempting to control the influence of the training data during the training process, specifically in the SGD computation. Several previous works have adopted this approach (e.g., (Song et al., 2013; Bassily et al., 2014)). To compute the SGD-DP, each step of the procedure computes the gradient $\nabla_{\theta}\mathcal{L}(\theta,z_{i})$ for a random subset of examples, clips the $\ell_{2}$ norm of each gradient, computes the average, adds noise for privacy, and takes a step in the opposite direction of the average noisy gradient.

As opposed to traditional cryptographic schemes, HE allows certain operations like addition, multiplication, and so forth to be performed directly over encrypted data without the need for decryption. When decrypted, computations produce the same results as if performed on unencrypted data. A homomorphic scheme is one that satisfies the following equation:

here, $\mathbf{w}_{1}$ and $\mathbf{w}_{2}$ are the model parameters from client 1 and 2 at the server side, $*$ represents the mathematical operation performed between the parameters and $\Psi$ represents encryption algorithm. The most commonly $\Psi$ are partially homomorphic encryption (PHE) (Morris, 2013), somewhat homomorphic (SHE) (Boneh et al., 2013), and fully homomorphic (FHE) (Brakerski et al., 2014). As we need to aggregate encrypted models with a federated setting, we use a fully homomorphic HE scheme (FHE) that offers support for an unbounded number of additive and multiplicative operations. To construct FHE structures, we apply Cheon-Kim-Kim-Song’s (CKKS) (Cheon et al., 2017) algorithm, which depends on the hardness of Learning-With-Error (LWE) (Regev, 2009). With CKKS, we can approximate arithmetic on real and floating point numbers.

We leverage large-scale datasets where each user would have multiple interactions with items for experimentation. Hence we adopted two publicly available datasets ”MovieLens 20M” (ML 20M) (Harper and Konstan, 2015) and ”Last.fm 360K” (FM 2306K) (Celma, 2010). MovieLens 20M contains 20 million interaction records for 162,000 users with a rating density of 0.52%. Here rating density means ”how many items in the dataset were rated by each user”. Last.fm dataset contains 17,559,530 interactions (tracks played) by 359,347 users, with a track played density of 0.016%. Smaller subsets of these datasets have been widely adopted by centralized recommendation literature/research (Kang and McAuley, 2018; Craw et al., 2015). The key characteristics of both datasets are summarized in Table 2. Using a smaller sample of the original dataset, we evaluate our client’s embedding model against state-of-the-art embedding models in a centralized setting. Detailed information about the smaller subsets can be found in Table 6, where MovieLens dataset is limited to 100,000 interactions, and Last.fm to 52,551. We first split the datasets into temporally sequential chunks in order to simulate sequential recommendations. Because the models must be deployed on resource-constrained end-devices, we build small sessions, each consisting of 50 interactions.

To efficiently evaluate the performance in our experimentation, we use the widely adopted ”leave-one-out” (Deshpande and Karypis, 2004) strategy. The latest interaction sequences of each user are held-out for testing, while all previous interaction sequences are used for training. The performance of ranked items is evaluated using Hit Ratio @10 (HR@10) and Normalized Discounted Cumulative Gain @10 (NDCG@10) (Wang et al., 2010; Yu et al., 2019; Sun et al., 2020; Chen et al., 2020). In sequential RS settings, HR@10 (Equation 10) is simply the number of times that the ground truth item appears among the top-10 recommendations.

where $|I^{hit}_{10}|$ is the correct number of hits among ten predictions. NDCG (Equation 13) is simply the normalization of DCG@10 (Equation 11) score with IDCG@10 (Equation 12) score. DCG penalizes relevant items being placed at the bottom and IDCG is the ideal ranking of items in descending order, according their relevance up to position 10.

where $G$ is the relevance score for item $i$ and $I^{\textbf{*}_{10}}$ represents the ideal list of items. We calculate both metrics for each client’s test data and report the average score among them.

Our implementation generally consists of the clients and a central server. The structure of client models is similar for each user and the embedding dimension $d$ for each client is set to 16. The VAE of the client’s embedding model consists of two convolution layers (Tang and Wang, 2018) with filter sizes of 32, 16 and the kernel size of 2. We restrict the approximation of the posterior using independent gaussians distribution. We test our model by setting the sequence window $w$ of multiple sizes, however since the number of interactions available for most users were low, we keep $w=16$ and the session size is kept at 100. For the recommender at the client side, any state-of-the-art model can be adopted. In our work we used GRU4Rec (Hidasi et al., 2016) and SASRec (Kang and McAuley, 2018) for two reasons. Firstly, they are the most widely adopted SRSs, Secondly, the technologies suggested by these frameworks i.e., GRU and the transformer, are widely adopted in variations by other state-of-the-art SRSs.

The VAE model used by the semantic sampler, at the server side, consists of two convolution layers (64,32) and three dense layers (16 units each). On the server side standard Gaussian distribution is used. Using the Elbow method, we determine the optimal number of clusters by setting $k$ between 1 and 100. Initially, 1,000 users were used to train the semantic sampler.

We evaluate the performance of ReFRS against three main baselines, using the large-scale datasets. Hyper-parameter settings for these federated baselines frameworks, including ReFRS are given in Table 3.

• •

  FedAvg (Sattler et al., 2019): The popular FedAvg algorithm aggregates the parameters of all client models into a single global model. In this work, each client model consists of a General Matrix Factorization (GMF) model (He et al., 2017), as adopted by FedFast (Muhammad et al., 2020).

• •

  FedFast (Muhammad et al., 2020): This method accelerates FRS tasks by applying an active aggregation method that propagates the updated models to similar clients. Each client contains multiple users, which are clustered based upon user similarity information. GMF (He et al., 2017) is used for the client model.

• •

  Federated Recommendation System-1 (FRS-1) : FRS-1 is the basic setting of ReFRS. It consists of a client model, using GRU4Rec as a recommender. Here, the client learns recommendations for each user separately, without the guidance of a federated server.

• •

  Federated Recommendation System-2 (FRS-2) : FRS-2 is the second basic setting of ReFRS, in which the federated server adopts FedAvg to aggregate shared models into a single global model. The client uses GRU4Rec as a recommender in FRS-2.

• •

  FedAvg-GRU4Rec : This setting adopts FedAvg algorithm to enable decentralized learning of GRU4Rec (Hidasi et al., 2015) algorithm. GRU4Rec utilizes GRU layers to model user interaction sequences per session.

• •

  FedAvg-SASRec : This setting adopts FedAvg algorithm to enable decentralized learning of SASRec (Kang and McAuley, 2018) algorithm. SASRec uses multi-head attention in order to recommend the next item.

• •

  FedFast-GRU4Rec : This setting of FedFast adopts GRU4Rec as the recommender model.

• •

  FedFast-SASRec : This setting of FedFast adopts SASRec as the recommender model.

• •

  ReFRS-GRU4Rec : This setting of ReFRS adopts GRU4Rec to compute next item recommendation.

• •

  ReFRS-SASRec : This setting of ReFRS adopts SASRec as the recommender model.

To show the effectiveness of ReFRS’s client module, we also compare it against the following state-of-the-art centralized sequential recommender models, using smaller datasets. All hyper-parameters are set following the original papers.

• •

  AutoInt (Song et al., 2019) learns feature interactions using the multi-head self-attentive neural network

• •

  GRU4Rec (Hidasi et al., 2015) utilizes GRU layers to model user interaction sequences per session.

• •

  Caser (Tang and Wang, 2018) uses horizontal and vertical convolutional to capture high-order Markov Chains.

• •

  SASRec (Kang and McAuley, 2018) uses multi-head attention in order recommend next item, for sequential recommendation task.

• •

  BERT4Rec (Sun et al., 2019) adopts a Cloze objective loss, on top of bidirectional self-attention mechanism, for sequential recommendation task.

• •

  HGN (Ma et al., 2019) uses hierarchical gated networks for capturing both long-term and short-term user interests.

• •

  FDSA (Zhang et al., 2019) generates feature sequences and model’s feature transition patterns using a feature level self-attention block.

• •

  $\textbf{S}^{3}$-Rec (Zhou et al., 2020) utilize the intrinsic data correlation to derive self-supervision signals and enhance the data representations via per-training. All hyper-parameters are set following the suggestions from the original papers.

We evaluate the performance of ReFRS in federated settings against FedAvg and FedFast. In order the effectiveness of our embedding method we upscale the basic General Matrix Factorization (GMF) based recommender approch adopted by FedFast and FedAvg. We replace basic GMF model by state-of-the-art GRU4Rec (Hidasi et al., 2015) and SASRec (Kang and McAuley, 2018) models. In our work we use GRU4Rec and SASRec since they are most widely adopted SRSs. In addition the learning mechanism proposed by these frameworks i.e., GRU and the transformer, are widly adopted in different variations by other state-of-the-art SRS.

In contrast to the FedFast paper, (Muhammad et al., 2020), which uses a small-scale dataset to evaluate their semantic models, in our work we use datasets that are over 200 percent larger. This approach tests the scalability of the proposed frameworks and simulates the real world better. This experiment evaluates the performance of all baselines as the number of client devices are increased. We divide ML and FM datasets into subsets containing 10%, 20%, 30%, 40%, 50% and 100% of the actual users. These subsets are generated at random. The HR@10 and NDCG@10 scores of ReFRS against all the base lines are given in Table 4.

In Table 4 all settings of the FedAvg algorithm constantly under performs our proposed approach. This is because, a large number of users in our datasets do not have enough interactions for the RS to effectively predict user’s long term interests and change in interaction patterns. This lack of interaction data in a large number of users causes lower performance of the global model as all user models are aggregated together. Global generalization of models improves the performance in the case of FedFast. However, since their model generalization is based upon aggregating models of users with similar Bios, they fail to outperform both settings ReFRS which groups users based upon model parameters. This shows that the semantic sampler in ReFRS maps similarly behaving user models close in the embedding space. ReFRS with SASRec performs better than GRU4Rec, indicating that attention-based techniques more accurately synthesize user behavior from embeddings, than recurrent neural networks. Note, shared model gradients do not provide any information regarding user behavior, rather each gradients only carry some effect on the input sequence (Sundararajan et al., 2017) (models with similar gradients will have the same effect). Hence, no personal information is leaked at the server side.

FL assures users some level of privacy since the data is not directly sent to the central server (McMahan et al., 2017). However, it is still possible to infer some information from the shared model parameters by the client. This may lead to the leakage of sensitive or private information. For this reason, to the effect of different privacy mechanisms on ReFRS, we adopt two widely used privacy mechanisms i.e., Differentially Private (DP) Stochastic Gradient Descent SGD and Homomorphic Encryption (HE). The DP noise multiplier is adjusted to regulate the amount of noise added during training. As a general rule, more noise corresponds to better privacy and less utility. In our experiments and to obtain rigorous privacy guarantees (Balle and Wang, 2018), the value is set to 0.3. We evaluate the performance of ReFRS-GRU4Rec and ReFRS-SASRec using both encryption mechanisms.

Table 5 shows the effect of DP-SGD and HE on our framework. The results show degradation in the results when DP-SGD is used. This is because the inclusion of noise during training of the client model in DP-SGD, makes the reconstruction task inaccurate. In addition, the noisy model parameter makes the semantic server improperly group client models. Therefore, the model fails to capture valuable client interaction patterns. However, in the case of HE a secure message is sent to the server, on which mathematical operations can be performed precisely. This does not effect either the client model or the semantic server. Hence, we suggest HE should be adopted as encryption mechanism when semantic sampling is evolved at the server side. The key sharing strategy adopted here is the same as in federated learning literature i.e. the private key distributed to each client is the same, distributed by a third party (unknown by the server and top-level clients).

ReFRS is designed for federated settings, where the central server has no user interaction data available. However, in order to further demonstrate the effectiveness of ReFRS’s client model, we compare it against state-of-the-art centralized SRSs. For this experiment we test the recommendation performance of ReFRS using SASRec as the recommender model of our client model. We select two smaller subsets of the previously adopted datasets i.e., MovieLens 100K (ML 100K) and Last.fm 1K (FM 1K) and evaluate performance of ReFRS against state state-of-the-art centralized SRSs. ML 100K contains 100,000 interactions of 1,682 users on 943 items, while FM 1K have 52,551 interactions of 1,090 users on 3,646 items.

The statistics of the datasets are given in Table 6.

Table 7 shows that our model performs comparably to state-of-the-art centralized SRSs. This is because the recommender model on each mobile device is personalized, which can effectively address the issues of biases in the centralized models. Central models are often critiqued as being “single thought” models that favors only the users with rich interaction data, leading to unsatisfactory performance for the long-tail users. Traditional centralized machine learning relies mainly on generic models: models tuned to an average target population. However, the ’good’ performance by these generic models does not necessarily translate to each individual. For MovieLens dataset, BERT4Rec performs comparably to our model. This shows that our model can also capture repeated behaviours (rating similar genre movies) of users in the ML dataset. For the Last.fm dataset, where the users’ interest evolve over time, ReFRS along with $S^{3}$-Rec are able to effectively capture higher-order interaction behaviors.

In real-time simulation settings, input into the client model are the next stream of user interactions. With the inclusion of new user interactions or new user clients, global groupings of client models are updated. Figure 7 shows the dynamic update of user grouping as the latest sequences of interactions for each user are added. Changes in the number of clusters over time by the ReFRS server depicts its adaptability to change and acceptance to scalability. ReFRS dynamically caters new interactions, as well as introduction of new clients.

An end-device’s memory and computation power must be taken into account when running a deep learning model. Apart from battery consumption, there are three aspects to consider here: the amount of space the model takes up in your app bundle (number of items to be stored at a time and the space taken by their embedded vectors), the amount of memory it uses at runtime (total number of parameters), and how fast the model runs. Table 8 shows the average on device memory consumption of ReFRS against GMF based FRS. The computation time represents the time taken by the client embedding module for a single batch training. Simulations of our experiments used CPUs with 2.2 GHz processing power, which is equal to any CPU found on most common android devices. Since ReFRS actively swaps in new interaction sessions with the old ones and does not require a full list of embedded items to update the client model, its memory consumption is far less than any other GMF-based federated model.