Secure Federated Clustering

Federated learning (FL) is an increasingly popular distributed learning paradigm, which enables decentralized clients to collaborate on training an AI model over their private data collectively, without surrendering the private data to a central cloud. When running the FedAvg algorithm introduced in [1], each client trains a local model with its private data, and sends the local model to a central server for further aggregation into a global model. Since its introduction, FL has demonstrated great potential in improving the performance and security of a wide range of learning problems, including next-word prediction [2], recommender systems [3], and predictive models for healthcare [4].

In this work, we focus on a foundational unsupervised learning task - clustering. In an FL system, the clustering problem can be categorized into client clustering and data clustering. Motivated by heterogeneous data distribution across clients and the needs for training personalized models [5, 6, 7], client clustering algorithms are developed to partition the clients into different clusters to participate in training of different models [8, 9, 10, 11]. On the other hand, data clustering problem aims to obtain a partition of data points distributed on FL clients, such that some clustering loss is minimized. In [12], a model-based approach UIFCA was proposed to train a generative model for each cluster, such that each data point can be classified into one of the clusters using the models. Another recent work [13] considers the classical $k$-means clustering problem, and proposed an algorithm $k$-FED to approximately execute the Lloyd’s heuristic [14] in the FL setting. $k$-FED is communication-efficient as it only requires one-shot communication from the clients to the server.

While being the state-of-the-art federated data clustering algorithms, both UIFCA and $k$-FED are observed to be limited in the following two aspects: 1) The clustering performance heavily depends on the data distribution across clients. Specifically, the clustering performance of $k$-FED is guaranteed only when the data points on each client are from at most $k^{\prime}\leq\sqrt{k}$ clusters, and a non-empty cluster at each client has to contain a minimum number of points; 2) Leakage of data privacy. Just like other model-based FL algorithms, the data privacy of UIFCA is subject to model inversion attacks (see, e.g., [15, 16, 17, 18]). In $k$-FED, each client performs Lloyd’s algorithm on local data, and sends the local cluster centers that are averages of private data points directly to the server, which allows a curious server to infer about the private dataset (e.g., number of local clusters, and the distribution of local data points).

Motivated by these limitations, we develop a secure federated clustering protocol named SecFC, for solving a $k$-means clustering problem over an FL network. SecFC builds upon the classical Lloyd’s heuristic and has the following salient properties:

• •

  Universal performance: The clustering performance of SecFC matches exactly that of running Lloyd on the collection of all clients’ data in a centralized manner, which is invariant to different data distributions at the clients;

• •

  Information-theoretical data privacy: Each client’s private data is information-theoretically private from a certain number of colluding clients. The server does not know the values of the private data points and the cluster centers.

In the first phase of SecFC, each client locally generates some random noises and mixes them with its private data using Lagrange polynomial encoding [19], and then securely shares the coded data segments with the other clients. In the second phase, the clients and the server jointly execute the Lloyd’s iterations over coded data. As each client obtains a coded version of the entire dataset in the first phase, leveraging the algebraic structure of the coding scheme, each client can compute a secret share of the distance between each pair of cluster center and data point. After receiving sufficient number of secret shares, the server is able to reveal the pair-wise distances between all cluster centers and all data points, so the center update can be carried out exactly as specified in the Lloyd’s algorithm. Importantly, the server can only recover the distance between a cluster center and a data point, without knowing their respective locations, which is the key enabler for SecFC to achieve performance and privacy simultaneously. We further extend SecFC to strengthen it with membership privacy. Specifically, clients privately align the IDs of their local data using private set union [20, 21, 22], such that data clustering is performed without revealing which data point belongs to which client.

We conduct extensive experiments to cluster synthetic and real datasets on FL systems, and compare SecFC with the centralized Lloyd’s algorithm and $k$-FED as our baselines. Under different data distributions across clients with different number of local clusters $k^{\prime}$, SecFC consistently achieves almost identical performance as the centralized Lloyd, which outperforms $k$-FED. Also, unlike $k$-FED whose performance varies substantially with the value of $k^{\prime}$, and deteriorates severely when $k^{\prime}=k$, the performance of SecFC is almost invariant to the value of $k^{\prime}$, indicating its universal superiority. We also evaluate the execution overheads of SecFC under various combinations of system parameters, which demonstrate the feasibility of applying SecFC to solve practical clustering tasks.

Clustering is an extensively studied learning task. We discuss existing works in three categories.

• •

  Centralized clustering. In centralized clustering, a central entity, i.e., server, performs the data partition. A well-known centralized clustering problem is $k$-means clustering, where the aim is to find $k$ centers such that the Euclidean distance from each data point to its closest center is minimized. Lloyd’s heuristic [14] is a popular iterative approach in performing $k$-means clustering due to its simplicity, even though its performance heavily depends on algorithm initialization. Unlike the Lloyd’s heuristic which does not provide any provable guarantees, Kanungo et al. [23] proposes an approximation algorithm for $k$-means clustering that is based on swapping cluster centers in and out, which yields a solution that is at most $(9+\epsilon)$ factor larger than the optimal solution. Awasthi and Sheffet [24] propose a variant of the Lloyd’s heuristic that is equipped with such an approximation algorithm to guarantee convergence in polynomial time.

