UltraRE: Enhancing RecEraser for Recommendation Unlearning via Error Decomposition
Authors: Yuyuan Li
Chaochao Chen
Yizhao Zhang
Weiming Liu
Lingjuan Lyu
Xiaolin Zheng
Dan Meng
Jun Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: recommendation unlearning
machine unlearning
recommender systems
ensemble learning

Abstract: With growing concerns regarding privacy in machine learning models, regulations have committed to granting individuals the right to be forgotten while mandating companies to develop non-discriminatory machine learning systems, thereby fueling the study of the machine unlearning problem. Our attention is directed toward a practical unlearning scenario, i.e., recommendation unlearning. As the state-of-the-art framework, i.e., RecEraser, naturally achieves full unlearning completeness, our objective is to enhance it in terms of model utility and unlearning efficiency. In this paper, we rethink RecEraser from an ensemble-based perspective and focus on its three potential losses, i.e., redundancy, relevance, and combination. Under the theoretical guidance of the above three losses, we propose a new framework named UltraRE, which simplifies and powers RecEraser for recommendation tasks. Specifically, for redundancy loss, we incorporate transport weights in the clustering algorithm to optimize the equilibrium between collaboration and balance while enhancing efficiency; for relevance loss, we ensure that sub-models reach convergence on their respective group data; for combination loss, we simplify the combination estimator without compromising its efficacy. Extensive experiments on three real-world datasets demonstrate the effectiveness of UltraRE.

UltraRE: Enhancing RecEraser for Recommendation Unlearning via Error Decomposition
Yuyuan Li
Chaochao Chen"
Yizhao Zhang
College of Computer Science Zhejiang University Hangzhou, China 118210228zjur edu. cn
College of Computer Science
College of Computer Science Zhejiang University Hangzhou, China 222213376zju edu cn
Zhejiang University Hangzhou, China z ejuccc0zju.edu.
Weiming Liu College of Computer Science
Lingjuan Lyu
Xiaolin Zheng
Sony AI Japan lingjuan wwwsolv.ecccooom com com
College of Computer Science Zhejiang University Hangzhou, China xlzhengozju. edu, cn
Zhejiang University Hangzhou, China 218310108zju. edu. on
Dan Meng OPPO Research Institute Shenzhen, China mengdan900163.com
Jun Wang
OPPO Research Institute
Shenzhen, China
junwang www.:lll@maalccm com
Abstract
With growing concerns regarding privacy in machine learning models, regulations have committed to granting individuals the right to be forgotten while mandating companies to develop non-discriminatory machine learning systems, thereby fuel- ing the study of the machine unlearning problem. Our attention is directed toward a practical unlearning scenario, i.e., recommendation unlearning. As the state-of- the-art framework, i.e., RecEraser, naturally achieves full unlearning completeness, our objective is enhance in terms of model utility and unlearning efficiency. In this paper, we rethink RecEraser from an ensemble-basee perspective and focus on three potential losses, i.e., redundancy, relevance, and combination. Under the theoretical guidance of the above three losses, we propose new framework named UI UltraRE, which simplifies and powers RecEraser for recommendation tasks. Specifically, for redundancy loss, incorporate transport weights in the clustering algorithm to optimize the equilibrium between collaboration and balance while enhancing efficiency; for relevance loss, ensure that sub-model reach convergence on their respective group data; for combination loss, we simplify the combination estimator without compromising its efficacy. Extensive experiments on three real-world datasets demonstrate the effectiveness of UltraRE. The source codes are available at httph:t///// http::///ttttis gighhu....... com homm/hhanggizhaa/lutraaaa
1 Introduction
Machine Learning (ML) models have made significant strides in various domains, including natural language processing (36), image recognition [15), and recommender systems [18] (7] (8). However, privacy concerns arise due individual data involved in training MI. models. These concerns are
"Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

mainly twofold. Firstly, the General Data Protection Regulation (GDPR) 44] provides individuals with the right to request the removal of their data, including any impact the data may have on the trained models, i.e., the right to be forgotten. Secondly, the Algorithmic Accountability Act [31 requires companies to evaluate the effect of their MI. systems on bias and discrimination.
Machine unlearning is a practical approach that promotes privacy in ML systems by removing previously used data and learned information from ML models. Individuals can remove sensitive information that is learned through their data, while companies can proactively unlearn biased [32] or inaccurate [24] data. Unlearning methods can be divided into two approaches based on the level of completeness, namely exact unlearning (full completeness), and approximate unlearning (partial completeness).
In this paper, we concentrate on recommendation unlearning. The personalized recommendation is typical scenario that urgently requires unlearning because (i) recommender systems rely heavily on individual data, and (ii) the performance of recommendation is highly sensitive to the quality of training data [40]. Existing recommendation unlearning method (7) follows the Exact Unlearning (EU) approach. As retraining is an algorithmic way to ensure fully complete unlearning, EU approach mainly developed on the ensemble retraining framework 4 26 48). Similar to the idea of ensemble learning (39), the ensemble retraining framework involves dividing the dataset into non- overlapping shards, training sub-mode for each shard independently, and ultimately combining all sub-models. The ensemble retraining framework limits retraining overhead to sub-models, thereby avoiding retraining from scratch on the entire dataset.
However, the ensemble retraining framework's non-overlapping division isolates user and item collaboration, which leaves considerable room for performance improvement in recommendation tasks. Guided by the intuition of collaboration preservation, RecEraser groups similar data together and combines sub-models with attention networks. In this paper, we analyze RecEraser as an ensemble system through a theoretical lens, and find that i) existing clustering algorithms exhibit an incongruity between the requirements of collaboration and balance, and ii) the usage of attention networks is not necessary. As shown in Figure I the lower bound of eπror rate B(E) in an ensemble system can be decomposed into three components, i.e., redundancy, relevance. and combination loss (34). Each of these components is associated with particular stage of the ensemble retraining framework. Considering the three loss components as a well-grounded set of metries, we simplify and power the State- Miee-OOfThheAAr (SOTA) recommendation unlearning framework, i.e., RecEraser. Specifically, for redundancy loss (stage I), we incorporate transport weights in the clustering algorithm to pursue the optimal trade-off between collaboration and balance; for relevance loss (stage II), we ensure that sub- models reach convergence on their respective shard data; for combination loss (stage III), we simplify the design of the sub-model combiner to reduce complexity without compromising its efficacy. As result, we propose a novel recommendation unlearning framework named Ultra RecEraser (Ul traRE) that offers greater model utility and efficiency while still achieving full completeness. The main contributions of this paper are summarized as follows:
We propose a novel ensemble retraining framework (UItraRE) to address the problem of recommendation unlcarning. UltraRE enhances both model utility and unlearning efficiency while achieving unlearning completeness at the algorithmic level.
During stage I (non-overlapping division), we propose an optimal balanced clustering algorithm that transforms the discrete clustering problem into a continuous optimization process while incorporating balanced constraint to achieve both balanced clustering and minimal inertia simultaneously.
During stage III (model combination), we take an empirical investigation into the choice of model combiners, and simplify the complexity of model combiner without compromising model utility.
We empirically validate and demonstrate the proposed framework through extensive experi- ments on three real-world datasets in terms of model utility and unlearning efficiency.
2 Preliminary
In this section, we first briefly introduce the goals and targets in recommendation unlearning, followed by the error decomposition of an ensemble system.

---

Lower Bound Decomposition
Leamnigg
Lombbs
Perr 2 B(e)
Unlearning
Prediction
Shard S1
Sub-model Mc
Original Training Data
Shard
Sub-model Mdz
Model M
Unlearning Request
E
Shard
Sub-model M,
Stage I: Non-overlapping Division
Stage II Independent Training
Stage III: Model Combination
Feddu: redundancy (==diverstty)
Jrie: relevance (=aacuurcc))
Loanh: combination (e.g., voting)
Figure 1:
Decomposition of error rate [34] in the ensemble retraining framework which is the SOTA framework for model-agnostie exact unlearning and recommendation unlearning.
2.1 Recommendation Unlearning
Unlearning Goals. As introduced in 77 26], there are mainly three goals for an unlearning task: (GI) Unlearning completeness, which requires completely eliminating the impact of target data from a previously trained model; (G2) Unlearning efficiency, which entails maximizing the efficiency of unlearning while minimizing the need for computationally expensive retraining; and (G3) Model utility, which ensures that the unlearned model can achieve recommendation performance comparable that of the model retrained from scratch.
As the ensemble-retaining framework belongs to the EU approach, which naturally achieves G1 at an algorithmic level, i.e., the highest level of completeness [43). In this paper, our objective is to enhance the quality of the ensemble-retraining framework within the recommendation context, with a view advancing G2 and G3.
Unlearning Targets. The concept of training data holds multifaceted view, resulting in different unlearning targets. In the context personalized recommendation, the user-item interaction serves as the training data. Considering ratings as a form of user-item interaction, the unlearning target may differ based on the perspective, either focusing on the user-wise, item-wise, or sample-wiss aspects. For instance, user-wise unlearning refers to unlearning all interactions made by the specific target user(s). In this paper, we focus on the ensemble retraining framework, which is versatile and can be applied to any type of unlearning target.
2.2 Ensemble System
Ensemble learning has proven to be successful in various fields of machine learning. An ensemble system involves combing multiple models, such as bagging [3] stacking [46], and mixture of experts 220 42). Early studies have been guided by the intuition that ensemble systems achieve better performance when employing a combination of accurate and diverse models. From theo- retical standpoint, using Fano's inequality of information theory, 344] decomposes the error rate of an ensemble system into three components, i.e., redundancy (model diversity). relevance (model accuracy), and combination (information lost during model combination) loss. As shown in Figure [] the aforementioned ensemble retraining framework is basically ensemble system. We divide the ensemble retraining into three stages, i.e., non-overlapping division, independent training, and model combination. Each stage is associated with one specific error component.
Related Work
3.1 Machine Unlearning
Machine unlearning the process of removing the influence specific training data, i.e., unlearning target, from a learned model (35). A naive approach to achieve this is by retraining the model from
3

