Differentially Private Federated $k$-Means Clustering with Server-Side Data

Thank you for your review and helpful comments. We have run additional experiments which can be found here https://anonymous.4open.science/r/FedDP-KMeans-Rebuttal-Figures-5B34/Rebuttal_Figures.pdf. We will reference this pdf when we address your specific concerns below.

lack of experiments for evaluating the clustering effect using external clustering evaluation indices

We have run experiments evaluating with the suggested Fowlkes-Mallows and Adjusted Rand Indices, see FIgures 6-9 of the additional experiments. The results are in line with those reported with k-means cost.

We would like to add that we believe that the metric we report, k-means cost, is fair and informative. All algorithms we compare are variants of k-means, so they all have the goal of minimizing the k-means objective.

Ablation experiments are also lacking, as well as some parameter analysis experiments, such as the number of clients (m), privacy parameters (\varepsilon)

Thank you for the suggestion, we have run additional ablation experiments testing how our method performs when the server data is missing some of the clusters. See Section 1 of the additional experiments. The performance of all methods that use server data deteriorates modestly as the number of missing clusters grows. In all settings FedDP-KMeans is still the best performing method.

Regarding number of clients, our current experiments do already cover a wide range of values of m. We have experiments with $m \in\lbrace 51,100,1000,2000,2720,5000,9237,10394,23266\rbrace$. Moreover, for the Gaussian mixture data we do in fact keep the distribution the same and vary $m \in\lbrace 1000, 2000, 5000\rbrace$ and discuss how the results change (Results paragraph on page 7). We hope this addresses your concerns.

Regarding analysis of the privacy parameters we provide a detailed analysis of these in Appendix G.4 and our main experiments (e.g. Figures 1 and 2) analyze the changes in performance as privacy parameters vary. Do these points answer your specific concern?

highly related works have not been cited/discussed:

Thank you for the references. It seems that [1], [3] and [4] are solving a related task of Clustered FL, where the goal is to cluster clients for better model training. [2] do propose a method for k-means clustering of the data, though their focus is on asynchronous and heterogeneous clients rather than privacy. We would be happy to include a discussion of these additional works in our Related Works section.

lacks a summary of the contributions.

We will include a clearer summary of the main contributions of our work:

• We propose a novel differentially private and federated initialization method that leverages small, out-of-distribution server-side data to generate high-quality initializations for federated $k$-means.
• We introduce the first fully federated and differentially private $k$-means algorithm by combining this initialization with a simple DP federated Lloyd’s variant.
• We provide theoretical guarantees showing exponential convergence to ground truth clusters under standard assumptions.
• We conduct extensive empirical evaluations, demonstrating strong performance across data-point and user-level privacy settings on both synthetic and real federated data.

About the level details in the introduction:

We aimed to make the work accessible to readers, who are not experts on privacy and FL, as these aspects are what make the problem of clustering much harder and unsolved. We’ll be happy to expand the discussion on initialization as well.

how do the authors solve the problem of the unknown number of clusters (k)

Thank you for the question. In practice, k-means is often used with a value of k determined by external factors, such as computational or memory demands [Jain, 2010]. If k is meant to be chosen based on the data itself, existing methods can be incorporated into our setting quite simply, by using the method on the weighted and projected server dataset, $\Pi Q$ with weights $\hat{w_q(\Pi P)}$. This dataset serves as a proxy for the client data and we can operate on it without incurring any additional privacy costs. We illustrate this using the popular elbow method [Thorndike, 1953]. Concretely, we run lines 1-16 of Algorithm 1 using some large value $k’$, then we run line 17 for $k=1, 2, 3, \dots$ and plot the $k$-means costs of the resulting clusterings. This is shown in Figure 10 of the additional experiments. Clearly, the elbow of the curve occurs at $k=10$ which is indeed the number of clusters in the true data distribution (we used the same Gaussian mixture dataset as in the original experiments).

the problem that k-means performs poorly on non-convex datasets?

Respectfully, we feel that this is not really a fair criticism of our method. Our contribution is a method for making k-means differentially private in a federated setting. It is not about trying to overcome principled shortcomings of the k-means objective.

Thank you for your time and your review. We address your questions and comments below.

Could you confirm that the privacy is not proven if the input is not from a Gaussian mixture?

This appears to be a misunderstanding that we find important to correct. Our algorithms (1 and 2) are always private, not just when the input comes from a Gaussian mixture. This is stated in Section 3.1 but we’ll add an explicit theorem to make this clearer.

