PaperlayerView exact revision on arXiv

Source-linked AI summary

Federated Unlearning for On-Device Recommendation

Wei Yuan, Hongzhi Yin, Fangzhao Wu, Shijie Zhang, Tieke He, Hao Wang

arXiv:2210.10958v2cs.IR

TL;DR

Federated recommenders lack an efficient way to erase individual users’ contributions, although such forgetting matters for privacy and resilience to malicious clients. FRU revises historical updates and uses compact on-device storage to reconstruct recommenders; experiments report effective recovery, with importance-based selection outperforming random selection across tested settings.

  • Problem

    FedRecs lack efficient user-specific unlearning, which matters for users’ data-withdrawal rights and resistance to malicious attacks.

  • Method

    FRU rolls back and calibrates historical client updates, using mixed negative sampling and importance-based selection to store updates efficiently on client devices.

  • Results

    FRU recovers attacked FedRecs and achieves better performance than retraining in all reported cases; importance-based selection outperforms random selection across tested α values.

  • Takeaways & Limitations

    FRU provides a model-agnostic approach for erasing specific users’ influence while avoiding full retraining and reducing client-side update-storage demands.

  • Takeaways & Limitations

    Direct comparison with fully retrained parameters is unreliable because federated training contains many stochastic processes, so evaluation uses retraining as a baseline in attack scenarios.

Abstract

from arXiv · show

The increasing data privacy concerns in recommendation systems have made federated recommendations (FedRecs) attract more and more attention. Existing FedRecs mainly focus on how to effectively and securely learn personal interests and preferences from their on-device interaction data. Still, none of them considers how to efficiently erase a user's contribution to the federated training process. We argue that such a dual setting is necessary. First, from the privacy protection perspective, ``the right to be forgotten'' requires that users have the right to withdraw their data contributions. Without the reversible ability, FedRecs risk breaking data protection regulations. On the other hand, enabling a FedRec to forget specific users can improve its robustness and resistance to malicious clients' attacks. To support user unlearning in FedRecs, we propose an efficient unlearning method FRU (Federated Recommendation Unlearning), inspired by the log-based rollback mechanism of transactions in database management systems. It removes a user's contribution by rolling back and calibrating the historical parameter updates and then uses these updates to speed up federated recommender reconstruction. However, storing all historical parameter updates on resource-constrained personal devices is challenging and even infeasible. In light of this challenge, we propose a small-sized negative sampling method to reduce the number of item embedding updates and an importance-based update selection mechanism to store only important model updates. To evaluate the effectiveness of FRU, we propose an attack method to disturb FedRecs via a group of compromised users and use FRU to recover recommenders by eliminating these users' influence. Finally, we conduct experiments on two real-world recommendation datasets with two widely used FedRecs to show the efficiency and effectiveness of our proposed approaches.

1 INTRODUCTION

Federated recommendation protects local interaction data but has not addressed efficient user-specific forgetting. FRU targets this gap by revising historical updates, reducing storage, and recovering recommenders after malicious-user attacks.

  • Motivation: FedRecs have not addressed forgetting specific users, despite privacy rules granting users control over and withdrawal of their data.Unlearning also supports robustness against malicious participants.
  • Research gap: Existing recommender unlearning methods require centralized training data, while federated-learning unlearning methods target computer-vision classification tasks.Retraining from scratch is the naive alternative for removing target users’ contributions.
  • FRU: FRU rolls back and calibrates historical client updates to erase target users’ influence and accelerate federated recommender reconstruction.It stores updates locally rather than imposing server storage that scales with the client population.
  • Storage efficiency: FRU reduces on-device storage through user-item mixed negative sampling and importance-based selection of updates to retain.The sampling method reduces item-embedding updates, while selection avoids storing every parameter update.
  • Evaluation: FRU is evaluated on NCF and LightGCN using MovieLens-100k and Steam-200k, with results showing malicious-user influence can be erased and at least 7x speedup over retraining.The experiments use an attack involving compromised users to test recovery.

2 PRELIMINARIES

