Heterogeneity for the Win: One-Shot Federated Clustering

Don Kurian Dennis, Tian Li, Virginia Smith

Abstract

In this work, we explore the unique challenges—and opportunities—of unsupervised federated learning (FL). We develop and analyze a one-shot federated clustering scheme, $k$-FED, based on the widely-used Lloyd's method for $k$-means clustering. In contrast to many supervised problems, we show that the issue of statistical heterogeneity in federated networks can in fact benefit our analysis. We analyze $k$-FED under a center separation assumption and compare it to the best known requirements of its centralized counterpart. Our analysis shows that in heterogeneous regimes where the number of clusters per device ($k'$) is smaller than the total number of clusters over the network $k$ ($k' \le \sqrt{k}$), we can use heterogeneity to our advantage—significantly weakening the cluster separation requirements for $k$-FED. From a practical viewpoint, $k$-FED also has many desirable properties: it requires only one round of communication, can run asynchronously, and can handle partial participation or node/network failures. We motivate our analysis with experiments on common FL benchmarks and highlight the practical utility of one-shot clustering through use-cases in personalized FL and device sampling.

Introduction

Statistical heterogeneity, or non-IID data distribution, is traditionally viewed as a primary obstacle in Federated Learning (FL). In supervised learning contexts, it often causes local models to diverge, slowing convergence and degrading global performance. This paper challenges that conventional wisdom by demonstrating that for unsupervised tasks—specifically clustering—heterogeneity can be a significant advantage.

Clustering is a foundational tool for exploratory data analysis, client selection, and personalization in FL. However, standard distributed clustering algorithms like parallel $k$-means typically require multiple rounds of communication, making them fragile in edge environments characterized by stragglers and limited bandwidth. We propose $k$-FED, a communication-efficient, one-shot algorithm that thrives in the very heterogeneous environments that usually hinder FL.

The $k$-FED Algorithm

The $k$-FED scheme is designed for simplicity and efficiency, operating in three distinct phases:

  1. Local Clustering: Each participating device independently runs a local $k$-means algorithm on its own data to identify local cluster centers.
  2. One-Shot Communication: Devices transmit only these local cluster centers to a central server. This involves just a single message of size $O(d \cdot k_{local})$, where $d$ is the data dimensionality.
  3. Global Aggregation: The server collects these local centers and performs a single round of Lloyd's heuristic to aggregate them into $k$ global clusters.

Theoretical Advantage of Heterogeneity

The core theoretical contribution of this work is the analysis of $k$-FED under a center-separation assumption. We define a highly heterogeneous network as one where the total number of global clusters is $k$, but each individual device only contains data from a small subset of clusters, $k'$.

In the regime where $k' \le \sqrt{k}$, we prove that the separation requirement between "inactive" cluster pairs (clusters that do not co-occur on the same device) is significantly relaxed. Specifically, the requirement is weakened from $\Omega(\sqrt{k})$ to $\Omega(k^{1/4})$. Intuitively, because the local clustering problem is simplified by heterogeneity, the global aggregation task becomes easier to solve with looser constraints.

Experimental Results

Theoretical Validation

We first validated our theoretical bounds using synthetic Gaussian mixture data. As shown in the figures below, $k$-FED achieves near 100% accuracy in recovering target clusters as the separation constant $c$ increases, even in high-dimensional spaces.

Accuracy of k-FED on synthetic Gaussian data across different separation constants c and network parameters. Accuracy approaches 100% as cluster separation increases.

Real-World Performance

Testing on real-world datasets from the LEAF benchmark—FEMNIST and Shakespeare—confirmed that heterogeneity boosts performance. When data is naturally partitioned (highly heterogeneous), the $k$-means cost achieved by $k$-FED is much closer to the "oracle" (ideal) clustering cost than when data is randomly distributed (IID).

Clustering cost ratio on FEMNIST and Shakespeare datasets as a function of local cluster count k'. Lower values indicate that higher heterogeneity (smaller k') leads to performance closer to the oracle clustering.

Key Insights and Applications

  • Heterogeneity as a Feature: If a network has 100 total user personas, but a single user's device only reflects 2 or 3, the local clustering task is vastly simpler. $k$-FED exploits this local simplicity to relax global requirements.
  • Personalized FL: Using $k$-FED as a pre-processing step to group similar clients allows for learning one model per cluster. On Rotated MNIST, this approach matches the accuracy of state-of-the-art iterative methods like IFCA (98.0%) while drastically reducing communication overhead.
  • Resilient Client Selection: $k$-FED can be used to ensure diverse client sampling. In our experiments on FEMNIST, this reduced the variance of final test accuracies across devices by 35%, leading to fairer and more stable convergence.

Conclusion

$k$-FED demonstrates that statistical heterogeneity can be a powerful tool rather than a hurdle. By leveraging the local simplicity inherent in non-IID data, we can achieve high-quality clustering with minimal communication. This work opens the door for further research into how other federated learning problems might similarly benefit from the unique structure of heterogeneous networks.

Summary updated

Abstract

In this work, we explore the unique challenges -- and opportunities -- of unsupervised federated learning (FL). We develop and analyze a one-shot federated clustering scheme, $k$-FED, based on the widely-used Lloyd's method for $k$-means clustering. In contrast to many supervised problems, we show that the issue of statistical heterogeneity in federated networks can in fact benefit our analysis. We analyse $k$-FED under a center separation assumption and compare it to the best known requirements of its centralized counterpart. Our analysis shows that in heterogeneous regimes where the number of clusters per device $(k')$ is smaller than the total number of clusters over the network $k$, $(k'\le \sqrt{k})$, we can use heterogeneity to our advantage -- significantly weakening the cluster separation requirements for $k$-FED. From a practical viewpoint, $k$-FED also has many desirable properties: it requires only round of communication, can run asynchronously, and can handle partial participation or node/network failures. We motivate our analysis with experiments on common FL benchmarks, and highlight the practical utility of one-shot clustering through use-cases in personalized FL and device sampling.
BibTeX
@inproceedings{dennis2021heterogeneity,
  author = {Don Kurian Dennis and Tian Li and Virginia Smith},
  title = {{Heterogeneity for the Win: One-Shot Federated Clustering}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=NsTIswey0n5},
}
Figure