---

Following SISA's scratch on the updated dataset that excludes the target. However, this approach can be computationally prohibitive in practice. Based on the degree of unlearning completeness, existing unlearning methods can be classified into the following two approaches.
Exact Unlearning. This approach aims to ensure that unlearning target is fully unlearned, i.e., as complete as retraining from scratch. Cao and Yang [6] achieved this by transforming training data points into reduced number of summations to enhance unlearning efficiency. Recently, Bourtoule et al. [4] proposed an ensemble retraining framework, i.c. SISA, which divides the dataset into non-overlapping subsets, trains sub-model on each subset, and combines all sub- models in the end. This design reduces the retraining overhead to subsets. Similarly, ARCANE [48] divides the dataset by class and applies one-class anomaly detection training on each subset. However, ARCANE can only be applied to classification tasks.
Approximate Unlearning. This approach estimates the influence of unlearning target, and removes the influence through direct parameter manipulation [I] efficient than exact unlearning, this approach faces challenges regarding unlearning completeness, ie.. exactness, due to the inaccurate estimation of influence. In this approach, the influence of unlearning target is estimated by influence function (21, which is found to be fragile in deep learning M. Recent studies also point out that the influence of individual training data on deep models is intractable to compute analytically [12
R 41 45) While theoretically more
3.2 Recommendation Unlearning
RecEraser proposed to achieve unlcarning in recommender systems 77.
ensemble retraining framework, RecEraser groups similar data together, instead of random divi- sion. This modification effectively preserves collaborative information necessary for personalized recommendations. In addition, RecEraser uses an attention based combination to further enhance model utility. Similarly, LASER also groups similar data together a model on each subset and combining them, LASER trains model sequentially on each subset using curriculum learning. While this modification significantly enhances model utility, it comes at the cost of reduced efficiency. Theoretically, LASER can only accelerate the unlearning speed two times compared to retraining from scratch, which is generally unsatisfying in practice. Recently, Approximate recommendation unlearning was proposed to enhance efficiency [25]. However, it still suffers from common weaknesses of approximate unlearning and is unable provide algorithmic unlearning completeness, which exact unlearning achieves.
[26]. However, instead of training
4 Methodology
In this section, we present our UltraRE for addressing the recommendation unlearning problem. Following the design of the ensemble retraining framework, we rethink RecEraser from ensemble- based perspective. Instructed by the eиrоr decomposition theory in ensemble systems (see Figure [ we associate each loss component with specific stage in the ensemble retraining framework. Our proposed UltraRE refines the design of each stage to minimize its corresponding loss component. In the following subsections, describe in detail the modifications we propose for each stage.
4.1 Redundancy Loss (Stage I)
In stage I, the ensemble retraining framework divides the original training data into several non- overlapping shards.
Random Balanced Division. The original framework (SISA 4. designed for the machine un-
learning problem). uses random balanced division. The assumption that there no prior knowledge regarding the distribution of unlearning requests is widely accepted and practical [4] 7 (26). In the absence of such knowledge, is optimal to presume that users submit these requests with equal prob- ability. Therefore, in order to attain optimal unlearning efficiency, the ensemble retaining framework needs to achieve balanced division. The theoretical explanation can found in Appendix

---

Balanced m-maans. Collecting collaborative information across users and items is essential to the performance of recommendation mod-
No. of grorg
No. of gooage
els. With the intuition of preserving collabora- tion, RecEraser 77] uses clustering algorithms to group similar samples together. Additionally, RecEraser needs to achieve balanced division. Thus, the balanced clustering algorithms were proposed 7
0.2
0.6
1.0
0.
04
0.6
Sample precentage
Sample percentage
(a) Balanced Grouping
(b) Imbalanced Grouping
Figure 2: anced grouping. We conducted an experiment on a real-world dataset (MI--1M), (a) and (b) are the re- sults of random balanced division and k-means re- spectively. Each color block represents one shard. The size of the block varies with the number of samples in the shard, with larger blocks represent- ing more samples.
An illustration of balanced and imbal-
g 26 Assume that there are N input samples a E IR for clustering. Note that the input samples can consist of user embedding, item embedding, or a combination of both de- pending on the unlearning target, i.e., user-wise, item-wise, or sample-wise. The core idea of their proposed algorithm is i) limiting the maxi- mum number of samples in one shard, typically |S S [N/k], ii) constructing priority list for sample to its destination shard by priority value.
every sample-centroid pair, and iii) assigning each
4.1.1 Optimal Balanced Clustering
The loss component for stage is redundancy loss, which directs ensemble systems to enhance
O P1
As
Ak
the diversity among shards (34] This theoretical
0.05
guidance conforms with prior work's intuition of collaboration preservation, which proposes the balanced k-means algorithm to group sim- ilar samples together 77. However, to achieve a balanced division, balanced k-means may not always assign samples their optimal clusters. In practice, as shown in Figure [ this can re- sult in a significant number sub-optimally assigned samples, which degrades the clustering performance. To address this incongruity, we propose an Optimal Balanced Clustering (OBC) algorithm that achieves an adaptive equilibrium between sample similarity and shard balance.
Balenced
Opeinal Balanced Clustoring
Figure 3: algorithms. The red block located at coordinate (x,, M4)) represents assigning æ; to pt. On the left, k-means groups samples hased solely on their sim- ilarity, resulting in imbalanced result. In the middle, balanced k-means forces a balanced re- sult by considering similarity-based priority list. On the right, Optimal Balanced Clustering (ÖBC) incorporates balanced constraint into the opti- mization process and assigns samples according to their transport weight values.
An illustration of different clustering
Generally speaking. OBC incorporates bal- anced constraint into the optimization process. As illustrated in Figure 3 we obtain the trans- port weight of assigning an input sample æ to cluster centroid μ through the optimization process. The input samples are assigned to the cluster with the largest weight. To start with the derivation of OBC, we first introduce the basic concept of k-means. The k-means algorithm minimizes the total distance of each sample-centroid pair, namely inertia I. It is formally defined as
| 1312. H, = Σies, C; jilies,
I
[S]
Considering x and il as two variables respectively sampled from subsets X and Y in the Euclidean space Rd. the problem of inertia minimization can be framed as the Monge-Kann Kantoroviit problem.
Problem 1 (Monge- Kantoroich Problem). Given the transport cost function e: X x Y - RR the objective of the Monge-Kantoron Kantorovich problem is to find the joint probability measure P X Y R that minimizes the total transport cost
E [( X Y) min {
c(x, 14).
XxY
The Honge-Kantoron problem offers the advantage of accommodating additional constraints to the probability measure. Turning back to the inertia minimization problem, we insert set of transport
5

---

weights w where their summation equals one into Eq I to mimic the function of the joint probability measure P. Then, we can rewrite the objective of k-means as
h
N
N
N
min 20
Wiy || My
s.t.
wij = w, E {0, N
Σ wij = k
(3)
j=1
==
where Waj 1/N denotes assigning H; to Mj. and the constraint E, Waj 1/k ensures each shard is treated equally. By introducing the transport weights w, we can transform the discrete clustering problem into a continuous optimization process. This transformation allows us to impose additional constraints
that facilitate more fine-grained control over the clustering process. Consequently, we add the constraint Σj Wij = 1/N to ensure a balanced division. Following the
Monge-Kantorove Kantorovich framework [3 [30 we also relax the range of w to IR+ to guarantee the existence of solution space for the objective. Finally, the shard assignment of x; is determined by arg max, Wij- However, the worst-case complexity of computing the optimum for such a transport objective with additional constraints scales in ( [37] To enhance efficiency, we utilize Sinkhorn divergence to
accelerate the optimization process 38 29 Specifically, we smooth the objective with entropic regularization as follows:
l Σ
N
Σ wij (log(wsy) - 1)
min wET
x3 Wij
+
where I' = [||/|]1 = 1.
0. w. E = }). The derived new objective can be
efficiently solved through Sinkhorn's 's matrix scaling algorithm with a complexity of ((N)) 9 10].
The optimization details can be found in Appendix B
4.2 Relevance Loss (Stage II)
In stage II, the ensemble retraining framework trains a sub-model on each shard independently. which means sub-models do not interfere with each other during training. The loss component associated with this stage is relevance loss, which implies that the aim is to enhance the performance of sub- models. However, to ensure unlearning completeness the algorithmic level, it is crucial that the sub models fully replicate the original model. This includes replicating not only the model structure, parameter initialization, and any other relevant elements. Therefore,
but also not break the requirement of full replication and also leave stage II unchanged 4 7 g. We assume that the shard data is i...d. with the original training data and ensure that all sub-models fully replicate the original model that attains convergence on the original training data. This ensures that sub-models reach convergence on their respective shard data.
do
4.3 Combination Loss (Stage III)
In stage III, the ensemble retaining framework combines the sub- models to obtain the final model. The original framework, i.e., SISA 44, uses average combiner. However, this is naive solution, since various shards may have different contributions to the final model. Thus, the model-based combiner is proposed by 7 g). Specifically, this approach utilizes machine learning models to determine the combination weights by the following objective:
min E
Σ E(3,a, R) + \I s.t. ||+|| = 1. = 0.
(5)
where f is the original loss function for recommendation tasks, R is the recommendation data, oa denotes the parameters of i-th sub-models, and denotes the weights of combination. Note that the parameters of sub-models are fixed during model combination. The L2 regularization parameterized by X on /3 is applied to prevent over-fitting. This approach is akin to the use of meta-estimators in ensemble systems B3], where they are employed to alleviate information loss during model combination. As empirically studied by (34), a simple meta-estimator such as Logistic Regression (LR) proves to be enough on deep models. Building on this insight, we empirically validate the effectiveness of LR on the recommendation tasks in Section 5.233 Our results show that LR can perform comparably to attention networks 7 while substantially reducing model complexity.

---

4.4 Putting Together
Our proposed UltraRE belongs to the ensemble retraining framework and follows the three-stage structure described in Figure [ In stage we obtain an adaptive equilibrium between sample similarity and shard balance by optimizing Eq (4) In stage II, we do not interfere with sub-model training, meeting the requirement of fully replicating the original model. stage III, we apply LR to determine the combination weight by optimizing Eq (5)
Experiments
We conduct experiments on three real-world datasets to evaluate the performance of our proposed UltraRE framework. The evaluation mainly focuses on G2 (unlearning efficiency) and G3 (model utility), our proposed method tUltraRE) belongs exact unlearning, which naturally achieves G1 (unlearning completeness). UltraRE can handle all three types of unlearning targets, i.e., user- wise, item-wise, and sample-wise. In this paper, we focus on user-wise unlearning without loss of generality, as it is the most common one in practice. Additionally, we perform an ablation study to further investigate the effectiveness of modification.
5.1 Experimental Settings
5.1.1 Datasets
We conduct experiments on the fol- lowing three real-world datasets: i)
Table 1: Summary of datasets.
Dataset
User #
Item #
Rating #
Sparsity
MovieLens 100k (ML-100K The MovieLens datasets are among the most extensively used in recommen- dation researchn [6). ML-100K contains 100 thousand ratings; ii) MovieLens 1M (ML-1M): This is stable version of the MovieLens dataset, containing million ratings; and iii) Amazon Digital Music (ADM The Amazon dataset contains several sub-datasets according the categories of Amazon products. ADM is the sub-dataset containing digital music reviews. To ensure reliable evaluations, we filter out the users and items that have less than interactions. Specifically,
100K
943
1,682
100,000
93.695%
ML-IM
6040
3,950
1,000,209
95.814%
ADM
478,235
266,414
836,006
99.999%
80% of ratings for training, 10% validation set for tuning hyper-parameters, and the remainder for testing. Table
I summarizes the statistics of three datasets.
5.1.2 Compared Models and Methods
Recommendation Models. Our proposed UltraRE model-agnostic, enabling its application to any recommendation model. In this paper, we select two representative recommendation models: a classic model, i.e., Deep Matrix Factorization (DMF) 47), and ii) the SOTA model, i.e. Light- GCN [8], for testing. Following the original papers, we adopt normalized binary cross entropy loss and Bayesian personalized ranking loss for DMF and LightGCN respectively, and employ Adam optimizer train the above models, We run all experiments for 10 trials and report the average results. Following 77 we use WMF [9 as a pre-training model to generate user and item embedding for the purpose of clustering.
Unlearning Methods. We compare UltraRE with the benchmark and the SOTA methods, in- cluding: i) Retrain: Retraining the model from scratch on the updated dataset; ii) SISA [4]: the SOTA generic exact unlearning method which is based on ensemble retraining framework; and iii) RecEraser [7]: the SOTA recommendation unlearning method which modifies SISA to boost performance in recommendation tasks. Following 7]. set the number of shards to 10 for all unlearning methods that involve division, ie., SISA, RecEraser, and UltraRE.

