Machine Unlearning for Federated Socially Fair $k$-Means Clustering

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× faster than retraining for the initialization-only model and remains 2.4× and 1.7× faster with one and two fair-refinement rounds, which improve worst-group cost. For individual record deletions, gains are modest (about 1.06×), and certifying cached assignments can cost more than it saves. These results map where exact unlearning can profitably reuse computation.