• •

  Parallel and distributed clustering. Distributed and parallel clustering implementations are particularly useful in the presence of large datasets that are prominent in many learning applications. The bottleneck in the centralized $k$-means clustering is the computation of distances among the data points and the centers. In parallel implementations of $k$-means clustering, the idea is to split the dataset into different worker machines so that the distance computations are performed in parallel [25, 26]. In addition to $k$-means clustering, there have been parallel implementations of other clustering schemes such as the density-based clustering scheme DBSCAN [27]. When the dataset is distributed in nature, it may not be practical to send local datasets to the central entity. In such cases, distributed clustering is favorable albeit a performance loss compared to the centralized setting [28, 29, 30].

• •

  Federated clustering. Clustering techniques have been used in FL systems to handle data heterogeneity [31, 9, 32, 13, 33], particularly focusing on personalized model training and client selection. References [31, 32, 9] focus on clustering the clients to jointly train multiple models, one for each cluster, whereas reference [13] clusters the client data points to reach more personalized models and perform a more representative client selection at each iteration. Unlike the $k$-means clustering which uses a heuristic to generate clusters, model-based clustering assumes that the data to be clustered comes from a probabilistic model and aims to recover that underlying distribution [34, 35]. In their recent work [12], using this approach, Chung et al. cluster heterogeneous client data in a federated setting by associating each data point with a cluster (model) with the highest likelihood. As also highlighted by [33], common to all these existing works on $k$-means clustering is the fact that none of them provides data privacy, in the sense that cluster center information as well as clients’ data are kept private. This motivates us to develop SecFC in this work, which is to the best of our knowledge, the first federated clustering algorithm with formal privacy guarantees.

Before we close this section, we briefly review some prior works on secure clustering.

Privacy-preserving clustering. When the clustering is performed on private client data as in the case of federated clustering, the issue of secure clustering emerges. The aim here is to cluster the entire dataset without revealing anything to the clients, including all intermediate values, but the output, i.e., final partition of data. Privacy-preserving clustering has been studied in the literature employing cryptographic techniques from secure multiparty computation, for the cases of horizontal, vertical, and arbitrary partitions of data [36, 37, 38, 39, 40, 41]. Among these works, we want to highlight [41], where authors implement a secret sharing-based secure $k$-means clustering scheme. Unlike the proposed SecFC scheme, however, [41] employs an additive secret sharing scheme and reveals the final cluster centers to the participants. In SecFC, clients use Lagrange coding to encode and share their private data. During the execution of SecFC, neither final nor any intermediate candidate center information is disclosed to the clients or the server, which is not the case in other earlier works [36, 37, 39] in the literature as well.

Notation. For a positive integer $n$, let $[n]$ denote the set of integers $\{1,\ldots,n\}$. Let $|{\cal S}|$ denote the cardinality of a set ${\cal S}$.

As SecFC leverages cryptographic primitives to protect data privacy, which operates on finite fields, we assume that the elements of each data point are from a finite field $\mathbb{F}_{q}$ of order $q$. In practice, one can quantize each element of the data points onto $\mathbb{F}_{q}$, for some sufficiently large prime $q$, such that overflow does not occur to any computation during the execution of the Lloyd’s algorithm. See Appendix A for one such quantization method.

In this section, we empirically evaluate the performance and complexity of the proposed SecFC protocol, for federated clustering of synthetic and real datasets. We compare SecFC with centralized implementation of Lloyd’s heuristic and the $k$-FED protocol as baselines. All experiments are carried out on a machine using Intel(R) Xeon(R) Gold 5118 CPU @ 2.30GHz, with 12 cores of 48 threads.

The center separation technique [24] is applied to all three algorithms, for clustering initialization to improve the performance. It is a one-time method to generate $k$ groups of data ${\cal S}^{\prime}_{1},\ldots,{\cal S}^{\prime}_{k}$ from a given clustering assignment. Given the current cluster centers $\boldsymbol{\mu}_{1},\ldots,\boldsymbol{\mu}_{k}$, each $S^{\prime}_{h}$ is selected such that $S^{\prime}_{h}\leftarrow\left\{i:\left\|{\bf x}_{i}-\boldsymbol{\mu}_{h}\right\|_{2}\leqslant\frac{1}{3}\left\|{\bf x}_{i}-\boldsymbol{\mu}_{s}\right\|_{2},\forall s\in[k]\right\}$. In this way, the data in ${\cal S}^{\prime}_{h}$ is close to center $\boldsymbol{\mu}_{h}$ and far from all other centers. Then, the means of ${\cal S}^{\prime}_{1},\ldots,{\cal S}^{\prime}_{k}$ are used as the initial centers for the subsequent iterative execution of the algorithms.