Federated recommendation predicts unseen-item preferences from decentralized user interactions, while machine unlearning removes selected users’ contributions. Retraining provides an ideal reference but is difficult to compare directly because federated training is stochastic.

  • Federated recommendation: FedRec predicts scores for non-interacted items and recommends each user’s top K ranked items.Users and items are represented through local interaction data and model embeddings.
  • Federated recommendation: A central server distributes global parameters, clients combine them with private user embeddings, and local training updates return for aggregation.User embeddings remain private while shared parameters are coordinated centrally.
  • Machine unlearning: Machine unlearning removes the contributions of a selected subset of users from the federated recommender.The unlearned model is expected to erase those users’ influence.
  • Evaluation: Retraining after removing users can produce an ideal reference model, but direct parameter comparison is unreliable because federated training includes many stochastic processes.Evaluation therefore uses the retrained model as a baseline in attack scenarios.

3.1 Overview

FRU reconstructs a federated recommender by using stored client updates rather than retraining from scratch. Its workflow combines compact on-device update storage with rollback and calibration of historical updates.

  • Efficient storage: Efficient on-device storage uses mixed negative sampling to reduce updated parameters and importance-based filtering to discard less important historical updates.These components address storage constraints on client devices.
  • Overview: FRU calibrates historical updates from the point at which a deleted client joined, then aggregates them to reconstruct the recommender.The workflow first rolls back and then revises updates for the remaining clients.
  • Update handling: Global or public updates, such as item embeddings, are uploaded for server aggregation, while local or private user-embedding updates remain on the client.The update notation distinguishes public and private parameter changes.

3.2 Base Federated Recommenders

The base FedRec setting combines private user embeddings with server-provided item embeddings and global parameters. FRU is evaluated with both neural and graph-based recommenders under a standard federated protocol.

  • Evaluation setup: FRU’s generalization is tested with NCF and LightGCN trained using the most typical federated learning protocol.These are presented as two commonly used recommender architectures.
  • NCF: NCF models complex user-item relationships with an L-layer feedforward network extending collaborative filtering.It uses user and item embeddings as inputs to the network.
  • LightGCN: LightGCN represents users and items as nodes in a bipartite interaction graph and learns embeddings by propagating neighbor information.Under FedRec, each client can access only its local user-item graph because neighbor-user embeddings remain unavailable.
  • Federated protocol: The federated protocol keeps each user embedding private while the server initializes and distributes item embeddings and other global parameters.Clients update the combined local model using their local interaction data.

3.3 Efficient On-Device Update Storing

FRU reduces on-device log storage by selecting important item updates and using fewer, semi-hard negative samples. These mechanisms target the item embeddings that dominate local model size while preserving recommendation performance under the reported settings.

  • Importance-based Update Selection: FRU stores only interacted and sampled-negative item updates, then filters them by update significance instead of retaining the whole item embedding table.The selected updates represent a small portion of the item set, and importance-based selection keeps only the top α proportion.
  • User-item Mixed Semi-hard Negative Sampling: The user-item mixed semi-hard sampler chooses candidate negatives using user or pseudo-user relevance and avoids the hardest items to reduce false negatives.At early training stages, the centroid of interacted-item embeddings supplies a pseudo-user embedding because item embeddings update more frequently.
  • User-item Mixed Semi-hard Negative Sampling: The method reduces required negative samples while retaining comparable model performance at β=0.5.The sampling process first forms a candidate pool and then randomly selects N×β samples from it.
  • Storage Space Cost Analysis: On Steam-200k, storing updates adds 17.5% space for NCF and 8.75% for LightGCN relative to FedRec without unlearning.The reported average storage costs are about 900C for NCF and 450C for LightGCN, with 5,134 total items.

3.4 Unlearning with Updates Revision

FRU unlearns users by rolling back the recommender and revising historical updates from remaining clients. It reconstructs the model with fewer local training epochs and reports up to 10x speedup, with an empirical 7x speedup, over retraining from scratch.

  • Rollback and Update Revision: FRU rolls back to the initial state or the first affected users’ joining state, removes target users, and recalibrates remaining clients’ historical updates.The process repeats across global rounds to obtain the unlearned model.
  • Accelerated Reconstruction: FRU uses λL local training epochs during reconstruction because it only needs to approximate directions that fit the remaining data.The recovered clients are the original round’s clients except those removed, and L is the original local-training epoch count.
  • Rollback and Update Revision: FRU combines newly computed update directions with original update lengths to construct calibrated updates for reconstructing global parameters.The method preserves update lengths while revising directions, and it also accounts for private user embeddings in FedRecs.
  • Accelerated Reconstruction: With λ=0.1, FRU achieves up to 10x speedup and is empirically 7x faster than retraining from scratch.The speedup follows from reducing local training, whose time dominates the federated unlearning process.

