SecEmb: Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
Authors: Peihua Mai
Youlong Ding
Ziyan Lyu
Minxin Du
Yan Pang
Venue: ICML 2025 poster (2025)
Keywords: Secure aggregation
recommender system
federated learning
Primary area: social_aspects->privacy
TL;DR: A secure federated learning method for recommender system with resource-constrained devices

Abstract: Federated recommender system (FedRec) has emerged as a solution to protect user data through collaborative training techniques. A typical FedRec involves transmitting the full model and entire weight updates between edge devices and the server, causing significant burdens to edge devices with limited bandwidth and computational power. The sparsity of embedding updates provides opportunity for payload optimization, while existing sparsity-aware federated protocols generally sacrifice privacy for efficiency. A key challenge in designing a secure sparsity-aware efficient protocol is to protect the rated item indices from the server. In this paper, we propose a lossless secure recommender systems with on sparse embedding updates (SecEmb). SecEmb reduces user payload while ensuring that the server learns no information about both rated item indices and individual updates except the aggregated model. The protocol consists of two correlated modules: (1) a privacy-preserving embedding retrieval module that allows users to download relevant embeddings from the server, and (2) an update aggregation module that securely aggregates updates at the server. Empirical analysis demonstrates that SecEmb reduces both download and upload communication costs by up to 90x and decreases user-side computation time by up to 70x compared with secure FedRec protocols. Additionally, it offers non-negligible utility advantages compared with lossy message compression methods.

SecEmb: Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
Peihua Mai
Youlong Ding? 2* Ziyan Lyu
Minxin Du Yan Pang'
Abstract
1. Introduction
Personalized recommendation systems (RecSys) model the interactions between users and items to uncover users' in- terests. To understand the underlying preferences of users and properties of items, various model-based approaches have been developed to learn hidden representations of both users and items (Koren et al., 2009; Xue et al., 2017; Rendle, 2010). These methods embed users and items into fixed-size latent vectors, which are then used to predict interactions. The parameters of these latent vectors known user and item embeddings.
Federated recommender system (FedRec) has emerged as a solution to protect user data through collaborative training techniques. A typical Fe- dRec involves transmitting the full model and entire weight updates between edge devices and the server, causing significant burdens to devices with limited bandwidth and computational power. While the sparsity of embedding updates provides opportunity for payload optimization, existing sparsity-awand aware federated protocols generally sac- rifice privacy for efficiency. A key challenge in designing a secure sparsity-aware efficient proto- col is to protect the rated item indices from the server. In this paper, we propose lossless secure recommender systems on sparse embedding up- dates (SecEmb). SecEmb reduces user payload while ensuring that the server learns no informa- tion about both rated item indices and individual updates except the aggregated model. The pro- tocol consists of two correlated modules: (1) a prrvacy-preservigg embedding retrieval module that allows users to download relevant embed- dings from the server, and (2) an update aggrega- tion module that securely aggregates updates the server. Empirical analysis demonstrates that SecEmb reduces both download and upload com- munication costs by up to 90x and decreases user- side computation time by up to 70x compared with secure FedRec protocols. Additionally, it offers non-negligible utility advantages compared with lossy message compression methods.
The development of personalized recommendation systems (RecSys) relies heavily on collecting user profiles and behav- ioral data, such as gender, age, and item interactions. How- ever, the sensitive nature of this information often makes users hesitate share it with service providers. Recent advancements in edge computing have provided poten- tial solution through federated learning (FL), which allows users to collaboratively train models on their local devices without exposing personal data (McMahan et al., 2017). In a typical federated recommender system (FedRec), edge devices download the model from the server, perform local training, and upload weight updates for aggregation. During update aggregation, plaintext gradients
reveal user infor- mation. To mitigate this risk, secure aggregation (SecAgg) (Bonawitz et al., 2017) is adopted to prevent the server from inspecting individual updates during training.
Despite its effectiveness in preserving privacy, the above paradigm suffers significant communication and computa- tion overheads as it requires transmission of the full model and complete updates (Bonawitz et al., 2019). This issue becomes particularly problematic in latent factor-based Rec- Sys, where the payload scales linearly with the number of items, potentially leading to substantial burden on resource- constrained edge devices with: (1) limited communication bandwidth, as the communication bandwidth between edge devices and the central server is often constrained; and (2) limited user computational power and storage, since edge devices generally have limited processing capabilities, mem- ory, and storage compared to centralized servers.
'Equal contribution 'National University of Singapore, Singa- pore HHebee University of Jerusalem, Jerusalem, Israel 'NUS (Chongging) Research Institute, Chongqing, China 'Hong Kong Polytechnic University, Hong Kong SAR, China. Correspondence to: Yan Pang <jamespang @ muss.cdu.sg>.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Fortunately, users typically interact with only a small sub-

---

SecEmb: Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
set of available items in practice, which presents two key opportunities for payload optimization. First, only the em- beddings of the items a user interacts with are relevant for model updates. As a result, users can retrieve and store only these relevant item emheddings, significantly reducing computational and storage overhead. Secondly, the update vector is highly sparse that only a small subset of the item embeddings are non-zero. Therefore, it is desirable to make the per-user communication and computation succinet, i.e., independent of or logarithmic in the item size.
as well as the correlation between privacy-preservvng em- bedding retrieval and update aggregation modules.
(3) Empirical studies demonstrate that SecEmb reduces both download and upload communication costs by up to 90x and decreases user-side computation time by up to 70x compared with FedRec utilizing the most efficient SecAgg protocol, with non negligible utility advantages over lossy message compression schemes.
2. Related Work
A key challenge in designing sparsity- aware efficient Fe- dRec is to ensure that the indices or coordinates of non-zero elements remain hidden from the server. Existing sparsity- aware FL. protocols reduce communication overhead at the cost of increased privacy leakage (Lin et al., 2022; Liu et al., 2023; Lu et al., 2023), they inevitably reveal the coordi- nates of non-zero elements or significantly narrow the set of potential non-zero updates. Such coordinate information is particularly sensitive in RecSys, as it directly indicates which items a user has rated. This raises a critical question: Can we achieve succinct user communication and computa- tion cost in FedRec, while ensuring that the server learns no information about both the rated item indices and user updates except the aggregated model?
2.1. Cross-User Federated Recommender System
In recent years, federated recommender system (FedRec) trained on individual users has gained growing interest in research community. FCF (Ammad-Ud-Din et al., 2019) and FedRec (Lin et al., 2020) are among the pioneering implementations of federated learning for collaborative fil- tering based matrix factorization. Privacy guarantees enhanced through the application of cryptographic meth- ods to the transmitted gradients (Chai et al., 2020; Mai & Pang, 2023). FedMF (Chai et al., 2020) ensures privacy with homomorphic encryption (HE) techniques, while in- curring substantial computation overhead. LightFR (Zhang et al., 2023) sacrifices utility for efficiency by binarizing continuous user/item embeddings through learning-to-Be to-hash. Difacto (Li et al., 2016) introduces a distributed factoriza- tion machine algorithm that is scalable to a large number of users and items. FedNCF (Perifanis & Efraimidis, 2022) is a federated realization of neural collaborative iltering (NCF), where secure aggregation is leveraged to protect user gradients. FMSS (Lin et al., 2022) proposes federated recommendation framework for several recommendation algorithms based on factorization and deep learning. (Rab- bani et al., 2023) and (Xu et al., 2022) improve the training efficiency for edge device using locality-sensitvv hashing (LSH) techniques (Chen et al., 2020; 2019). Despite the de- velopment various algorithms for FedRec systems, there is a lack of research on designing sparsity-awart aware efficient FedRee while simultaneously ensure privacy and utility.
In this paper, we address the problem by proposing a sparsity-aware secure recommender systems with large em- bedding updates (SccEmb). The implementation is available at https///gitubb.com/Nun cwwp////issssraaaiicacy/eeeetet Our SecEmb consists of two correlated modules: (I) a
embedding retrieval module that allows users to download relevant embeddings from the server, and (2) an update ag- gregation module that securely aggregates updates at the server. Our protocol is efficient, secure, and lossless:
Efficient edge device update. SecEmb achieves suc- cinct download and upload communication, with op- timized user computation and memory costs as opera- tions are performed only on rated item embeddings. ppeeevypr model training. Both rated item indices and user updates (including non-zero embed- ding index and their gradient values) remain hidden from the server throughout the training process. Lossless message compression. Unlike dimension reduction or quantization methods, SecEmb reduces communication costs without compromising accuracy.
2.2. Secure Aggregation for Machine Learning
Secure Aggregation (SecAgg) computes the summation of private gradients without revealing any individual updates. (Bonawitz et al., 2017) introduces secure aggregation pro- tocol for FL, leveraging combination of pairwise masking, Shamir's Secret Sharing, and symmetric encryption tech- niques. (Bell et al., 2020) reduces the communication and computation overhead to depend logarithmic in the client size. FastSecAgg (Kadhe et al., 2020) designs a mecti- sharing protocol based on Fast Fourier Transform save computation cost. SAFELearn (Fereidooni et al., 2021) de- signs secure two-party computation protocol for efficient
The contribution of our work can be summarized as follows:
(1) Leveraging the sparsity of embedding updates, we de- velop a lossless efficient FedRee training protocol that achieves succinct user communication and computation costs, while ensuring the privacy of individual updates.
(2) We further optimize the payload of SecEmb by exploit- ing the wise sparsity of the embedding update matrix
2

---

