Netflix and Forget: Efficient and Exact Machine Unlearning from Bi-linear Recommendations

Mimee Xu, Jiankai Sun, Xin Yang, Kevin Yao, Chong Wang

Introduction

In the modern digital landscape, regulations like GDPR have codified the "Right to be Forgotten," requiring platforms to delete user data upon request. In recommendation systems, this goes beyond simple database deletion; it necessitates removing the influence of that data from the underlying machine learning models. For instance, a user might want to stop receiving recommendations based on a specific period of their watch history to move past certain life events.

Conceptual motivation for machine unlearning in recommendation systems.

The gold standard for privacy in this context is "retraining from scratch" without the deleted data. However, for industrial-scale systems like Netflix or Amazon, full retraining is computationally prohibitive. This paper introduces Unlearn-ALS, a method designed for bi-linear recommendation models that achieves the exactness of retraining with the efficiency of fine-tuning.

The Unlearn-ALS Framework

The authors focus on bi-linear models (e.g., matrix factorization) optimized via Alternating Least Squares (ALS). The Unlearn-ALS algorithm (and its heuristic counterpart, Untrain-ALS) follows a three-step procedure:

  1. Preference Reset: The target user-item interaction $p_{ui}$ is set to zero.
  2. Confidence Blocking: The confidence score $c_{ui}$ for that interaction is also set to zero, effectively removing its weight from the loss function.
  3. Efficient Fine-tuning: The model is updated starting from its previous state rather than a random initialization.

A key technical contribution is the application of the Woodbury matrix identity. By recognizing that deleting a single interaction only alters one entry in the diagonal confidence matrix, the authors reduce the complexity of the required matrix inverse update from $O(k^3)$ to $O(k^2)$, where $k$ is the number of latent features.

Experimental Validation

The method was evaluated using the MovieLens-100K and MovieLens-1M datasets. The primary goal was to verify if the unlearned model could match the performance of a model retrained from scratch across various "removal fractions"—the percentage of training data requested to be forgotten.

Convergence of the unlearned (untrained) model to the retrained baseline over 10 iterations.

As shown in the figure above, the "untrained" (unlearned) model rapidly converges to the "retrained" model's AUC. While the model initially retains the performance of the undeleted state (at iteration 0), by iteration 10, the performance is virtually identical to the retrained baseline across all removal percentages (from 5% to 90%). This confirms the "exactness" of the method: it reaches the same optimal model state as full retraining but significantly faster. While retraining on MovieLens-1M typically requires 40 to 70 iterations, Unlearn-ALS achieves parity in just 10.

Privacy and Robustness

The paper also explores the inherent robustness of low-rank models. Because matrix factorization generalizes across broad user-item patterns, the removal of a small number of random data points often has minimal impact on the global model parameters.

To measure privacy more effectively, the authors critique standard Membership Inference (MI) attacks as being too noisy for this specific task. They propose a new metric, Intrinsic Vulnerability ($IV'$), which isolates the privacy risk specifically introduced by the unlearning process by subtracting the baseline vulnerability of the original, undeleted model.

Conclusion

Unlearn-ALS provides a mathematically rigorous and computationally efficient solution for exact machine unlearning in bi-linear recommendation systems. By leveraging the Woodbury identity and the properties of ALS, the authors demonstrate that platforms can honor deletion requests without sacrificing model utility or incurring the massive costs of full retraining. Future work remains to extend these principles to deep neural network-based recommenders and to further refine empirical privacy evaluations.

Summary updated

Abstract

People break up, miscarry, and lose loved ones. Their online streaming and shopping recommendations, however, do not necessarily update, and may serve as unhappy reminders of their loss. When users want to renege on their past actions, they expect the recommender platforms to erase selective data at the model level. Ideally, given any specified user history, the recommender can unwind or "forget", as if the record was not part of training. To that end, this paper focuses on simple but widely deployed bi-linear models for recommendations based on matrix completion. Without incurring the cost of re-training, and without degrading the model unnecessarily, we develop Unlearn-ALS by making a few key modifications to the fine-tuning procedure under Alternating Least Squares optimisation, thus applicable to any bi-linear models regardless of the training procedure. We show that Unlearn-ALS is consistent with retraining without \emph{any} model degradation and exhibits rapid convergence, making it suitable for a large class of existing recommenders.
BibTeX
@misc{xu2023netflix,
  author = {Mimee Xu and Jiankai Sun and Xin Yang and Kevin Yao and Chong Wang},
  title = {{Netflix and Forget: Efficient and Exact Machine Unlearning from Bi-linear Recommendations}},
  year = {2023},
  eprint = {2302.06676},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2302.06676},
}
Figure