acceptodds
Under review as a conference paper at ICLR 2027

Machine Unlearning for Federated Socially Fair -Means Clustering

Abstract

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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
machine unlearning, federated clustering, socially fair k-means, group fairness, exact unlearning, unsupervised learning, responsible AI

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_JkhdOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This work studies exact machine unlearning for federated socially fair k-means clustering, aiming to minimize the maximum group-average clustering cost. Group-separated local summaries allow unaffected information to be reused after deletion, while a replay procedure based on exact sufficient statistics and optional assignment certificates supports unlearning. Under specified sampling assumptions, the paper establishes an approximation guarantee for initialization and proves that same-seed replay reproduces the declared training procedure. Experiments cover both individual-record and whole-client deletion, showing substantial speedups in certain whole-client deletion settings but much smaller gains for individual-record deletion. Additional analyses examine the effects of fair refinement on clustering quality and replay efficiency.

Critical strengths

S1. Group-separated initialization addresses an important challenge in federated socially fair clustering. Deleting a record changes global group weights and may affect summaries held by otherwise unaffected clients. By keeping those local summaries reusable after deletion, the approach avoids unnecessary reconstruction. Theorem 1 provides an approximation guarantee independent of client group proportions under the stated assumptions, while Theorem 2 highlights the potential limitations of a locally balanced merged-summary alternative under group heterogeneity.

S2. Exact replay is carefully formulated. Under fixed preprocessing and representation assumptions, Theorem 5 establishes exact same-seed reproduction of the indexed center trajectory of the declared training procedure, and all 810 comparisons match the corresponding retraining results. Consistency checks at this scale provide substantial support for the reported correctness.

Critical weaknesses

W1. Appendix I.7 compares initialization methods after refinement on real datasets, but these experiments use only a single random seed. Proposition 7 also shows that one refinement round can eliminate the initialization gap in a controlled setting. Together, these results leave some uncertainty about whether the advantage of group-separated initialization remains consistent enough to matter in practice.

W2. Efficiency gains are concentrated in a limited set of settings: 35.79× for initialization-only whole-client deletion, 2.36× and 1.70× with direct replay after one and two refinement rounds, and approximately 1.06× aggregate algorithm-time speedup for individual-record deletion. Assignment certification offers little additional benefit, with useful coverage of just 0.76% and 1.35%, while increasing end-to-end runtime. Overall, the results support the computational value of reusing initialization summaries, but show limited additional efficiency gains from the more elaborate assignment-certification mechanism.

Questions for authors

Q1. Proposition 7 shows that one refinement round can eliminate the initialization gap in a matched-budget construction, while Appendix I.7 uses only a single seed. Under what levels of group heterogeneity or refinement budgets would the authors expect the advantage to remain measurable after refinement?

Q2. Assignment certification saves very little computation in Table 1. What characteristics of the data or deletion requests would make these certificates effective enough to outperform direct replay? Is this mechanism mainly intended for a restricted class of stable clustering configurations?

1 comment

Thank you for reviewing our paper and for highlighting the distinction between an initialization guarantee and a lasting quality advantage. We agree that Proposition 7 and the single seed in submitted Appendix I.7 leave the latter question open.

After submission, we repeated the comparison with ten seeds and separately varied group skew on Adult. At the largest tested mismatch, κ=107.6\kappa=107.6, the mean relative gap favored Merged-1k by 1.70% at initialization and SplitGroup by 0.16% after ten rounds. We found no skew threshold that predicted a lasting advantage on these data.

We also agree with your interpretation of certification. If every center moves by at most ε\varepsilon, a point keeps its assignment whenever its runner-up distance exceeds its winning distance by more than 2ε2\varepsilon. In the submitted Census suite, only three of 95 trials obtained useful coverage, and certification increased aggregate end-to-end time. Its practical value depends on enough assignments remaining stable to justify the cost of checking them.

Reviewer_N8s6OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes SPLITGROUP-2K for exact unlearning in federated socially fair k-means. Perclient summaries are built locally and only weighted by global group sizes at the server, so untouched summaries survive deletions. All 810 replay comparisons match retraining, and whole-client deletion is 35.8× faster at T=0.

Critical strengths
  1. The theory is well-scoped.

  2. All 810 replay comparisons match retraining exactly.