SecEmb: Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
FL implementation. LightSecAgg (So al., 2022) reduces the computation complexity via one-shot reconstruction of aggregated mask. The two-server additive secret sharing (ASS) protocol (Xiong et al., 2020) represents the most effi- cient SecAgg approach in terms of computation and com- munication complexity. Refer to Table 6 for the complexity of existing SecAgg algorithms. However, current Agg protocols incur communication costs that scale linearly with model size, and existing attempts on sparse update aggre- gation (Ergun et al., 2021; Liu et al., 2023; Lu et al., 2023) fail to ensure security for individual updates (including both indices and values of non-zero updates).
(2) The feed-forward layers within a deep neural network model.
In each training round, users locally update their private pa- rameters 2 and upload their updates of public parameters ge, to the server. To safeguard the privacy of individual gradients, the server employs SecAgg to aggregate the gra- dients from all active clients and update the public model θ,
3.2. Function Secret Sharing
Our protocol builds on function secret sharing (FSS) (Boyle et al., 2015; 2016) optimize the communication payload. FSS secret shares a function f {0,1)" abelian group G. into two functions fi, f2 such that: (I) f(z) = =' fa( for any x, and (2) each description of fi hides f.
3. Background and Preliminaries
G, for some
3.1. Problem Statement
In FedRec, a number of users want to jointly train a recom- mendation system based on their private data. Denote U = {ui, u2,..., uh.) } as the set of users and I = {i,, i2, ..., } as the set of available items. Each user u E 2/ has a private interaction set R., In denotes the set of items rated by user u and Tu, denotes the rating user u gives to item: i. Denote X E RR and Y E mgxl as the user and item feature matrix, respectively, capturing user and item attributes such demographic de- tails, genre, price. Note that R. reflects user-item in- teractions, excluding these auxiliary features. Our goal is to generate a rating prediction that minimizes the squared deviation between actual and estimated ratings.
Definition 3.1 (Function Secret Sharing). A function secret sharing (FSS) scheme with respect to a function class F is pair of efficient algorithms (FSS.Gen, FSS Eval):
(ú E I C [m]] x IR, where
ESS.Gen(1*., f): Based on the security parameter 1 and function description f. the key generation algo- rithm outputs a pair of keys, (k1, k2).
FsK, Based on key k; and input x e {0, 13", the evaluation algorithm outputs party i's share of f(x), denoted as f((z). fz( and fa(x) form additive shares of f(x).
We focus on class of RecSys that models oow-dineniional latent factors for user and items (Koren et al., 2009; Xue et al., 2017; Rendle, 2010). The recommender fits model f comprising of d-dimensional latent factors (or embeddings) for user P E Raxd and item Q E Rm along with the remaining parameters 0. Denote pu. E I&d and qi E Rd as the latent factors (or embeddings) for user u and item i. A general form of the rating prediction can be expressed as:
FSS scheme should satisfy the following informal properties (defined formally in Appendix B.2):
Correctness: Given keys (A1, k2) of function f F. it holds that FSS. FSS.EEvl(K), + FSS. A.S..Eval(K2,. .)) fzr) for any x.
Security: Given keys (k1, k2) of a function f E F, a cnaputttioonlly-bbundee
adversary that learns either ki or li2 gains no information about the function S. except that f E F.
Fu, = [Taa yis Prey qs, 0),
where zu E R and y/ E R/ denote the feature vector for user u and item i, and a, the estimated prediction for user on item i.
A naive form of FSS scheme to additively secret share each entry in the truth-table of f. However, this approach results in each share containing 2n elements. To obtain polynomial share size, nontrivial scheme of FSS has been developed for simple function classses, e.g., point functions (Boyle et al., 2015; 2016). Our approach utilizes the ad- vanced FSS scheme for the point function. In the following, we provide the formal definition of point function.
Denote 1(-) as a general loss function. The model is trained by minimizing:
C
Σ Irra,s Pa.i) U,S
The remaining parameters 0 typically include but are not limited to: (1) Feature extractors that convert user and item feature vectors into fixed size representations, denoted as Fz TR/ -> xla and Fg R.v -> Rloxd, respectively.
Definition 3.2 (Point Function). For a E {0, 13" and 3 e G, the point function fa.s : {0,1]" + G is defined as fa,a(a) = B and f())( = 0 for x + a.
3

---

SecEmb: Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
4. Methodology
users to download targeted embeddings from the server without exposing the corresponding item indices.
Observing that the public gradients primarily consist of highly sparse item embedding updates, we propose SecEmb, secure FedRec protocol optimized to reduce the costs associated with item embeddings. Figure 1 illustrates the design of SecEmb, which is comprised of two modules: (1) a preeecciin embedding retrieval module and (2) an update aggregation module.
Our key idea is to encode the rated item go E R into some point functions. Then we can construct a 2-server private retrieval scheme based on the function secret sharing (FSS) of these point functions. Suppose the user rates m items. The private retrieval process can be performed using the following steps:
Encode rated item with a point function, g:" + Su,i- User u begins by encoding each rated item E [m]]] with a point function fu. : I + G, for some abelian group G. The function fu,s takes an item id x E I as input and outputs (x) =
Step 1:
Uevice
Server
Prhvre ombedoinng reclool
Compute secret sharas smbeddingg
x = i, and elsewhere.
look updeee
Goadlnnt segenasiion and modei uprito
Arhone embedsting
FSS
Generate keys for the point function. User se- cret shares each function fu, with FSS scheme and outputs pair of keys, i.e., (reK u,a u rek,,) 2,)) = FSS..Gen(1* Su,s). The keys rek u,s and rek u,5 are sent to server and 1, respectively.
Step 2:
update
Figure 1. Overview of SecEmb, which is comprised of two secure and communication-effiient modules: (1) A secure embedding retrieval module and (2) A secure embedding aggregation module.
Step 3: Compute secret shares of item embedding. On receiving rek each server s E {0, computes their secret shares of the target item embeddings as follows:
4.1. Key observation
In most practical recommendation scenarios, the number of items a user has previously interacted with is typically much smaller than the total number of available items (see Figure 2(a)). This observation is linked to the information overload phenomenon, which recommender systems aim to address. Consequently, the gradient of the item embedding is zero for all items except those with which the user has previously interacted.
v u.j
Σ FSS. FSS.Eval(re Q5 Vi E [m]]]-
(3)
Step 4: Reconstruct embedding of target item. On receiv- ing va.; from two servers, user u recovers the embeddings of target items by:
Qitx()) = vo.i + Vu,e Vi E [m/,],
(4)
where idx(i) denotes the global index of the i-th rated item.
Denote go as the gradient of item embedding Q, which is sparse matrix. In typical FedRec with general-purpost SecAgg, the communication cost to download embedding Q and upload the sparse matrix gQ is at least O(bmd), where b is number of bits required to represent a single numerical value. The computation cost is at least (md)). It is important to note that this corresponds to the bottleneck, since the embedding layer dominates the total model size as the item size increases (see Figure 2(b)).
4.2.2. SECURE AGGREGATION ON EMBEDDING UPDATE
The update aggregation module also leverages FSS to re- duce communication costs. Exploiting the sparsity of the embedding update matrix go E _m each non-zero gra- dient value is encoded into some point functions. We begin with the case where user u rates single item, i.e., m 1.
Suppose user u's 's item embedding update lies in sparse gradient matrix gQ" E Rxd Let i denote the item index for the con-zero update. The SecAgg can be performed using the following steps:
Our goal is to optimize the payload for embedding layer, this can significantly reduce the overall overhead, particu- larly under huge value of item size m.
Step 1: Encode non-zero elements with point functions,
4.2. Initial Construction of EmbSec
SQ; fu,tk for k E [d]. User begins by encoding each element gQ%, E R with point function fu,i, I + G. The function Su,i, takes an item id E I as input and outputs (x) BQ% E T r = i, and 0 E R elsewhere.
4.2. 1. PRIVACY-PRESERSS
EMBEDDING RETRIEVAL.
In FedRec, only the embeddings for interacted items are relevant for model updates. Therefore, the user can retrieve and store only these item embeddings during training instead of the entire embedding matrix. Accordingly, we design a embedding retrieval protocol that allows
Step 2: Generate keys for the point function. User u performs FSS on fa.kk and outputs d pairs of keys, i.e.,
4

---