We cluster data points with ground truth labels, and use classification accuracy as the performance measure. For each $i\in[m]$, let $y_{i}$ and $y^{\prime}_{i}$ respectively denote the ground truth label of data point ${\bf x}_{i}$, and the index of the cluster it belongs to after the clustering process, such that $y_{i},y^{\prime}_{i}\in[k]$. As the clustering operation does not directly predict ${\bf x}_{i}$’s label, the classification of ${\bf x}_{i}$ is subject to a potential permutation $\pi$ of the label set $[k]$. We use the Hungarian method [47] to find the optimal permutation $\pi_{0}$ that maximizes $\sum_{i\in[m]}\mathbbm{1}\left(y_{i}=\pi(y^{\prime}_{i})\right)$, where $\mathbbm{1}(\cdot)$ is the indicator function. Then, the accuracy of a $k$-means clustering algorithm is given by $\frac{1}{m}\sum_{i\in[m]}\mathbbm{1}\left(y_{i}=\pi_{0}(y^{\prime}_{i})\right)$.

One shortcoming of SecFC is that distribution of the global dataset, i.e., $({\cal I}_{1},\ldots,{\cal I}_{n})$, where ${\cal I}_{j}$ denotes the set of indices of the local data points at client $j$, will become publicly known during data sharing. It would be desirable for client $j$ to also keep ${\cal I}_{j}$ private, so that from the final clustering result $({\cal S}_{1},\ldots,{\cal S}_{k})$, no client or the server can infer which data point belongs to which client.

Private ID alignment. This can be achieved by adding an additional step of private ID alignment before data sharing in SecFC. We assume that each data point has a unique ID (e.g., its hash value), and we denote the set of IDs of the data points in ${\cal D}_{j}$ at client $j$ as ${\cal E}_{j}$. Before the clustering task starts, both ${\cal D}_{j}$ and ${\cal E}_{j}$ are kept private at client $j$, and are not known by the other clients and the server. As the first step of the clustering algorithm, all clients collectively run a private set union (PSU) protocol (see, e.g., [20, 21, 22]), over the local ID sets ${\cal E}_{1},\ldots,{\cal E}_{n}$, such that by the end of PSU, each client knows the set of all data IDs ${\cal E}=\cup_{j\in[n]}\mathcal{E}_{n}$ in the network, without knowing the individual ID sets of other clients. Let $|{\cal E}|=m$. All the clients and the server agree on a bijective map between ${\cal E}$ and $[m]$. This also induces a bijective map between ${\cal E}_{j}$ and ${\cal I}_{j}$ at each client $j$.

After private ID alignment, each client learns the total number of data points in the system. During the secure data sharing phase, to protect the privacy of ${\cal I}_{j}\subset[m]$, each client $j$ secret shares a data $\overline{{\bf x}}_{i}^{(j)}$ for each $i=1,\ldots,m$, as described in Section 4.1. Here $\overline{{\bf x}}_{i}^{(j)}={\bf x}_{i}$ for $i\in{\cal I}_{j}$ and $\overline{{\bf x}}_{i}^{(j)}={\bf 0}$ otherwise. We denote the secret share of $\overline{{\bf x}}_{i}^{(j^{\prime})}$ created by client $j^{\prime}$ for client $j$ as $\widetilde{{\bf x}}^{(j^{\prime})}_{i,j}$. Unlike the original data sharing where each client $j$ only receives one secret share $\widetilde{{\bf x}}_{i,j}$ from the owner of ${\bf x}_{i}$, for each $i=1,\ldots,m$, now with membership privacy, client $j$ receives $n$ shares $\widetilde{{\bf x}}^{(1)}_{i,j},\ldots,\widetilde{{\bf x}}^{(n)}_{i,j}$, one from each client. Each client $j$ computes $\widetilde{{\bf x}}_{i,j}=\sum_{j^{\prime}=1}^{n}\widetilde{{\bf x}}^{(j^{\prime})}_{i,j}$. This completes the data sharing phase. Next, the clients perform the same coded center update process as in SecFC to obtain the final $k$-clustering.

With the extension of incorporating the private ID alignment step, SecFC can further protect the membership privacy of the data points, without sacrificing data privacy and clustering performance. We give more detailed description and analysis of this extended version of SecFC in Appendix B.

We propose a secure federated clustering algorithm named SecFC, for clustering data points arbitrarily distributed across a federated learning network. SecFC’s design builds upon the well-known Lloyd’s algorithm, and SecFC universally achieves identical performance to a centralized Lloyd’s execution. Moreover, SecFC protects the data privacy of each client via secure data sharing, and computation over coded data throughout the clustering process. It guarantees information-theoretic privacy against colluding clients, and no explicit knowledge about the data points and cluster centers at the server. Experiment results from clustering synthetic and real data demonstrate the universal superiority of SecFC and its computational practicality under a wide range of system parameters. Finally, we propose an extended version of SecFC to further provide membership privacy for the clients’ datasets, such that, while knowing the final clustering, no party knows the owner of any data point.

While the high level of security provided by SecFC is desirable for many applications, it cannot be directly applied to scenarios where the centers of clusters (e.g., in mean estimation [49, 50]), or the membership of specific data points (e.g., in clustering-based outlier detection [51, 52]) need to be known explicitly. These problems can be resolved respectively by having $\ell+t$ clients to collectively reveal the cluster centers, and having each client publish the IDs of their local data.