Differentially Private Federated Clustering with Random Rebalancing

Xiyuan Yang, Shengyuan Hu, Soyeon Kim, Tian Li · 2025

Read Differentially Private Federated Clustering with Random Rebalancing by Xiyuan Yang, Shengyuan Hu, Soyeon Kim, Tian Li (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-06183.txt.

Introduction

Xiyuan Yang and co-authors fix a privacy flaw in federated clustering in this 2025 paper. Federated clustering groups similar clients so each group trains its own model. Adding standard privacy noise hurts here, because small clusters average too little noise away. Cluster sizes are uncontrolled, so some groups end up tiny and noisy.

Their add-on, RR-Cluster, randomly rebalances assignments to guarantee each cluster a minimum size. The trade is clear: less noise, but some clients land in the wrong group. The authors bound that trade-off and prove convergence. Plugged into strong clustering methods, the add-on improved the privacy-utility balance on both synthetic and real data.

Catalog record

CREATORXiyuan Yang, Shengyuan Hu, Soyeon Kim, Tian Li
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE75 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-06183

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Differentially Private Federated Clustering with Random Rebalancing Xiyuan Yang, Shengyuan Hu, Soyeon Kim, Tian Li Abstract Federated clustering aims to group similar clients into clusters and produce one model for each cluster. Such a personalization approach typically improves model performance compared with training a single model to serve all clients, but can be more vulnerable to privacy leakage. Directly applying client-level differentially private (DP) mechanisms to federated clustering could degrade the utilities significantly. We identify that such deficiencies are mainly due to the difficulties of averaging privacy noise within each cluster (following standard privacy mechanisms), as the number of clients assigned to the same clusters is uncontrolled. To this end, we propose a simple and effective technique, named RR-Cluster , that can be viewed as a light-weight add-on to many federated clustering algorithms. RR-Cluster achieves reduced privacy noise via r andomly r ebalancing cluster assignments, guaranteeing a minimum number of clients assigned to each cluster. We analyze the tradeoffs between decreased privacy noise variance and potentially increased bias from incorrect assignments and provide convergence bounds for RR-Cluster . Empirically, we demonstrate that RR-Cluster plugged into strong federated clustering algorithms results in significantly improved privacy/utility tradeoffs across both synthetic and real-world datasets. 1 Introduction Clustering is a critical approach for adapting to varying client distributions in federated learning (FL) by learning one statistical model for each group of similar clients [ 17 , 14 ] . It usually outperforms the canonical FL formulation of learning a single global model, as it outputs several models to serve heterogeneous client population [ 11 ] . Federated clustering typically works by identifying clusters each client belongs to and incorporating model updates into the corresponding cluster models iteratively. However, performing clustering requires clients to transmit additional data-dependent information, making the federated learning system more vulnerable to privacy leakage. In this work, we aim to finally output k clustered models such that the set of these k models satisfies a global client-level differential privacy (DP) [ 10 , 28 ] , with a trusted central server. Despite recent attempts privatizing federated clustering by DP [ 20 , 3 ] , we identify that a fundamental tension between DP and clustering still remains—DP tries to hide individual client’s contributions to the output models, whereas clustering may expose more client information (i.e., client model updates), especially if the cluster size is small (or even one). We need much larger effective noise to privatize those clients that have a huge impact on their assigned clusters, which can degrade the overall privacy/utility tradeoffs. For instance, we observe significant utility drops if directly applying standard DP mechanisms on top of existing federated clustering algorithms (Figure 1 and Section 5 ). Figure 1 : Test accuracy on FashionMNIST [ 36 ] with a neural network model. Directly privatizing previous clustering method [ 11 ] (DP-IFCA) degrades model performance significantly, even underperforming the non-personalized approach (DP-FedAvg [ 28 ] ) for some privacy budgets. The proposed RR-Cluster plugged into IFCA achieves higher accuracy in private settings under various \varepsilon ’s. Inspired by these insights, we propose a simple and light-weight technique, RR-Cluster , that prevents too small clusters by randomly sampling a subset of clients’ model updates belonging to large clusters into small ones, thus guaranteeing each cluster having at least B assigned model updates at each round. Such data-independent random rebalancing step can be applied on top of various clustering algorithms where the server aggregates model updates within each cluster based on learnt cluster assignments, without extra privacy or communication costs. RR-Cluster has at least B client model updates within each cluster, thus resulting in a smaller effective privacy noise after model averaging. We note that a key hyperparameter here is B , the lower bound of the number of clients assigned to each cluster. When B=0 , it recovers any base clustering algorithm. When B increases, we reduce privacy noise at the cost of potentially increasing clustering bias by moving clients from correct clusters to incorrect ones. Theoretically, we analyze the effects of B in the convergence bounds when plugged into a competitive clustering algorithm [ 11 ] in federated settings. Empirically, we find that (1) small values of B can improve privacy/utility tradeoffs significantly, (2) and that the potential clustering bias from RR-Cluster does not hurt the learning process too much, especially in cases where the original assignment before rebalancing may not be accurate. Our contributions are summarized as follows. • We propose RR-Cluster , a simple technique to improve privacy/utility tradeoffs for federated clustering by randomly sampling model updates from large clusters to small ones (Section 3 ). It can be used as a light-weight add-on on top of various federated clustering algorithms. • We theoretically analyze the privacy and convergence bounds of RR-Cluster in convex settings, revealing a tradeoff between reduced privacy noise and increased bias (Section 4 ). • Empirically, we demonstrate the effectiveness of RR-Cluster across both real-world and synthetic federated datasets under natural and controlled heterogeneous data distributions (Section 5 ). RR-Cluster outperforms vanilla private baselines by a large margin. 2 Related Works and Background Federated Clustering and Personalization. Federated clustering is a critical approach for federated networks by learning one model for each group of similar clients, which can benefit various downstream tasks including personalization [ 9 ] . The IFCA method [ 11 ] is one of the most popular clustering algorithm, where each client 1) computes the losses of all cluster models on the local dataset and 2) selects the cluster having model of minimum test loss as their belonged cluster. Other clustering approaches leverage different distance measures for the cluster assignment [ 22 ] or incorporate an additional global model to improve performance [ 24 ] . While these clustering methods significantly enhance the performance of federated systems, challenges remain to guarantee differential privacy (DP) for the entire learning pipeline. In Section 5 , we show how plugging RR-Cluster into some of these clustering methods can effectively protect data privacy while achieving better performance relative to directly privatizing these clustering methods. Differentially Private Distributed/Federated Clustering. It is critical to ensure (differential) privacy when clustering distributed and sensitive data, which has been studied extensively in prior works mostly for data analytics [ 30 , 33 , 13 , 4 , 6 , 8 , e.g.,] . However, joint clustering and learning algorithms under privacy constraints are generally less explored. In the context of federated learning, existing works have considered private federated clustering in different settings. For instance, the DCFL algorithm [ 3 ] combines a dynamic clustering method with DP under global DP. Malekmohammadi et al. 2025 perform cluster assignments based on clients’ model updates and loss values. We note that some works may provide insufficient privacy protection without privatizing all the raw-data-dependent intermediate information in the clustering process (e.g., cluster assignment identifiers) [ 20 , 23 ] . Despite the existence of private federated clustering algorithms, issues related to high sensitivity of averaged model updates that belong to small clusters (thus resulting in large privacy noise) still remain. Some works target at sample-level DP [ 21 ] or local DP [ 12 ] , different from our setting focusing on client-level

Read the complete text