SecEmb: Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding

Thanks for your insightful comment and recognition of our work. Hope our response below could address your concerns.

Q1: I will mention that the Theorems provided and proven in the supplementary material should be summarized in the main body.

Ans: Thanks for your suggestion. We will move Theorem F.1 and F.2 to the main body to highlight our theoretical insights.

Q2: Questions on problem setting – mapping from X,Y to P,Q and then going from P,Q to the recommendation value & relationship between R and Y.

Ans: We will add more explanation in 3.1. Problem Statement to make the setting clearer. P and Q refer to the user and item embedding respectively, while X and Y refer to the user and item attributes respectively. P and Q are matrices that encode the user or item ids into embeddings. X and Y represents attributes of users or items, such as demographic details, genre, or price.

For example, in DeepFM, we map the user id into a vector $p\in \mathbb{R}^d$ using matrix P, and map the item id into a vector $q\in \mathbb{R}^d$ using matrix Q. Similarly, X and Y are converted into embedding matrices $V_x\in \mathbb{R}^{l_x\times d}$ and $V_y\in \mathbb{R}^{l_y\times d}$, where $l_x$ and $l_y$ are the number of user and item attributes. Then the embeddings $p$, $q$, $V_x$, and $V_y$ are concatenated together and go through several hidden layers to obtain the final prediction.

Below we further provide explanations of R, Y, and X:

• R represents the ratings users assign to items (the item and user attributes are NOT included). $R_u$ is the collection of (item id, rating) for user u.
• Y denotes item attributes, such as price and genre. $Y\in \mathbb{R}^{m\times l_y}$ gives the attributes for each item, and $y_i\in \mathbb{R}^{l_y}$ is the attributes for item i.
• X is the attribute of users, such as their age. $X\in \mathbb{R}^{n\times l_x}$ gives the attributes for each user, and $x_u\in \mathbb{R}^{l_x}$ is the attributes for user u.

Therefore, R, X, and Y provide distinct information, ensuring they complement rather than overlap with each other.

Q3: The novelty simply revolves around applying a new secure retrieval and aggregation method fit for existing latent RecSys methods.

Ans: Our work aims to construct a lossless and efficient secure training protocol for embedding-based RecSys. For security, we would like to ensure that the server learns nothing about individual gradients except the aggregated results during federated training. To achieve this goal, existing FL protocols typically adopt full model downloading and SecAgg, which incur significant communication and computation cost.

This paper designs an efficient protocol based on the properties of embedding-based RecSys: 1) users typically interact with only a small fraction of available items; 2) only the interacted item embedding are relevant for prediction, and thus the gradient of item embedding is a sparse matrix. Accordingly, we design a secure and lossless protocol that is efficient both computationally and communicationally. In Table 10 (Appendix J) we compare SecEmb with existing protocols, showing the distinct advantage of SecEmb in terms of efficiency, security, and utility for resource-constrained edge devices, highlighting our contribution of significant speedup while ensuring accuracy and security.

Note that it is a non-trivial task to simultaneously ensure security and succinct user computation & communication cost (i.e., cost depends linearly on the number of non-zero elements in each user’s update, and independent of or logarithmic in the total parameter size), and to the best of our knowledge, there is no work that simultaneously achieves the two goals for embedding-based models (including LM and RecSys). We address the problem by a novel construction of FL training algorithm for embedding-based RecSys, which can be extended to the training of other large embedding models, such as language model (see Appendix L.2. and response to Reviewer EqFa’s Q6).

Q4: What are the compression rates used for the other message compression methods? Are the hyper-parameters consistent across the methods?

Ans: The compression rates for other message compression methods, given by the Reduction Ratio in Table 2 Section 5, are computed as a result of:

• For SVD and CoLR, based on the rank of the reduced item embedding update matrix (Table 9, Appendix I). The ranks are chosen to ensure a comparable reduction ratio with SecEmb while preserving utility.
• For Bit8quant and Ternquant, based on the bit size per value of the quantized embedding udpates. Note that the bit size to represent a single value is fixed for each quantization method.