SecEmb: Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
8000
7000
6000
4.61%
3.00%
# Rated Items
5000
(e2 Ak (term))
90% users
36.30%
4000
Embeddling
3000
2000
200%
Paramatters
Yelp (93 Ak ttems)
97.37%
24.14%
User
Embudding sizu d-32
Embedeing sime d-64
(a) Distribution of # rated items
(b) Proportion of parameters
Figure (a) The long-tailed distribution number rated items in ML.0M. The x-axis the user sorted by their activeness, and the y-axis represents the number of rated items for the user. For MLI0M dataset with 27,278 items, nearly 90% users have rated only up to 300 items. (b) The proportion item embeddings and other parameters within a layer deep factorization machine (DeepFM) for ML25M and Yelp, under two different embedding sizes d = 32 and d 64.
(ogKū, k, ,g = D.SS.Gen(1,, fu,ix), which are then sent their corresponding servers.
4.2.3. ANALYSIS OF INITIAL CONSTRUCTION
We briefly analyze the complexity and security for the above construction as follows.
Step 3: Aggregate secret shares from users. On receiving agKa,, from all participating users, each server E {0, 1} computes their secret shares of the aggregated matrix as follows:
During privacy-preserving embed- ding retrieval, only m' keys and embeddings exchanged between user and server, rather than the entire embed- ding matrix. For update aggregation, user u uploads only mld keys to each server instead of the whole sparse ma- trix. Therefore, the communication cost is approximately O [Key)) for upload transmission and O(m', d) for download transmission, where Key| denotes the key size.
Commmunication cost:
Σ FSS FsS.Evallag I),, Vj EI, E [d]. (5)
Step 4: Reconstruct gradient aggregation. The two servers can collaborate to reconstruct the plaintext aggrega- tion matrix. To be specific, server 1 sends the aggregated secret shares to server 0, and the plaintext aggregation can be recover by:
Computation cost: The user computation cost primarily stems from the generation of FSS keys. In total, user generates m (d + 1) keys, resulting in a computation over- head of O FGen). where FGen represents the cost of generating a single key.
BQ= v2 + vg.
(6)
Security: FSS security ensures that user updates and inter- actions remain hidden from the server. In preeacyppesservig embedding retrieval, each server is ignorant of the targeted item indices. During update aggregation, servers learn no information about the rated item index i and its gradient SQr To further hide the number of rated items m', from servers, we can pre-specify unified update size m', and accordingly pad or truncate the target indices well as updated vectors to contain m' items (see Appendix C), thus keeping the entire sparse update matrix and target item set hidden from the server.
Below extends the method
where m², >>
SecAgg for m/, > 1: In step 1, user generates mi, point functions fu,ik I + G for i E [m,]]. Let idx(x:) denote the global index of the i-th rated item. Accord- ingly, fu.ik takes a item id x E I as input and outputs fu.i, (x) = "Q E R if x = idx(i), and E I else- where. In step 2, user u produces m', d pairs of secret keys (agK), u.ikk ag ng (...)) for i E [m,,) & [d]. In step 3, each server 8 E {0, 1} computes their secret shares of the aggre- gated matrix as follows:
4.3. Optimization of SecEmb
VOJ
PSS.Eval(agK", (.) E I. E [d].
We identify a crucial property of the FSS key- soy--oore party E (0, 1), the key, denoted as [CW* ||C|+++++
EE [m))
5

---

SecEmb: Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
(where is the bit length of the input), consists of two components: (1) sg || |CW", the seed and correction words used to determine whether the input index corresponds to the non-zero element, and (2) CW*+1, the correction word used to convert the final seed into group elements in the abelian group G (see Figure 3). The for- mer part can be identical for point functions with the same non-zero index, presenting an opportunity to eliminate re- dundancy in FSS keys. Leveraging this insight, propose two optimizations of SecEmb to further reduce user payload. Algorithm 3 outlines the improved SecEmb.
shares of the aggregated matrix follows:
v2. = Σ
Σ M rE(m')
FSS.Eval(ag 5), VjEI.
(8)
After the optimization, each user generates and uploads only m' keys instead of m' d keys for update aggregation.
4.3.2. SHARING PATH FROM RETRIEVAL STAGE
For each user, the indices of relevant embeddings remain the same across both stages. If user u generates an embed- ding retrieval key reK and an update aggregation key agK", for item i, the former components of both keys can be identical.
Delre the wayld nctvern indec Lomlkyy component: "''=" (JOWS
$8.45 osl
Consequently, in the update aggregation stage, each user can generate and transmit CW*+1 instead of the whole FSS key, leading to much lower computation and communication cost. Furthermore, server s E {0. 1} can reuse the binary tree path identified in private emhedding retrieval stage compute FSS. FSS.Eval(ag ",, for E U, E I, [m').
A6p- 1b 4455118 cot
Spah 600 ei or!
Sueh -Alpee od
Corvert aood io ement abella graae composentt
(-17 [omwent - cw*")
The optimization reduces the key size in the update aggre- gation stage from n + 2 seeds and corrections words to a single correction word. Additionally, each user eliminates n AES operations for pseudorandom generation when secret sharing the embedding update.
Figure 3. Evaluation of FSS scheme for party b E 10, For simplification, we use s (c.) and se (t") interchangeably.
1. EFFICIENT RISE ENCODING
The gradient update of item embeddings forms a row-wise sparse matrix, with a few rows containing non-zero values. The initial method generate FSS keys separately for each element, introducing redundancy for updates from the same item. A more efficient approach is to encode each non-zero row as a point function, requiring only a single key pair per embedding update (see Figure 4).
4.4. Complexity and Security Analysis
4.4. 1. COMPLEXITY ANALYSIS
Denote À as the security parameter of FSS scheme, and as the number of bits required to represent single numerical value. The variables d and refer to the embedding size and the parameters other than item embeddings. The keys sizes for the private embedding retrieval and secure aggregation stages are (A + 2) log m and bd, respectively (Boyle et al., 2016). The computation cost to generate an FSS key in private embedding retrieval stage is Ollog m AES), and the cost to derive partial key in upload aggregation is negli- gible compared with the AES operations. Considering m' functions and [@] dense updates, we have upload communi- cation complexity of O (m' (bd + X log m)) + 10]b), down- load complexity of O (m' bd + [0]b), and computation cost of O (m' log m AES + (8))
Initial Constructionn
4f Aidde II H-jew (jww"" ko Sudd 1- (ewgr
Embedding Update
Zero optatee
Nomaero updates
Remove Combing
Zero
A Alrrtprr' y-. -I
Impeoved Construcioon
Table compares the user-side cost between SecEmb and secure FedRec (Xiong et al., 2020). Secure FedRec uti- lizes full model download and adopts the most efficient SecAgg for update aggregation (see Table 6). The com- munication cost of SecEmb scales linearly with m' and logarithmically with m. SecEmb outperforms secure Fe- dRec in upload communication cost as long as m' < mbd/ ((A - 2) log m + b(d+ 1)), and in download cost as long as m' < m/2. Appendix K.5 we demonstrate that
Figure 4. Row-wise encoding of item embedding gradient.
Specifically, user u encodes the embedding gradients for targeted items into m' point functions fu, : I - G for i E [m²]. The function fu, takes an item id x E I as input and outputs fz) = BQy E IRd if = idx(i). and 0 e d elsewhere. Then m' pairs of FSS keys are generated cor- respondingly, i... (agKō, agK],) a.a) = FSS. (en(aGnnn11 fu.s)
for E [m']. Each server 8 E (0, 1) computes their secret
6

---

SecEmb: Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
these inequalities usually hold for RecSys with sparse up- date. The computation complexity of SecEmb primarily arises from AES operations, which can be mitigated when m' is sufficiently small compared with m.
Table 2. Upload communication cost (in MB) per user for SecEmb and Secure FedRec (SecFedRec) in one iteration. Reduction ratio is computed as the communication overhead SecFedRec by that of SecEmb.
ML100K 1,682
MLIM
ML10M
ML25M 62,423
Yelp 93,386
Item Size m
3,883
10,681
Table 1. User computation and communication cost of SecEmb and secure FedRec. CommunDown and CommunUp Up refer to download and upload communication cost, respectively.
MF
SecFedRec SecEmb
0.86
1.99
5.47
31.96
47.81
0.17
0.27
0.28
0.51
0.52
SecEmb
Secure FedRec
Red. Ratio
4.99
7.35
19.22
62.07
91.22
Cown
O (in bel (0())
O (mrbd + [0[b)
NCF
Up
0 (mm (A logom m + bdd + (0)b)
O 0mbd + [8]b)
Computation
O (m' log m AES + (0))
0 0md + [0])
SecFedRcc
0.44
1.00
4.11
23.98
29.89
SecEmb
0.13
0.20
0.26
0.46
0.44
Red. Ratio
3.44
5.02
15.93
51.80
68.46
4.4.2. SECURITY ANALYSIS
FM
The FSS security property ensures that the two non- colluding servers learn no more information than just the aggregated gradients. The FSS keys hide the rated item index as well as the values of updated gradients from each server. Under a pre-determined m', servers are ignorant about the number of rated item for each user. Consequently, no information about the individual updates is revealed to the servers except the aggregation. Below is the formal security formulation for the update aggregation stage; comprehensive security analysis is provided in Appendix F.
SecFedRec SocEmb Red. Ratio
0.91
2.01
5.48
31.97
47.82
0.18
0.28
0.29
0.53
0.53
5.05
7.22
18.76
60.87
91.05
DeepFM
SecFedRec
14.95
8.84
8.63
35.13
50.45
SecFmb
14.22
7.10
3.45
3.68
3.16
Red. Ratio
1.05
1.24
2.50
9.54
15.98
Lens 10M (MLI0M), MovieLens 25M (ML25M), and Yelp (Harper & Konstan, 2015; Yelp, 2015). For the Yelp dataset, we sample portion of top users ranked in descending order by their number of rated items, and obtain a subset contain- ing 10,000 users and 93,386 items. Table 7 summarizes the statisties for the datasets.
For C C u [b} (b E 1)). let Reals, be the joint view of colluding parties C' in experiments executing secure update aggregation in SecEmb. Denote (gg", , 0n)) hreu as the set of gradients from all users. Then we have the security of the aggregation protocol follows.
Our framework is tested with four latent factor-based recom- mender models: matrix factorization with biased term (MF) (Koren et al., 2009), neural collaborative filtering (NCF) (He et al., 2017), factorization machine (FM) (Rendle, 2010), and deep factorization machine (DeepFM) (Guo al., 2017). Detailed hyperparameters for each model are provided in Appendix I. We provide coarse- coarse-grained comparison be- tween SecEmb and existing FL protocols in Appendix J.
Theorem 4.1 (Security of secure update aggregation). There exists PPT simulator Sim Sagg, such that for all user in- put ((gq,,.)) bw))heu and C C luuu U {b} (b E {0, 1}), the output of Sim X,gg and Reat x.gg are computationally indis- tinguishable:
Real X,gg (1>, ((QQ((( buerne))c)
=SimS,agg (I>, (m', Gi,... Gm', ge; 82)),
5.2. Efficiency Analysis
where BQ and go denote the aggregated gradients for item embedding and the remaining parameters, respectively.
5.2.1. COMMUNICATION COST
To evaluate the communication efficiency of our framework, we conduct comparative analysis of the communication payload between SecEmb and secure FedRec as presented in Table 2 and 12. We use the two-server ASS, which has the minimal communication overhead, to compute the upload cost for secure FedRee (see Table 6). A key finding is that SecEmb's communication overhead increases at a significantly slower rate with item size compared to secure FedRec, particularly for models characterized by higher proportion of sparse updates.
It is important to note that our algorithm can be integrated
with differential privacy (DP) to achieve stronger privacy protection. In particular, each server can independently add calibrated noises to the aggregated secret shares matrix, so that recovered aggregation matrix adheres to (c, -DD (Dwork, 2006; Cormode et al., 2018) (see Appendix G).
5. Experiment Evaluation
5.1. Experiment Setting
For upload communication, our protocol reduces costs by approximately 4x to 90x for MF and FM, which have mini- mal dense updates, depending on the dataset item size. For
We evaluate our SecEmb on five public datasets: Movie- Lens 100K 10L,, MovieLens 1M (MLIM), Movie-
7

---

SecEmb: Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
SedEmb
Secure FedRec
42
33
28
ML1M
ML10M
ML25M
Yelp
Figure 5. User computation time (in milliseconds) for secret shares generation during training phase.
NCF that includes small share of dense updates, SecEmb achieves overhead reductions ranging from roughly 3.5x to 70x. For DeepFM, the reduction is less pronounced for the ML100K and MLIM datasets with item sizes lower than 4k, while the cost savings become more substantial as the item size exceeds 10k. A similar pattern is observed for download communication (see Appendix K.1).
achieves similar reduction ratios on datasets with smaller item sizes, its communication benefits significantly surpass those of other compression methods on ML25M and Yelp, where the item size exceeds 60k. (2) The performance is de- graded on an average by 1.29%, 1.74%, 1.95%, and 2.04% for Bit8Quant, TernQuant, SVD, and CoLR, respectively, suggesting that SecEmb offers negligglii advantages over the lossy message compression mechanisms.
We also compare SecEmb with existing sparse aggrega- tion protocols in Appendix K.3.
5.4. Application to Sequential Recommendation
5.2.2. COMPUTATION CoST
We extend our framework to sequential recommendation tasks, which predict the next item user will interact with based their historical interactions. Specifically, we apply SecEmb to the item embedding layers of sequential recom- mendation models. We evaluate our approach using two sequence models, Caser (Tang & Wang, 2018) and SAS- Rec (Kang & McAuley, 2018), on the MLIM and Amazon datasets. Experimental settings are detailed in Appendix K.6
Figure 5 compares the user computation time to generate the secret shares for SecEmb and secure FedRec with the most efficient SecAgg protocol. SecEmb has an advantage over secure FedRec in terms of the computation overhead, since each generates fewer shares when m' < Furthermore, the computation time for SecEmb scales more slowly with an increase in item size compared to secure FedRec. This results in a significantly higher reduction ratio for datasets encompassing a greater number items, achieving nearly 70x for Yelp withs MF and FM.
Our findings in Table 4 indicate that compared with Se- cEmb, applying existing message compression techniques results in average reductions of 0.5%, 2.7%, 2.6%, and 2.6% for Bit&Quant, TernQuant, SVD, and CoLR, respectively. Notably, for the Amazon dataset, which has a vast item set and exhibits high sparsity (density< 0.002%)), our Se- cEmb method achieves up 2500x reduction in upload communication cost.
5.3. Utility Analysis
We evaluate the utility of SecEmb against several lossy mes- sage compression methods for communication efficiency, in- cluding: (I) Singular value decomposition (SVD) (Nguyen al., 2024), (2) Correlated Low-rank Structure (CoLR) (Nguyen et al., 2024), (3) 8-bit quantization (Bit8Quant) (Dettmers, 2015), and (4) Ternary Quantization (TermQuant) (Wen et al., 2017). The first two methods represent di- mension reduction upproaches, and the latter two employ gradient quantization method. For fair comparison, the lossy message compressions are applied only to item embeddings.
5.5. Ablation Studies
To investigate the effectiveness of optimizations, compare SecEmb with two variants: (1) initial construction of SecEmb (SecEmb-Init), and (2) initial construction of SecEmb optimized by efficient row-wise encoding (SecEmb- RowEnc). Table 5 presents the user cost with MF model, and for full results refer to Section K.7. The initial construc- tion of SecEmb suffers substantially higher communication overhead than the improved one, and its cost can be higher than that for secure FedRec dataset with item size lower
Table 3 presents the prediction accuracy and reduction ratio of communication cost. We focus on the upload commu- nication as most baselines do not optimize download costs (see Table 1).. It can be observed that: (1) While SecEmb
8

---

SecEmb; Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
Table RMSE and Reduction Ratio (R.R.) for SecEmh and various message compression methods. The values for RMSE denote the mean + standard deviation of four rounds of experiments. R.R. refers to the ratio of upload communication cost before and after the application the compression mechanism.
ML100K
MLIM
MLI0M
ML25M
Yelp
RMSE
R.R.
RMSR
R.R.
RMSE
R.R.
RMSE
R.R.
RMSE
R.R.
Bit8quant
0.948+00.004
4.00
0.91440.000
4.00
0.872#0.001
4.00
0.870
4.00
1.050=0.001
4.00
Ternquant
0.951 20.002
8.00
0.91620.000
8.00
0.873
8.00
0.87440.00
8.00
1.050=0.001
8.00
MF
SVD
0.95211-000
5.22
0.91710.000
6.39
0.87220.00 001
0.87310 000
16.23
1.050 o01
16.24
CoLR
0.951+0.001
5.42
0.916+0.001
6.50
0.872+0.001
16.25
0.873+00000
16.25
1.049:0 002
16.25
SecEmb
0.944 003
4.99
0.903 002
7.35
0.868 003
19.22
0.864=o.0dd
62.07
1.050=0.00
91.22
Bit8quant
0.950+0.011
3.86
0.898#0.00
3.94
0,832
3.97
0,820
3.99
1.035+0.0
4.00
Ternquant
0.951#0.005
7.37
0.901 #0.000
7.71
0.833
7.84
0,825
7.97
1.036:0.00 000
7.98
NCF
SVD
0.952:00006
3.15
0.903 007
4.02
0.838 002
11.81
0.824 .000
12.17
1.035 002
10.22
CoLR 0.947 005
3.21
0.91 220 ous
4.06
0. 0.85620 ooe
11.87
0.839 out
12.18
1. 100320 001
10:22
SecEmb
0.949910.014
3.44
0.897 o 006
5.02
0.819 003
15.93
0.786 008
51.80
1. 1.035 0001
68.46
Bit8quant
0.945220-001
3.41
0.91 220 000
3.86
0.845 non
3.98
0.83610 001
4.00
1.009
4.00
Ternquant
0.94811.oo 002
5.70
0.913
7.37
0.856
0.850 onu
7.98
1.010 ouz
7.99
FM
SVD
0,946:40.0u1
4.21
0.913
6.00
0.870#0.0ua
15.71
0. 0,85640.mm
16.16
1.009
16.20
CoLR
0.9444+0.004
4.33
0.915+0.000
6.10
0,867 18867000000
15.81
0.851 +0.00
16.17
1. 1.008=0.001
16.21
SecEmb
0.937 004
5.05
0.906 10.000
7.22
0.848 002
18.76
0.789 = o03
60.87
1. 1008000 003
91.05
Bit&quant
0.947
1.05
0.91220.nm
1.21
0.84020.001
1.92
0.832 0.00
3.16
1.012
3.47
Ternquant
0.94920.004
1.06
0.91420.um 002
1.25
0.847 000
2.26
0.8422.0 001
4.94
1.018200 001
5.88
DeepIiM
SVD
0.954
1.05
0.913 out
1.24
0. 0.853 002
2.48
0.847 oun
6.90
1.0142u.om
9.09
CoLR
0.952+0.001
1.05
0.905 001
1.24
0.856
2.49
0,841+0 .000001
6.90
1.017=0.000
9.10
SecEmb
0.939=0.000
1.05
0.902=0.00
1.24
0.821 0.001
2.50
0.791-0.001
9.54
1.011+0
15.98
Table RMSE and Reduction Ratio (R.R.) for SecEmb and various message compression methods Sequential Recommender System. R.R. refers to the ratio of upload communication cost before and after the application of the compression mechanism.
MLIM (3,883 items)
Amazon (9,267,503 items)
HR @ 10
NDCG@ 10
R.R.
HR 10
NDCG@ 10
R.R.
Bit8quant
0.473
0.267
3.51
0.628
0.481
Ternquant
0.468
0.261
6.03
0.623
0.478
Caser
SVD
0.471
0.266
9.71
0,627
0,483
38
CoLR
0.465
0.263
9.78
0.625
0,480
38
SecEmb
0.475
0.270
4.79
0.629
0.483
2549
Bit8quant
0.468
0.266
2.55
0,636
0,485
4
Ternquant
0.443
0.248
3.44
0.635
0.483
SASRec
SVD
0.444
0.249
3.00
0.621
0.472
CoLR
0.464
0,262
3.02
0.600
0.463
SecEmb
0.472
0.268
3.86
0.639
0,485
2342
than llk. Additionally, sharing the binary path between the two modules reduces the communication cost by around 36%. Similarly, the two optimizations substantially improve user computation costs.
6. Conclusion
This paper proposes SecEmb, lossless recommender system designed for essource-constraiig de- vices with optimized payload sparse embedding updates. SecEmb achieves succinct communication costs, i.c., cost independent of item size m for downloads and logarithmic in m for uploads, while preserving the secrecy individ- ual gradients. Additionally, it reduces device-side memory and computation overhead by processing only relevant item embeddings. The empirical evaluation demonstrates that: (1) SecEmb reduces communication costs by up to 90x and decreases user computation time by up to 70x compared with secure FedRec. (2) SecEmb offers non-negligible util- ity advantages compared with lossy message compression methods. Further discussions on our framework are pro- vided in Appendix L.
Table Upload communication cost and computation cost for secret generation per user for SccEmb and its variants with MF.
ML.00K
MLIM
MLI0M
ML.55M
Yelp
Upload communication cost (in MB)
SevEmb-Init
4.56
7.60
8.51
16.83
17.43
SecEmb Row Fine
0.28
0.43
0.45
0.78
0.79
SecEmb
0.17
0.27
0.28
0.51
0.52
Computation
milliseconds)
SecEmb-Init
5.34
15.35
22.56
28.53
26.43
SecEmm-RRowFing RowFine
0.37
0.90
0.91
1.34
1.47
SecEmb
0.31
0.47
0.47
0.72
0.74
9

---

SecEmb; Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
Acknowledgements
2017 ACM SIGSAC Conference Computer and Communications Security, pp. 1 1175-1191, 2017.
Ding was supported in part by a grant from the Israel Science Foundation (ISF Grant No. 1774/20), and by the European Union (ERC, ICALE.101162665 expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.
Bonawitz, K., Eichner, H., Grieskamp, W., Huba, D., Inger-
Views and opinions
man, A., Ivanov, V., Kiddon, C., Konečný, J., Mazzocchi, S., McMahan, B., et al. Towards federated learning scale: System design. Proceedings of Machine Learning and Systems. 1:374-388, 2019.
Boneh, D., Boyle, E., Conrigan- Gibbs, H., Gilboa, N., and Ishai, Y. Lightweight techniques for private heavy hitters. 2021 IEEE Symposium on Security and Privacy (SP), pp. 762-776. IEEE, 2021.
Impact Statement
This paper presents work aimed at advancing the field of privacy-preserving computation, particularly focusing improving user privacy in federated recommender system through our SecEmb framework. Our proposed framework contributes to the technical evolution federated learning and presents substantial benefits in data protection. We be- lieve that the ethical impacts and social consequences align with established principles in responsible Al development.
Boyle, E., Gilboa, N., and Ishai, Y. Function secret shar- ing. In Annual international conference on the theory and applications of cryptographic techniques, pp. 337- 367. Springer, 2015.
Boyle, E., Gilboa, N., and Ishai, Y. Function secret shar- ing: Improvements and extensions. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 1292-1300 2016.
References
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I, Talwar, K., and Zhang, I.. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Boyle, E., Gilboa, N., Ishai, Y., and Kolobov, V. I. Information-theoreti distributed point functions. In 3rd Conference on Information- Theorrtiic Cryptography, 2022.
Addanki, S., Garbe, K., Jaffe, E., Ostrovsky, R., and Poly- chroniadou, A. Priot: Privacy preserving aggregate statis- tics via boolean shares. In International Conference on Security and Cryptography for Networks, pp. 516-539. Springer, 2022.
Chai, D., Wang, L., Chen, K., and Yang, Q. Secure federated matrix factorization. IEEE Intelligent Systems, 36(5):1 20, 2020.
Chen, B., Medini, T., Farwell, J., Gobriel, S., Tai, C., and Shrivastava, A. Slide: In defense of smart algorithms over hardware acceleration for large-scale deep learning systems. arXiv preprint rxXiv:1903.03122 2019.
Aji, A. F. and Heafield, K. Sparse communication for dis- tributed gradient descent. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp. 440 445, 2017.
Chen, B., Liu, Z.,, Peng, B., Xu, Z.,, L. L.., Dao, T., Song, Z., Shrivastava, A., and Re, Mongoose: learnable Ish framework for efficient neural network training. In International Conference Learning Representations, 2020.
Ammad-Ud-Din, M., Ivannikova, E., Khan, S. A., Oyomno, W., Fu, Q., Tan, K. E., and Flanagan, A. Federated collab- orative filtering for privacy-preserving personalized rec- ommendation system. arXiv preprint arXiv: 1XXiv:1901.09883 009888, 2019.
Chen, R., Wu, Y., Chen, L., Liu, G., He, Q. Xiong, T., Liu, C., Guo, J., and Huang, H. Your vision-language model itself is a strong filter: Towards nigh-quality instruction tuning with data selection. In ACL (Findings). 2024a.
Bell, J. H., Bonawitz, K. A., Gascón, A., Lepoint, T., and Raykova, M. Secure single-server aggregation with (poly) logarithmic overhead. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pp. 1253-1269, 2020.
Chen, R., Wu, Y., Guo, J., and Huang, H. De-mark: Water- mark removal in large language models. arXiy preprint arXiv:2410.13800 2024b.
Bonawitz, K., Ivanov, V., Kreuter, B., Marcedone, A., McMahan, H. B., Patel, S., Ramage, D., Segal, A., and Seth, K. Practical secure aggregation for privacy- preserving machine learning. In proceedings of the
Chen, R., Wu, Y., Guo, J., and Huang. H. Improved unbiased watermark for large language models. arXiv preprint arXiv:2502.11266 2025.
10

---

SecEmb: Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
Cheon, H., Kim, A., Kim, M., and Song. Y. Ho- momorphic encryption for arithmetic of approximate numbers. In Advances in CryplologyASIAACRVA 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part 23, pp. 409-437. Springer, 2017.
Han, Z., Gao, C., Liu, J., Zhang, J., and Zhang, S. Q- Parameter-effiient fine-tuning for large models: A com- prehensive survey. arXiv preprint arXiv:2403. 2024.
Harper, F. M. and Konstan, J. A. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tis), 5(4):1-19, 2015.
Cormode, G., Jha, S., Kulkarni, T., Li, N., Srivastava, D., and Wang, T. Privacy at scale: Local differential privacy in practice. In Proceedings of the 2018 International Conference on Management of Data, pp. 1655-1658, 2018.
He, X., Liao, L., Zhang. H.,, Nie. L., Hu, X., and Chua, T-S. Neural collaborative filtering. In Proceedings of the 26th international conference on world wide web, pp. 173-182, 2017.
Hu, E. J., Wallis, P., Allen-Zhu, Z., Li, Y., Wang, S., Wang, L., Chen, W., et al. Lora: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2022.
Corrigan-Gibbs, H. and Bonch, D. Prio: Private, robust, and scalable computation of aggregate statistics. In 14th USENIX symposium on networked systems design and implementation (NSDI 17), pp. 259 282, 2017.
Hua, J., Xia, C., and Zhong, S. Differentially pri- vate matrix factorization. In Proceedings of the 24th International Conference on Artificial Intelligence, IJ- CAI'5, pp. 1763-1770. AAAI Press, 2015. ISBN 9781577357384.
Cramer, R., Damgård, I. B., et al. Secure multiparty computation. Cambridge University Press, 2015.
Dettmers, T. 8-bit approximations for parallelism in deep learning. arXiv preprint arXiv: 1.00466,, 2015.
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., et al. The Ilama herd of models. arXiv preprint arXiv:2407.21783, 2024.
Kadhe, S., Rajaraman, N., Koyluoglu, O. O., and Ram- chandran, K. Fastsecagg: Scalable secure aggregation for privacy-preserving federated learning. arXiv preprint arXiv:2009. 11000009911119 1248, 2020.
Dwork, C. Differential privacy. In International colloquium on automata, languages, and programming, pp. 1-12. Springer, 2006.
Kang, W--. and McAuley, Self-attentive sequential recommendation. In 2018 IEEE international conference on data mining (ICDM), pp- 197-206. IEEE, 2018.
Ergun, I., Sami, H. U., and Guler, B. Sparsified secure aggre- federated learning. arXiv
Kingma, D. P. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.66 2014.
gation for preprint arXiv:2112.12877 2021.
Koren, Y., Bell, R., and Volinsky, C. Matrix factorization
Fercidooni, H., Marchal, S., Miettinen, M., Mirhoseini, A., Möllering, H., Nguyen, T. D., Rieger, P., Sadeghi, A.-R., Schneider, T., Yalame, H., et al. Safelearn: Se- cure aggregation for private federated learning. In 2021 IEEE Security and Privacy Workshops (SPW), pp. 56-62. IEEE, 2021.
techniques for recommender systems. Computer, 42(8): 30-37, 2009.
Li, M., Liu, Z., Smola, A. J., and Wang, Y.-.. Difacto: Distributed factorization machines. In Proceedings of the Ninth ACM International Conference on Web Search and Data Mining, pp. 377-386, 2016
Guo, H., Tang, R., Ye, Y., Li, Z.,, and He, X. Deepfm: a factorization-machine based neural network for etr pre- diction. In Proceedings of the 26th International Joint Conference Artificial Intelligence, pp. 1725-1731, 2017.
Lin, G., Liang, F., Pan, W., and Ming, Z. Fedrec: Federated recommendation with explicit feedback. IEEE Intelligent Systems, 36(5):21-30, 2020.
Lin, Z., Pan, W., Yang, Q. and Ming, Z. A generic federated recommendation framework via fake marks and secret sharing. ACM Transactions on Information Systems, 41 (2):1 2022.
Gupta, V., Choudhary, D., Tang, P., Wei, X., Wang, X., Huang, Y., Kejariwal, A., Ramchandran, K., and Ma- honey, M. W. Training recommender systems at scale: Communication-cfficiee model and data parallelism. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 2928 2936, 2021.
Liu, K., Hu, S., Wu, S. Z., and Smith, V. On privacy and per- sonalization in cross-silo federated learning. Advances in neural information processing systems, 35:5925-599 5940, 2022.

---

SecEmb: Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
Liu, T., Wang, Z., He, H., Shi, W., Lin, L.., An, R., and Li, C. Efficient and secure federated learning for financial applications. Applied Sciences, 13(10):5877, 2023.
conference web search and data mining, pp. 565-573, 2018.
Wei, K., Li, J., Ding, M., Ma, C., Yang. H. H.,, Farokhi, F,, Jin, S., Quek, T. Q., and Poor, Federated learning with differential privacy: Algorithms and performance analysis. IEEE transactions information forensics and security, 15:3454-3469 2020.
Lu, S., Li, R., Liu, W., Guan, C., and Yang, X. Top-k spar- sification with secure aggregation for rivacc-preservvnn federated learning. Computers & Security, 124: 102192 2023.
Mai, P. and Pang.
multiview ma- trix factorization for recommender systems. IEEE Transactions Artificial Intelligence, 5(1):267-277, 2023.
Wen, W., Xu, C., Yan, F., Wu, C., Wang, Y., Chen, Y., and Li, H. Terngrdd: Ternary gradients to reduce communi- cation in distributed deep learning. Advances in neural information processing systems, 30, 2017.
McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. Communication-effiieenn learning of
Xiong, L.,, Zhou, W., Xia, Z., Gu, Q. and Weng, Efficient privacypreservvig computation based on additive secret sharing. arXiv preprint arXiv:2009.053: 05356, 2020.
deep networks from decentralized data. In Artificial intelligence and statistics, pp. 1273-1282. PMLR, 2017.
Xu, Z., Liu, L.,, Xu, Z., and Shrivastava, A. Adaptive sparse federated learning in large output spaces via hashing. In Workshop on Federated Learning: Recent Advances and New Challenges (in Conjunction with NeurIPS 2022). 2022.
Mohassel, and Zhang, Y. Secureml: A system for scalable srivacy-preserving machine learning. 2017 IEEE symposium on security and privacy (SP), pp. 19- 38. IEEE, 2017.
Nguyen, N.-H., Nguyen, T.-A., Nguyen, T., Hoang, V. T., Le, D. D., and Wong, K.-S. Towards efficient communi- cation and secure federated recommendation system via low-rank training. In Proceedings of the ACM Web Conference 2024, pp. 3940-3951, 2024.
Xue, H.-.,, Dai, X., Zhang, J., Huang, S., and Chen, Deep matrix factorization models for recommender systems. In IJCAL, volume 17. pp. 3203-3209, Melbourne, Australia, 2017.
Yelp. Yelp dataset. 2015. URL https: htttps:/wwww.yel.. com/ com/dataset.
Perifanis, V. and Efraimidis, Federated neural collabo- rative filtering. Knowledge- Based Systems, 242:108441, 2022.
Zhang, H., Luo, F. Wu, J., He, X., and Li, Y. Lightfr: Lightweight federated recommendation with privacy- preserving matrix factorization. ACM Transactions on Information Systems, 41(4):1-25 2023.
Rabbani, T., Bornstein, M., and Huang, Large-scale dis- tributed learning via private on-device cocality-sensiiivy hashing. In Proceedings of the 37th International Conference Neural Information Processing Systems, pp. 16153-16171 2023.
Rendle, S. Factorization machines. In 2010 IEEE International conference on data mining, pp. 995-1000.
IEEE, 2010.
Sanh, V. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. In Proceedings of Thirty-third Conference on Neural Information Processing Systems (NIPS2019), 2019.
So, J., He, C., Yang, Li, Yu, Q., E Ali, R., Guler, B., and Avestimehr, S. Lightsecagg: a lightweight and versatile design for secure aggregation federated learn- ing. Proceedings of Machine Learning and Systems, 4: 694-720, 2022.
Tang. J. and Wang, K. Personalized top-n sequential recommendation via convolutional sequence embed- ding. In Proceedings of the eleventh ACM international
12

---

SecEmb: Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
A. Complexity of Existing SecAgg Algorithms
In Table 6, we summarize the computation and communication complexity of existing SecAgg algorithms. can be observed that a) two-server ASS represents the most efficient algorithm in terms of both computation and communication complexity, and b) the per-client communication cost depends linear in the model size for all protocols.
Table 6. Computation and communication complexity of existing SecAgg algorithms. SecAgg and SecAgg+ refer to the algorithm proposed by (Bonawitz al., 2017) and (Bell al., 2020) respectively. a and / denote client size and model size, respectively.
Server
Client
Rounds
Computation
Communication
Computation
Communication
SecAgg
O(n
O(vl + n²)
O(nl + n²)
O( n)
SecAgg+
Onnl logn nlooo n)
O(nl + logn)
O(llog log" m)
0( logn)
3
FastSecAgg
O ((llog))
O(nl +n")+nn))
O( log n)
0
3
LightSeoAgg
(n! m)
O
O(ni log n)
((n))
2
SAFELeam
O(nl)
O(n))
O(1)
0())
2
Two-server ASS
(nn)
O(nl)
O
O(t)
1
B. Preliminaries
B.1. Additive Secret Sharing
Additive secret sharing (ASS) (Cramer et al., 2015) divides secret Fp from finite field into shares, such that Ei= Ty (mod p) Consequently, any shares reveal nothing about the secret Furthermore, given two secret shares [>]] = (I., Zn) and [b] = (y1,... yn) from Fp,, it holds that [x + y] = (I1 + 9i. In + yr).
B.2. Function Secret Sharing
In this section we formally define the correctness and security properties of FSS scheme. Definition B.1 (FSS Correctness and Security). Let FSS = (FSS.Gen, FSS.Eval) be a FSS scheme for function class F, satisfying the following properties:
Correctness: For every x in the domain of f. holds that:
Pr Σ
FSS. FSS.Eval(k;, x) = f(x) E FF (k), + FSS. 1.
(10)
Security:
For any party & E {1, there exists a PPT algorithm Sim (simulator), such that for every function f E F, the outputs of the following experiments REAL and IDEAL are computationally indistinguishable:
REAL(1A, f) (k. (k1, R2) FSS.Gen(11, f))
- IDEAL(IA, (.FF = [kg + Sim(1>,F)}
C. Standardization of Uploaded Item Size
To conceal m', from the server, uniform m' can be applied to all users. An optimal m' should be substantially smaller than m to reduce communication overhead, yet not excessively small to encompass the rated items of majority of users. To determine a suitable value of m', the server can compute the average number of rated items from all users via a SecAgg protocol and select m' follows:
m' = a 1 Σ mm
(11)
where a is pre-specified multiplier on the average. Note that the SecAgg operation on the number of rated items is cheap, incurring (1) communication and computation overheads per user.
Given the unified m', each user can: (1) convert their target item indices set into size of m according to Algorithm 1, and (2) standardize their non-zero updates for item embedding to be a m' d matrix according to Algorithm 2.
13

---

SecEmb: Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
Algorithm 1 PadOrTruncidx
Input: m and Zu = {11, (i1,.., hm
Output: Ty (i,.... km)). if [Iu] < m' then
Randomly sample m' - [Zul elements from IiZ and insert them into Zy form Izz else if m > m' then Randomly sample m' elements from I, to form T
else
Let T' - In end
return T
Algorithm 2 PadOrTruncEmb
Input: mn' and gis E RR xd Output: Bq. E <Rmm'xd xd
if m'y < m then Create padding matrix of zero elements (mm'mm/, xd Concatenate gQ. and form s'e.. E 12m else if m', m' then
Randomly sample m' rows from SQ, to form &Q. E Rmm' xd else
Let BQQ.. = gQ. end
return BQ.
D. Secure Aggregation Dense Update
We employ additive secret sharing for SecAgg on the dense update go. In particular, user u generates a pair of additive secret shares for the gradients [go] (v), v2), and sends the secret shares the corresponding servers. Each server aggregates the secret shares from all participating users:
(12)
Same step in Section 4.2.2, the two servers can subsequently collaborate reconstruct the plaintext aggregated update.
E. Algorithm of SecEmb
Algorithm 3 outlines the final version of SecEmb, which consists of two modules: (1) privacy-preserving embedding retrieval, and (2) secure update aggregation.
F. Formal Security Analysis
For security, require that the two servers should be non-colluding, However, restriction is placed on the collusion between one server and the clients. User privacy is guaranteed as long as at least one server is honest, even if the other colludes with any number of clients.
F.1. Security Analysis for Private Embedding Retrieval
Let CUC (b} (b (0, 1)) denote the union of one server and any subset of the users. Given security parameter X, let Realf reet be the combined view of colluding parties C in experiments executing privacy-preservig embedding retrieval in SecEmb. Denote Iy as the target indices all users. We show that the joint view of each non-colluding server and the clients can simulated given the allowable leakage. In other words, the collusion between one server and any number of clients reveals no information about the honest clients.
14

---

SecEmb; Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
Algorithm 3 SecEmb
Server E 10:
Initialize public parameters G,
for t E [1,7] do
Privacy-preserving embedding retrieval:
Ar. Compute secret shares of item embedding via equation 3, and store immediate values from the evaluation (u,ids,8,,,)) = FSS. PathEval(s, rek...)))
Receive FSS keys (reKa, a.eeemm) from
Send secret shares {v hee(me) to users E A..
Secure update aggregation:
Receive partial FSS keys {CWu,)hiemmr and secret shares for dense update vä, from users u A,. Compute the secret shares of the aggregated sparse update via:
v2g En Eis(ne) TSS.ConvertEvva((s f 8u,i,f CW u,)) for I.
-Aggregate the secret shares of the dense update via equation 12.
if 5 0 then
Receive the aggregated secret shares (v2) vgg) from server 1
Recover the gradients for public parameters gQ, go-
Update public parameters θ, = (Q, 0) with the gradients.
Synchronize public parameters with server
else
-Send the aggregated secret shares (v2- vg) to server 0. Receive updated public parameters from server O.
end if
end for
User u lt: for t [T] do
if Ar then
Privacy-preserving embedding retrieval:
Standardize the size of target indices, i.e., I, = PadOrTruneldx(m2,22 T.).
Encode each index in Iy with a point function, obtaining (aai)eemm
Generate FSS keys (reK' a,i: rek1] u.i) = FSS. E.S..Gen111, fua) for i E [m²], and store the intermediate values from the generation (t,,, s0,5s ( FSS. PSt..eahGenn1.. iixx(())))xx(()))))))))) for e [m/].
Send ireks,))eEln (E|mx) to server E (0, 1).
Receive {vā (v.. (iemm from server E {0, 1}. discard irrelevant embeddings, and reconstruct targeted embedding
Q" using equation 4.
Secure update aggregation:
Calculate gradients locally and update private parameters Op-
Construct additive secret shares (v... vo..) for dense gradient ga
Pad or truncate the sparse gradient into m' x d matrix, gQ PadOrTruncEmb(m' .gq)).
Generate partial FSS keys for the sparse gradients (CWa,ihhsm = PSS.ConvertGen(! (1 u..s sn s B'oz) for
i E [m'].
Send (vá., (CW,, (eem,))))))) to server E {0. 1}.
end if end for
Algorithm 4 CoSvernnvrll
Let Convert; {0, 1} + G be a map converting random X-bit string to pseudorandom group element of G.
Input: (()), s(n), CW(++1)
Output: G
(-1)b (Convert(s(n)) + 1()) CW(++)]
return v
15

---

SecEmb: Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
Algorithm 5 FSS.ConvertGen
Let Converte : {0, + G.
G be a map converting random A-bit string to pseudorandom group element of
Input: 1A, (n) (n) (m)
80 81 .BE
Output: CW(++))
G
CW(n+1) < (-1)4") β Convert(s?))) ) + Convert( (8 ((r))
return CW(++1)
Algorithm 6 PSS..aatEEval
Let G:: 1)^ + {0, 1}2(A+1), a pseudorandom generator.
Input: k2 and
Output: f(m) {0. 1} and s(/) E 1)
Parse hn =|0|)// (|CC(++)))))
for i = 1 to do
Parse CW(() = sow |1 &'w
7(8) + ()) @ (t(-)) 1) [sow (scw/lt66lll
Parse (() = 1 || (0, 1)
if 2; = 0 then
(() - , 100) t
else
(()) s t(0) th
end if
end for return (e(m), ((n))
Algorithm 7 FSS.PathGen
Let G: 10, + {0, 112(+11, a pseudorandom generator.
Input: 1^ and
f0, 13a, and s(t) E (0. 11^ Let a1 .... an E 10, be the bit decomposition of
Output: {(m)
{0, s0
Sample random 5g
(0)
- {0, 1}* and (0) < 10.
Sample random (0) {0, 13 and let (() 100h e
for
do
s | 5 | + G($ (
sf | + G(s) ()
if a. = then
Keep L, Lose R
else
Keep + R, Lose L
end if
sew + sooe @ stose
tl tow - th @ tf @ as +
fww th @ fetRa a;
CW + -swwllt 1 |
( - sb
koep a tth (1-1)
scw for b = 0,
kee a t
(e-1) Keen for = 0, 1
to + t
end for
return (1()) ,0 ,8
(n)
16

---

SecEmb; Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
Theorem F.1 (Security of private embedding retrieval). There exists PPT simulator Sim such that for all user inpul Tu and C cu (& e {0, the ouiput of Sim and Real xeett are computationally indistinguisubbl:
Reatx (anne) = Sre (m', Gi,.., Gml)
(13)
Proof. For each j {0, I....,,'!! m'), we consider a distribution Hyb, as follows:
i S J. each
E C.C construct rek server by: (1) sample s6 (0, 11 at random, and & b;
(2) choose CW()), CW([logm)) + {0, 1 at random; (3) sample CW m]+1) <- at random; (4) output 11)),
reKü, 0 || |11wo"111-..... -. [[C
i > j. compute rek server b honestly using the function secret sharing algorithm.
The output of the experiment is {rek (., to server E {0, 13.
The FSS security ensures that Hyb, and H are computationally indistinguishable for E 10, m' - -1}. Note that Hyb, corresponds to the Reals,ret distribution in the execution of SecEmb, where as Hyb,,. generates a completely random key.
Hence, complete the proof.
F.2. Security Analysis for Secure Update Aggregation
Proof. For each (0, ..., m'), we consider a distribution Hyb, as follows:
Compute v honestly using ASS to server b.
if S j. sample CW.,5 +- G at random.
i > j. compute CW,, +- G honestly following steps in SecEmb.
The output of the experiment is (v2, (Cea.))eem)) to server E {0,
The proof of Theorem 4.1 requires to demonstrate that Hyb, and Hyby+1 J+1 are computationally indistinguishable. To justify this argument, we consider a intermediate distribution Hybj between Hyb, and Hyb,.1:
Compute v honestly using ASS server b. i j, sample CW. u,i G at random.
i = j. construct CW u, = HybCW(12, idx, (i)) via Algorithm 8, where (1) denotes the global index of the i-th
item for user
If > j. compute CW.,; + G honestly following steps in SecEmb.
The output of the experiment is (và,, (C))))) to server E 10.
The security of the pseudorandom generator G ensures that Hyb, and Hyb Hyyb--j+1 are computationally indistinguishable (see Claim 3.7 in (Boyle et al., 2016)). The security of the pseudorandom Convert ensures that Hyb, -yyb,+j41 and Hyb j+1 are computationally indistinguishable (see Claim 3.8 in (Boyle et al., 2016)).
Next,we consider the following distribution Hybm
Sample v < GG randomly to server b.
Sample CW., u,i t- at random for i E [m'].
The output of the experiment is (va,, (CW,,) (CW..:)eemm)) to server E (0,1).
The properties of additive secret sharing guarantee that the distribution of Hyb is identical to Hyb,, Note that Hyb corresponds to the RealS.agg distribution in the execution of SecEmb, where as Hyb outputs set of random secrets and keys.
Hence, we complete the proof.
17

---

SecEmb: Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
Algorithm 8 HybCW
Let Converte {0, 11A + G be a map converting random A-bit string to pseudorandom group element of
G.
Input: 1A, Output: CW((+1)
Let 01: On E (0, be the bit decomposition of a.
Sample s + [0,1)" and let 1/2
for to [log m|
Compute 1 11 G(5b (()6
if' a; = 0 then
Keep t L, Lose +- R
else
Keep - R, Lose f-
end if
Sample CW t (0, 13A+2
Parse CW()) = scw cww &
(1)
Keep + t (f-1)
SCW
Keep
+ 1.- 11-1) Keep
b
low
end for
CW(++1) (-1)tt
B Convert(s!")) + Convert (m)))
return (W+++1)
G. Providing Differential Privacy
G.1. Implementation of Differentially Private Protocol
During the update aggregation stage, SecEmb ensures that each server learns only the aggregated updates. Consequently, only need to ensure that the aggregated updates-cquivalent to the servers' view-satisfy differential privacy (DP) throughout the training process.
Our protocol is possible to achieve the record-level DP that obfuscates single user-item interaction's contribution (Liu et al., 2022; Wei et al., 2020; Hua et al., 2015). To implement DP the two-server setting, each user conducts per-sample clipping on their local gradients g + g max (1, 22/g) (Abadi et al., 2016), and secret shares the clipped gradients for aggregation. On computing the secret shares of aggregated update Us. each server {0, 1} adds Gaussian noise independently v/ +- v, + +N(, To achieve (c, dDD the noise scale can be set as:
o (nn(125/00) A2/E.
(14)
G.2. Empirical Analysis
We deploy the SecEmb with (e. 8D guarantee on MLIM dataset under experiment settings described in Section 5.1, using batch sizes of 100 and 500. The privacy budget is analyzed with moments accountant (Abadi et al., 2016), which provides a tight bound over multiple iterations. Figure 6 shows that: (1) MF has the best trade-off between privacy and utility, where the uility loss within 2% for 2 This suggests that models with fewer parameters better preserve utility under similar privacy guarantees. (2) Increasing the batch size improves the privacy-utility trade-off, as noise is amortized more samples.
While DP is sufficient to provide formal privacy guarantee, combining DP with SecAgg reduces the overall magnitude of noise, thus offering significantly better privacy-utility trade-off than local DP. In Figure 7, we compare the utility between SecEmb and De-FedRec with MF model. De-FedRec operates without SecAgg, where each user independently adds Guassian noises to their uploaded gradients to satisfy (e, 60-ccll DP. Integrating SecAgg with DP improve the performance by over 57% under < 1.5 on ML.M, and over 47% under 13 on Yelp.
18

---

SecEmb; Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
satch_iize-00
betch size=
Non-DP
Nor abonalic fiterig
Doep facta toadon
1.0
RM/SE
110
iww.o
Figure Performance on MLIM dataset under various differential privacy budget c.
Sectmb Dn-Fusfacc
SedEimb
DP-fuctte:
33
33
34
13
14
Figure 7. Performance of SecEmb and DP-FedRec under various privacy budget using MF.
H. Dataset and Pre-processing
For each dataset, we encode the user and item features into binary vectors for model training. The features we select for binary encoding are given as follows:
ML100K: movie genre, user gender, user age, and user occupation.
MLIM: movie genre, user gender, user age, and user occupation.
ML10M: movie genre.
ML25M: movie genre.
Yelp: restaurant state.
The statistics of the datasets listed in Table 7.
Table 7. Statistics of the datasets. Yelp refers to the subset sampled from the whole dataset.
# Users
Items
# Ratings
User Features
Item Features
Density
ML100K
943
1,682
100,000
84
19
6.30%
ML1M
6,040
3,883
1,000,209
30
18
4.26%
MLIOM
69,878
10,681
10,000,054
0
20
1.34%
ML25M
162,541
62,423
25,000,095
0
20
0.25%
Yelp
10,000
93,386
1,007,956
16
0.11%
I. Hyperparameters of Recommender System
Each dataset is divided into 80% training and 20% testing data. For all cases, the recommender system is trained for 200 epochs. Each user represents an individual client and 100 clients are selected in each iteration. The parameters are updated
19

---

SecEmb; Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
using Adaptive Moment Estimation (Adam) (Kingma, 2014) method. We the combination of MSE and the regularization term the loss function. The security parameter is À 128. Each experiment run for four rounds and the average values are reported. Table 8 lists the specific hyperparameters for each dataset and model.
Table 8. Hyperparameters for federated training of recommender system.
ML100K
MLIM
MLIOM
ML25M
Yelp
Embedding size
64
64
64
64
64
MF
Learning rate Regularization weight
0.025
0.025
0.01
0.01
0.01
0.01
0.001
0.001
0.001
0.01
Embedding size
16
16
24
24
20
NCF
Learning rate Regularization weight
0.001
0.0001
0.001
0.001
0.001
0.001
0
0
0
0
Embedding size Learning rate Regularization weight
64
64
64
64
64
FM
0.025
0.025
0.005
0.005
0.01
0.1
0.001
0
0
0.01
Embedding size
64
64
64
64
DeepFiM
Learning rate Regularization weight
0.025
0.025
0.005
0.005
0.01
0.1
0.001
0
0
0.001
For NCF, we fix the the architecture of the neural network layers 2d - d/2. For DeepFM, the neural network layers are fixed to (1, + l, 2)d 4d > 2d. We set the number of selected items m' for ML100K, ML1M, ML10M, ML25M, and yelp 200, 300, 300, 500, and 500, respectively. Table 9 presents the size of sparse and dense parameters, corresponding to the item embedding (including item bias term) and the remaining parameters.
Table Size of dense and sparse parameters. # Sparse, # Non-zero Spr., and # Dense denote, respectively, the size of sparse update, size of non-zero elements in sparse update, and size of dense update.
ML100K
MLIM
MLIOM (10.7k Items)
ML25M
Yelp
(1.7k Items)
(3.9k Items)
(62.4k Items)
(93.4k Items)
# Sparse
109,330
252,395 10,764
694.265 9,295
4,057,495 9,945
6,070,090
# Non-zero Spr.
6,893
6,552
# Dense
0
0
# Sparse
55,506
128,139
523,369
3,058,727
3,828,826
NCF
# Nou-Zero Spr.
3,499
5.465
7,007
7.497
4,133
# Dense
688
688
1,512
1,512
1,060
# Sparse
109,330
252,395
694,256
4,057,495
6,070,090
# Non- zero Spr.
6,893
10,764
9,295
9,945
6,552
# Dense
6,696
3,121
1,301
1,301
1,041
# Sparse
109,330
252,395
694,256
4,057.495
6,070,090
DeepFM
# Non-zero Spr.
6,893
10,764
9,295
9,945
6,552
# Dense
1.761.065
856,370
395,798
395,798
330,002
In FedRec using SVD and CoLR message compression techniques, the rank of the reduced matrix is specified in Table 10. A lower value of rank indicates higher level of reduction ratio.
Table 10. Rank for reduced update matrix FedRec with SVD and CoLR compression techniques.
ML000K
MLIM
MLIOM
ML25M
Yelp
MF
4
NCF
10
4
4
FM
12
10
4
4
4
DeepFM
12
10
4
4
4
20

---

SecEmb; Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
J. Comparison among FL Protocols
compare our SecEmb with the following FL protocols:
Secure FedRec that downloads full model and utilizes the most efficient SecAgg protocol.
Two FL protocols with pearitty-aaars aggregation top-k sparsified gradients (Gupta et al., 2021; Aji & Heafield, 2017): Secure Aggregation with Mask Sparsification (SecAggMask) (Liu et al., 2023) and Top-k Sparse Secure Aggregation (TopkSecAgg) (Lu et al., 2023).
Two quantization methods: 8-bit quantization (Bit8Quant) (Dettmers, 2015) and Temary Quantization (TemQuant) (Wen et al., 2017).
Two low-rank update methods: singular value decomposition (SVD) (Nguyen al., 2024), and correlated Low-rank Structure (CoLR) (Nguyen al., 2024).
Table 11 summarizes the comparison along four dimensions:
Secure FL training: The training process should be secure, or compatible with SecAgg. other words, the server learns no information about client updates, including non-zero indices and their values, except the aggregated model. Mask and TopkSecAgg are not secure as they leak information about the non-zero indices. Kvsagg leaks more information the server than SecEmb it also exposes the exact number of clients who rated each item within batch beside aggregated results. The quantization and low-rank methods are compatible with SecAgg protocols.
Reduced model download: The client can download model in reduced size from the server, rather than the full model. Only CoLR and SecEmb allow to download the reduced model from the server.
Reduced gradient transmission: The client can upload parameter gradients in reduced size to the server, rather than the entire gradients. The listed algorithms, except secure FedRec, compress the transmitted gradients for communication-efficienn aggregation.
Operation on reduced model: The client can store and operate on reduced-size model locally for improved memory and computation efficiency. Unlike other algorithms, which assume users maintain full model for local updates, SecEmb enables efficient operation without this requirement.
The training process should be lossless. Only secure FedRec and SecEmb are lossless in principle, and thus lossless in practice. Kvsagg has minor failure rate, occasionally yielding inaccurate aggregation results, whereas SecEmb ensures error-free aggregation.
Lossless:
Among the FL protocols, only SecEmb simultaneously ensures efficiency, security, and utility for resource-comstrained edge devices.
Table 11.
Coarse -barse-grained comparison among FL protocols.
Secure FL
Reduced model
Reduced gradient transmission
Operation reduced model
Lossless
training
download
Secure FedRec
SecAggMask
x
X
TopkSecAgg
Kvsagg
X
X
Bit8Quant TerqQuant
X
X
X
X
SVD
X
X
CoLR
X
SeeEmb
21

---

SecEmb; Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
K. Additional Experiment Evaluation
K.1. Download Communication Cost
The download communication cost is presented in Table 12. We compare our SecEmb against secure FedRee that downloads the full model for local update. For MF and NCF, our protocol reduces costs by approximately 4x to 90x, depending on dataset item size. For FM, SecEmb achieves overhead reductions ranging from roughly 10x to 116x. In DeepFM, cost savings are modest (within 2x) for MI.10K and MLIM (item size less than 4k) but become more significant item size increases, reaching around 20x for the Yelp dataset.
Table 12. Download communication cost (in MB) per user for SecEmb and Secure FedRec in one iteration. Reduction ratio computed the communication overhead of Secure FedRec by that of SecEmb.
ML100K
MLIM
MLIOM (10.7k Items)
ML25M (62.4k Items)
Yelp
(1.7k Items)
(3.9k Items)
(93.4k Items)
Secure FedRec
0.43
0.99
2.73
15.98
23.91
MF
SecEmb Reduction Ratio
0.10
0.15
0.15
0.26
0.26
4.21
6.47
17.80
62.42
93.39
Secure FedRee
0.22
0.50
2.06
11.99
14.95
NCF
SecEmb
0.05
0.08
0.12
0,20
0.44
Reduction Ratio
4.04
6.28
16.96
60.55
91.00
Secure FedRec
1.12
1.74
3.59
20.97
29.88
FM
SecEmb Reduction Ratio
0.11
0.16
0.16
0.26
0.26
10.50
11.00
22.76
80.32
116.50
Secure FedRec
8.14
5.15
5.17
22.55
31.20
DeepFM
SecEmb
7.12
3.57
1.74
1.84
1.57
Reduction Ratio
1.14
1.44
2.98
12.26
19.84
K.2. Training Memory and Storage Analysis
In Figure 8 we present the training memory and storage cost for two cases: (1) SecEmb where each user utilizes merely the related item embeddings for model training. (2) Secure FedRec where users maintain the full model for training. It can be observed that SecEmb leads to substantial saving in memory and storage cost when the sparse item embedding matrix dominates the model parameters. For memory cost, the average savings are 12x, 21x, 101x, and 214x for MLIM, ML10M, ML25M, and Yelp, respectively. For storage cost, the average savings are 13x, 23x, 111x, and 247x for ML1M, ML10M, ML25M, and Yelp, respectively.
K.3. Comparison with Sparse Aggregation Protocol
In this section, we discuss the advantages of our SecEmb over existing sparse aggregation protocols. We consider two SOTA frameworks. Secure Aggregation with Mask Sparsification (SecAggMask) (Liu et al., 2023) and Top-k Sparse Secure Aggregation (TopkSecAgg) (Lu al., 2023). The key problem with the two frameworks that they fail ensure that the server learns nothing except the aggregated gradients. In particular:
Leakage of rated item index. For SesAggMask, each transmits the union of gradients with non-zero updates and masks to the server. For TopkSecAgg, each user is required to upload the coordinate set of non-zero gradients along with a small portion of perturbed coordinates. In both methods, the server could narrow down the potential rated items to a much smaller set.
Leakage of gradient values. While TopkSecAgg protects the values of non-zero updates against the server, SecAggMask would reveal the plaintext values to the server. Specifically, SecAggMask randomly masks a portion of the gradients to reduce communication cost, and fails to ensure that all non-zero gradients would be masked against any attackers.
As the above sparse aggregation protocols focus on minimizing the transmission during update aggregation stage, we compare the upload communication between our SecEmb and these protocols in Table 13. For SecAggMask, we adopt a mask threshold such that 60% non-zero gradients would masked in expectation. For TopkSecAgg, we set the perturbation proportion y to be 0.1, following (Lu et al., 2023). Both approaches result in higher communication cost than SecEmb
22

---

SecEmb: Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
SecEmb
Secure FedRec
Memory (Mib)
22
00
10
1000
000
9000
830
5000
1000
830
Storage
1000
800
430
1500
2000
200
230
Ceaff
ML1M
ML10M
ML25M
Yelp
Figure 8. Average memory cost (in MB) and storage (in 10 parameters) per during training phase. The memory cost computed with batch size of 1.
because: (1) Besides the non-zero embedding gradients, SecAggMask requires the user to send certain proportion of randomly masked zero updates to the server. (2) To cancel out the mask values, in TopkSecAgg each user sends the union of rated item embeddings for all participating user, rather than the those for each single user.
Table 13. Communication cost (in MB) per user for SecEmb and Sparse SecAgg during upload transmission in one iteration. General SecAgg adopts two-server ASS that has minimum communication overhead.
ML100K
MLIM
ML10M (10.7k Items)
ML25M (62.4k Items)
Yelp (93.4k Items)
(1.7k Items)
(3.9k Items)
General SecAgg
0.87
2.02
5.55
32.46
48.56
SecAggMask
0.27
0.61
1.66
9.60
14.35
MF
TopkSecAgg
0.32
0.66
0.91
1.17
1.95
Kvsagg
1.21
2.49
3.41
4.37
7.31
SecEmb
0.17
0.27
0.28
0.51
0.52
General SecAgg
0.45
1.03
4.20
24.48
30.64
SecAggMask
0.14
0.31
1.25
7.21
8.98
NCF
TopkSec
0.17
0.34
0.69
0.89
1,23
Kvsagg
0.61
1.25
2.57
3.29
4,58
SecEmb
0.13
0.20
0.26
0.46
0.43
General SecAgg
0.93
2.04
5,56
32.47
48.57
SecAggMask
0.27
0.61
1.66
9.60
14.35
FM
Agg
0.32
0.66
0.91
1.17
1.95
Kysugg SecEmb
1.21
2.49
3.41
4.37
7.31
0.22
0.29
0.29
0.52
0.53
General SecAgg
14.96
8.87
8.72
35.63
51.20
SecAggMask
14.30
7.44
4,81
12.76
16.99
DeepFM
TopkSecAgg
14.36
7.49
4.07
4.32
4,58
Kvsagg
15.25
9.31
6.57
7.53
9,94
SecEmb
14.26
7.12
3.45
3.68
3.16
23

---

SecEmb: Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
K.4. Server Computation Cost
To validate the practicality of SecEmb, we evaluate the server computation cost under increasing number of devices during the training stage. Note that the server computation can be speed up utilizing the efficient full domain evaluation in (Boyle et al., 2016). Table 14 compares the computation time of our framework with homomorphic encryption (HE) approaches with CKKS cryptosystem (Cheon et al., 2017). Though both frameworks scales linearly with the number of participating devices, SecEmb is approximately 1600x faster than the typical HE protocol on average.
Table [4. Server computation cost (in minutes) per iteration for MLIM dataset.
# of Active Users
100
200
300
400
500
HE (CKKS)
127.26
244.51
391.76
519.05
646.38
SecEmb
0.08
0.16
0.25
0.33
0.41
K.S. Breakpoint Analysis of Communication Cost
In Section 5.2.1 show that SecEmb offers advantages over the secure FedRec in terms of upload communication long as m' < mbd/ ((A log m + bd). The inequality usually holds for recommender system with sparse update. Note that the benefit on download communication is obvious where most users should rate over 50% of the total items to break the inequality-an an unrealistic scenario in practice.
Table 15 presents the maximum number of m' for each dataset where the aforementioned inequality holds. We use security parameter À= = 128 and 32-bit precision b = 32. It can be observed that the breakpoint of m' is sufficiently large, over 50% of the total item size m. is highly improbable for user to rate such a substantial proportion of items in practical scenarios.
Table 15. Maximum Value of mn' for Communication Cost Advantage over secure FedRec under Various Embedding Dimension d.
ML100K (1.7k Items)
MLIM (3.9k Items)
MLIOM (10.7k Items)
ML25M
Yelp
(62.4k Items)
(93.4k Items)
d = 64
1001
2210
5775
31038
45418
d = 128
1255
2817
6408
37453
56031
d 512
1550
3547
9655
55418
82495
K.6 Hyperparameters of Sequence Recommendation
We filter out users with less than ratings in Amazon dataset (https://csent) ucsd. edu/ edu/-mmcalleyy datasets/ wttpetts/ammmo//iinini
html), resulting in 9,267,503 items and 6,775,277 users. In each training round, 100 clients participate, and approximately 50,000 rounds are required to train the model on this extensive dataset. SecEmb and the four message compression baselines utilize the same hyperparameters as those used in prior sequence models. For SVD and CoLR, the rank of the reduced item embedding update matrix is set to 4 for the Amazon dataset and 8 for MLIM.
K.7. Ablation Study
We compare SecEmb with two variants that eliminates one or two optimizations describe in Section 4.3. Table 16 and 17 present the per user upload communication cost and computation cost, respectively. The initial construction of SecEmb incurs over 20x higher communication and computation costs on average compared to the improved version, and the cost can be higher than that for secure FedRec on dataset with lower item size (m <11k). Furthermore, sharing the binary path between the two modules reduces the communication and computation cost by around 1.5x.
L. Discussion
L.1. Assumption of Two Non-Colluding Servers
Our protocol relies on two non-colluding servers for security. Note that user privacy is guaranteed as long as one of the servers is honest, even if the other colludes with any number of clients. In practice, the two servers can be: (1) a cloud service provider who makes the recommendation, and a third party who provides the cryptography or evaluation service; or (2) two third parties who provide the cryptography or evaluation service.
24

---

SecEmb: Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
Table 16. Upload communication cost (in MB) for SecEmb and its variants.
ML100K
MLIM
MLI0M
ML25M
Yelp
Secure FedRec
0.86
1.99
5.47
31.96
47.81
SecEmb-Init
4,56
7.60
8.51
16.83
17.43
MF
SecEmb-RowwEn
0.28
0.43
0.45
0.78
0.79
SecEmb
0.17
0.27
0.28
0.51
0.52
Secure FedRee
0.44
1.00
4.11
23.98
29.89
SecEmb-Init
2.32
3.86
6.42
12.70
11.00
NCF
BocEmb-RowEing
0.18
0.28
0.38
0.67
0.61
SecEmb
0.13
0.20
0.26
0.46
0.44
Secure FedRec
0.91
2.01
5.48
31.97
47.82
SecEmb-Init
4.80
7.84
8.74
17.16
17.47
FM
SecEmb-RowEne
0.29
0.44
0.46
0.80
0.79
SecEmb
0.18
0.28
0.29
0.53
0.53
Secure FedRee
14.95
8.84
8.63
35.13
50.45
SecEmb-Init
18.84
14.66
11.89
20.23
20.10
DeepFM
SecEmb-RowEne
14.33
7.27
3.61
3.95
3,43
SecEmb
14.22
7.10
3.45
3.68
3.16
Table 17. Computation cost (in milliscconds) for secret generation per user for SecEmb and its variants.
MI.10KK
MI.IM
MI.IOM
M1.25M
Yelp
Secure FedRee
0.79
1.80
4.91
28.67
51.04
SecEmb-Init
5.34
15.35
22.56
28.53
26.43
MF
BecEmb-RowEne
0.37
0.90
0.91
1.34
1.47
SecEmb
0.31
0.47
0.47
0.72
0.74
Secure FedRec
0.40
0.92
3.71
21.68
27.09
SecEmb-IIi
5.50
8.76
15.03
25.95
21.76
NCF
SecEmb-Row
0.57
0.65
0.70
1.27
1.15
SccEmb
0.37
0.44
0.48
0.81
0.80
Secure FedRee
0.83
1.82
4.91
28.65
51.14
SecEmb-Inil
18.30
19.04
29.02
29.28
37.95
FM
SecEmb-Rowe
0.69
0.75
0.70
1.07
1.15
SecEmb
0.46
0.50
0.48
0.74
0.74
Secure FedRee
13.16
7.84
7.69
38.84
53.90
SecEmb-Init
38.94
35.74
37.78
34.85
39.94
DcepFM
SecEmb-RowEnc
13.15
7.88
4.84
5.48
6.33
SecEmb
12.99
6.67
3.45
3.77
3.54
While non-colluding parties common assumption in multi-party computation (MPC) protocols (Corrigan- Gibbs Boneh, 2017; Addanki al., 2022; Boneh al., 2021; Mohassel & Zhang, 2017), would be valuable to increase the colluding threshold of our protocol for enhanced security. A multi-party FSS for point function with full threshold t >> 2 achieves key size subpolynomial in domain size (Boyle et al., 2015; 2022), as opposed to the exponential reduction in the two-party case. For item embedding updates, the communication cost scales roughly with the square root of the item size m, rather than logarithmic in m as in the two-party setting. A scalable solution with an increased collusion threshold requires a more communication-cffiene
scheme.
L.2. Practical Considerations for Implementation of SecEmb
First, users might drop out during the implementation of our protocol. Our algorithm consists of two communication rounds per iteration: one for private embedding retrieval and another for secure update aggregation. Let and Uz denote the participating users in these rounds, with U2 C U1. users drop out the update aggregation phase, servers could
25

---

SecEmb: Sparsity-Aware Secure Federated Learning of On-Device Recommender System with Large Embedding
simply aggregate the gradients from users in Ug. Since each user independently generates their upload messages, the update aggregation on the retaining users remains unaffected.
Second, the aggregated gradients and updated models should be within the range [-R, R] to avoid overflow in group operation. Consider n2 participating users in each iteration, each user's s input should be constrained to [~R Ru, where Ru = R PR-11/ 1/pp- In SecEmb, this can be enforced by limiting the size CW(++1) to [log, R. .d bits, thereby restricting the range values each user can transmit.
Finally, we consider a dynamic setting where users rate new items during the training process. Since m' is a pre-specified. unified value determined the start based the average my, additionally ratings might increase each user's my. potentially making m' insufficient for most users. To address this issue, we periodically update m' based on the average of m While larger m' increases user payload, the efficiency gains remain substantial as long as m' is sufficiently small compared with m.
L.3. Application to Language Model Training
Our framework optimizes training efficiency in the embedding layer, making it applicable beyond RecSys to models with sparse embeddings updates, such as language models (LM) (Dubey et al., 2024; Sanh, 2019; Chen et al., 2024b;a; 2025). In the federated training of LM, users retrieve related token embeddings via our private embedding retrieval protocol, update the model locally, and upload the gradients our secure update aggregation module. Specifically, 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 aggregates the secret shares of token embedding updates for SecAgg. For scalable federated LM training, it is essential to integrate our framework with other parameter-efficier finetuning methods (Han et al., 2024; Hu et al., 2022).
26


Reviews:
[{"review_id": "tU8rHgy0gA", "reviewer": "Reviewer_TCtN", "summary": "This paper introduces a secure federated recommender system, tailored to the case where user data is sparsely presented. Conventional federated secure aggregation methods suffer from unnecessary communication overhead. Thus, the authors use function secure sharing and propose two modules (embedding retrieval module and update aggregation module) that forms the proposed lossless secure protocol SecEmb. The computation and communication complexities are analyzed. Emprical results demonstrates the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful comment and positive rating of our paper. Hope our response below could address your concerns.\n\n*Q1*: Elaboration on \"only the embeddings for interacted items are relevant for model updates\"\n\n*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:\n\n- Latent factor-based collaborative filtering RSs and their extensions, such as MF, NCF, FM, and DeepFM.\n- Sequential RSs based on item embeddings, such as CNN-based models (Caser), RNN-based models (GRU4Rec), and Attention-based models (SASRec).\n\n*Q2*: Assumption on two non-colluding servers.\n\n*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.\n\nCompared 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]. \n\n**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.\n\n[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).\n\n[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).\n\n[3]Boneh, D., ... & Ishai, Y. (2021). Lightweight techniques for private heavy hitters. In 2021 IEEE Symposium on Security and Privacy (SP) (pp. 762-776).\n\n[4]Apple and Google. (2021). Exposure Notification Privacy-preserving Analytics (ENPA) white paper.\n\n[5]https://machinelearning.apple.com/research/scenes-differential-privacy\n\n[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).\n\n[7]Chai, D., ... & Yang, Q. (2020). Secure federated matrix factorization. IEEE Intelligent Systems, 36(5), 11-20.\n\n[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).\n\n*Q3*: Application to unknown sparsity.\n\n*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. \n\n*Q4*: Abrupt introduction of l_x & Vague explanation for \"remaining parameters theta\"\n\n*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). \n\n*Q5*: Robustness to local devices drop out.\n\n*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).", "claims_and_evidence": "Line 215: \"only the embeddings for interacted items are relevant for model updates.\" Could the authors elaborate more on this claim? For example, is it a claim made for a specific type of recommendation systems, or it stands for any recommendation systems?\n\nOther main claims seem to be supported by both complexity analysis and empirical experiments.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "Experiment design is sound.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper is overall well written, and the evaluation is comprehensive in the given scope. That being said, the scope is limited: the proposed method only applies to secure federated recommendation system, where user data is sparse, and with two non-colluding servers. The paper would be strengthened if it can be applied to a wider range of settings, such as only one trusted server, or where the sparsity is unknown.", "other_comments_or_suggestions": "* Line 123. The introduction of l_x is abrupt, and its explanation only comes a few paragraphs later. \n* The explanation for \"remaining parameters theta\" is vague", "questions_for_authors": "* Is it easy to relax the assumption of two non-colluding servers? \n* How robust is the proposed method to local devices dropping out during training?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JQJIkg2De3", "reviewer": "Reviewer_EqFa", "summary": "This paper proposes a lossless and efficient federated recommendation training protocol to address the challenge of balancing efficiency and privacy in federated recommendation systems. \n\nAdditionally, it explores the use of row-wise sparsity in embedding matrices to optimize computational load. \n\nExtensive experiments demonstrate the protocol's superior performance in terms of communication and computational efficiency.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful comment and valuable suggestions. Hope our response below could address your concerns.\n\n*Q1*: The evaluation criterion for utility in this paper is relatively outdated.\n\n*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.\n\n[**Table R1.** Accuracy on ML1M using MF.]\n||SecEmb|Bit8quant|Ternquant|SVD|CoLR|\n|-|-|-|-|-|-|\n|HR@10|0.593|0.593|0.592|0.591|0.590|\n|NDCG@10|0.337|0.335|0.333|0.335|0.331|\n\n*Q2*: The paper’s original theoretical innovations are relatively limited.\n\n*Ans*: We would like to highlight the theoretical contributions of our work as follows:\n\n- **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).\n\n- **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.\n\nTo 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.\n\n*Q3*: The dimensional settings of NCF vary across different datasets\n\n*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.\n\n[**Table R2.** RMSE and Reduction Ratio (R.R.) for NCF under d=24.]\n|||SecEmb|Bit8quant|Ternquant|SVD|CoLR|\n|-|-|-|-|-|-|-|\n|ML100K|RMSE|0.944|0.951|0.953|0.947|0.961|\n||R.R.|4.27|3.90|7.56|4.62|4.75|\n|ML1M|RMSE|0.902|0.904|0.913|0.908|0.919|\n||R.R.|6.30|3.96|7.80|5.94|6.01|\n|Yelp|RMSE|1.029|1.031|1.032|1.037|1.059|\n||R.R.|76.54|4.00|7.99|12.21|12.22|\n\n*Q4*: Some essential related works, such as FedMF and LightFR, are missing. \n\n*Ans*: We will add more discussion of both works in our paper as follows:\n\n- 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.\n\n- 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).\n\n*Q5*: Does the experiment of MF and FM exist redundancy?\n\n*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.**\n\n*Q6*: Necessity of conducting the related experiments on language models\n\n*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).", "claims_and_evidence": "This paper makes a convincing case to a certain extent. Extensive experiments demonstrate the protocol's superior performance in terms of communication and computational efficiency.", "methods_and_evaluation_criteria": "The method proposed in this paper is relatively reasonable, using a lossless and efficient aggregation protocol to enhance efficiency and privacy. However, the evaluation criterion for utility in this paper is relatively outdated. Specifically, this paper uses RMSE to assess the performance of the algorithm, while the current mainstream methods for verifying the performance of recommendations mainly include HR, NDCG, MRR, etc.", "theoretical_claims": "I have examined the theoretical contributions of the paper and found that its original theoretical innovations are relatively limited.", "experimental_designs_or_analyses": "I examined the experimental setup and analysis and found that the dimensional settings of NCF vary across different datasets, whereas other backbone models, such as MF, FM, and DeepFM, maintain consistent dimensions across datasets. This inconsistency may lead to an unfair comparison.", "relation_to_broader_scientific_literature": "This paper leverages the sparsity of embedding matrices to achieve a lossless and efficient federated recommendation training protocol, which is likely to attract widespread attention from researchers.", "essential_references_not_discussed": "This paper primarily focuses on addressing efficiency and privacy issues in federated recommendation systems. However, some essential related works, such as FedMF [1] and LightFR [2], are missing. Specifically, FedMF introduces a homomorphic encryption technique to ensure privacy in federated recommendation systems, while LightFR leverages learning to hash to balance efficiency and privacy. The authors should conduct a more thorough review of the field and incorporate relevant literature to enhance the completeness of their work.\n\n\n[1] Chai D, Wang L, Chen K, et al. Secure federated matrix factorization[J]. IEEE Intelligent Systems, 2020, 36(5): 11-20.\n\n[2] Zhang H, Luo F, Wu J, et al. LightFR: Lightweight federated recommendation with privacy-preserving matrix factorization[J]. ACM Transactions on Information Systems, 2023, 41(4): 1-28.", "other_strengths_and_weaknesses": "Strengths:\n\n    1. The overall logic of this article is relatively clear. \n\n    2.This paper employs a large number of experiments and analyses to verify the effectiveness of the proposed method.\n\nWeaknesses:\n\n    1. In the experimental part, there are some inconsistent settings for the experiments, which may lead to unfair comparisons.\n     \n    2. The relevant work needs to be further supplemented to improve the overall progress in the relevant field.\n\n    3. The paper lacks effective analysis on certain experimental setups, such as why additional relevant experiments on language models are conducted and the necessity of MF and FM experiments.", "other_comments_or_suggestions": "As far as I know, this paper merely utilized the behavioral interaction information within the recommendation system. On this basis, FM is equivalent to MF without the utilization of additional auxiliary information. Therefore, does the experiment of MF and FM exist redundancy?", "questions_for_authors": "The core topic of this paper is to explore the privacy and efficiency of the embedding tables in recommendation systems. However, the appendix includes additional experiments related to the embedding tables of language models, which may lead to ambiguity in the topic. This is because the entities of Embedding in recommendation systems and those in language models are different. In recommendation systems, the objects are items, while in language models, the objects are tokens. Therefore, the author needs to provide an analysis of the necessity of conducting the related experiments.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eMbk68RxO6", "reviewer": "Reviewer_WwRR", "summary": "In the context of federated recommendation systems, this paper proposed the SecEmb protocol based on the Functional Secret Sharing algorithm and its coding property, which combines on-device request and update consistency on item indices. The protocol allows the client-side to only download and upload the embeddings of rated items, rather than the complete embedding table. It also ensures that the server is unaware of the rated items of each user and corresponding updated embeddings. Compared to the Secure FedRec, it significantly reduces the communication overhead between edge devices and the servers, as well as the computational overhead on the user side. Unlike existing dimensionality reduction and quantization methods, it retains complete information without sacrificing accuracy.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable comment and suggestions. Hope our response below could address your concerns.\n\n*Q1*: The criteria for dataset splitting should be added.\n\n*Ans*: We randomly split the ratings **for each user** into training and testing set.\n\n*Q2*: More large-scale datasets are desired & Add evaluation on sequence recommendation models\n\n*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. \n\nWe 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.\n\n[**Table R1.** Accuracy and Reduction Ratio (R.R.) using sequence models on Amazon dataset.]\n|||SecEmb|Bit8quant|Ternquant|SVD|CoLR|\n|-|-|-|-|-|-|-|\n|Caser|HR@10|0.629|0.628|0.623|0.627|0.625|\n||NDCG@10|0.483|0.481|0.478|0.483|0.480|\n||R.R.|2549|4|8|38|38|\n|SASRec|HR@10|0.639|0.636|0.635|0.621|0.600|\n||NDCG@10|0.485|0.485|0.483|0.472|0.463|\n||R.R.|2342|4|8|12|12|\n\n[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)\n\n[2]Kang, W. C., & McAuley, J. (2018). Self-attentive sequential recommendation. In 2018 IEEE international conference on data mining (ICDM) (pp. 197-206).\n\n*Q3*: The comparison with Kvsagg should be added.\n\n*Ans*: We will add the comparison as follows:\n\n- **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.\n-  Kvsagg has a **minor failure rate**, occasionally yielding inaccurate aggregation results, whereas SecEmb ensures error-free aggregation.\n- **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.\n\n[**Table R2.** Upload communication cost (in MB) using MF.]\n||ML100K|ML1M|ML10M|ML25M|Yelp|\n|-|-|-|-|-|-|\n|Kvsagg|1.21|2.49|3.41|4.37|7.31|\n|SecEmb|0.17|0.27|0.28|0.51|0.52|\n\n*Q4*: Issues of two server setting\n\n*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.\n\nCompared 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).\n\n[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).\n\n[4]Chai, D., ... & Yang, Q. (2020). Secure federated matrix factorization. IEEE Intelligent Systems, 36(5), 11-20.\n\n*Q5*: The font size in most figures is somewhat small.\n\n*Ans*: Thanks for pointing out. We will refine the figures to enlarge the font size.\n\n*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.\n\n*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)\n\ni 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.\n\n*Q7*: Compared to downloading the full embedding table, does this approach result in any loss?\n\n*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).", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "The evaluation was conducted on MovieLens and Yelp datasets using factorization-based models.", "theoretical_claims": "Yes, I checked Section Complexity and Security Analysis.", "experimental_designs_or_analyses": "Evaluation can be enhanced as follows:\n- The criteria for dataset splitting should be added. Is it divided according to the chronological order of all samples, the rating time of each user, or some other method? \n- More large-scale datasets are desired, such as the series of Amazon datasets.\n- The current mainstream sequence recommendation models should be added for evaluation.", "relation_to_broader_scientific_literature": "Federated learning for recommendation models with item embeddings.", "essential_references_not_discussed": "The comparison with Kvsagg: Secure aggregation of distributed key-value sets published in ICDE 2023 should be added.", "other_strengths_and_weaknesses": "The key innovation of this work lies in effectively utilizing redundant data from two transmissions to minimize various overheads in federated learning as much as possible. However, a limitation of this method is requiring at least two server parties, and it must be ensured in the application that the data from these two parties can be collated. Other suggestions on evaluation and comparison with related work can be found above.", "other_comments_or_suggestions": "The font size in most figures is somewhat small and difficult to read (for instance, the text in the overall framework of Figure 1 is not clear enough). 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.", "questions_for_authors": "Q1: Is it possible to adapt this method to a single server?\n\nQ2: Compared to the method of downloading the full embedding table, does this approach result in any loss in recommendation effectiveness?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9MOR4NRZ2t", "reviewer": "Reviewer_sPkh", "summary": "This paper proposes a privacy-preserving retrieval and aggregation method, SecEmb, that can be applied to federated recommender systems that leverage sparse embeddings. Likewise, due to the latent representation, SecEmb achieves faster computational & communication times versus standard (uncompressed) FedRec protocols. This is important in the federated setting, where communication, memory, and computational constraints are heavily present.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful comment and recognition of our work. Hope our response below could address your concerns.\n\n*Q1*: I will mention that the Theorems provided and proven in the supplementary material should be summarized in the main body.\n\n*Ans*: Thanks for your suggestion. We will move Theorem F.1 and F.2 to the main body to highlight our theoretical insights.\n\n*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.\n\n*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. \n\nFor 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.\n\nBelow we further provide explanations of R, Y, and X:\n\n- 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.\n- 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.\n- 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.\n\nTherefore, R, X, and Y provide distinct information, ensuring they complement rather than overlap with each other.\n\n*Q3*: The novelty simply revolves around applying a new secure retrieval and aggregation method fit for existing latent RecSys methods.\n\n*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.\n\nThis 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.**\n\nNote 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).\n\n*Q4*: What are the compression rates used for the other message compression methods? Are the hyper-parameters consistent across the methods?\n\n*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: \n\n- 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.\n- 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.\n\nThe **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.", "claims_and_evidence": "> Our SecEmb consists of two\ncorrelated modules: (1) a privacy-preserving embedding\nretrieval module that allows users to download relevant em-\nbeddings from the server, and (2) an update aggregation\nmodule that securely aggregates updates at the server.\n\nSection 4 nicely details each piece and provides insight into SecEmb's communication efficiency.", "methods_and_evaluation_criteria": "The paper does have a nice experimental section comparing SecEmb to many other compressed messaging schemes. It is a robust section which does showcase SecEmb's (marginal) improvement in performance.", "theoretical_claims": "I did not check the correctness. I will mention that the Theorems provided and proven in the supplementary material should be summarized in the main body.", "experimental_designs_or_analyses": "I did not thoroughly check the validity of the experimental analysis.", "relation_to_broader_scientific_literature": "It seems that this paper is slightly orthogonal to actual Federated RecSys training (i.e. actual compression) and instead focuses on how to transmit the compressed representations in a secure manner. I would ask for a more detailed description of the Federated RecSys setting (see my question below). However, I am not familiar enough in the secure messaging area to know how novel this new messaging scheme is.", "essential_references_not_discussed": "Not to my knowledge.\\.", "other_strengths_and_weaknesses": "## Strengths\n1. Effective retrieval and aggregation method applied to Federated RecSys. This is useful for the burgeoning federated recsys area.\n2. Well-written. \n3. Good empirical performance.\n\n## Weakness\n1. Slightly unclear RecSys problem formulation (see comment below).\n2. The novelty simply revolves around applying a new secure retrieval and aggregation method fit for existing latent RecSys methods. Much of the speedup arises from using a smaller, compressed space.", "other_comments_or_suggestions": "I would add more information about the problem setting. I had to dig a bit further into your cited work (e.g., Xue 2017) to better understand the low-dimensional latent factor setting. Specifically, a better understanding of the mapping from X,Y to P,Q and then going from P,Q to the recommendation value. Furthermore, aren't R and Y related? I didn't see this mentioned.", "questions_for_authors": "1. What are the compression rates used for the other message compression methods? Are the hyper-parameters consistent across the methods?\n2. Is the novelty of this work simply constructing a secure message process on top of existing latent RecSys methodology?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a lossless secure recommender systems on sparse embedding updates (SecEmb), which reduces user payload while ensuring that the server learns no information about both rated item indices and individual updates except the aggregated model. All reviewers are in favor of weakly accepting this paper and authors have addressed most of the concerns during the rebuttal phase, so I recommend acceptance.
Decision: Accept (poster)