{'fraction_non_alphanumeric': 0.04330175913396482, 'fraction_numerical': 0.018276081321225362, 'mean_word_length': 4.344893691181596, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Machine Unlearning of Federated Clusters

Federated clustering is an unsupervised learning problem that arises in a number of practical applications, including personalized recommender and healthcare systems. With the adoption of recent laws ensuring the"right to be forgotten", the problem of machine unlearning for federated clustering methods has become of significant importance. 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. The gist of our approach is to combine special initialization procedures with quantization methods that allow for secure aggregation of estimated local cluster counts at the server unit. As part of our platform, we introduce secure compressed multiset aggregation (SCMA), which is of independent interest for secure sparse model aggregation. In order to simultaneously facilitate low communication complexity and secret sharing protocols, we integrate Reed-Solomon encoding with special evaluation points into the new SCMA pipeline and derive bounds on the time and communication complexity of different components of the scheme. Compared to completely retraining K-means++ locally and globally for each removal request, we obtain an average speed-up of roughly 84x across seven datasets, two of which contain biological and medical information that is subject to frequent unlearning requests.


Introduction
The availability of large volumes of user training data has contributed to the success of modern machine learning models. For example, most state-of-the-art computer vision models are trained on large-scale image datasets including Flickr (Thomee et al., 2016) and ImageNet (Deng et al., 2009). Organizations and repositories that collect and store user data must comply with privacy regulations, such as the recent European Union General Data Protection Regulation (GDPR), the California Consumer Privacy Act (CCPA), and the Canadian Consumer Privacy Protection Act (CPPA), all of which guarantee the right of users to remove their data from the datasets (Right to be Forgotten). Data removal requests frequently arise in practice, especially for sensitive datasets pertaining to medical records (numerous machine learning models in computational biology are trained using UK Biobank (Sudlow et al., 2015) which hosts a collection of genetic and medical records of roughly half a million patients (Ginart et al., 2019)). Removing user data from a dataset is insufficient to ensure sufficient privacy, since training data can often be reconstructed from trained models (Fredrikson et al., 2015;Veale et al., 2018). This motivates the study of machine unlearning (Cao & Yang, 2015) which aims to efficiently eliminate the influence of certain data points on a model. Naively, one can retrain the model from scratch to ensure complete removal, yet retraining comes at a high computational cost and is thus not practical when accommodating frequent removal requests. To avoid complete retraining, specialized approaches have to be developed for each unlearning application (Ginart et al., 2019;Guo et al., 2020;Bourtoule et al., 2021;Sekhari et al., 2021).
At the same time, federated learning (FL) has emerged as a promising approach to enable distributed training over a large number of users while protecting their privacy Chen et al., 2020;. The key idea of FL is to keep user data on their devices and train global models by aggregating local models in a communication-efficient and secure manner. Figure 1: Overview of our proposed federated clustering scheme. K-means++ initialization and quantization are performed at each client in parallel. The SCMA procedure ensures that only the server knows the aggregated statistics of clients, without revealing who contributed the points in each individual cluster. The server generates points from the quantization bins with prescribed weights and performs full K-means++ clustering to infer the global model.
Due to model inversion attacks (Zhu et al., 2019;Geiping et al., 2020), secure local model aggregation at the server is a critical consideration in FL, as it guarantees that the server cannot get specific information about client data based on their local models (Bonawitz et al., 2017;Bell et al., 2020;So et al., 2022;Chen et al., 2022). Since data privacy is the main goal in FL, it should be natural for a FL framework to allow for frequent data removal of a subset of client data in a cross-silo setting (e.g., when several patients request their data to be removed in the hospital database), or the entire local dataset for clients in a cross-device setting (e.g., when users request apps not to track their data on their phones). This leads to the largely unstudied problem termed federated unlearning (Liu et al., 2021;Wu et al., 2022;Wang et al., 2022). However, existing federated unlearning methods do not guarantee exact or approximate unlearning (Ginart et al., 2019;Guo et al., 2020), they do not come with theoretical performance guarantees after model updates, and often, they are vulnerable to adversarial attacks.
Our contributions. We describe the first unlearning framework for a newly developed federated clustering approach (Figure 1) which addresses the following problems: • Unlearning of clusters at the client level via an intuitive application of K-means++ initialization without subsequent Lloyd's iterations. The advantage of using K-means++ is that the models do not need to be updated unless removed points were selected as initial centroids. At the server level, full K-means++ can be performed to improve the overall federated clustering performance.
• Enabling secure aggregation of sparse vectors via a novel approach termed secure compressed multiset aggregation (SCMA). The gist of SCMA is to encode quantized local data into information pertaining to the identifiers of quantization bins and their occupancies using specialized Reed-Solomon code evaluations, and followed by secure model aggregations.
• Ensuring privacy-accuracy-efficiency trade-offs through the introduction of a privacy criterion suitable for federated clustering and unlearning with simple communication protocols. In this context, we derive theoretical performance guarantees for the computational and communication complexity of model training and unlearning procedures.
• Compiling a collection of datasets for benchmarking unlearning of federated clusters, including two new datasets which contain anonymized cancer genomics and microbiome information that is subject to frequent unlearning requests. Experimental results reveal that our one-shot algorithm offers an average speed-up of roughly 84x compared to complete retraining across seven datasets.

Related Works
Machine unlearning. For centralized machine unlearning problems, two types of unlearning requirements were proposed in previous works: exact unlearning and approximate unlearning. For exact unlearning, the unlearned model is required to perform identically as a completely retrained model. To achieve this, Cao & Yang (2015) introduced distributed learners, Bourtoule et al. (2021) proposed sharding-based methods, Ginart et al. (2019) used quantization to eliminate the effect of removed data in clustering problems, and  applied sharding-based methods to Graph Neural Networks. For approximate unlearning, the "differences" in behavior between the unlearned model and the completely retrained model should be appropriately bounded, similarly to what is done in the context of differential privacy. Following this latter direction, Guo et al. (2020) introduced the inverse Newton update for linear models, Sekhari et al. (2021) studied the generalization performance of approximately unlearned models, while  extended the analysis to linearized Graph Neural Networks. A limited number of recent works also investigated data removal in the FL settings: Liu et al. (2021) proposed to use fewer iterations during retraining for federated unlearning, Wu et al. (2022) introduced Knowledge Distillation into the unlearning procedure to eliminate the effect of data points requested for removal, and Wang et al. (2022) considered removing all data from one particular class via inspection of the internal influence of each channel in Convolutional Neural Networks. These federated unlearning methods are (mostly) empirical and do not come with theoretical guarantees for model performance after removal and/or for the unlearning efficiency. In contrast, our proposed federated clustering framework not only enables efficient data removal in practice, but also provides theoretical guarantees for the unlearned model performance and for the expected time complexity of the unlearning procedure.
Federated clustering. The idea of federated clustering is to perform clustering using data that resides at different edge devices. It is closely related to clustered FL (Sattler et al., 2020), whose goal is to learn several global models simultaneously, based on the cluster structure of the dataset, as well as personalization according to the cluster assignments of client data in FL (Mansour et al., 2020). One difference between federated clustering and distributed clustering (Guha et al., 2003;Ailon et al., 2009) is the assumption of data heterogeneity across different clients. Recent works (Ghosh et al., 2020;Dennis et al., 2021;Chung et al., 2022) exploit the non-i.i.d nature of client data to improve the performance of some learners. Another difference pertains to data privacy. Most previous methods were centered around the idea of sending exact (Dennis et al., 2021) or quantized client (local) centroids (Ginart et al., 2019) to the server, which may not be considered private as it leaks the data statistics or cluster information of all the clients. To avoid sending exact centroids,  proposes sending distances between data points and centroids to the server without revealing the membership of data points to any of the parties involved. Note that there is currently no formal definition of computational or information-theoretic secrecy/privacy for federated clustering problems, making it hard to compare methods addressing different aspects of FL. Our method introduces a simple-to-unlearn clustering process and new privacy mechanism that is intuitively appealing as it involves communicating obfuscated point counts of the clients to the server.

Preliminaries
We start with a formal definition of the centralized K-means problem. Given a set of n points X arranged into a matrix X ∈ R n×d , and the number of clusters K, the K-means problem asks for finding a set of points where || · || F denotes the Frobenius norm of a matrix, · denotes the 2 norm of a vector, and C ∈ R n×d records the closest centroid in C to each data point x i (i.e., c i = arg min cj ∈C x i − c j ). Without loss of generality, we make the assumption that the optimal solution is unique in order to facilitate simpler analysis and discussion, and denote the optimum by C * = {c * 1 , ..., c * K }. The set of centroids C * induces an optimal partition We use φ * c (X) to denote the optimal value of the objective function for the centralized K-means problem. With a slight abuse of notation, we also use φ * c (C * k ) to denote the objective value computed over the optimal cluster C * k . A detailed description of a commonly used approach for solving the K-means problem, K-means++, is available in Appendix A.
In federated clustering, the dataset X is no longer available at the centralized server. Instead, data is stored on L edge devices (clients) and the goal of federated clustering is to learn a global set of K centroids C s over the union of client data. For simplicity, we assume that there exists no identical data points across clients, and that the overall dataset X is the union of the datasets X (l) arranged as X (l) ∈ R n (l) ×d on devices l, ∀l ∈ [L]. To make sure the global model can be learned securely, we allow all clients to communicate with each other as well as the server only to perform secure model aggregation (Bonawitz et al., 2017;Bell et al., 2020;So et al., 2022). The server will receive the aggregated cluster statistics of all clients, while each client will only know the cluster assignment of its own data X (l) and not that of the global server clusters. In this case, the federated K-means problem asks for finding K global centroids C s that minimize the objective where C (l) s ∈ R n (l) ×d records the centroids of the global clusters that data points {x on client l belong to. A formal definition of global clusters is given in Definition 5.1. Here, φ f stands for the objective of federated clustering, not to be confused with the centralized φ c from Equation (1).
Exact unlearning. For clustering problems, the exact unlearning criterion may be formulated as follows. Let X be a given dataset and A a (randomized) clustering algorithm that trains on X and outputs a set of centroids C ∈ M, where M is the chosen space of models (centroid sets). Let U be an unlearning algorithm that is applied to A(X ) to remove the effects of one data point x ∈ X . Then U is an exact unlearning algorithm if ∀C ∈ M, x ∈ X , P(U(A(X ), X , x) = C) = P(A(X \x) = C). To avoid confusion, in certain cases, this criterion is referred to as probabilistic (model) equivalence.
Privacy-accuracy-efficiency trilemma. How to trade-off data privacy, model performance, communication and computational efficiency is a long-standing problem in distributed learning (Acharya & Sun, 2019;Chen et al., 2020;Gandikota et al., 2021) that also carries over to FL and federated clustering. Solutions that simultaneously address all these challenges in the latter context are still lacking. For example, Dennis et al. (2021) proposed a one-shot algorithm that takes model performance and communication efficiency into consideration by sending the exact centroids of each client to the server in a nonanonymous fashion. This approach may not be desirable under stringent privacy constraints as the server can gain information about individual client data. On the other hand, privacy considerations were addressed in  by performing K-means Lloyd's iterations anonymously via distribution of computations across different clients. Since the method relies on obfuscating pairwise distances for each client, it incurs computational overheads to hide the identity of contributing clients at the server and communication overheads due to interactive computations. None of the above methods is suitable for unlearning applications. To simultaneously enable unlearning and address the trilemma in the unlearning context, our privacy criterion involves transmitting the number of client data points within local client clusters in such a manner that the server cannot learn the data statistics of any specific client, but only the overall statistics of the union of client datasets. In this case, computations are limited and the clients on their end can perform efficient unlearning, unlike the case when presented with data point/centroid distances.
Random and adversarial removal. All previous unlearning literature focuses on the case where all data points are equally likely to be removed, a setting known as random removal. However, adversarial data removal requests may arise when users are sensitive towards certain points that are critical for model training (i.e., boundary points in optimal clusters). We refer to such a removal request as adversarial removal. Note that adversarial removal may be of more importance in practice, especially for medical data. For example, if the data points correspond to gene mutations of patients, the sparsely distributed boundary points usually represent rare mutations where most patients would like to keep their privacy, leading to a larger probability to be removed. In Section 4.2 and 5.3, we provide theoretical analysis for both types of removal requests.

Machine Unlearning via Specialized Seeding
We exhibit next a useful connection between exact unlearning and the K-means++ initialization procedure. Throughout this section we consider the problem in the centralized setting so as to set the stage for the discussion of the federated clustering setting in Section 5. The first step is to introduce the unlearning mechanism based on the initial centroid set, as described in Algorithm 1.

Algorithm 1 Unlearning via K-means++ Initialization.
1: input: Dataset X , centroid set C obtained by K-means++ initialization on X , removal request set  Sample x from X with probability d 2 (x,C ) φc(X ;C ) . 13: 14: end for 15: end if 16: return C

Performance Analysis
Since the centroids chosen through K-means++ initialization are true data points, the results returned by Algorithm 1 are guaranteed to contain no information about the data points that have been removed. To verify that Algorithm 1 is an exact unlearning method, we also need to check that C is probabilistically equivalent to the models generated by rerunning the K-means++ initialization process on X , the set of point remaining after removal. This observation is best explained through an example, while a formal proof is provided in Appendix B.
Suppose that one would like to unlearn the data point x i from the clustering model represented by an initial centroid set C. For the first chosen centroid c 1 in C, there are only two possibilities: c 1 = x i and c 1 = x i . In the first case, we will have to re-run the initialization over X , which is retraining the model. In the second case, since we know c 1 = x i , the probability of choosing c 1 from X as the first centroid becomes the conditional probability P(choose c 1 from X as the first centroid|c 1 = x i ) = 1 n−1 = P(choose c 1 from X as the first centroid), where n is the number of data points in X . Therefore, the first centroid c 1 returned by Algorithm 1 can always be viewed as the first centroid obtained by re-running the initialization over X . This can be generalized for c j ∀j ∈ [K] and arbitrary X R . Since Algorithm 1 is an exact unlearning method, we can have the performance guarantees in Lemma 4.1 based on Theorem 1.1 of Vassilvitskii & Arthur (2006). Lemma 4.1. For any set of data points X and removal set X R , assuming that the remaining dataset is X and the centroid set returned by Algorithm 1 is C , we have E(φ c (X ; C )) ≤ 8(ln K + 2)φ * c (X ).

Complexity Analysis
We show next that Algorithm 1 supports removing R random points in expected time O(RK 2 d) and R adversarial points in expected time O(RK 3 1 2 d). In contrast, the corresponding time complexity of retraining is O(nKRd). To analyze the removal time complexity of Algorithm 1, we first state two assumptions pertaining to optimal cluster sizes and outliers.
Assumption 4.2. Let 1 = n Ksmin be a constant denoting what we refer to as cluster size imbalance, where s min equals the size of the smallest cluster in the optimal clustering; when 1 = 1, all clusters are of the same size n K . Assumption 4.3. Assume that 2 ≥ 1 is a fixed constant. An outlier x i in X satisfies The assumption is not overly restrictive, as outliers are commonly defined as points that are well-separated from all "regular" clusters: the distance between an outlier and its closest centroid is larger than a scaled proxy for the empirical standard deviation of the average distance between the cluster points and that centroid (Chien et al., 2018;Dennis et al., 2021). There also exist many different approaches for removing outliers for clustering purposes (Chawla & Gionis, 2013;Gan & Ng, 2017), which effectively reduce the probability of outliers to negligible values.
Assumptions 4.2 and 4.3 can be used to derive an expression for the probability of x i ∈ C when x i needs to be unlearned, which equals the probability of retraining with X .
Lemma 4.4. Assume that the number of data points in X is n and the probability of the dataset containing at least one outlier is upper bounded by O (1/n). Let C be the centroid set obtained by running K-means++ on X . For unlearning a data point x i ∈ X we have that for random removal: Based on Algorithm 1, we need to reinitialize the centroids only when the point that requests removal lie in the original centroid set. We need O(K) time to check if this is the case, and we need extra O(nd) time to sample every new centroid due to the distance computation. Therefore, we arrive at an estimate of the expected removal time as shown in Theorem 4.5, which is independent of the problem size n.

Unlearning Federated Clusters
We introduce next our federated clustering framework (Algorithm 2) based on the discussion from Section 4. The removal procedure is described in Algorithm 3. We introduce an oversampling coefficient α for clients, following a common strategy for distributed K-means clustering (Bahmani et al., 2012) to improve the final federated clustering performance. In practice, a constant value α suffices, and for simplicity, we set α = 1 in our subsequent analysis. For Algorithm 2 to satisfy the privacy criterion stated in Section 3, we need to design an efficient protocol for aggregating information at the server pertaining to the overall dataset without leaking individual client data statistics. This approach is discussed in Section 5.1. A simplified version of Algorithm 2 is discussed in Appendix I, for applications where the privacy criterion is not an imperative concern.
Algorithm 2 Secure Federated Clustering 1: input: Dataset X distributed on L clients (X (1) , . . . , X (L) ), client oversampling coefficient α. 2: Run (αK)-means++ initialization on each client l in parallel, obtain the initial centroid sets C (l) , and record the corresponding cluster sizes (|C . 3: Perform uniform quantization of C (l) on each dimension, and flatten the quantization bins into a vector . Set q (l) j = 0 for all other indices. 5: Securely sum up q (l) at server by Algorithm 4, with the aggregated vector denoted as q. 6: For index j ∈ {t : q t = 0}, sample q j points based on pre-defined distribution and denote their union as new dataset X s at server. 7: Run full K-means++ clustering at server with X s to obtain the centroid set C s at server. 8: return Each client retains its own centroid set C (l) , server retains X s , q and C s .

Note that
Step 6 of Algorithm 2 involves generating q j points for the j-th quantization bin. The simplest idea is to choose the center of the quantization bin as the representative point and assign weight q j to it. Then, in Step 7, we can use the weighted K-means++ algorithm at the server to further reduce the computational Algorithm 3 Unlearning of Federated Clusters 1: input: Dataset X distributed on L clients (X (1) , . . . , X (L) ), (C (l) , X s , q, C s ) obtained by Algorithm 2 on X , removal request set X (l) R for single-client removal or L R for multi-client removal. 2: if single-client removal then 3: Run Algorithm 1 on client l and update q (l) if client l has to perform retraining. 4: else 5: q (l) ← 0 on client l, ∀l ∈ L R . 6: end if 7: Securely sum up q (l) at server by Algorithm 4, with the aggregated vector denoted as q . 8: if q = q then 9: C s ← C s . 10: else

11:
Generate X s with q .

12:
Run full K-means++ at the server with X s to obtain C s . 13: end if 14: return Client centroid sets C (l) , server data X s , q and centroids C s . complexity at the server side, by reducing the problem size at the server from n, which is the total number of data points, to KL. However, in practice we find that when the server computational power is not the bottleneck in the FL system, generating data points uniformly at random for the quantization bins with non-zero weights can often lead to better clustering performance. Thus, this is the default choice in our subsequent simulations.

SCMA
To utilize off-the-shelf secure aggregation methods developed for FL (Bonawitz et al., 2017;Bell et al., 2020;So et al., 2022), we first need to quantize the centroids of client data and convert the information into vectors. For simplicity, we use uniform quantization with step size γ for each dimension in Step 3 of Algorithm 2. A detailed description of the quantization process is available in Appendix H. Once the vector representations q (l) of length B d (B = 1/γ), l ∈ [L] of client data are generated, we can use standard secure model aggregation methods (Bonawitz et al., 2017;Bell et al., 2020;So et al., 2022) to sum up all q (l) securely and obtain the aggregated results q at the server. However, since the length of each q (l) is B d , securely aggregating the whole vector would lead to very high communication complexity for each client if γ is small (i.e., if we need finer quantization) or d is large (i.e., if we have to cluster high dimensional data). Moreover, each q (l) is a sparse vector since the number of client centroids is much smaller than the number of quantization bins (i.e., K B d ). So it is inefficient and unnecessary to send out the entire q (l) for aggregation. This motivates us to first compress the vectors and then perform the secure aggregation, and we refer to this process as SCMA.
i is a random key uniformly distributed over F p and hidden from the server. The keys {z [2KL] are generated offline using standard secure model aggregation so that l z (l) . Given S i , the server computes the coefficients of the polynomial g(x) = j:qj =0 (1 − j · x) using the Berlekamp-Massey algorithm (Berlekamp, 1968;Massey, 1969). Then, the server factorizes g(x) over the field F p to determine the roots j −1 , q j = 0, using the polynomial factorizing algorithm (Kedlaya & Umans, 2011). Finally, the server solves a set of 2KL linear equations , by considering q j as unknowns and j i−1 as known coefficients for q j = 0. 4: return q reconstructed at the server.
By observing that there can be at most K nonzero entries in q (l) , ∀l ∈ [L] and at most KL nonzero entries in q, we invoke the Reed-Solomon code construction (Reed & Solomon, 1960) for designing SCMA. Let F p = {0, 1, . . . , p − 1} be a finite field of prime order p ≥ max{n, B d }. We treat the indices of the quantization bins as distinct elements from the underlying finite field, and use them as evaluation points of the encoder polynomial. In addition, we treat a nonzero entry q (l) j in vector q (l) as a substitution error at the j-th entry in a codeword. Then, we use our SCMA scheme shown in Algorithm 4, where the messages that the clients send to server can be treated as syndromes in Reed-Solomon decoding. The discussion about the differences between SCMA and a related problem termed private set union is available in Appendix L. Note that in our scheme, the server does not know q (l) , l ∈ [L] beyond the fact that l∈ [L] q (l) = q, which fits into our privacy criterion. This follows because z

Performance Analysis
We describe next the performance guarantees of Algorithm 2 w.r.t. the objective defined in Equation (2), using the definition of global clusters from Definition 5.1 originally proposed in Dennis et al. (2021). Note that only the global clustering information can be sent to clients by the server, if requested (i.e., global centroids will not be interactively communicated between clients and server). We first consider the case where no quantization is used (see Algorithm 5). The proof is relegated to Appendix F.
Definition 5.1. Suppose that the local clusters at client l are denoted by C , and that the clusters at the server are denoted by j . Note that (P 1 , . . . , P K ) forms a partition of the entire dataset X , and the representative centroid for P k is defined as c s,k in C s returned by Algorithm 2.
Lemma 5.2. Suppose that the entire dataset across clients is denoted by X , and the set of server centroids returned by Algorithm 5 is The result of Lemma 5.2 holds for any distribution of data across clients, and Algorithm 5 may perform even better than for the case of homogeneous assignments. This is best explained through the following example. In the extreme case of data heterogeneity, each client stores a different cluster w.r.t. the global optimal clustering (L = K). Then Algorithm 5 can be viewed as seeding each optimal cluster by a data point uniformly at random chosen from that cluster, through 1-means clustering at each client. This leads to a performance guarantee of E (φ f (X; C s )) = 2φ * c (X), where the approximation factor is independent of K. A more detailed discussion how data heterogeneity can benefit our unlearning method is available in Appendix F. Next, we consider the distortion introduced by quantization. The performance guarantee is given in Theorem 5.3. Note that SCMA does not contribute to the distortion as it always returns the exact sum. Furthermore, following the same reasoning as in Lemma 4.1, one can show that the result of Theorem 5.3 also holds for the remaining dataset X after running the unlearning procedure in Algorithm 3, as shown in Corollary 5.4. Theorem 5.3. Suppose that we performed uniform quantization with step size γ in Algorithm 2. Then we To make the second term in the upper bound a constant w.r.t. n, we can choose γ = Θ(1/ √ n), which is a good choice in practice offering good performance across different datasets.
Corollary 5.4. Denote by X the data set after removal, C s the updated global centroids, and R the number of removals. After unlearning, we have

Complexity Analysis
We derive a cohort of in-depth analysis pertaining to the computational complexity of both types of data removals, SCMA at the client and server side, as well as the communication complexity at the clients. The results are listed as follows.

Removal time complexity.
We consider the removal requests in two federated clustering settings: removing R points from only one client l (cross-silo, single-client removal), and removing all data points from R clients l 1 , . . . , l R (cross-device, multi-client removal). For the case where multiple clients want to unlearn only a part of their data, the approach is similar to that of single-client removal and the corresponding analysis is based on a simple union bound.
For single-client removal, we know from Theorem 4.5 that the expected removal time for client l is O(RK 2 d) for random removal requests and O(RK 3 1 2 d) for adversarial removal requests. Other clients do not require additional computations, because our federated clustering algorithm is one-shot and thus their centroids will not be affected by the removal requests. On the other hand, the expected removal time for the server is upper bounded by O(K 2 LdT ) for both types of removal requests, where T is the maximum number of iterations of Lloyd's algorithm at the server before convergence.
For multi-client removal, no client needs to perform additional computations. Since in this case we always re-run the full K-means++ clustering at the server, the expected removal time complexity at the server equals O((L − R)K 2 T d).
Communication complexity of SCMA at the client end. Since each S Computational complexity of SCMA at the server end. The computational complexity at the server is dominated by the complexity of the Berlekamp-Massey decoding algorithm (Berlekamp, 1968;Massey, 1969), factorizing the polynomial g(x) over operations over F p (Eisinberg & Fedele, 2006). Hence, the total computational complexity at the server side is max{O(K 2 L 2 ), O((KL) 1.5 log p + KL log 2 p)} operations over F p .

Experimental Results
To empirically characterize the trade-off between the efficiency of data removal and performance of our newly proposed federated clustering method, we compare it with baseline methods on both synthetic and real datasets. Due to space limitations, more in-depth experiments and discussions are delegated to Appendix M.
Datasets and baselines. We use one synthetic dataset generated by a Gaussian Mixture Model (Gaussian) and six real datasets (Celltype, Covtype, FEMNIST, Postures, TMI, TCGA) in our experiments. We preprocess the datasets such that the data distribution is non-i.i.d. across different clients. The symbol K in Figure 3 represents the maximum number of (true) clusters among clients, while K represents the number of true clusters in the global dataset. A detailed description of the data statistics and the preprocessing procedure is available in Appendix M. Since there is currently no off-the-shelf algorithm designed for unlearning federated clusters, we adapt DC-Kmeans (DC-KM) from Ginart et al. (2019) to apply to our problem setting, and use complete retraining as the baseline comparison method. To evaluate federated clustering performance on the complete dataset (before data removals), we also include the K-FED algorithm from Dennis et al. (2021) as the baseline method. In all plots, our Algorithm 2 is referred to as MUFC. Note that in FL, clients are usually trained in parallel so that the estimated time complexity equals the sum of the longest processing time of a client and the processing time of the server.
Clustering performance. The clustering performance of all methods on the complete dataset is shown in the first row of Table 1. The loss ratio is defined as φ f (X; C s )/φ * c (X) 1 , which is the metric used to evaluate the quality of the obtained clusters. For the seven datasets, MUFC offered the best performance on TMI and Celltype, datasets for which the numbers of data points in different clusters are highly imbalanced. This can be explained by pointing out an important difference between MUFC and K-FED/DC-KM: the quantized centroids sent by the clients may have non-unit weights, and MUFC is essentially performing weighted K-means++ at the server. In contrast, both K-FED and DC-KM assign equal unit weights to the client's centroids. Note that assigning weights to the client's centroids based on local clusterings not only enables a simple analysis of the scheme but also improves the empirical performance, especially for datasets with highly imbalanced cluster distributions. For all other datasets except Gaussian, MUFC obtained competitive clustering performance compared to K-FED/DC-KM. The main reason why DC-KM outperforms MUFC on Gaussian data is that all clusters are of the same size in this case. Also note that DC-KM runs full K-means++ clustering for each client while MUFC only performs initialization. Although running full K-means++ clustering at the client side can improve the empirical performance on certain datasets, it also greatly increases the computational complexity during training and the retraining probability during unlearning, which is shown in Figure 3. Nevertheless, we also compare the performance of MUFC with K-FED/DC-KM when running full K-means++ clustering on clients for MUFC in Appendix M.
We also investigated the influence of K and γ on the clustering performance. Figure 3(a) shows that MUFC can obtain a lower loss ratio when K < K, indicating that data is non-i.i.d. distributed across clients. Figure 3(b) shows that the choice of γ does not seem to have a strong influence on the clustering performance of Gaussian datasets, due to the fact that we use uniform sampling in Step 6 of Algorithm 2 to generate the server dataset. Meanwhile, Figure 3(c) shows that γ can have a significant influence on the clustering performance of real-world datasets, which agrees with our analysis in Theorem 5.3. The red vertical line in both figures indicates the default choice of γ = 1/ √ n, where n stands for the number of total data points across clients.
Unlearning performance. Since K-FED does not support data removal, has high computational complexity, and its empirical clustering performance is worse than DC-KM (see Table 1), we only compare the unlearning performance of MUFC with that of DC-KM. For simplicity, we consider removing one data point from a uniformly at random chosen client l at each round of unlearning. The second row of Table 1 records the speed-up ratio w.r.t. complete retraining for one round of MUFC unlearning (Algorithm 3) when the removed point does not lie in the centroid set selected at client l. Figure 3(e) shows the accumulated removal time on the TMI dataset for adversarial removals, which are simulated by removing the data points with the highest contribution to the current value of the objective function at each round, while Figure 3(f)-(l) shows the accumulated removal time on different datasets for random removals. The results show that MUFC maintains high unlearning efficiency compared to all other baseline approaches, and offers an average speed-up ratio of 84x when compared to complete retraining for random removals across seven datasets. We also report the change in the loss ratio of MUFC during unlearning in Figure 3(d). The loss ratio remains nearly constant after each removal, indicating that our unlearning approach does not significantly degrade clustering performance. Similar conclusions hold for other tested datasets, as shown in Appendix M.

Conclusion
We described a novel federated clustering approach that achieves good clustering performance, and low computational and communication complexity while meeting the privacy criteria that are commonly used in classical FL literature. Furthermore, we proposed an intuitive and efficient exact unlearning algorithm to accommodate data removal requests within our federated clustering framework. Our empirical studies on seven benchmark datasets established fundamental performance-complexity trade-offs between unlearning and complete retraining.

A K-means++ Initialization
The K-means problem is NP-hard even for K = 2, and when the points lie in a two-dimensional Euclidean space (Mahajan et al., 2012). Heuristic algorithms for solving the problem, including Lloyd's (Lloyd, 1982) and Hartigan's method (Hartigan & Wong, 1979), are not guaranteed to obtain the global optimal solution unless further assumptions are made on the point and cluster structures (Lee et al., 2017). Although obtaining the exact optimal solution for the K-means problem is difficult, there are many methods that can obtain quality approximations for the optimal centroids. For example, a randomized initialization algorithm (K-means++) was introduced in Vassilvitskii & Arthur (2006) and the expected objective value after initialization is a (log K)-approximation to the optimal objective (E(φ) ≤ (8 ln K + 16)φ * ). K-means++ initialization works as follows: initially, the centroid set C is assumed to be empty. Then, a point is sampled uniformly at random from X for the first centroid and added to C. For the following K − 1 rounds, a point x from X is sampled with probability d 2 (x, C)/φ c (X; C) for the new centroid and added to C. Here, d(x, C) denotes the minimum 2 distance between x and the centroids in C chosen so far. After the initialization step, we arrive at K initial centroids in C used for running Lloyd's algorithm.

B Proof of Lemma 4.1
Proof. Assume that the number of data points in X is n, the size of X R is R, and the initial centroid set for X is C. We use induction to prove that C returned by Algorithm 1 is probabilistically equivalent to re-running the K-means++ initialization on X = X \X R .
The base case of induction amounts to investigating the removal process for c 1 , the first point selected by K-means++. There are two possible scenarios: c 1 ∈ X R and c 1 / ∈ X R . In the first case, we will re-run the initialization process over X , which is equivalent to retraining the model. In the second case, since we know c 1 / ∈ X R , the probability of choosing c 1 from X as the first centroid equals the conditional probability 1 n − R = P(choose c 1 from X as the first centroid|c 1 / ∈ X R ) = P(choose c 1 from X as the first centroid).
Next suppose that K > 1, i = (arg min j c j ∈ X R ) − 1. The centroids C i−1 = {c 1 = c 1 , . . . , c i−1 = c i−1 } returned by Algorithm 1 can be viewed probabilistically equivalent to the model obtained from re-running the initialization process over X for the first i − 1 rounds. Then we have where (a) holds based on the definition of i, indicating that the i-th centroid is not in X R . Therefore, the centroid c i = c i returned by Algorithm 1 can be seen as if obtained from rerunning the initialization process over X in the i-th round. Again based on the definition of i, it is clear that for j > i, c j are the centroids chosen by the K-means++ procedure over X . This proves our claim that C returned by Algorithm 1 is probabilistic equivalent to the result obtained by rerunning the K-means++ initialization on X .
Theorem 1.1 of Vassilvitskii & Arthur (2006) then establishes that which completes the proof.

C Proof of Lemma 4.4
Proof. Since outliers can be arbitrarily far from all true cluster points according to Equation (3), during initialization they may be sampled as centroids with very high probability. For simplicity of analysis, we thus assume that outliers are sampled as centroids with probability 1 if they exist in the dataset. Note that for the adversarial removal scenario, we also assume that outliers will request unlearning with probability 1, meaning that we will always need to re-run the K-means++ initialization when outliers exist in the complete dataset before any removals.
For random removals, where the point requested for unlearning, x i , is drawn uniformly at random from X , it is clear that P(x i ∈ C) = K n , since C contains K distinct data points in X . For adversarial removals, we need to analyze the probability of choosing x i as the (k + 1)-th centroid, given that the first k centroids have been determined and x i / ∈ C k = {c 1 , . . . , c k }. For simplicity we first assume that there is no outlier in X . Then we have For the denominator y =xi d 2 (y, C k ) + d 2 (x i , C k ), the following three observations are in place where c y , c * y are the closest centroid in C k and C * to y, respectively. Here, (a) is a consequence of the fact . Since x i is not an outlier for C * i based on our assumption, we have Consequently, For . Thus, (7) can be lower bounded by Combining (8) and (6) we obtain Using this expression in (5) results in which holds for ∀k ∈ [K]. Thus, the probability P(x i ∈ C) can be computed as Here, we assumed that C 0 = ∅.
For the case where outliers are present in the dataset, we have P(x i ∈ C) = P(x i ∈ C|x i is outlier)P(x i is outlier) + P(x i ∈ C|x i is not outlier)P(x i is not outlier) which completes the proof for the adversarial removal scenario.

D Proof of Theorem 4.5
Proof. Assume that X R denotes the removal request set over X . From the union bound we have Random removals: P(∃j : c j ∈ X R ) < O RK n , Therefore, the expected removal time for random removals can be upper bounded by E(Removal time) = E(Removal time|new initialization needed)P(new initialization needed)+ E(Removal time|new initialization not needed)P(new initialization not needed) Following a similar argument, we can also show that the expected removal time for adversarial removals can be upper bounded by O(RK 3 1 2 d). This completes the proof.

E Comparison between Algorithm 1 and Quantized K-means
In Ginart et al. (2019), quantized K-means were proposed to solve a similar problem of machine unlearning in the centralized setting. However, that approach substantially differs from Algorithm 1. First, the intuition behind quantized K-means is that the centroids are computed by taking an average, and the effect of a small number of points is negligible when there are enough terms left in the clusters after removal. Therefore, if we quantize all centroids after each Lloyd's iteration, the quantized centroids will not change with high probability when we remove a small number of points from the dataset. Meanwhile, the intuition behind Algorithm 1 is as described in Lemma 4.4. Second, the expected removal time complexity for quantized K-means equals O R 2 K 3 T 2 d 2.5 / , which is high since one needs to check if all quantized centroids remain unchanged after removal at each iteration, where T denotes the maximum number of Lloyd's iteration before convergence and is some intrinsic parameter. In contrast, Algorithm 1 only needs O(RK 3 1 2 d) even for adversarial removals. Also note that the described quantized K-means algorithm does not come with performance guarantees on removal time complexity unless it is randomly initialized.

F Proof of Lemma 5.2
Proof. Let C * denote the optimal set of centroids that minimize the objective (1) for the entire dataset X ∈ R n×d , let C * ∈ R n×d be the matrix that records the closest centroid in C * to each data point, C s the set of centroids returned by Algorithm 2, and C s ∈ R n×d the matrix that records the corresponding centroid in C s for each data point based on the global clustering defined in Definition 5.1. Since we perform K-means++ initialization on each client dataset, for client l it holds where C (l) ∈ R n (l) ×d records the closest centroid in C (l) to each data point x i in X (l) , C (l) * is the optimal solution that can minimize the local K-means objective for client l, and C * ,(l) denotes the row in C * that corresponds to client l. Summing up (11) over all clients gives At the server side the client centroids are reorganized into a matrix X s ∈ R n×d . The weights of the client centroids are converted to replicates of rows in X s . Since we perform full K-means++ clustering at the server, it follows that where C s, * ∈ R n×d is the optimal solution that minimizes the K-means objective at the server. It is worth pointing out that C s, * is different from C * , as they are optimal solutions for different optimization objectives. Note that we still keep the expectation on RHS for (a). The randomness comes from the fact that C (l) is obtained by K-means++ initialization, which is a probabilistic procedure.
Combining (12) and (13) results in For Replacing (15) into (14) shows that E (φ f (X; C s )) < O(log 2 K) · φ * c (X), which completes the proof. If we are only concerned with the performance of non-outlier points over the entire dataset, we can upper bound the term E Here, we used the fact that rows of C (l) are all real data points sampled by the K-means++ initialization procedure. For each data point where X t corresponds to all non-outlier points. Remark. In Theorem 4 of Guha et al. (2003) the authors show that for the distributed K-median problem, if we use a O(b)-approximation algorithm (i.e., φ ≤ O(b) · φ * ) for the K-median problem with subdatasets on distributed machines, and use a O(c)-approximation algorithm for the K-median problem on the centralized machine, the overall distributed algorithm achieves effectively a O(bc)-approximation of the optimal solution to the centralized K-median problem. This is consistent with our observation that Algorithm 5 can offer in expectation a O(log 2 K)-approximation to the optimal solution of the centralized K-means problem, since K-means++ initialization achieves a O(log K)-approximation on both the client and server side.
We also point out that in Dennis et al. (2021) the authors assume that the exact number of clusters from the global optimal clustering on client l is known and equal to K (l) , and propose the K-FED algorithm which performs well when K = max l∈[L] K (l) ≤ √ K. The difference between K and K represents the data heterogeneity across different clients. With a slight modifications of the proof, we can also obtain is known for each client beforehand, and perform K (l) -means++ on client l instead of K-means++ in Algorithm 2. For the extreme setting where each client safeguards data of one entire cluster (w.r.t. the global optimal clustering (L = K, K = 1)), the performance guarantee for Algorithm 2 becomes E (φ f (X; C s )) < O(1) · φ * c (X), which is the same as seeding each optimal cluster by a data point sampled uniformly at random from that cluster. From Lemma 3.1 of Vassilvitskii & Arthur (2006) we see that we can indeed have E (φ f (X; C s )) = 2φ * c (X), where the approximation factor does not depend on K. This shows that data heterogeneity across different clients can benefit the entire federated clustering framework introduced.

G Proof of Theorem 5.3
Proof. Following the same idea as the one used in the proof of Lemma 5.2, we arrive at where C (l) is the quantized version of C (l) . The first term can be upper bounded in the same way as in Lemma 5.2. For the second term, the distortion introduced by quantizing one point is bounded by √ dγ 2 , if we choose the center of the quantization bin as the reconstruction point. Therefore, The third term can be bounded as Replacing (18) and (19) into (17) leads to which completes the proof.
Similar as in Lemma 5.2, we can have that for non-outlier points

H Quantization
For uniform quantization, we setŷ = γ · a(y), where a(y) = arg min j∈Z |y − γj|, y ∈ R 2 . The parameter γ > 0 determines the number of quantization bins in each dimension. Suppose all client data lie in the unit hypercube centered at the origin, and that if needed, pre-processing is performed to meet this requirement. Then the number of quantization bins in each dimension equals B = γ −1 , while the total number of quantization bins for d dimensions is B d = γ −d .

I Simplified Federated K-means Clustering
When privacy criteria like the one stated in Section 3 are not enforced, and as done in the framework of Dennis et al. (2021), one can skip Steps 3-6 in Algorithm 2 and send the centroid set C (l) obtained by client l along with the cluster sizes (|C (l) 1 |, . . . , |C (l) αK |) directly to the server. Then, one can run the weighted K-means++ algorithm at the server on the aggregated centroid set to obtain C s . The pseudocode for this simplified case is shown in Algorithm 5. It follows a similar idea as the divide-and-conquer schemes of (Guha et al., 2003;Ailon et al., 2009), developed for distributed clustering.

In
Step 5 of Algorithm 5, weighted K-means++ would assign weights to data points when computing the sampling probability during the initialization procedure and when computing the average of clusters during the Lloyd's iterations. Since the weights we are considering here are always positive integers, a weighted data point can also be viewed as there exist identical data points in the dataset with multiplicity equals to the weight.

J The Uniqueness of the Vector q given {S i } i∈[2KL]
To demonstrate that the messages generated by Algorithm 4 can be uniquely decoded, we prove that there exists a unique q that produces the aggregated values {S i } i∈ [2KL] at the server. The proof is by contradiction. Assume that there exist two different vectors q and q that result in the same {S i } i∈ [2KL] . In this case, we have the following set of linear equations j:qj =0 q j · j i−1 − j:q j =0 q j · j i−1 = 0, i ∈ [2KL]. Given that Algorithm 5 Simplified Federated K-means Clustering 1: input: Dataset X distributed on L clients (X (1) , . . . , X (L) ), client oversampling coefficient α. 2: Run (αK)-means++ initialization on each client l in parallel, obtain the initial centroid sets C (l) , and record the corresponding cluster sizes |C αK | as the weights for the corresponding rows, ∀l ∈ [L]. 5: Run full weighted K-means++ clustering at server with X s to obtain the centroid set at server C s . 6: return Each client retains their own centroid set C (l) while the server retains X s and C s .
{q j : q j = 0} and {q j : q j = 0} represent at most 2KL unknowns and j i−1 coefficients, the linear equations can be described using a square Vandermonde matrix for the coefficients, with the columns of the generated by the indices of the nonzero entries in q. This leads to a contradiction since a square Vandermonde matrix with different column generators is invertible, which we show below. Hence, the aggregated values {S i } must be different for different q. Similarly, the sums j: If two vectors q and q result in the same ) be the set of integers such that at least one of q im and q im is nonzero for m ∈ [u]. Note that u ≤ 2KL. Rewrite this equation as Since u ≤ 2KL, we take the first u equations in (20) and rewrite them as is a nonzero vector since q = q . It is known that the determinant of a square Vandermonde matrix B is given by m1<m2,m1,m2∈[u] (i m2 − i m1 ), which in our case is nonzero since all the i 1 , . . . , i u are different. Therefore, B is invertible and does not admit a non-zero solution, which contradicts the equation Bv = 0.

K A Deterministic Low-Complexity Decoding Algorithm for SCMA at the Server
In the SCMA scheme we described in Algorithm 2, the goal of the server is to reconstruct the vector q, given values S i = j:qj =0 q j · j i−1 mod p for i ∈ [2KL]. To this end, we first use the Berlekamp-Massey algorithm to compute the polynomial g(x) = j:qj =0 (1 − j · x). Then, we factorize g(x) over the finite field F p using the algorithm described in Kedlaya & Umans (2011). The complexity O((KL) 1.5 log p + KL log 2 p) referred to in Section 5.3 corresponds to the average complexity (finding a deterministic algorithm that factorizes a polynomial over finite fields with poly(log p) worst-case complexity is an open problem). The complexity max{O(K 2 L 2 ), O((KL) 1.5 log p + KL log 2 p)} referred to in Appendix 5.3 for the SCMA scheme represents an average complexity.
We show next that the SCMA scheme has small worst-case complexity under a deterministic decoding algorithm at the server as well. To this end, we replace the integer p in Algorithm 4 with a large number p ≥ max{KLB 2dKL , n} + 1 such that p is larger than the largest possible S i and there is no overflow when applying the modulo p operation on S i . It is known (Bertrand's postulate) that there exists a prime number between any integer n > 3 and 2n − 2, and hence there must be a prime number lowerbounded by max{KLB 2dKL , n} + 1 and twice the lower bound 2(max{KLB 2dKL , n} + 1). However, since searching for a prime number of this size can be computationally intractable, we remove the requirement that p is prime. Correspondingly, F p is not necessarily a finite field. Then, instead of sending S i are independently and uniformly distributed over {0, . . . , p − 1} and hidden from the server. After obtaining S i , i ∈ [2KL], the server can continue performing operations over the field of reals since there is no overflow in computing S i mod p . We note that though p is exponentially large, the computation of S

L Comparison among SCMA, Private Set Union and Sparse Secure Model Aggregation
Our SCMA scheme is different from a related problem of private set union (Kissner & Song, 2005;Frikken, 2007;Seo et al., 2012), in which multiple parties communicate with each other to securely compute the union of their sets. In SCMA we aggregate multisets, which include the frequency of each element that is not revealed in the private set union problem. In addition, our scheme includes only one round of communication from clients to the server, while there is no server in the private set union problem and multi-round client to client communication is needed. Note that SCMA may also be adapted to solve problems related with sparse secure model aggregation (Beguier et al., 2020;Ergun et al., 2021), which is another interesting but orthogonal research direction to this work.

M.1 Datasets
In what follows, we describe the datasets used in our numerical experiments. Note that we preprocessed all datasets such that the absolute value of each element in the data matrix is smaller than 1. Each dataset has an intrinsic parameter K for the number of optimal clusters, and these are used in the centralized K-means++ algorithm to compute the approximation of the optimal objective value. We use φ * c (X) in subsequent derivation to denote the objective value returned by the K-means++ algorithm. Besides K, we set an additional parameter K ∼ √ K for each client data so that the number of true clusters at the client level is not larger than K . This non-i.i.d. data distribution across clients is discussed in Dennis et al. (2021). For small datasets (e.g., TCGA, TMI), we consider the number of clients L as 10, and set L = 100 for all other datasets.
Celltype [n = 12009, d = 10, K = 4] (Han et al., 2018;Gardner et al., 2014b) comprises single cell RNA sequences belonging to a mixture of four cell types: fibroblasts, microglial cells, endothelial cells and mesenchymal stem cells. The data, retrieved from the Mouse Cell Atlas, consists of 12009 data points and each sample has 10 feature dimensions, reduced from an original dimension of 23, 433 using Principal Component Analysis (PCA). The sizes of the four clusters 3 are 6506, 2328, 2201, 974.
Postures [n = 74975, d = 15, K = 5] (Gardner et al., 2014b;a) comprises images obtained via a motion capture system and a glove for 12 different users performing five hand postures -fist, pointing with one finger, pointing with two fingers, stop (hand flat), and grab (fingers curled). For establishing a rotation and translation invariant local coordinate system, a rigid unlabeled pattern on the back of the glove was utilized. There are a total of 74975 samples in the dataset and the data dimension is 15. The sizes of the given clusters are 19772, 17340, 15141, 12225, 10497. Covtype [n = 15120, d = 52, K = 7] (Blackard & Dean, 1999) comprises digital spatial data for seven forest cover types obtained from the US Forest Service (USFS) and the US Geological Survey (USGS). There are 52 cartographic variables including slope, elevation, and aspect. The dataset has 15120 samples. The sizes of the seven clusters are 3742, 3105, 2873, 2307, 1482, 886, 725. Gaussian [n = 30000, d = 10, K = 10] comprises ten clusters, each generated from a 10-variate Gaussian distribution centered at uniformly at random chosen locations in the unit hypercube. From each cluster, 3000 samples are taken, for a total of 30000 samples. Each Gaussian cluster is spherical with variance 0.5.
FEMNIST [n = 36725, d = 784, K = 62] (Caldas et al., 2018) is a popular FL benchmark dataset comprising images of digits (0-9) and letters from the English alphabet (both upper and lower cases) from over 3500 users. It dataset is essentially built from the Extended MNIST repository (Cohen et al., 2017) by partitioning it on the basis of the writer of the digit/character. We extract data corresponding to 100 different clients, each of which contributed at least 350 data points. Each image has dimension 784. The size of the largest cluster is 1234, and that of the smallest cluster is 282.
TMI [n = 1126, d = 984, K = 4] contains samples from human gut microbiomes. We retrieved 1126 human gut microbiome samples from the NIH Human Gut Microbiome (Peterson et al., 2009). Each data point is of dimension 983, capturing the frequency (concentration) of identified bacterial species or genera in the sample. The dataset can be roughly divided into four classes based on gender and age. The sizes of the four clusters are 934, 125, 46, 21.

M.2 Baseline Setups
We use the publicly available implementation of K-FED and DC-KM as our baseline methods. For DC-KM, we set the height of the computation tree to 2, and observe that the leaves represent the clients. Since K-FED does not originally support data removal, has high computational complexity, and its clustering performance is not comparable with that of DC-KM (see Table 1), we thus only compare the unlearning performance of MUFC with DC-KM. During training, the clustering parameter K is set to be the same in both clients and server for all methods, no matter how the data was distributed across the clients. Experiments on all datasets except FEMNIST were repeated 5 times to obtain the mean and standard deviations, and experiments on FEMNIST were repeated 3 times due to the high complexity of training. Note that we used the same number of repeated experiments as in Ginart et al. (2019).

M.3 Enabling Complete Client Training for MUFC
Note that both K-FED and DC-KM allow clients to perform full K-means++ clustering to improve the clustering performance at the server. Thus it is reasonable to enable complete client training for MUFC as well to compare the clustering performance on the full datasets. Although in this case we need to retrain affected clients and the server for MUFC upon each removal request, leading to a similar unlearning complexity as DC-KM, the clustering performance of MUFC is consistently better than that of the other two baseline approaches (see Table 2). This is due to the fact that we utilize information about the aggregated weights of client centroids. Loss ratio MUFC 1.05 ± 0.01 1.03 ± 0.00 1.02 ± 0.00 1.02 ± 0.01 1.02 ± 0.00 1.12 ± 0.00 1.02 ± 0.00 K-FED 1.84 ± 0.07 1.72 ± 0.24 1.25 ± 0.01 1.56 ± 0.11 1.13 ± 0.01 1.21 ± 0.00 1.60 ± 0.01 DC-KM 1.54 ± 0.13 1.46 ± 0.01 1.02 ± 0.00 1.15 ± 0.02 1.03 ± 0.00 1.18 ± 0.00 1.03 ± 0.02

M.4 Loss Ratio and Unlearning Efficiency
In Figure 4 we plot results pertaining to the change of loss ratio after each removal request and the accumulated removal time when the removal requests are adversarial. The conclusion is consistent with the results in Section 6.