The hyper-parameters for SecEmb and other message compression methods remain consistent across the models and datasets, using those given by Table 7 in Appendix I.

Thanks for your valuable comment and suggestions. Hope our response below could address your concerns.

Q1: The criteria for dataset splitting should be added.

Ans: We randomly split the ratings for each user into training and testing set.

Q2: More large-scale datasets are desired & Add evaluation on sequence recommendation models

Ans: We add experiments on the full Amazon datasets (https://cseweb.ucsd.edu/~jmcauley/datasets/amazon/links.html). After filtering out users with less than 3 ratings to train sequence recommendation model, we have 9,267,503 items and 6,775,277 users.

We test two sequence models: Caser[1] and SASRec[2] (using hyperparameters in [1] and [2]), with results presented in Table R1. SecEmb reduces the upload communication cost by up to 2500x under huge item size (9 million+) and highly sparse data (density<0.002‰) while maintaining accuracy.

[Table R1. Accuracy and Reduction Ratio (R.R.) using sequence models on Amazon dataset.]

[1] Tang, J., & Wang, K. (2018). Personalized top-n sequential recommendation via convolutional sequence embedding. In Proceedings of the eleventh ACM international conference on web search and data mining (pp. 565-573)

[2]Kang, W. C., & McAuley, J. (2018). Self-attentive sequential recommendation. In 2018 IEEE international conference on data mining (ICDM) (pp. 197-206).

Q3: The comparison with Kvsagg should be added.

Ans: We will add the comparison as follows:

• Kvsagg leaks more information to the server than SecEmb. Beyond aggregated results, KvsAgg exposes the exact number of clients who rated each item within a batch, whereas SecEmb limits the server's knowledge to the aggregate alone.
• Kvsagg has a minor failure rate, occasionally yielding inaccurate aggregation results, whereas SecEmb ensures error-free aggregation.
• Kvsagg incurs higher communication costs than SecEmb. Kvsagg's cost scales with the union of all participating users' rated items, whereas SecEmb's cost scales with each single user's rated items. Table R2 presents the upload communication cost of the two methods, showing SecEmb's communication benefits.

[Table R2. Upload communication cost (in MB) using MF.]

Q4: Issues of two server setting

Ans: Two server setting is common in MPC protocols and has been adopted in industry by companies such as Goolge and Apple (see Response to Reviewer TCtN's Q2). In SecEmb, one of the servers could be recommendation service provider, and the other could be a governmental organisation or a privacy service provider. Both parties have sufficient motivation to train a strong model and perform the computation correctly.

Compared with two server protocols, the single server secure computation solutions generally incur significant overhead. They either require multiple rounds of communication and heavier user computation[3], or rely on computationally intensive homomorphic encryption[4]. While it becomes inefficient under a single server setting, we can relax the two non-colluding server assumption using a multi-party distributed point function (see Response to Reviewer TCtN's Q2).

[3]Bonawitz, K., ... & Seth, K. (2017). Practical secure aggregation for privacy-preserving machine learning. In proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (pp. 1175-1191).

[4]Chai, D., ... & Yang, Q. (2020). Secure federated matrix factorization. IEEE Intelligent Systems, 36(5), 11-20.

Q5: The font size in most figures is somewhat small.

Ans: Thanks for pointing out. We will refine the figures to enlarge the font size.

Q6: The distinction between X, Y, and P, Q is unclear in Section 3, and the symbols x and i are somewhat confusing in terms of their meanings in Section 4.

Ans: P and Q are embedding matrices that encode the user or item ids into embeddings. X and Y represents attributes of users or items, such as demographic details, genre, or price. (see Response to Reviewer sPkh's Q2)

i denotes the target item id, while x denotes any item id fed into the point function. The point function outputs non-zero value only when x=i.

Q7: Compared to downloading the full embedding table, does this approach result in any loss?

Ans: SecEmb does NOT result in any loss compared with full embedding download, as long as users utilize only the embeddings of the target and previously interacted items to predict the rating or likelihood (the embeddings of other items are irrelevant). Most embedding-based RecSys models satisfy this criterion (see Response to Reviewer TCtN's Q1).

Thanks for your insightful comment and valuable suggestions. Hope our response below could address your concerns.

Q1: The evaluation criterion for utility in this paper is relatively outdated.

Ans: Our paper focuses on the rating prediction task, and thus utilizes RMSE to measure the discrepancy between predicted and actual ratings. We have added experiments to evaluate the HR and NDCG, with a subset of results presented in Table R1, showing the superior performance of SecEmb over baselines. In response to Reviewer WwRR's Q2, we also present the experiment results in terms of HR and NDCG for sequence recommender system.

[Table R1. Accuracy on ML1M using MF.]

Q2: The paper’s original theoretical innovations are relatively limited.

Ans: We would like to highlight the theoretical contributions of our work as follows:

• Reduction of User Overhead: Existing SecAgg protocols incur user communication and computation overhead linear in the item size $m$, while we theoretically show that our protocol achieves exponential reduction to $\log m$ (Section 4.4.1).

• Security analysis: We provide a rigorous theoretical proof that our optimized construction of SecEmb maintains security, i.e., the server learns nothing except the updated models (Appendix F). We will move Theorem F.1 and F.2 to the main body to highlight our theoretical insights.

To the best of our knowledge, we are the first to achieve both security and minimal user overhead for embedding-based models, demonstrating efficiency benefits both theoretically and practically, while remaining lossless in principle and practice.

Q3: The dimensional settings of NCF vary across different datasets

Ans: For NCF we adjusted the embedding sizes based on each dataset's characteristics, but the comparison is fair as we use consistent hyperparameters (including dimension) for both SecEmb and the baselines. To further validate our approach, we added experiments to set the embedding size for ML100K, ML1M, and Yelp as 24, matching that of ML10M and ML25M. The results, presented in Table R2, demonstrate similar observations that SecEmb maintains utility and reduce upload communication cost by up to 76x for NCF.

[Table R2. RMSE and Reduction Ratio (R.R.) for NCF under d=24.]

Q4: Some essential related works, such as FedMF and LightFR, are missing.

Ans: We will add more discussion of both works in our paper as follows:

• FedMF ensures privacy with HE techniques. Compared with SecEmb, FedMF incurs substantial computation overhead, and fails to simultaneously reduce user computation & communication cost and ensure security.

• LightFR improves the efficiency by binarizing continuous user/item embeddings through learning-to-hash, but it suffers utility loss in principle and incurs overhead linear in item size m (as opposed to SecEmb's exponential reduction).

Q5: Does the experiment of MF and FM exist redundancy?

Ans: In our framework, MF updates involve only item embeddings, while FM updates encompass both item embeddings and item feature embeddings. This distinction results in differing parameter sparsities between the two models since item feature embeddings are not generally sparse (see Table 8, Appendix I). By evaluating SecEmb's efficiency and utility across models with varying item embedding proportions and thus update sparsity ratios, we provide a thorough assessment of its performance.

Q6: Necessity of conducting the related experiments on language models

Ans: We aim to show that our framework is applicable to the federated training of language models by substituting rated item IDs with target token IDs in SecEmb's algorithm. Roughly speaking, each user encodes the relevant token ids (i.e., token ids appear in their local dataset) with FSS keys, and the server computes secret shares of token embeddings for embedding retrieval or aggregates the secret shares of token embedding updates for SecAgg. It helps to reduce the overhead since the tokens appearing in each user’s local dataset are typically a small subset of the entire vocabulary. Table 17 shows that SecEmb achieves an overhead reduction ratio between 1.06 and 1.55 for full-parameter fine-tuning, and it can achieve higher reduction ratio when combining with parameter-efficient finetuning (e.g., up to 30x reduction when applying LoRA on Llama3-8b).

Thanks for your insightful comment and positive rating of our paper. Hope our response below could address your concerns.

Q1: Elaboration on "only the embeddings for interacted items are relevant for model updates"

Ans: It works for recommender systems (RS) based on item embeddings, as long as users utilize only the embeddings of the target and previously interacted items to predict the rating or likelihood (the embeddings of other items are irrelevant). In other words, to predict $r_{ui}$, user $u$ only utilizes the embeddings of item $i$ or previously interacted items $I_u$. Most embedding-based RSs satisfy this criterion, including but not limited to:

• Latent factor-based collaborative filtering RSs and their extensions, such as MF, NCF, FM, and DeepFM.
• Sequential RSs based on item embeddings, such as CNN-based models (Caser), RNN-based models (GRU4Rec), and Attention-based models (SASRec).

Q2: Assumption on two non-colluding servers.

Ans: Two non-colluding server is a common assumption in MPC protocols [1][2][3], and has been adopted in industry. For example, Prio[1] has been used by Google and Apple to measure the effectiveness of Covid-19 exposure-notification apps on iOS and Android[4] and improve the iOS Photos app[5]. In SecEmb, one of the servers could be recommendation service provider, and the other could be a governmental organisation or privacy service provider.

Compared with two server protocols, the single server secure computation solutions generally incur significantly higher communication and computation cost. They either require multiple rounds of communication and heavier user computation[6], or rely on computationally intensive homomorphic encryption[7].

The two non-colluding servers assumption can be relaxed using m-party distributed point function (m>2), allowing collusion among up to m-1 parties[8]. Each user generates m FSS keys for their updates, which are distributed to m servers for aggregation and reconstruction. However, this protocol has less overhead reduction than the two server setting, since user overhead depends sub-polynomially in item size $O(\sqrt{m})$, rather than logarithmically $O(\log m)$ in the two server case. We leave further reduction to future research.

[1]Corrigan-Gibbs, H., & Boneh, D. (2017). Prio: Private, robust, and scalable computation of aggregate statistics. In 14th USENIX symposium on networked systems design and implementation (pp. 259-282).

[2]Mohassel, P., & Zhang, Y. (2017). Secureml: A system for scalable privacy-preserving machine learning. In 2017 IEEE symposium on security and privacy (SP) (pp. 19-38).

[3]Boneh, D., ... & Ishai, Y. (2021). Lightweight techniques for private heavy hitters. In 2021 IEEE Symposium on Security and Privacy (SP) (pp. 762-776).

[4]Apple and Google. (2021). Exposure Notification Privacy-preserving Analytics (ENPA) white paper.

[5]https://machinelearning.apple.com/research/scenes-differential-privacy

[6]Bonawitz, K., ... & Seth, K. (2017). Practical secure aggregation for privacy-preserving machine learning. In proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (pp. 1175-1191).

[7]Chai, D., ... & Yang, Q. (2020). Secure federated matrix factorization. IEEE Intelligent Systems, 36(5), 11-20.

[8]Boyle, E., Gilboa, N., & Ishai, Y. (2015). Function secret sharing. In Annual international conference on the theory and applications of cryptographic techniques (pp. 337-367).

Q3: Application to unknown sparsity.

Ans: SecEmb supports unknown sparsity, where the server lacks prior knowledge of the sparsity ratio. Each user uploads a self-defined number of FSS keys based on their own data sparsity, which can exceed the number of interacted items to obscure it. The server aggregation still proceeds correctly with varying FSS key counts across clients. Appendix K.5. shows that SecEmb effectively reduces overhead when the density of item embedding update is within 50% in general cases. This approach extends to other sparse embedding update settings (with unknown sparsity ratio), such as language model.

Q4: Abrupt introduction of l_x & Vague explanation for "remaining parameters theta"

Ans: Thanks for pointing out and we will revise the paper accordingly. $l_x$ is the number of user features. Remaining parameters $\theta$ refer to the parameters other than user and item embeddings. For example, $\theta$ in DeepFM is the collection of: 1) parameters in hidden and output layers, and 2) embeddings for user and item attributes (rather than user or item ids).

Q5: Robustness to local devices drop out.

Ans: For n participants, SecEmb is robust to up to n-1 dropouts. It has one communication round for private embedding retrieval and another round for secure update aggregation. If users drop out in the second round, servers could still aggregate the gradients for remaining users correctly (see Appendix L.3).