Critical weaknesses
  1. The theory only covers initialization. More analysis of the different states of the refined model is needed.

  2. Heavy reliance on AI-generated theory/proofs/code.

  3. The evaluation is too thin, e.g., five seeds, one desktop, no network/stragglers, and a single preselected client per dataset.

  4. Why keep certificates if they are no longer valid end-to-end?

  5. How will relative unlearning speedups behave when T increases to realistic convergence values like 15 or 20?

  6. The source code should be available to check.

Questions for authors

Please see the weaknesses part.

1 comment

Thank you for reviewing our paper and for your comments on refinement and reproducibility. Your question about 15–20 rounds prompted us to test those budgets directly.

After submission, we tested whole-client deletion on three datasets with five seeds each. With inputs resident, Direct replay’s speedup over matched retraining fell to 1.13× at 15 rounds and 1.07× at 20 because it repeats each refinement round. All 105 comparisons across seven budgets matched retraining. A separate initialization-only follow-up covered 60 clients and five seeds each. All 300 replays matched. These were local measurements.

In the submitted method, each guarded round preserves or lowers worst-group cost, so the initialization bound carries through refinement under the same assumptions. Theorem 5 establishes same-seed trajectory equality. Certificates safely reuse assignments that pass the check, although checking them increased aggregate end-to-end time in the submitted suites.

ICLR 2027’s author policy covers AI assistance with theory, proofs, and implementation and requires disclosure. We disclosed these uses in the manuscript and submission form. We read the paper thoroughly, revised it for clarity before submission, and take responsibility for its claims and code. The original supplement contains the source and reproduction commands. We welcome specific questions about any proof step, implementation choice, or passage that merits clarification. ICLR 2027 AI Policy for Authors We feel penalizing authors for correctly disclosing AI use only discourages honesty in AI Use disclosure.

Reviewer_x9XmOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies exact unlearning for federated socially fair k-means through group-separated summaries and replay of fair refinement. It establishes same-seed equality with retraining under fixed preprocessing and the stated execution assumptions.

Critical strengths
  1. The paper identifies a concrete interaction between deletion and demographic normalization and provides a coherent summary-reuse design.
  2. The exactness specification is careful, and the authors transparently report unfavorable timing outcomes and quality tradeoffs.
Critical weaknesses
  1. Limited methodological advance. The framework combines established representative-based federated clustering, fair updates, and movement-bound certificates. Separating local summaries from global normalization is useful, but the overall contribution appears incremental.
  2. Insufficient external comparison. Runtime comparisons mainly concern variants within the proposed framework. A matched comparison with a fair adaptation of the closest prior method would better establish the practical advance.
  3. Limited and conditional efficiency benefits. Certification generally fails to improve aggregate runtime over Direct replay. The strongest whole-client gains concern initialization-only models, while refinement improves clustering quality and reduces the relative savings. Client-deletion coverage is narrow, and the local evaluation does not establish performance in a deployed federated system.
  4. Unquantified privacy exposure. Transmitted anchors and accessible aggregate statistics can reveal information about individual records. Although acknowledged, these risks are not evaluated under an explicit observer model. Exact replay of model outputs does not protect information disclosed through the transcript or establish physical erasure.
Questions for authors
  1. How does the complete method compare with a matched fair adaptation of the closest prior framework?
  2. Under what conditions does certification reliably outperform Direct?
  3. Which summaries and statistics are visible to each observer, and how substantial is the resulting exposure?
1 comment

Thank you for reviewing our paper and for your comments on the baseline comparison, certification, and privacy. Your suggestion prompted us to test a fair adaptation of the closest prior method.

After submission, we compared SplitGroup with Merged-1k, which uses one locally group-balanced summary per client. After two matched refinement rounds on Adult, Bank, and Credit, neither method consistently achieved lower replay time or worst-group cost. The submitted Theorems 1–2 establish a worst-case distinction: under ideal sampling, SplitGroup’s initialization guarantee is independent of client group proportions.

In the submitted Census suite, the three trials with an unchanged initializer certified nearly all point-rounds. The other 92 had zero useful coverage. This supports using certificates selectively when center movements are small relative to assignment margins. Deployment performance remains unmeasured.

The server sees anchors, multiplicities, and group-cell statistics. At zero snapping, an anchor reveals a represented record, and a singleton cell’s sum reveals its coordinates. Other clients see broadcast centers, and outside recipients see the released model. Exact replay cannot undo prior disclosures. We did not quantify leakage or establish physical erasure.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.