Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a new federated unlearning method for a specific federated clustering workflow. A key to the federated unlearning method is secure compressed multiset aggregation (SCMA) to aggregate local contributing data and enhance data privacy. Theoretical analysis is shown to demonstrate the computation and communication effectiveness of the proposed method. Experimental results are also shown to justify the practical speedup of the proposed method.
strength_and_weaknesses: Strength:
- The paper is well-written.  
- Solving the unlearning problem for federated tasks is of great importance.  
- Both theoretical analysis and experimental results are shown to justify the effectiveness of the proposed method.  

Weaknesses:
- It seems the scope of the proposed method is a bit limited as it seems to only be designed for federated clustering. I wonder how hard it will be to generalize the proposed method to general federated unlearning.  
- the scale of the experiment is a bit small. What will the performance look like on datasets with the ImageNet scale?  
- I am almost sure that SCMA (or at least its variants) has been studied in communication-efficient distributed optimization, e.g., via gradient or model quantization and/or sparsification. This limits the novelty of the proposed method.  
clarity,_quality,_novelty_and_reproducibility: - Clarity: the presentation of the paper is clear, and the proposed method is easy to follow. 
- Quality: the paper is well written. Both theoretical and empirical results seem to come with good quality.    
- Novelty: the proposed method is novel.  
- Reproducibility: enough implementation details are provided to demonstrate the effectiveness of the proposed method.
summary_of_the_review: The paper proposes a good and efficient method for federated unlearning of federated clustering tasks. Both theoretical and empirical results are shown to justify its performance. The scope of the proposed method is limited by it only tackles federated clustering problems.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper focuses on unlearning federated clustering problems with k-means++ initialization and secure compressed multiset aggregation. The idea of unlearning is to perform k-means++ initialization at each local client. By exploiting the nature of k-means++ approximation, the centroid set C may remain unchanged if removed points are not in C.
strength_and_weaknesses: Strength:
1.The paper proposes a unlearning mechanism for federated clustering with privacy criteria that enables  efficient data removal at the client and server level.

2. The extensive theoretical analyses are derived to validate the performance guarantees of the proposed method.

3. The algorithm is evaluated on a number of datasets to demonstrate the effectiveness of the proposed approach for machine unlearning.

Weakness:
1.	According to algorithms 1 and 4, the unlearning process requires the help of removal set XR. This requirement is naturally fulfilled in the context of centralized unlearning but may not be available. In such case, the retraining in line 3 in algorithm 4 will always be required and significantly increase the complexity.
2.	The unlearning strategy in this paper relies heavily on the k-means++ algorithm, which approximates the k-means problem proposed in 2007. The paper exploits the nature of k-means++ initialization with no technical improvement, making the novelty and contribution questionable.
3.	Line 2 in algorithm 1 implies that the centroid set C can remain the same if the removal point is not inside the centroid set C without further restrictions. This is very questionable when a certain number of biased data points are removed within a single request. In the unlearning experiment setting, the unlearning requests are carried out with one data point per client at each round of unlearning, which is insufficient to evaluate the performance of the proposed unlearning method. 
clarity,_quality,_novelty_and_reproducibility: It is understandable to a large extent, but parts of the paper need more work.
summary_of_the_review: In general, the studied problem is interesting and important. In addition, the methodology is principled with three major merits as discussed above. However, the work still has some unaddressed concerns to well justify its technical and empirical contributions.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a novel approach for unlearning data under federated learning setting for the purpopse of clustering. The proposed method also has security gaurantees. Theoretical analysis in terms of clustering performance and complexity analysis has been done for the proposed method.
strength_and_weaknesses: The paper discusses a new topic of federated unlearning for the purpose of clustering. Given the rich content of the paper, the reviewer believe additional work needs to be done to make the story easier to follow. The reviewer has several suggestions:

1. There are several places in the paper that a term is described first and the definition is given several sections later in the paper, which brings difficulty for the reader to follow.
2. The reviewer thinks it would be useful to first introduce the intuitions behind the algorithms and then present the algorithm. This is particularly the case for algorithm 2.
3. In section 4.2, the reviewer feel a little bit lost since the outliers are introduced in the paper. The discussion of outlier removal is not very closely related to the existence of outliers. Given the space limit of the paper, it would be clearer to focus only on one topic and brings other issues in the appendix or the discussion section.

Major concerns:
1. The reviewer has several questions in terms of algorithm 2 that needs further clarification.
- The quantization of $C^{(l)}$ is performed dimension-wise, can the authors be more specific on how step 4 is performed? 
- There is a well known label switching issue under clustering, in step 5 to sum up $q^{(l)}$ at the server, will there be any issue if the label is switched? The reviewer believes switching label at the first place will lead to different $q^{(l)}$ at the first place and hence $q$, this could potentially be a severe issue for clustering.

2. For removing adversarial points, will the cost be necessarily smaller than refitting the model? This is not discussed as the magnitude of $\epsilon_2$ and $s_{\text{min}}$ is not specified in the main paper.

Minor issues:

1. Could the author ellaborate more on the difference between $\phi_f$ and $\phi_{c}$? The value of these two terms are equal when $C=C_s$, are there any particular reason to define two terms?

2. Can the authors ellaborate more on the role of the hyperparameters $\alpha$ and $p$ in the proposed method?
clarity,_quality,_novelty_and_reproducibility: The reviewer thinks the topic in this paper is very interesting and is of importance in practice. The proposed method is novel to the best of the reviewer's knowledge. However, the description of the method is not clear, the reviewer found it not easy to follow the logic flow of the paper. 
summary_of_the_review: The reviewer thinks the topic in this paper is very interesting and is of importance in practice. However, there are several concerns that is critical to the proposed method. Therefore, the reviewer believe additional work or clarification is needed before the work can be published.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work proposes the first known unlearning mechanism for federated clustering with privacy criteria that support simple, provable, and efficient data removal at the client and server level, by combining special initialization procedures with quantization methods that allow for secure aggregation of estimated local cluster counts at the server unit.

In the empirical studies, results show it can achieve 84x across seven datasets compared to completely retraining K-means++ locally and globally for each removal request
strength_and_weaknesses: My major concern is the benchmark comparison. Authors claim it is the first unlearning algorithm for federate cluster, so it makes hard to understand how innovative compared with peer works
clarity,_quality,_novelty_and_reproducibility: The experiments are in high quality. For example, authors used shaded areas represent the standard deviation so it is very clear how significant is the improvement. 

Reproducibility: authors provided detailed instruction for the script as well as the source code, so I believe it is reproducible. (Though I didn't fully reproduce it by myself).
summary_of_the_review: Overall I believe it is an interesting paper, with clear writing as well as high quality experiment. My major concern is the benchmark comparison. Authors claim it is the first unlearning algorithm for federate cluster, so it makes hard to understand how innovative compared with peer works. So I choose marginal above threshold with low confidence.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The main contribution of this work lies in efficient unlearning for privacy-preserving federated clustering based on the secure compressed multiset aggregation (SCMA) framework that can achieve low communication complexity while ensuring local data privacy and exact aggregated data recovery.

After reviewing and responding to the authors' rebuttal and an active discussion, (A) most reviewers have agreed that the contributions of this work (especially the SCMA framework and theoretical analysis of K-means++ enabling exact unlearning) are novel and interesting. 

Some reviewers have initially raised a number of concerns requiring clarifications. The authors have carefully addressed them in the rebuttal and revised paper to alleviate the reviewers' concerns.
justification_for_why_not_higher_score: Reviewer j6JM has correctly pointed out that the impact of this work is limited to unlearning in federated clustering rather than a general-purpose unlearning method.
justification_for_why_not_lower_score: See reason (A) above.
Decision: Accept: poster