Abstract: Clustering is a cornerstone of data analysis that is particularly suited to identifying coherent subgroups or substructures in unlabeled data, as are generated continuously in large amounts these days. However, in many cases traditional clustering methods are not applicable, because data are increasingly being produced and stored in a distributed way, e.g. on edge devices, and privacy concerns prevent it from being transferred to a central server. To address this challenge, we present FedDP-KMeans, a new algorithm for $k$-means clustering that is fully-federated as well as differentially private. Our approach leverages (potentially small and out-of-distribution) server-side data to overcome the primary challenge of differentially private clustering methods: the need for a good initialization. Combining our initialization with a simple federated DP-Lloyds algorithm we obtain an algorithm that achieves excellent results on synthetic and real-world benchmark tasks. We also provide a theoretical analysis of our method that provides bounds on the convergence speed and cluster identification success.

Lay Summary:

Clustering is a technique used to group similar items in large, unlabeled datasets. Traditional clustering methods assume that all the data is stored in one central location. However, in today's world, data is often generated and stored across many separate devices, like smartphones, and privacy concerns often prevent this data from being shared.To address this challenge, we introduce a new method that allows devices to collaborate on clustering without sharing their raw data. This approach protects user privacy using a technique called differential privacy, which ensures that nothing specific about any individual device can be inferred from the final clustering results. A key part of our method is using a small amount of publicly available or server-side data to help kick-start the clustering process, which is then refined collaboratively.We support our method with both a theoretical analysis of its performance and an experimental evaluation that demonstrates its practical usefulness.