4 EXPERIMENTS

The experiments evaluate FRU against Retrain and FedRemove for recovering attacked federated recommenders, measuring both recovery effectiveness and efficiency. FRU recovers attacked models while substantially reducing recovery time compared with retraining from scratch.

  • Experimental Setup: Experiments use MovieLens-100k and Steam-200k with NCF and LightGCN, evaluating recovery after malicious clients upload poisoning gradients.The study measures whether the FedRec is recovered and how efficiently unlearning reconstructs it.
  • Recovery Effectiveness: FRU recovers attacked FedRecs and achieves better recommendation accuracy than Retrain in all tested cases.FedRemove performs poorly for both NCF and LightGCN, highlighting the importance of calibrating updates.
  • Recovery Effectiveness: Importance-based update selection further improves FRU, while over-calibration can negatively affect model performance.The results indicate that calibrating only important updates is preferable to calibrating all updates.
  • Efficiency of Unlearning: 7x faster than Retrain, FRU recovers both NCF and LightGCN under the reported settings.FRU is also slightly faster than FRU without importance-based update selection because fewer item embedding updates require calibration.
  • Efficiency of Unlearning: FedRemove is the fastest unlearning method but has the worst unlearning effectiveness because it does not calibrate updates.This comparison illustrates the trade-off between recovery speed and removing malicious users’ influence.

4.3 Ablation Study and Hyperparameter Analysis

The ablations examine how update-selection, negative-sampling, and recovery-speed settings affect FRU across NCF and LightGCN. Importance-based selection and mixed semi-hard negative sampling improve efficiency-related trade-offs, while larger recovery speed factors increase recovery time and generally reduce performance.

  • Experimental Setting: The experiments use MovieLens-100k and Steam-200k with NCF and LightGCN, while reporting MovieLens-100k because similar trends appear on Steam-200k.Other component hyperparameters remain unchanged when one component is investigated.
  • Importance-based Update Selection: Importance-based update selection outperforms random selection across all tested α values for NCF and LightGCN.FRU performance first rises and then falls as α increases, indicating that storing too many unimportant updates can hurt performance.
  • User-item Mixed Semi-hard Negative Sampling: The mixed semi-hard negative sampling method outperforms all baselines under the same β values.β=0.5 uses half the original negative-sampling rate.
  • User-item Mixed Semi-hard Negative Sampling: The proposed negative sampling method at β=0.5 achieves almost the same performance as random sampling at β=1.0.This reduces negative-sample size and item-embedding updates without compromising recommendation performance.
  • Recovery Speed Factor: Recovery time consistently increases as λ increases, while larger λ values generally lower performance across FedRecs.NCF performance drops with increasing λ; LightGCN shows a more complex but overall similar pattern.

5 RELATED WORK

Related work covers federated recommendation and machine unlearning. Prior FedRec studies improve training, feedback use, security, or modeling, while unlearning research distinguishes exact and approximate approaches and has not addressed this paper’s setting.

  • Federated Recommendation: Prior federated recommendation work improves convergence, feedback utilization, security, and graph-based modeling.Examples include FedFast, explicit-feedback methods, denoising techniques, and GNN-based frameworks.
  • Machine Unlearning: Machine unlearning methods are classified as exact or approximate according to whether they theoretically guarantee removal of data influence.Exact methods require complicated calculations and are generally limited to specific simple models.
  • Machine Unlearning: Approximate unlearning relaxes certifiable erasure and provides statistical assurance that targeted data are forgotten to a large extent.Existing federated unlearning approaches described here use gradients or knowledge distillation and target federated classification settings.

6 CONCLUSION

The paper presents FRU as a federated unlearning framework for on-device recommendation. It combines historical-update calibration, storage-efficient mechanisms, malicious-user attacks, and experiments showing influence removal with 7x recovery speedup.

  • Conclusion: FRU stores historical updates, calibrates them to reconstruct FedRecs, and uses importance-based selection plus negative sampling for device efficiency.The framework is model-agnostic and is designed for resource-constrained devices.
  • Conclusion: FRU evaluates unlearning by attacking FedRecs with compromised clients and then removing those users’ influence.Experiments use two popular recommenders and two real-world recommendation datasets.
  • Conclusion: FRU eliminates specific users’ influence and recovers FedRecs with 7x speedup.The paper also reports ablation studies examining the contributions of FRU’s components.
Loading 2210.10958v2…