---

Table 2: Running time (s) of the learning process.
DMF
LightGCN
MI.-100K
Retrain
SISA
RecEraser
UltraRE
Retrain
SISA
RecEraser
UltraRE
Stage
0.000
0.013
0,662
0.048
0,000
0.014
0.645
0.050
Stage II
1,442.263
193.317
189.742
190.289
4,422.531
582.659
194.714
591,638
Stage III
0.000
0.001
42.673
31.540
0.000
0.003
383.132
315,822
Total
1,442.263
193.331
233.077
221.877
4,422.531
582.676
978.491
907,510
DMF
LightGCN
ML-IM
Retrain
SISA
RecEraser
UltraRE
Retrain
SISA
RecEraser
UltraRE
Stage
0.000
0.046
23.904
0.429
0,000
0.058
23.950
0.467
Stuge
3,732.366
376.237
378.475
374,999
11.372.446
1,218,335
1,211.275
1,218.875
Stage
0.000
0.003
93.519
69.327
0.000
0.004
682.182
624,349
Total
3.732.366
376,286
495.898
444.755
11,372.446
1,218,397
1,917.407
1,843.691
DMF
LightGCN
ADM
Retrain
SISA
RecEraser
UltraRE
Retrain
SISA
RecEraser
UltraRE
Stage
0.000
0.052
20.864
0.373
0,000
0.054
20.851
0,352
Stage
2,012.655
207.457
201.769
206.417
6,724.734
698.737
679.051
682.742
Stage
0.000
0.003
57.352
48.975
0.000
0.004
404.110
374.253
Total 2,012.655
207.512
279.985
255.765
6,724.743
698.795
1,104.012
1,057.347
5.2
Results and Discussion
5.2.1 Unlearning Efficiency (G2)
We use running time evaluate the efficiency of unlearning. To fully exploit the efficiency of the ensemble retraining framework, we run all shards in parallel. Specifically, we measure the running time of each stage during the learning process and report the results in Table 2 As the shard division (stage I) and combination weights (stage III) are determined during learning and remain unchanged during unlearning, their time cost during unlearning is negligible during unlearning compared to retraining (stage II). Since all shards run in parallel, the running time of stage II remains consistent between learning and unlearning. Therefore, by measuring the running time of stage II during learning, we can evaluate the running time of unlearning. We run all experiments on the same Ubuntu 20.04 LTS System server with 48-core CPU, 256GB RAM and NVIDIA GeForce RTX 3090 GPU. From Table 2 SISA, RecEraser, and UltraRE, significantly enhance unlearning efficiency. Although spending more time in stages I and III, these frameworks decrease the total running time by an average of 85.39%; ii) Using random balanced division and average combiner, SISA enjoys notably faster speed than other ensemble retraining frameworks. Nevertheless, this simple design also limits SISA's performance regarding model utility (see Scction 5.2.2); and iii) Among the comparison of recommendation unlearning frameworks, i.c., RecEraser and UltraRE, time of both stages and III. In stage I, our proposed optimal balanced clustering algorithm can improve the efficiency by 98. 1% average. This improvement is even greater when dealing with larger datasets, i.e., ML-IM and ADM. In stage III, we simplify the choice of the model combiner, resulting in average efficiency increase of 11.95%.
we observe that i) compared with Retrain, the ensemble retraining frameworks, i.e.,
proposed UltraRE decreases the running
5.2.2 Model Utility (G3)
We use two common metrics, i.c., Normalized Discounted Cumulative Gain (NDCG) and Hit Ratio (HR), to evaluate the performance of recommender models [17 47]. For both metrics, we truncate the ranked list at 10, and report NDCG@ 10 and HR @ 10 during both the learning and unlearning processes. To simulate user-w user-wise unlearning, we randomly select 9% of users to unlearn, where
investigated in (5, 10) across all datasets. From Table we observe that i) Retrain achieves the best performance, suggesting using ensemble retraining frameworks (including SISA, RecEraser, and UltraRE) may come at the cost of slightly increased error rates. This trade-off occurs because these frameworks prioritize unlearning efficiency over preserving model utility: ii) The performance of cluster-based division methods, i.e., RecEraser and UltraRE, surpasses that of the random division method, i.c., SISA. This implies that by clustering similar samples together, redundancy loss can be
8

---

