Machine Unlearning for Federated Socially Fair k-Means Clustering

Machine unlearning in federated clustering is computationally feasible but with important limitations: The paper demonstrates that when an entire client (e.g., a hospital) withdraws from a federated clustering system, the system can recompute results 35.8× faster using cached data rather than starting from scratch. However, for individual record deletions (like a single patient's data), the speedup is minimal (only 1.06×), suggesting that exact unlearning is most practical at the organizational level rather than the individual level.

Data deletion can disrupt fairness in clustering systems: The research reveals a critical tension in responsible AI: when records are deleted from a federated clustering system, the remaining population's demographic balance shifts, which can alter how the remaining groups are clustered. This means that honoring deletion requests (like GDPR's right to erasure) requires careful recalibration of fairness protections to ensure no group is disadvantaged by others' departures.

Keeping separate records by demographic group enables efficient, fair unlearning: The paper's key technical innovation—maintaining separate local summaries for each demographic group—allows institutions that weren't directly affected by a deletion to avoid recomputation. This design means that fairness adjustments at the global level don't force every participating organization to recalculate their local data, reducing computational burden across the federated network.

Certification of fairness guarantees can be more expensive than recomputation: The research found that verifying whether cached clustering assignments remain valid after deletions sometimes costs more computational resources than simply retraining the system from scratch, suggesting that practitioners may need to choose between computational efficiency and formal fairness verification.