Differentially Private Federated Clustering over Non-IID Data

Yiwei Li, Shuai Wang, Chong-Yung Chi, Tony Q. S. Quek

Introduction

Clustering is a fundamental unsupervised learning task, but performing it in a Federated Learning (FL) environment—where data remains on local devices—presents significant challenges. This paper introduces DP-FedC, a novel federated clustering algorithm designed to effectively partition unlabeled data across decentralized clients while providing rigorous differential privacy (DP) guarantees. By reformulating the classic k-means problem into a soft-clustering optimization and leveraging privacy amplification through client subsampling, DP-FedC achieves superior clustering accuracy on non-IID (heterogeneous) data compared to existing state-of-the-art methods.

Problem Statement: Challenges in Federated Clustering

Performing clustering in a decentralized setting involves three major hurdles:

  1. Data Heterogeneity (Non-IID): Real-world clients often possess data from only a subset of clusters. Traditional algorithms like k-means frequently fail to converge or produce poor global models under these heterogeneous conditions.
  2. Privacy Leakage: Although raw data is not shared, the cluster centroids (model updates) uploaded to a central server can inadvertently reveal sensitive information about a client's local dataset to an adversary.
  3. Computational Complexity: The standard k-means problem is NP-hard due to its binary assignment constraints, making it difficult to optimize across thousands of resource-constrained devices.
System model of federated learning with an adversary attempting to intercept model updates.

Methodology: The DP-FedC Algorithm

The authors propose DP-FedC, which addresses these challenges through several key technical innovations:

  • Soft-Clustering Reformulation: Instead of the "hard" binary constraints of k-means, the problem is reformulated into a non-convex optimization with a single convex constraint. This "soft" assignment approach creates a smoother optimization landscape, making it more resilient to the "messiness" of non-IID data.
  • Alternating Local Updates: Clients perform multiple local steps, updating local cluster indicator matrices via projected gradient descent and local centroids via stochastic gradient descent.
  • Differentially Private Aggregation: To protect against privacy leakage, clients add Gaussian noise to their local centroids before uploading them to the Parameter Server (PS).
  • Privacy Amplification: The algorithm employs "Partial Client Participation" (PCP). By selecting only a subset of clients in each round, the privacy loss is mathematically amplified (reduced). This allows the algorithm to use less noise while maintaining the same level of protection, significantly improving the privacy-utility tradeoff.

Experimental Evaluation

The researchers evaluated DP-FedC on two real-world datasets:

  1. TCGA (The Cancer Genome Atlas): High-dimensional gene expression data (5,314 samples, 5,000 features) across 20 cancer types.
  2. MNIST: Handwritten digits (10,000 samples, 784 features).

Both IID and non-IID scenarios were simulated to test resilience to data heterogeneity.

Key Results

DP-FedC consistently outperformed benchmark algorithms (DK++, DKM, FKM, and FZKM):

  • Accuracy: On the non-IID TCGA dataset with a privacy budget ($\bar{\epsilon} = 20$), DP-FedC achieved 72.2% accuracy, outperforming the next best competitor, FZKM (66.9%).
  • Robustness: DP-FedC showed a much smaller performance gap between private and non-private versions compared to other methods.
  • Convergence: The authors provide a theoretical proof that DP-FedC converges at a rate of $O(1/\sqrt{R})$, even under non-IID and non-convex conditions.

Conclusion and Future Work

DP-FedC demonstrates that moving to a soft-clustering formulation and utilizing subsampling-based privacy amplification can overcome the traditional trade-offs in federated clustering. Future work includes addressing hyperparameter sensitivity (e.g., penalty parameters $\rho, \mu_h, \mu_w$), optimizing for extremely low-bandwidth environments, and investigating the impact of "straggler" clients on convergence.

Summary updated

BibTeX
@article{li2024differentially,
  author = {Yiwei Li and Shuai Wang and Chong-Yung Chi and Tony Q. S. Quek},
  title = {{Differentially Private Federated Clustering over Non-IID Data}},
  journal = {IEEE Internet of Things Journal},
  year = {2024},
  doi = {10.1109/jiot.2023.3312852},
}
Figure