Technically, the $(\varepsilon, \delta)$-DP guarantee comes from the appropriately scaled noise that is added to the client statistics (e.g. lines 6, 15, 23 of Algorithm 1). Nowhere in the analysis of how noise is added to enforce privacy (section 3.1) do we require that the inputs come from a Gaussian mixture. Indeed our experiments are always run with $(\varepsilon, \delta)$ differential privacy, not just in the Gaussian mixture setting. The Gaussian mixture assumption is only required to theoretically prove accuracy and convergence. We also point out that, to define “accuracy” and “convergence”, assumptions such as the Gaussian mixture model are required.

The theoretical guarantees of the proposed approach fall short when some clusters are not represented in the server data at all even when they make up the majority of the client data, though. The experiments cover cases with unrelated noise, but do not explicitly cover the case that some regions of the input are not covered by the server data at all.

For our theoretical guarantees you are of course correct. It is, however, not a requirement for the algorithm to work in practice. To test this we have now run additional experiments in exactly this setting that certain clusters are missing from the server dataset, the results can be found in Section 1 here: https://anonymous.4open.science/r/FedDP-KMeans-Rebuttal-Figures-5B34/Rebuttal_Figures.pdf. As seen in Figure 1, performance of FedDP-KMeans deteriorates modestly as the number of clusters missing from the server dataset increases. Figures 2-5 show that this also occurs in the other baselines that make use of the server data and that FedDP-KMeans is still the best performing method in this scenario. Thank you for the suggestion to consider this scenario in our experimental evaluation.

Thank you for your time and for your review. We discuss your feedback below.

One potential drawback is in the requirement that the server have a representative datapoint for each cluster on hand. This assumption may be too strong, since often the purpose of running k-means clustering is to identify clusters.

We would like to clarify one point: the server holds data points, but does not have any a priori information on the clustering on those points. In addition, the requirement that there is at least one point per cluster is only required for the theoretical contributions (where we want to identify ground truth GMM components). In practice, the algorithm performs well even without this assumption, see our answer below.

What would happen if the server simply took in each user's projected, noisy points and attempted to form seeds based on this?

The issue with this is that directly sharing the projected user data points themselves with the server, while still having meaningful DP guarantees, would require so much noise as to destroy any signal in the points themselves. To give a concrete illustration, for the Gaussian mixtures data in the easier data-point level privacy setting with $\varepsilon = 2$, we would be forced to add iid 0 mean Gaussian noise with standard deviation $\approx35$ to each dimension of each projected user point before sending it to the server. So the expected norm of the noise vector to be added to each point is at least $35 \sqrt{10} \approx 105$. For reference the norms of the projected data points are mostly in the range (5, 7).

Can the assumption that Q need to contain a point from each cluster beforehand be relaxed at all?

The requirement that the server holds a point from each cluster is only needed to prove our theoretical guarantees on clustering accuracy and convergence in the Gaussian mixtures setting. It is not strictly required for the algorithm to run or work in practice. We have now run additional experiments to test the method’s performance in the scenario where some clusters are completely missing in the server data, Q. The results can be found in Section 1 here: https://anonymous.4open.science/r/FedDP-KMeans-Rebuttal-Figures-5B34/Rebuttal_Figures.pdf. As seen in Figure 1, the performance of FedDP-KMeans deteriorates modestly as the number of clusters missing from the server dataset increases. Figures 2-5 show that this also occurs in the other baselines that make use of the server data and that FedDP-KMeans is still the best performing method in this scenario.

Thank you for your time and for your review. We discuss your comments below.

I would say the writing of this paper needs to be improved. Generally, I cannot grab a clear structure of Background-Motivation-Method-Contribution from the intrroduction. (‘background’ here doesn’t refers to the Section2, and I think the Section2 is more likely a Preliminary.)

Thank you for the feedback. We can rename Section 2 as Preliminary and rewrite the introduction so that the motivation is clearer. We will also include a more explicit summary of our contributions as follows:

• We propose a novel differentially private and federated initialization method that leverages small, out-of-distribution server-side data to generate high-quality initializations for federated k-means.
• We introduce the first fully federated and differentially private k-means algorithm by combining this initialization with a simple DP federated Lloyd’s variant.
• We provide theoretical guarantees showing exponential convergence to ground truth clusters under standard assumptions.
• We conduct extensive empirical evaluations, demonstrating strong performance across data-point and user-level privacy settings on both synthetic and real federated data.

I’m curious that is there any other clustering method that is less sensitive to the initialization? And will your plugin improve those initialization-less-sensitive clustering method more marginally than Kmeans?

Of course. For example, there’s methods that do not need any initialization, such as single-linkage clustering (Gower,, Ross 1969), or that converge to the same solution, regardless of the initialization, such as convex clustering (Pelckmans et al 2005). But k-means is used much more in practice, because it has better properties.