CS Paper Radar

Federated Clustering with Unknown Local and Global Cluster Cardinalities

Mitushi Goyal, Tarun S., Riddhanya Senapathi, Arun Raman

cs.LG cs.DCstat.ML ·submitted 2026-09-29 05:33 UTC · v1

Abstract

Federated clustering methods that do not require the global number of clusters $K$ still assume that each client knows its local number $K_g$. This assumption is hard to justify when clients know no more about their data than the server does, as in fault diagnosis across independently operated industrial sites. We propose a two-phase framework in which neither count is known: each client first estimates $K_g$ from its own data, and an aggregator that requires local counts, such as FedGEM, then uses these estimates in place of the true values. For the first phase we introduce Adaptive Split--Merge (ASM), which grows a spherical Gaussian mixture by BIC-driven splitting and then merges excess components. ASM uses no labels, selects its hyperparameters on held-out client data only, and makes no assumption about how clusters are shared across clients. We derive a closed-form split criterion whose critical cluster size falls with anisotropy and rises with dimension, and show empirically that over-fragmentation grows with the number of points per cluster, which federation divides among clients. Across eight datasets, ASM with FedGEM attains a mean ARI of 0.333, against 0.256 for the next best label-free estimator and 0.361 when the true local counts are supplied. It also gives the most reliable global estimates of $K$ and is robust when client size is decoupled from local cardinality.

Closest papers

Nearest neighbours by meaning across the whole index.

Machine Unlearning for Federated Socially Fair k-Means Clustering