Table 3: Recommendation performance during learning and unleaming (G3: model utility). The best results except Retrain are highlighted in bold. The superscript indicates < 0.01 for the t-test of UltraRE against RecEraser.
DMF
LightGCN
MI-100K
Retrain
SISA
RecEraser
UltraRE
Retrain
SISA
RecEraser
UltraRE
NDCG
0.3956
0.3716
0,3795
0.3847
0,3997
0,3684
0,3812
0,3859
Learn
HR
0.4374
0.4227
0.4273
0.4326
0.4395
0.4203
0.4257
0.4312
NDCG
0.3934
0.3709
0.3762
0.3815
0.3976
0.3677
0.3799
0,3841
HR
0.4359
0.4222
0.4232
0.4297
0.4387
0.4201
0.4233
0,4295
NDCG
0.3905
0.3702
0.3734
0.3786
0.3953
0.3669
0.3793
0,3836
Unlearn@ @ 10
HR
0.4353
0.4205
0.4183
0.4245*
0.4362
0.4186
0.4221
0.4267
DMF
LightGCN
ML-IM
Retrain
SISA
RecEraser
UltraRE
Retrain
SISA
RecEraser
UltraRE
NDCG
0,4382
0.3956
0,3973
0.4042
0.4437
0,3941
0,4171
0.4241
Learn
HR
0,5402
0.5141
0.5134
0.5183
0,5493
0.4672
0.5160
0.5217
NDCG
0.4398
0.3937
0.3965
0.4031 *
0.4403
0.3908
0.4138
0,4189
U
HR
0.5411
0.5125
0.5129
0.5179
0.5464
0.4543
0.5140
0.5206
NDCG
0.4391
0.3914
0.3963
0.4013
0.4396
0.3912
0.4129
0,4181
Unlearn @ 10
HR
0.5411
0,5108
0.5127
0.5184
0.5421
0.4495
0.5090
0,5146
DMF RecFraser
LightGiNN RecEraser
ADM
Retrain
SISA
UltraRE
Retrain
SISA
UltraRE
NDCG
0.4549
0.4063
0.4234
0.4294
0.4603
0.4025
0.4281
0.4345
Learn
HR
0.7914
0.7012
0.7230
0.7311 x
0.7931
0.6912
0.7406
0.7472
NDCG
0.4551
0.4021
0.4214
0.4273*
0.4594
0.3963
0.4251
0.431 1
@
HR
0.7915
0.6959
0.7202
0.7283
0.7945
0.6851
0.7311
0.7403
NDCG
0.4554
0,3973
0,4198
0.4262
0.4595
0.4043
0.4239
0.4306
Unlearn @ 10
HR
0.7916
0.6772
0.7222
0.7298
0.7936
0.6781
0.7192
0,7255
significantly reduced. iii) Our proposed UltraRE demonstrates superior performance compared to the SOTA recommendation unlearning framework, i.e., RecEraser. On average, our model achieved an improvement in recommendation metrics of 1.31%, 1.26%, and 1.26%, on ML--10K: ML-IM and ADM respectively. The improved results can be attributed to Ul UltraRE's ability to generate better clustering outcomes while meeting the balance requirement; and iv) Strong performance during the learning process serves as reliable indicator of strong performance during unlearning.
5.2.3 Ablation Study
To fully understand the effectiveness of our proposed U1 UltraRE, we conduct ablation studies regarding the main modifications during stages I (non-overlapping division) and III (model combination). as well as varying numbers of shards.
Effect of Division. In stage I, we propose a novel division algorithm, named Optimal Balanced Clustering (OBC). We conduct an ablation study to compare OBC with Balanced Random Division (BRD, used in SISA 4 Balanced k-means (BKM, used in RecHraser 7 and k-mmans (KM). Although KM causes the issue of imbalance in clustering, can still be a valuable baseline for evaluating division performance. We use inertia in Eq (I) to evaluate division performance. A lower inertia value indicates better division performance. We present the results obtained with k 10 in Figure 4 From it, we observe that Among balanced grouping algorithms, our proposed OBC significantly outperforms BKM (by 46.32% on average) and BRD (by 22.01% 01% on average); ii) OBC also achieves comparable inertia to KM, indicating that OBC achieves balanced grouping without compromising sample similarity, and iii) BRD even outperforms BKM. This indicates that the usage of priority list in BKM leads to significant degradation in division performance, making worse than random division.
OBC
BRD
BKX
KM
Inertia
1000
500-
MI-100K
ML-IM
ADM
Figure Effect of division (Stage

---

Effect of Combination. In stage II we sim-
plity the choice of the model combiner. To validate our choice, we compare our logistic regression (L.) based combiner with Average combiner (AVG which is used in SISA [ and
NDC O
0,400
0,400
0.375
0.755
Attention combiner (ATT which is used in Re- cEraser 77. As shown in Figure model-based combiners, i.e., LR and ATT, outperform AVG by significant margin. On average, AVG's per- formance is decreased by 3.53% on DMF and 6.51% % on LightGCN. Among model-basee combiners, LR can achieve comparable performance with ATT while substantially reducing the model complexity.
ML-IM
ML-100K
AIX
(a) DMF
(b) LightGCN
Figure 5: Effect of combination (Stage III..
Effect of Shard Number. To demonstrate the robustness of UltraRE, we empirically study the effect of shard number and compare it with the SOTA recommendation unlearning frame- work RecEraser. We investigate the number of shards in [10, 20, 50). As shown in Figure 6 UltraRE yields consistent improvements over RecEraser regarding both unlearning efficiency (time) and model utility (NDCG@ 10). More- over, as the shard number increases, UltraRE exhibits greater efficiency enhancement over RecEraser. This is because larger shard number reduces the time taken in stage II, thereby highlighting the efficiency of UltraRE in stages and III.
(igh0
inght
NDCcagto
848
500
NOCOgtt
8.42
2008
420
1889
0.2
100
350
(a) DMF
(b) LightGCN
Figure 6: Effect of shard number (ML--IM).
Conclusion
In this paper, we refine the SOTA exact unlearning framework, i.e., ensemble retraining framework, in recommendation tasks. Our proposed UltraRE breaks away from the prior work's intuition on preserving collaboration 17 8 226). Instead, it is guided by the theoretical analysis of error decomposition ensemble systems. Among the three stages in the ensemble retraining framework, our modifications mainly lie in stages (non-overlapping division) and III (model combination). In stage I, proposed an optimal balanced clustering algorithm that can achieve adaptive equilibrium between sample similarity and shard balance. In stage III, we simplify the complexity of the model combiner without increasing the combination loss. Extensive experiments on three real- world recommendation datasets demonstrate that U1 traRE can not only greatly enhance unlearning efficiency, but also outperform the SOTA unlearning models in terms of model utility.
7 Broader Impacts and Limitations
Recommendation unlearning can have various implications on society, including addressing issues related to privacy, fairness, bias, and manipulation. UltraRE can also be generalized to other unlearning tasks and is especially adept in aasociationn-snsiiive tasks, e.g., graph learning. common limitation of the ensemble retraining framework is the absence of experiments
large-scale datasets with a large shard number [4] 26). As shown in Section [.2. the major time of unlcarning is spent stage II, which cannot fully demonstrate the efficiency of the ensemble retraining framework. We manage to investigate the effect of large shard number in Section 5.2.3
Acknowledgments and Disclosure of Funding
This work was supported in part by Leading Expert of Ten Thousands Talent Program of Zhejiang Province (No.2021R52000 and the National Natural Science Foundation of China (No.62172362).
References
[1] S Basu, P Pope. and S Feizi. Influence functions in deep learning are fragile. In In International Conference on Learning Representations (ICLR), 2021.
10

---

[2] Rajendra Bhatia and Chandler Davis. A cauchy-schwarz inequality for operators with applications. Linear Algebra and its Applications, 223: 223:119-129, 1995.
Vladimir I Bogachev and Aleksandr Kolesnikov. The monge-kantorovich problem: achievements, connections, and perspectives. Russian Mathematical Surveys, 67(5))885 2012.
[4] Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette- Choo. Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lic, and Nicolas Papernot. Machine unlearning. In Proceedings in the 42nd IEEE Symposium on Security and Privacy (SP), 2021.
[5] Leo Breiman. Bagging predictors. Machine learning, 24:123 140, 1996.
[6] Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In Proceedings in the 36th IEFE Symposium on Security and Privacy (SP), pages 463-480, 2015.
[7] Chong Chen, Fci Sun, Min Zhang, and Bolin Ding. Recommendation unlcarning. In Proceedings of the ACM Web Conference 2022 (WWW), pages 2768-2777, 2022.
[8] Min Chen, Zhikun Zhang. Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang. Graph unlearning. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 499-499-499 2022.
[9] Marco Cuturi. Sinkhorn distances: Lightspeed computation optimal transport. Advances in Neural Information Processing Systems (NewrIPS), 26, 2013.
[10] Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z Alaya, Aurélie Boisbumon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, et al. Pot: Python optimal transport. The Journal of Machine Learning Research, 22(1):3571-3578 2021.
[11] Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Eternal sunshine of the spotless net: Selective forgetting in deep networks. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition (CVPR), pages 92 2020.
[12] Laura Graves, Vineel Nagisetty, and Vijay Ganesh. Amnesiac machine learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11516 11524, 2021.
[13] Chuan Guo, Tom Goldstein, Awni Hanmun, and Laurens Van Der Maaten. Certified data removal from machine learning models. Proceedings of the 37th International Conference on Machine Learning (ICML), pages 3832-388-800 3842, 2020.
[14] F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm Transactions Interactive Intelligent Systems (TIS), 5-4):1119, 2015.
[15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition (CVPR), pages 770-778,
2016.
[16] Ruining He and Julian McAuley. Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering. In proceedings of the 25th International Conference on World Wide Web (WWW), pages 507-517, 2016.
[17] Xiangnan He. Tao Chen, Min- Yen Kan, and Xiao Chen. Trirank: Review-aware explainable recommenda- tion by modeling aspects. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management (CIKM), pages 1661-1670, 2015.
[18] Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. Lightgen: Simplifying and powering graph convolution network for recommendation. In Proceedings of the 43rd International ACM SIGIR conference on research and development Information Retrieval, pages 639-648, 2020.
[19] Yifan Hu, Yehuda Koren, and Chris Volinsky. Collaborative filtering for implicit feedback datasets. In 2008 Eighth IEEE international conference on data mining, pages 263-272. leee, 2008
[20] Robert Jacobs, Michael Jordan, Steven Nowlan, and Geoffrey E Hinton. Adaptive mixtures of local experts. Neural computation, 3(1):79-87, 1991.
[21] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International Conference Machine Learning (ICML), pages 1885 1894, 2017.
11

---

[22] Pang Wei W Koh. Kai-Siang Ang. Hubert Teo, and Percy S Liang. On the accuracy of influence functions for measuring group effects. In Advances in Neural Information Processing Systems (NeurlPS), volume 32, 2019.
[23] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in Neural Information Processing Systems (NeurIPS), 30, 2017.
[24] Bo Li, Yining Wang, Aarti Singh, and Yevgeniy Vorobeychik. Data poisoning attacks on factorization-baseed collahorative filtering. Advances Neural Information Processing Systems (NeurIPS), 29, 2016.
[25] Yuyuan Li, Chaochao Chen, Xiaolin Zheng, Yizhao Zhang, Biao Gong, Jun Wang, and Linxun Chen. Selective and collaborative influence function for efficient recommendation unlearning, Expert Systems with Applications, 234: 121025, 2023.
[26] Yuyuan Li, Xiaolin Zheng, Chaochao Chen, and Junlin Liu. Making recommender systems forget: Learning and unlcarning for erasable recommendation. arXiv preprint arXiv:2203 /491, 2022.
[27] Weiming Liu, Chaochao Chen, Xinting Liao, Mengling Hu, Jianwei Yin, Yanchao Tan, and Longfei Zheng. Federated probabilistic preference distribution modelling with compactness co-clustering for privacy- preserving multi-domain recommendation. In Proceedingy of the 32rd International Joint Conference on Artificial Intelligence (IJCAI), pages 2206-2214, 2023.
[28] Weiming Liu, Jiajie Su. Chaochao Chen, and Xiaolin Zheng. Leveraging distribution alignment via stein path for cross-domain cold-start recommendation. Advances in Neural Information Processing Systems (NeurIPS), 34: 1111122222244240 2021.
[29] Weiming Liu, Xiaolin Zheng. Chaochao Chen, Jiajie Su, Xinting Liao, Mengling Hu, and Yanchao Tan. Joint internal multi-interest exploration and external domain alignment for cross domain sequential recommendation. Proceedings of the ACM Web Conference 2023, pages 383-394, 2023.
[30] Weiming Liu, Xiaolin Zheng. Jiajie Su, Mengling Hu, Yanchao Tan, and Chaochao Chen. Exploiting variational domain-invariant user embedding for partially overlapped cross domain recommendation. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 22122,12222 2022.
[31] Mark MacCarthy. An examination of the algorithmic accountability act of 2019. Available SSRN 3615731, 2019.
[32] Ninarch Mchrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and faireess in machine learning. ACM Computing Surveys (CSUR), 54(6):1-35, 2021.
[33] Gaku Morio, Terufumi Morishita, Hircaki Ozaki, and Toshinori Miyoshi. Hitachi at semeval- 2020 task 10: Emphasis distribution fusion fine-tuned language models. In Proceedings of the Fourteenth Workshop on Semantic Evaluation, pages 1658-1664, 2020.
[34] Terufumi Morishita, Gaku Morio, Shota Horiguchi, Hiroaki Ozaki, and Nobuo Nukaga. Rethinking fanos inequality in ensemble learning. In International Conference on Machine Learning (ICML), pages 15976-1 16016. PMLR, 2022.
[35] Thanh Tam Nguyen, Thanh Trung Huynh, Phi Le Nguyen, Alan Wee-Chung Liew, Hongzhi Yin, and Quoc Viet Hung Nguyen. survey of machine unlearning. arXiv preprint arXtv:2209.02299, 2022.
[36] OpenAI. GPT-4 technical report. CoRR, abs/2303.08777 2023.
[37] Ofir Pele and Michael Werman. Fast and robust earth mover's distances. In 2009 IEEE 12th international conference on computer vision (ICCV), pages 460-467. IEEE, 2009.
[38] Gabriel Peyré, Marco Cuturi, al. Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning, 11(5-6):355 607, 2019.
[39] Omer Sagi and Lior Rokach. Ensemble learning: A survey, Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 8(4), 2018
[40] Ben Schafer, Dan Frankowski, Jon Herlocker, and Shilad Sen. Collaborative filtering recommender systems. In The adaptive web, pages 291-324, Springer, 2007.
[41] Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning. In Advances in 34th Neural Information Processing Systems (NeurIPS), 2021.
12

---

[42] Noam Shazeer, Azalia Mirhoseini. Krzysztof Maziarz, Andy Davis. Quoe Le, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely-gated mixture-of-experts layer. arXiv preprint wrX.v.7701.06338, 2017.
[43] Anvith Thudi, Hengrui Jia, Ilia Shumailov, and Nicolas Papernot. On the necessity of auditable algorithmic definitions for machine unlearning. 31st USENIX Security Symposium (USENIX Security) pages 4007-4022 2022.
[44] Paul Voigt and Axel Von dem Bussche. The eu general data protection regulation (gdpr). Practical Guide, 1st Ed., Cham: Springer International Publishing, 10(1152676):00 5555, 2017.
[45] Alexander Warnecke, Lukas Pirch, Christian Wressnegger, and Konrad Rieck. Machine unlearning of features and labels. In Network and Distributed System Security (NDSS) Symposium 2023, 2023.
[46] David Wolpert. Stacked generalization, Neural networks, 5(2):24 259, 1992.
[47] Hong-Jian Xue, Xinyu Dai, Jianbing Zhang, Shujian Huang, and Jiajun Chen. Deep matrix factorization models recommender systems. Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), volume 17, pages 3203-3209. Melbourne, Australia, 2017.
[48] Haonan Xiaoguang Ziyao Guo, Hui Li, Fenghua and Xiaodong Lin. Arcane: An efficient architecture for exact machine unlearning. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), 2022.
13

---

A Theoretical Validation of Balanced Division
Supposing there no prior knowledge regarding distribution of unleaming requests, optimal to presume that users submit requests with equal probability. Under this condition, a balanced division in the ensemble retraining framework can achieve maximum unlcarning efficiency.
Proof. Let h, denote the training overhead shard S, which is in proportion to shard size, i.c., the number of samples in the shard. Since the users submit unlcarning requests with equal probability, the probability of a request located in shard S; is P: h where Z = En h5. Thus, the expectation of retraining overhcad when dealing with an unlearning request is
8
h
B(H)
Σ
P. h4 Z
4 1=1
(6)
According to Cauchy-Schwarzz Inequality (2]. for n random variables Iú, we can get a lower bound Σ,
x2 as:
Σ
24
7
Taking it into (6) we have
B B(H)
Σ
h3
Z
7
We can easily find that setting 14 Z/k achieves this lower bound, which indicates that balanced division achieves the maximum unlearning efficiency.
B Sinkhorn Algorithm
this section, we provide the details of optimizing the objective of the optimal balanced clustering algorithm. Firstly, we smooth the objective with an entropic regularization term:
min TH
Wiy
u4
wiy (log(wss) 1)
(9)
1, Eg =
We rewrite Eq 9 with Lagrange multipliers as
max min J
CeyCis + Σ
Σ
why (log(w)s) - 1) Σ 83
Σ Wis
1.9
w
N
F
Wej
Ci = ||:: 11,1122
(10)
N
Taking the differentiation w.r.t. Wey Eq
10
have
0J
0
Cay + e llo((us)) f3 g: = 0.
(1))
Trii
To update variables, we first fix gi and update fj with
fftt1 of log (2)
log
Σ exp
9.00 Cij
(12)
k
Then we fix fy and update 9, with
5(()) -ey Caj
((+1) 9
= log
log
exp
(13)
In summary, iteratively update and gi until obtain the final solutions.
14

---

Table 4: Running time of the learning process on ML-I0M.
DMF
LightGCN
ML-10M
RecEraser
UltraRE
RecEraser
UltraRE
Stage
872.53m
259.18; 18s
879.06m
257.83s
Stage II
213.55s
208.44s
860.12s
852.32s
Stage III
83.74s
67.26s
384.50s
376.57s
Total
877.48m
534.88s
899.80m
1,486.72s
C
Additional Experiments the Large-scale dataset
As illustrated in Section / current experiments do sufficiently demonstrate the efficiency enhancement of UltraRE, because the majority time spent during stage II (independent training) while the enhancements occur in stages (non-overlapping division) and III (model combination). Thus, following 7 we further conduct experiments on ML-10M (the largest dataset used in 7 with 50 shards (a large shard number), and report the results in Table From it, observe that UltraRE significantly improves efffccinccy compared RecEraser. Specifically, in stages and III, UltraRE demonstrates average efficiency enhancements of 20,227.85 87% 13.30% respectively, Note that, in the large-scale dataset, our proposed clustering algorithm (OBC) outperforms the BKM used in RecEraser, reducing clustering time from several hours to just few minutes (in stage I, 18s/257.833. The experimental results demonstrate higher efficiency improvements
372.53m/879 m0m when compared to the results reported in the main text, providing additional evidence of the substantial efficiency enhancements achieved by our method.
15


Reviews:
[{"review_id": "yc5Dd54aa7", "reviewer": "Reviewer_oK8f", "summary": "This paper investigates the problem of recommendation unlearning, with a specific focus on the exact unlearning approach. The authors adopt an ensemble-based perspective to redefine the exact unlearning framework and break down the framework into three components regarding prediction error. The primary modification made by the authors pertains to the first component, where a novel optimal balanced clustering algorithm is proposed. The authors also simplify the third component to improve efficiency. Extensive experiments are conducted across three benchmark datasets.", "questions": "The improvement brought by the proposed optimal balanced clustering algorithm appears to be inconsistent. On the one hand, the inertia is significantly reduced. On the other hand, the model utility is not significantly improved. Please explain this phenomenon.", "limitations": "The authors have discussed the issue that the efficiency improvement of stages I and III is not significant, and provided a practical experimental setting.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The investigated problem is interesting. Unlearning has gained increasing attention in the field of privacy-preserving machine learning. This paper focuses on a practical scenario of unlearning, i.e., recommendation system.\n\n2) This paper offers ease of comprehension. The ideas within are clearly presented.\n\n3) This paper uses the theory of ensemble learning to provide a theoretical foundation for the exact unlearning approach. This provides valuable insights for improving the performance of the exact unlearning approach.\n\n4) The authors propose a novel clustering algorithm which achieves an optimal trade-off between (i) shard balance and (ii) sample similarity. This modification effectively tackles  the trade-off issue from an optimization perspective.\n", "weaknesses": "1) The improvement brought by the proposed optimal balanced clustering algorithm appears to be inconsistent. On the one hand, the inertia is significantly reduced. On the other hand, the model utility is not significantly improved. Please explain this phenomenon.\n\n2) There exist some small errors, for example, in line 211, the complexity is O(Nk) instead of O(N^2).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your valuable comments and suggestions. We hope our response addresses your concerns.\n\n**Q1**:\tInconsistent improvements between inertia and model utility.\n\n**Response**: Inertia is the summation of the inner-cluster distance of all sample-centroid pairs, ranging in $[0, \\infty]$. Model utility is evaluated by NDCG and HR, both of which range in $[0, 1]$. Therefore, the scales of inertia and model utility are different, leading to inconsistent improvements between them. To subtly investigate the relationship between inertia and model utility (NDCG@10), we conduct another ablation study. Specifically, we vary the clustering algorithms in stage I (non-overlapping division) and use Logistic Regression (LR) in stage III (model combination) for all compared methods, and report corresponding inertia and NDCG (during learning). We choose LR due to its comparable performance to ATTention networks (ATT), as shown in the \"Effect of Combination\" section. For easy comparison, we also report the result of original RecEraser and SISA.\n\n| ML-100K      | Stage I | Stage III | Inertia (stage I) | DMF-NDCG (stage III) | LightGCN-NDCG (stage III) |\n|--------------|---------|-----------|-------------------|----------------------|---------------------------|\n| UltraRE      | OBC     | LR        | 816.32            | 0.3847               | 0.3859                    |\n| RecEraser-LR | BKM     | LR        | 1,738.24          | 0.3792               | 0.3808                    |\n| RecEraser    | BKM     | ATT       | 1,738.24          | 0.3795               | 0.3812                    |\n| SISA-LR      | BRD     | LR        | 852.50            | 0.3824               | 0.3836                    |\n| SISA         | BRD     | AVG       | 852.50            | 0.3716               | 0.3684                    |\n\n| ML-1M        | Stage I | Stage III | Inertia (stage I) | DMF-NDCG (stage III) | LightGCN-NDCG (stage III) |\n|--------------|---------|-----------|-------------------|----------------------|---------------------------|\n| UltraRE      | OBC     | LR        | 729.46            | 0.4042               | 0.4241                    |\n| RecEraser-LR | BKM     | LR        | 1,318.31          | 0.3968               | 0.4169                    |\n| RecEraser    | BKM     | ATT       | 1,318.31          | 0.3973               | 0.4171                    |\n| SISA-LR      | BRD     | LR        | 1,129.72          | 0.3972               | 0.4173                    |\n| SISA         | BRD     | AVG       | 1,129.72          | 0.3956               | 0.3941                    |\n\n| ADM          | Stage I | Stage III | Inertia (stage I) | DMF-NDCG (stage III) | LightGCN-NDCG (stage III) |\n|--------------|---------|-----------|-------------------|----------------------|---------------------------|\n| UltraRE      | OBC     | LR        | 775.22            | 0.4294               | 0.4345                    |\n| RecEraser-LR | BKM     | LR        | 1,319.61          | 0.4230               | 0.4278                    |\n| RecEraser    | BKM     | ATT       | 1,319.61          | 0.4234               | 0.4281                    |\n| SISA-LR      | BRD     | LR        | 1,052.74          | 0.4255               | 0.4273                    |\n| SISA         | BRD     | AVG       | 1,052.74          | 0.4063               | 0.4025                    |\n\nBased on the presented tables, we obtain several key observations:\n* Comparing UltraRE, RecEraser-LR, and SISA-LR, we observe that a lower inertia is associated with a higher recommendation performance. This suggests a positive correlation between clustering performance and recommendation performance.\n* LR demonstrates similar recommendation performance to ATT, surpassing AVG, when compared to the LR-versions (RecEraser-LR and SISA-LR) and their original versions (RecEraser and SISA). This finding is consistent with the results from the \"Effect of Combination\" section.\n* In ML-1M and ADM datasets, SISA-LR achieves comparable recommendation performance to RecEraser-LR, while outperforming it in ML-100k. This aligns with the differences in inertia across the various datasets, indicating that (i) clustering performance generally correlates positively with recommendation performance, and (ii) the advancements in RecEraser are primarily attributed to the effectiveness of the combiner (ATT).\n\nIn conclusion, superior clustering performance corresponds to improved recommendation performance. Our proposed clustering algorithm (OBC) exhibits substantial superiority over the compared methods.\n\n**Q2**:\tTypos.\n\n**Respond**: We will carefully review the paper and fix any typos during revision."}, {"review_id": "cTzGT72fxZ", "reviewer": "Reviewer_zuBB", "summary": "This paper addresses the problem of recommendation unlearning, which arises due to privacy concerns and the right to be forgotten. The authors identify limitations in previous methods, which prioritize unlearning efficiency over preserving model utility and fail to optimize the balance between collaboration and balance. To address these limitations, the authors propose a new framework called UltraRE, which simplifies and powers RecEraser for recommendation tasks. UltraRE optimizes the equilibrium between collaboration and balance, ensures convergence on group data, and simplifies the combination estimator. The authors conduct extensive experiments on three real-world datasets and demonstrate that UltraRE outperforms the state-of-the-art recommendation unlearning framework, RecEraser, achieving an improvement in recommendation accuracy and unlearning efficiency on ML-100k, ML-1M, and ADM, respectively.", "questions": "- How can the proposed method maintain efficient when dealing with multiple deletion request at one time?\n- What and how significant is the major technical contribution of UltraRE compared to  RecEraser?", "limitations": "The paper targets at solving negative societal impact of existing works.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The paper well-formalize machine unlearning into a three-target problem including unlearning completeness, unlearning efficiency, and model utility.\n\n- The proposed method cleverly transform KMeans into the Monge-Kantorovich problem, to enable optimization for the clustering process.\n\n- The proposed UltraRE performs superior in model utility as well as unlearning efficiency.", "weaknesses": "- The paper only focuses on exact unlearning, and ignore the important research line of approximate unlearning [1-2], which is much more efficient when dealing with multiple unlearning requests.\n- Compared to the SOTA method RecEraser, the proposed UltraRE only makes incremental improvements, including modifying the KMeans clustering algorithm and applying simpler aggregation method, which makes the technical contribution rather limited.\n- The experimental datasets are all of small size, which may limit the accuracy of efficiency test.\n\n[1] GIF: A General Graph Unlearning Strategy via Influence Function\n\n[2] GNNDelete: A General Strategy for Unlearning in Graph Neural Networks", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your valuable comments and suggestions. We hope our response addresses your concerns.\n\n**Q1**:\tDiscussion about approximate unlearning.\n\n**Response**: First of all, it is important to highlight that, in this paper, we focus on exact recommendation unlearning, which is orthogonal to the studies you mentioned, i.e., approximate graph unlearning, in the field of machine unlearning. Exact unlearning approaches fully guarantee the most fundamental requirement of unlearning, i.e., completeness. Algorithmic retraining has been established as the sole authoritative way of ensuring completeness [37]. This is the inherent advantage of exact unlearning and cannot be attained through approximate unlearning. We do agree that approximate unlearning approaches have gained much attention due to their efficiency, and we did not ignore them. Instead, we have reviewed various representative studies in the “Related Work” section. We sincerely apologize for missing the studies you mentioned, and we will ensure to include them during revision.\n\n**Q2**:\tHow to maintain efficiency when dealing with multiple requests?\n\n**Response**: From a theoretical perspective, ensemble retraining frameworks can increase shard number and employ parallel training. In this way, the time required for unlearning is limited to sub-model retraining. Besides the unique authority and inherent advantages of exact recommendation unlearning that we mentioned in *Response to Q1*, it is noteworthy that within the context of recommendation, the approximate unlearning approaches are not as efficient as expected. This inefficiency can be attributed to two main reasons. First, the inherent computation of the Hessian matrix is time-consuming. Although approximations can be made to accelerate the computation process, these approximations compromise the completeness and model utility, and do not eliminate the need for at least one offline computation of the Hessian matrix. Second, both user and item embeddings are dense feature matrices that contain a large number of parameters, thereby further increasing computational overhead in the context of recommendation.\n\nFrom a practical perspective, current experiments do not sufficiently demonstrate the efficiency enhancement, because the majority of time is spent during stage II (independent training) while the enhancements occur in stages I (non-overlapping division) and III (model combination). Thus, following [6], we further conduct experiments on ML-10M (large-scale dataset) with 50 shards (large shard number), and report the results in the table below.\n\n| ML-10M    | DMF-RecEraser | DMF-UltraRE | LightGCN-RecEraser | LightGCN-UltraRE |\n|-----------|---------------|-------------|--------------------|------------------|\n| Stage I   | 872.53m       | 259.18s     | 879.06m            | 257.83s          |\n| Stage II  | 213.55s       | 208.44s     | 860.12s            | 852.32s          |\n| Stage III | 83.74s        | 67.26s      | 384.50s            | 376.57s          |\n| Total     | 877.48m       | 534.88s     | 899.80m            | 1,486.72s        |\t\n\t\t\nThe results indicate that our proposed UltraRE significantly improves efficiency compared to RecEraser. Specifically, in stages I and III, UltraRE demonstrates average efficiency improvements of **20,227.87%** and 13.30% respectively. Note that, in the large-scale dataset (ML-10M), our proposed clustering algorithm (OBC) significantly outperforms the BKM used in RecEraser, *reducing clustering time from several hours to just a few minutes* (in stage I, 872.53m/879.06m vs 259.18s/257.83s).\n\n**Q3**: The experimental datasets are small-size, which may limit the accuracy of efficiency test.\n\n**Response**: As responded above, following SOTA [6], we have conducted experiments on ML-10M (the largest dataset used in [6]). The experimental results demonstrate higher efficiency improvements when compared to the results reported in the paper, providing additional evidence of the substantial efficiency enhancements achieved by our method.\n\n**Q4**: Major technical contribution compared with RecEraser (SOTA).\n\n**Response**: Please refer to *Response to Q1* in the rebuttal to all reviewers."}, {"review_id": "EtK5q7Wt1X", "reviewer": "Reviewer_55Fw", "summary": "This paper tackles the issue in recommendation unlearning algorithm, specifically focusing on RecEraser. The authors introduce UltraRE, a framework devised to optimize the RecEraser. UltraRE aims at mitigating three primary losses - redundancy, relevance, and combination. By integrating transport weights in the clustering algorithm, it addresses redundancy loss, balancing collaboration and balance. Besides, it simplify the complexity of the model combiner without diminishing efficacy. The authors put these modifications together to enhance both unlearning efficiency and model utility, and empirically validate the proposed framework through extensive experiments on three real-world datasets.\n", "questions": "In the ablation study, the authors investigated the inertia performance of clustering algorithms in data partitioning for different algorithms. From Figure 4, it is evident that OBC (UltraRE) and BRD (SISA) significantly outperform BKM (RecEraser) in terms of clustering inertia. However, UltraRE does not show a substantial improvement over RecEraser in unlearning performance, and interestingly, SISA performs worse than RecEraser. \n* Could the authors elaborate on the relationship between clustering performance (inertia) and unlearning performance? \n* Additionally, what specifically contributes to the improvements presented by the proposed method, UltraRE?", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "*  The paper is written in a clear and engaging style, making it easy to follow.\n*  It addresses a timely and critical issue, machine unlearning in recommender systems, which is essential in the context of data privacy regulations.\n*  The proposed UltraRE framework is straightforward and effective. And the authors conduct extensive experiments on three real-world datasets to demonstrate the efficacy of the proposed framework.\n", "weaknesses": "* The improvements in efficiency and effectiveness brought by UltraRE are very marginal, raising questions about its practical impact and value.\n* The novelty in UltraRE is limited, as it mainly employs the existing method to improve the previous method RecEraser.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**:\tNovelty of our proposed UltraRE.\n\n**Response**: Please refer to *Response to Q1* in the rebuttal to all reviewers.\n\n**Q2**:\tRelationship between clustering performance (inertia) and unlearning performance.\n\n**Response**: Our proposed UltraRE, being an exact unlearning approach, inherently achieves optimal unlearning performance (completeness). Thus, considering this observation and the comments provided, we infer that the unlearning performance you mentioned refers to model utility (recommendation performance). \n\nInertia is the summation of the inner-cluster distance of all sample-centroid pairs, ranging in $[0, \\infty]$. Model utility is evaluated by NDCG and HR, both of which range in $[0, 1]$. Therefore, the scales of inertia and model utility are different, leading to inconsistent improvements between them. To subtly investigate the relationship between inertia and model utility (NDCG@10), we conduct another ablation study. Specifically, we vary the clustering algorithms in stage I and use Logistic Regression (LR) in stage III for all compared methods, and report corresponding inertia and NDCG (during learning). We choose LR due to its comparable performance to ATTention networks (ATT), as shown in the \"Effect of Combination\" section. For easy comparison, we also report the result of original RecEraser and SISA.\n\n| ML-100K      | Stage I | Stage III | Inertia (stage I) | DMF-NDCG (stage III) | LightGCN-NDCG (stage III) |\n|--------------|---------|-----------|-------------------|----------------------|---------------------------|\n| UltraRE      | OBC     | LR        | 816.32            | 0.3847               | 0.3859                    |\n| RecEraser-LR | BKM     | LR        | 1,738.24          | 0.3792               | 0.3808                    |\n| RecEraser    | BKM     | ATT       | 1,738.24          | 0.3795               | 0.3812                    |\n| SISA-LR      | BRD     | LR        | 852.50            | 0.3824               | 0.3836                    |\n| SISA         | BRD     | AVG       | 852.50            | 0.3716               | 0.3684                    |\n\n| ML-1M        | Stage I | Stage III | Inertia (stage I) | DMF-NDCG (stage III) | LightGCN-NDCG (stage III) |\n|--------------|---------|-----------|-------------------|----------------------|---------------------------|\n| UltraRE      | OBC     | LR        | 729.46            | 0.4042               | 0.4241                    |\n| RecEraser-LR | BKM     | LR        | 1,318.31          | 0.3968               | 0.4169                    |\n| RecEraser    | BKM     | ATT       | 1,318.31          | 0.3973               | 0.4171                    |\n| SISA-LR      | BRD     | LR        | 1,129.72          | 0.3972               | 0.4173                    |\n| SISA         | BRD     | AVG       | 1,129.72          | 0.3956               | 0.3941                    |\n\n| ADM          | Stage I | Stage III | Inertia (stage I) | DMF-NDCG (stage III) | LightGCN-NDCG (stage III) |\n|--------------|---------|-----------|-------------------|----------------------|---------------------------|\n| UltraRE      | OBC     | LR        | 775.22            | 0.4294               | 0.4345                    |\n| RecEraser-LR | BKM     | LR        | 1,319.61          | 0.4230               | 0.4278                    |\n| RecEraser    | BKM     | ATT       | 1,319.61          | 0.4234               | 0.4281                    |\n| SISA-LR      | BRD     | LR        | 1,052.74          | 0.4255               | 0.4273                    |\n| SISA         | BRD     | AVG       | 1,052.74          | 0.4063               | 0.4025                    |\n\nBased on the presented tables, we obtain several key observations:\n* Comparing UltraRE, RecEraser-LR, and SISA-LR, we observe that a lower inertia is associated with a higher recommendation performance. This suggests a positive correlation between clustering performance and recommendation performance.\n* LR demonstrates similar recommendation performance to ATT, surpassing AVG, when compared to the LR-versions (RecEraser-LR and SISA-LR) and their original versions (RecEraser and SISA). This finding is consistent with the results from the \"Effect of Combination\" section.\n* In ML-1M and ADM datasets, SISA-LR achieves comparable recommendation performance to RecEraser-LR, while outperforming it in ML-100k. This aligns with the differences in inertia across the various datasets, indicating that (i) clustering performance generally correlates positively with recommendation performance, and (ii) the advancements in RecEraser are primarily attributed to the effectiveness of the combiner (ATT).\n\nIn conclusion, superior clustering performance corresponds to improved recommendation performance. Our proposed clustering algorithm (OBC) exhibits substantial superiority over the compared methods.\n\n**Q3**:\tWhat contributes to the improvements of UltraRE?\n\n**Response**: For model utility improvement, it is attributed to the superior clustering performance of OBC (as shown in *Response to Q2*). For efficiency improvement, it is attributed to both LR and OBC (as shown in *Response to Q2* in the rebuttal for all reviewers)."}, {"review_id": "gOuPEapkKS", "reviewer": "Reviewer_Jkju", "summary": "This paper studies the recommendation unlearning problem and focuses on the exact unlearning approach. The authors rethink the exact unlearning framework from an ensemble-based perspective, and decompose the error into three components. The authors mainly modify the existing SOTA framework regarding the first and the third components. For the first component, a new optimal balanced clustering algorithm is proposed to improve efficacy and efficiency. For the third component, the model aggregator is simplified to improve efficiency. Extensive experiments are conducted on three real-world datasets and across different recommendation models.", "questions": "Please refer to Weakness 1.  \n\nThis paper focuses on exact unlearning, but approximate unlearning has gained much attention due to its efficiency. There is also an approximate unlearning method in recommendation unlearning. Although it adopts a different approach, it would be helpful to have a discussion about it.  \n\n[a] Li, Y., Chen, C., Zheng, X., Zhang, Y., Gong, B., & Wang, J. (2023). Selective and Collaborative Influence Function for Efficient Recommendation Unlearning. arXiv preprint arXiv:2304.10199.", "limitations": "NA", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The topic (recommendation unlearning) is significant and timely. Recommendation is a typical scenario of machine unlearning where the data naturally comes from diverse users.\n\n2. This paper rethinks the exact unlearning framework from an ensemble-based perspective, and modifies the framework with theoretical guidance, which distinguish this work from prior intuition-motivated modification.\n\n3. One key technical contribution of this paper is the proposed optimal balanced clustering algorithm, which incorporates the balanced constraint into the optimization process, addressing the incongruity between user similarity and shard balancing.\n\n4. Extensive experiments are conducted to evaluate the proposed framework. The evaluations include the performance of two unlearning goals and an ablation study of each stage.\n\n5. In general, this paper is well-organized and easy to follow.", "weaknesses": "1. The optimization process of Eq (5) is not clear. Is it identical to prior work [6, 7]? Please provide more details.\n\n2. As shown in Table 2, the improvements in stages I and III appear to be significant. But the time costs of these stages are not comparable with that of stage II, where the authors remain unchanged. Therefore, this makes the overall improvement insignificant.\n\n3. There are some typos in the paper:   \nLine 203 “\\sum_i w_{ij}” -> “\\sum_j w_{ij}”  \nLine 365 “[6, 7, 24] Instead” -> “[6, 7, 24]. Instead”", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**:\tOptimization process in stage III (model combination).\n\n**Response**: Although different from prior work [6, 7] in terms of the model used, our method also utilizes the stochastic gradient descent algorithm for optimization. We will provide further explanations regarding these details during the revision.\n\n**Q2**:\tSignificance of efficiency enhancement.\n\n**Response**: As mentioned in the “Broader Impacts and Limitations” section, a common limitation of ensemble retraining frameworks is the lack of experiments on large-scale datasets. Current experiments do not sufficiently demonstrate the efficiency enhancement, because the majority of time is spent during stage II （independent training）while the enhancements occur in stages I (non-overlapping division) and III (model combination). Thus, following [6], we further conduct experiments on ML-10M (large-scale dataset) with 50 shards (large shard number), and report the results in the table below.\n\n| ML-10M    | DMF-RecEraser | DMF-UltraRE | LightGCN-RecEraser | LightGCN-UltraRE |\n|-----------|---------------|-------------|--------------------|------------------|\n| Stage I   | 872.53m       | 259.18s     | 879.06m            | 257.83s          |\n| Stage II  | 213.55s       | 208.44s     | 860.12s            | 852.32s          |\n| Stage III | 83.74s        | 67.26s      | 384.50s            | 376.57s          |\n| Total     | 877.48m       | 534.88s     | 899.80m            | 1,486.72s        |\t\n\t\t\nThe results indicate that our proposed UltraRE significantly improves efficiency compared to RecEraser. Specifically, in stages I and III, UltraRE demonstrates average efficiency improvements of **20,227.87%** and 13.30% respectively. Note that, in the large-scale dataset (ML-10M), our proposed clustering algorithm (OBC) significantly outperforms the BKM used in RecEraser, *reducing clustering time from several hours to just a few minutes* (in stage I, 872.53m/879.06m vs 259.18s/257.83s). The experimental results demonstrate higher efficiency improvements when compared to the results reported in the paper, providing additional evidence of the substantial efficiency enhancements achieved by our method.\n\n**Q3**:\tTypos.\n\n**Response**: We will carefully review the paper and fix any typos during revision.\n\n**Q4**:\tDiscussion about approximate recommendation unlearning.\n\n**Response**: We will provide a brief introduction to the mentioned paper in the “Related Work” section."}]

Author rebuttal:
We sincerely thank all the reviewers for their valuable comments and suggestions, which are crucial for improving our work. We hope our response addresses your concerns.

**Q1**: Major technical contribution compared with RecEraser (SOTA).

**Response**: We summarize the contributions in the table below, followed by a detailed explanation.

|No.|Contributions|UltraRE (ours)|RecEraser [6]|Significance|
|-|-|-|-|-|
|1|Analyse with error decomposition, aiming to reduce redundancy loss (stage I) and combination loss (stage III)|Theory|Intuition|The first exact unlearning method that is guided by theory|
|2|Propose a novel clustering algorithm (stage I)|OBC|BKM [6, 7, 24]|Improve recommendation performance by 1.28%, reduce time cost by 98.11% (20,227.87% on ML-10M)|
|3|Simplify model combiner (stage III)|LR|ATT|Achieve comparable recommendation performance, reduce time cost by 11.95% (13.30% on ML-10M)|

Firstly and most importantly, we rethink exact unlearning from the perspective of ensemble learning and provide a theoretical analysis for prediction error, which serves as the theoretical basis for existing exact unlearning approaches, i.e., ensemble retraining frameworks. To the best of our knowledge, this is the first exact recommendation unlearning method that offers theoretical guarantees, setting it apart from previous work [6, 24] that relied on the intuition of collaboration preservation. Building upon this theory, we decompose the error into three distinct components and establish correlations with corresponding stages. Our goal is to enhance performance by reducing the error at each stage (I and III). While this may appear similar to the improvement direction pursued by prior works [6, 7, 24], we want to emphasize that our approach is guided by theory, not intuition. In other words, our work provides theoretical support for prior intuitions.

Secondly, we propose a novel algorithm to address an important issue in stage I, i.e., the incongruity between sample similarity and shard balance. Prior work [6, 7, 24] relies on the manual insertion of a priority list to achieve balanced clustering (BKM). This approach, once again, relies solely on intuition without any theoretical support. As shown in our empirical study (Figure 4), BKM fails to effectively resolve this incongruity, compromising sample similarity to achieve shard balance. In contrast, we propose a novel balanced clustering algorithm (OBC) that aims to obtain the optimal solution by optimizing the Monge-Kantorovich Problem. To further enhance efficiency, we solve the optimization objective through Sinkhorn distance. The experimental results (Tables 2 and 3, and Figure 4) demonstrate that the proposed algorithm significantly outperforms compared methods, efficiently achieving an equilibrium between the incongruity. Our freshly included experimental results in *Response to Q2* on a large-scale dataset provide additional evidence of the substantial efficiency enhancements achieved by our method.

Thirdly, guided by the experience in ensemble learning, we simplify the model complexity by employing LR. Additionally, we conduct an empirical study to validate that the model complexity in stage III can be reduced while maintaining comparable performance.

**Q2**: Significance of efficiency improvement.

**Response**: Current experiments do not sufficiently demonstrate the efficiency enhancement, because the majority of time is spent during stage II (independent training) while the enhancements occur in stages I (non-overlapping division) and III (model combination). Thus, following [6], we further conduct experiments on ML-10M (the largest dataset used in [6]) with 50 shards (large shard number), and report the results in the table below.

| ML-10M    | DMF-RecEraser | DMF-UltraRE | LightGCN-RecEraser | LightGCN-UltraRE |
|-----------|---------------|-------------|--------------------|------------------|
| Stage I   | 872.53m       | 259.18s     | 879.06m            | 257.83s          |
| Stage II  | 213.55s       | 208.44s     | 860.12s            | 852.32s          |
| Stage III | 83.74s        | 67.26s      | 384.50s            | 376.57s          |
| Total     | 877.48m       | 534.88s     | 899.80m            | 1,486.72s        |	
		

The results indicate that our proposed UltraRE significantly improves efficiency compared to RecEraser. Specifically, in stages I and III, UltraRE demonstrates average efficiency enhancements of **20,227.87%** and 13.30% respectively. Note that, in the large-scale dataset, our proposed clustering algorithm (OBC) outperforms the BKM used in RecEraser, *reducing clustering time from several hours to just a few minutes* (in stage I, 872.53m/879.06m vs 259.18s/257.83s). The experimental results demonstrate higher efficiency improvements when compared to the results reported in the paper, providing additional evidence of the substantial efficiency enhancements achieved by our method.

Meta-review: The paper introduces an intriguing perspective on the exact unlearning framework, utilizing an ensemble-based approach while incorporating theoretical advancements. The authors' unique integration of theoretical guidance to disentangle the error into three distinct components, each correlating with corresponding stages, is a noteworthy contribution that distinguishes their work from previous intuition-driven modifications to the framework.

The reviews for this submission have generally been positive, with one exception being Reviewer zuBB, who recommended a borderline reject. Upon careful consideration of Reviewer zuBB's critique and the authors' response, it is my opinion that Reviewer zuBB's concern regarding "approximate unlearning" may not carry substantial weight. The authors' response to the other points raised by this reviewer is convincing and demonstrates a robust understanding of the subject matter. Furthermore, it is important to note that Reviewer zuBB has not provided any additional feedback or objections following the authors' response.

Based on my comprehensive evaluation of the paper and the entire review process, I would like to recommend the acceptance for this submission.
Decision: Accept (poster)