- 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?
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, 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 ε, a point keeps its assignment whenever its runner-up distance exceeds its winning distance by more than 2ε. 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.