cs.LG cs.DS ·2026-10-09 ·Aravind Reddy, Deeraj S K, Mohd Wasif Raza, Saurav Prakash
theorycode/data similarity 0.61
Abstract · 53 pages, 7 figures, including appendices. The first three authors contributed equally. Supplementary code, data and scoped Lean proofs (v1.…

Federated clustering can support applications such as patient stratification across hospitals and customer segmentation across distributed financial datasets. Responsible AI calls for fair representation of demographic groups and support for data deletion, motivated in part by rights such as the GDPR's right to erasure. These goals interact: deleting records can change the balance between groups and alter the clustering of the remaining population. We study exact machine unlearning for federated socially fair $k$-means, whose objective is to minimize the largest group-average squared distance to the nearest center. Our approach keeps separate local summaries for each group, so summaries at unaffected institutions remain valid as global fairness weights change. For two groups, we prove an initialization approximation guarantee independent of client group proportions under ideal sampling, and we show that same-seed replay reproduces retraining exactly. Reuse pays off most when a whole client withdraws: across three datasets, replay is $35.8\times$ faster than retraining for the initialization-only model and remains $2.4\times$ and $1.7\times$ faster with one and two fair-refinement rounds, which improve worst-group cost. For individual record deletions, gains are modest (about $1.06\times$), and certifying cached assignments can cost more than it saves. These results map where exact unlearning can profitably reuse computation. Code and reproducibility materials are available at https://github.com/arareddy/mufsc.

0.39

Federated Soft Clustering via Generalized Total Variation Minimization

cs.LG stat.ML ·2026-09-16 ·Shamsiiat Abdurakhmanova, Alexander Jung
similarity 0.59
Abstract · submitted to ICASSP '27

We study federated soft clustering over federated learning (FL) networks of devices that each hold a private local dataset and fit a personalized Gaussian mixture model (GMM). Generalized total variation minimization (GTVMin) couples the local maximum likelihood problems through a graph regularizer that penalizes a discrepancy between the models of connected nodes. The choice of discrepancy measure is a key design decision: we compare a squared Euclidean distance between model parameters, which requires component matching, with two measures that compare the local model distributions directly and hence need no matching: a Monte-Carlo approximated Kullback-Leibler (KL) divergence and a closed-form maximum mean discrepancy (MMD). All three resulting GTVMin instances are optimized by synchronous projected gradient updates; for the smooth MMD instance we provide a convergence guarantee to stationary points. We characterize their computational cost and evaluate their robustness to data heterogeneity.

0.38

Kernelised covariance matrices, dimension reduction and imbalanced spectral clustering

cs.LG stat.MLmath.PRmath.SP ·2026-10-23 ·Xiaoyu Dong, Subhro Ghosh, Soumendu Sundar Mukherjee, Himasish Talukdar
similarity 0.58
Abstract

The Gaussian Mixture Model (abbrv. GMM) is a classic generative model for clustered data, for which spectral clustering based on dimension reduction via PCA has been an effective framework. In this work, we investigate kernelised covariance matrices as an alternative mechanism for dimension reduction and spectral clustering, focusing on truncation kernels that select pairs of data points with suitable separation constraints. The structure of these matrices is motivated by considerations from statistical mechanics of repulsive particle systems. Our approach is particularly relevant for the setting of imbalanced clusters, where the sizes of the largest and smallest clusters have a diverging ratio with the problem size, and existing PCA-based methods turn out to be of limited effectiveness. We demonstrate efficient dimension reduction and clustering performance of these modified covariance matrices, substantiated by quantitative bounds. In particular, they achieve superior dimension reduction guarantees compared to PCA for a wide range of parameters in the regime of imbalanced clusters. For spectral clustering, our approach exhibits improvements over PCA in the imbalanced setting, in particular guaranteeing accurate clustering in a much larger regime of intra-cluster separations. Our theoretical guarantees reflected in a range of simulation experiments that exhibit these improvements for unbalanced clustering problems. Our analytical approach, based on kernel Laplacians, provide a toolbox as well as a relevant conceptual ingredient for clustering problems at large. We believe that our work will motivate the application of such kernelised covariance matrices for related classes of statistical problems, as well as spur new investigations in the theory of random matrices.

0.22

Evolving Federated Density Peak Clustering with Shuffler-Based Anonymization

cs.LG cs.CRcs.DCeess.SY ·2026-10-22 ·Miha Ožbot, Seiichi Ozawa, Igor Škrjanc
publishedbenchmarkcode/data similarity 0.57
Abstract · 30 pages, 4 figures. Published open access (CC BY 4.0) in Evolving Systems 17, 123 (2026). Code: https://github.com/mihaozbot/eFDPC

In this paper, we present a novel one-shot federated clustering approach based on evolving fuzzy clustering and shuffler-based anonymization. In federated clustering, each round reveals additional model information to the server and can increase the opportunity to infer properties of local datasets, even when raw samples are never shared. Consequently, fewer client-server exchanges and unlinkability are important, so transmitted information cannot be attributed to any single client. Data-stream clustering algorithms, which learn in a single pass over the data, align well with the one-shot federated learning paradigm, where a single communication round can be sufficient. The proposed Evolving Federated Density Peak Clustering (eFDPC) method combines evolving fuzzy data-stream clustering and density peak clustering in a federated setting. Each client independently evolves micro-clusters from private data mini-batches through cluster addition and merging. To limit communication, density peak clustering is applied to the learned micro-clusters and only the selected peaks are transmitted, rather than the full local models. A shuffler-based layer is introduced between the clients and the server to anonymize contributions prior to reconstruction and global peak selection. We consider a peak-only variant, eFDPC-P, as well as eFDPC-G with server-side label propagation. Experiments on synthetic and real-world benchmark datasets show that eFDPC outperforms recent federated clustering baselines in one-shot settings and scales to higher-dimensional, non-IID data.

0.41

Bracketing Uncertainty in Clustering Under the Manifold Hypothesis

cs.LG stat.MLq-bio.QM ·2026-09-15 ·Savik Kinger, Luciano Dyballa, Steven W. Zucker
similarity 0.56
Abstract

The manifold hypothesis suggests a natural criterion for clustering: partition data according to the manifold component from which each point is drawn. Whether two components are separable depends on a geometric tradeoff: the ambient separation between components versus the largest gap in sampling. In practice, this tradeoff is rarely assessed explicitly, leading standard methods to over-commit to a single clustering assignment even when the data do not support a unique answer. We formalize this tradeoff by combining intrinsic manifold geometry (volume growth and reach) with sample-level quantities (fill distance and density), yielding a threshold phenomenon for mutual-$k$-nearest-neighbor graphs: when the offset-to-fill ratio exceeds a conservative upper threshold, component separation is preserved; below a lower threshold, components fuse. The gap between these thresholds defines a geometric uncertainty zone in which the number of clusters is not identifiable from the data. Nevertheless, conventional approaches still seek one: sweeping parameters (an engineering approach) or fitting a generative mixture model (a model-based approach). Rather than forcing a single estimate of the number of clusters, we propose Manifold-Based Clustering (MBC), which returns an explicit bracket interval to quantify the underlying data uncertainty. This bracket acts as an empirically calibrated diagnostic: it narrows when a single resolution is supported, widens when multiple resolutions coexist, and collapses to one when no separated structure is detectable. Empirically, we find that many real datasets lie within the uncertainty zone rather than admitting one clear answer. Our results suggest that ambiguity in cluster number is often intrinsic, and should be quantified rather than resolved.

0.47

NVE: A Separability and Coverage-Aware Internal Validation Metric for Biclustering

cs.LG ·2026-08-29 ·Paritosh Tiwari, I Navin Kumar, James C. Bezdek, Punit Rathore
unusual similarity 0.55
Abstract

Biclustering, or co-clustering, aims to discover coherent submatrices by grouping rows and columns of a data matrix simultaneously. This local two-dimensional structure makes validation more difficult than in ordinary clustering, where internal indices usually rely on compactness and separation in a single shared feature space. Existing popular internal biclustering measures such as Mean Squared Residue (MSR), and Virtual Error (VE) mainly evaluate within-bicluster coherence. Although useful, these measures do not directly assess whether the extracted biclusters are mutually distinct or whether they explain a meaningful portion of the data matrix. This paper investigates Normalised Virtual Error (NVE), an internal validation metric that extends VE using a super-bicluster normalization strategy. By comparing the VE of each bicluster with the VE obtained after merging it with other biclusters, NVE introduces a relative notion of separability and redundancy. We also study a coverage-adjusted variant, NVE\textsubscript{cov}, which penalizes solutions that obtain low error by selecting only very small submatrices. Through controlled synthetic benchmarks and yeast gene-expression datasets, we examine whether NVE and NVE\textsubscript{cov} provide information beyond standard coherence-based metrics. The results show that NVE is sensitive to redundant and poorly separated biclusters, while NVE\textsubscript{cov} changes solution rankings when low-error biclusters cover only a negligible part of the matrix. These findings suggest that NVE-based measures are useful complementary criteria for internal co-clustering validation, especially when coherence, separability, and coverage must be considered jointly.

0.26

CF-LoRA: Decoupled Factor Aggregation and Adaptation-Aware Client Clustering for Federated LoRA Fine-Tuning

cs.AI cs.DC ·2026-09-29 ·Mengjun Yi, Langxing Yang, Suhan Guo, Furao Shen, Jian Zhao
similarity 0.55
Abstract

Federated LoRA fine-tuning enables parameter-efficient adaptation of pre-trained models without sharing private data, but suffers from two fundamental mismatches under heterogeneous client data: a structural aggregation mismatch caused by independently averaging LoRA factors, and a statistical collaboration mismatch caused by enforcing a single global adapter across divergent clients. To address these issues, we propose CF-LoRA, a clustered federated LoRA fine-tuning framework that combines decoupled factor aggregation with adaptation-aware client clustering. CF-LoRA first learns a globally shared $A$ factor while retaining personalized $B_i$ factors, then identifies clients with similar adaptation patterns based on the cosine similarity of their learned $B_i$ factors, and finally performs intra-cluster $B$-factor aggregation with a frozen $A$ factor. By decoupling LoRA factor aggregation, CF-LoRA preserves the low-rank structure and mitigates the structural aggregation mismatch, while adaptation-aware clustering promotes collaboration among clients with similar adaptation patterns and reduces negative transfer caused by statistical heterogeneity. Experiments on four language tasks and four vision datasets with RoBERTa and ViT show that CF-LoRA achieves the highest average accuracy in both modalities while communicating only one LoRA factor per optimization round.

0.09

Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling

cs.LG stat.MLmath.PR ·2026-09-06 ·Diptarka Chakraborty, Satyaki Mukherjee, Gaurav Vallabhdas Revankar, Hoang-Son Tran
benchmark similarity 0.55
Abstract

Massive datasets in modern machine learning have made data reduction a central challenge, particularly for clustering tasks where memory and computational constraints demand compact yet faithful summaries. A standard approach is to construct an \textit{$ε$-coreset}: a small weighted subset that approximately preserves the clustering cost for every plausible choice of centers. For the \textit{$(k,z)$-clustering problem}, existing worst-case bounds on coreset size are essentially tight, ruling out substantially smaller coresets in general. However, such worst-case instances are often unrepresentative of real-world data. In this work, we show that significantly smaller coresets are possible under mild and natural assumptions on the underlying data distribution. We introduce a new correlated sampling framework, called \textit{determinantal sampling}, based on a novel application of determinantal point processes. Using this framework, we obtain an efficiently constructible $\varepsilon$-coreset for $(k,z)$-clustering in $\mathbb R^d$ whose dependence on $1/\varepsilon$ has exponent strictly smaller than $2$ when $d$ is fixed. This improves over the worst-case $\varepsilon^{-2}$ barrier under our beyond-worst-case assumptions. To the best of our knowledge, this is the first result that provably surpasses these lower bounds through beyond-worst-case assumptions. Finally, we validate our approach on synthetic and real-world benchmark datasets, where it consistently achieves smaller coresets than existing state-of-the-art methods, even without explicitly enforcing the assumptions used in the analysis.

0.16