- Rating
- 2(+1)
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
The paper proposes a 2 phase federated clustering framework, without prior knowledge of either the local or the global number of clusters, similar to non-parametric clustering algorithms.
In the first phase, each client estimates its local number of clusters using the Adaptive Split–Merge (ASM) algorithm, a hierarchical divisive clustering method that combines recursive binary splitting guided by the BIC with a merging step.
Critical strengths
Th paper provides a closed-form theoretical derivation of the BIC split criterion, demonstrating that the critical size at which a cluster splits decreases with its anisotropy and increases with dimension.
Critical weaknesses
-Fragility of the Heuristic Merge Stage under Large Client Sample Sizes and Complex Data Geometry
-Scaling is not being studied
-Some references to nonparametric clustering are missing.
K. Meguelati, B. Fontez, N. Hilgert, and F. Masseglia. Dirichlet Process Mixture Models made Scalable and Effective by means of Massive Distribution. In SAC 2019 - 34th ACM/SIGAPP Symposium on Applied Computing, pages 502–509, Limassol, Cyprus, Apr. 2019. ACM/SIGAPP.
Reda Khoufache, Mustapha Lebbah, Hanene Azzag, Etienne Goffinet, Djamel Bouchaffra. Distributed Collapsed Gibbs Sampler for Dirichlet Process Mixture Models in Federated Learning. SIAM International Conference on Data Mining (SDM24), Apr 2024, pp.815 - 823, ⟨10.1137/1.9781611978032.93⟩.
The novelty of the proposed approach relative to the existing literature is unclear.
Questions for authors
Why did you not evaluate their method on synthetic 2D datasets with different cluster geometries, such as half-moons, spirals, and spherical clusters? These would help assess the behavior and robustness of the proposed clustering algorithm across different cluster shapes and distributions.
One of the main objectives of federated learning is to enable scalable processing across distributed clients and large datasets. In my opinion, you should conduct experiments on synthetic datasets, even in 2D, to evaluate the scalability ( 200K, …1000K).
All comparisons are currently based on the ARI. To provide a more comprehensive evaluation, you should also report other clustering metrics, such as NMI and clustering accuracy (ACC).
4 comments
Comparison with DisCGS; scaling, the merge, 2D shapes and metrics (1/2)
(Comment 1/2) We ran the experiments the reviewer suggested. Summary:
- DisCGS (below): ASM + FedGEM is competitive in accuracy and much faster. DisCGS's accuracy depends on a concentration setting shared by all sites, for which its paper gives no rule, and at 1M points it would take an estimated 11–19 hours against about 4 minutes.
- Scaling (comment 2/2): up to 2M points and with 100–200 clients, ASM (sample) + FedGEM matches FedGEM given the true counts.
- The merge with large clients: it raises ARI and reduces the local count, but the count stays too high. ASM (sample) removes the over-count on our synthetic large clients (10K–240K points) and helps slightly on large image clients.
- 2D shapes: ASM-S is within 0.035 of the best label-free method on blobs and two moons; circles and spirals defeat even FedGEM given the true counts.
- NMI, AMI and ACC lead to the same conclusions as ARI.
Comparison with DisCGS Setup. We ran the authors' public code unchanged for its 100 iterations, with one worker per client, so each worker holds one of our clients rather than an even share of the data. We scored its clusters with the same rule as ours. We compare DisCGS end to end with ASM + FedGEM.
Benchmarks. Our partitions and seeds (5 seeds, 3 for MNIST), with DisCGS's published setting for real data; ASM-S is scored on the same seeds, so it differs slightly from the 10-seed averages in the paper. Federated ARI:
| Dataset | Part. | DisCGS | ASM-S |
|---|---|---|---|
| Waveform | A | 0.000 | 0.253 |
| Abalone | A | 0.098 | 0.097 |
| Frog A | A | 0.622 | 0.639 |
| Frog B | A | 0.388 | 0.376 |
| MNIST | A | 0.473 | 0.429 |
| Waveform | B | 0.000 | 0.283 |
| Abalone | B | 0.102 | 0.095 |
| Frog A | B | 0.868 | 0.563 |
| Frog B | B | 0.582 | 0.391 |
DisCGS is ahead on MNIST and on both Frog datasets in partition B and ties ASM-S on the rest, except Waveform, where it returns one cluster. It crashed on CIFAR-10, and FMNIST and EMNIST were not run. NMI and AMI also favour DisCGS on the Frog datasets in partition A, and ACC favours ASM-S on Frog B there; the revised submission will report all four metrics. An MNIST run of DisCGS takes about 32 minutes on 12 threads.
At scale. 2D mixtures of 10 clusters, either round Gaussians (easy) or elongated clusters with heavy Student-t tails (hard), over 10 clients that each hold a subset of the clusters (seed 42, the same 12 threads). ASM is ASM (sample) from the scorecard in our closing comment: it chooses its settings on a 10K-point sample of each client and reads its count from that fit. The DisCGS paper gives no rule for its concentration parameters, so we ran both settings its authors use: 5 at both levels for their synthetic data, and 10⁻¹⁴ (master) and 1 (workers) for their real data. A full DisCGS run was feasible up to 200K points:
| Family | Points | DisCGS, synthetic setting (ARI, time) | DisCGS, real-data setting (ARI, time) | ASM + FedGEM (ARI, time) |
|---|---|---|---|---|
| Easy | 100K | 0.849, 8.3 min | 0.630, 6.9 min | 0.811, 1.9 min |
| Easy | 200K | 0.872, 29 min | 0.760, 22 min | 0.862, 2.4 min |
| Hard | 100K | 0.639, 12.5 min | 0.781, 7.1 min | 0.727, 2.3 min |
| Hard | 200K | 0.503, 39 min | 0.742, 29 min | 0.742, 2.5 min |
With the better setting for each family, DisCGS is ahead by 0.01–0.05 in three runs and ties in the fourth; with the other setting, it is behind ASM + FedGEM in all four. Which setting is better depends on the data, and DisCGS does not provide a way for choosing it.
ASM + FedGEM is 3–16 times faster in these runs, and the gap widens with size because DisCGS's cost grows roughly with the square of the points per client. At 1M and 2M points, 2 of DisCGS's 100 iterations take 13–15 and 64–78 minutes, against about 4 and 6 minutes for the complete ASM + FedGEM run. A full DisCGS run would take about 11–19 hours at 1M points and 2.5–4 days at 2M (estimated from the completed runs). Spread over 200 clients, DisCGS becomes cheaper, an estimated 1 hour at 1M points against 12 minutes for ASM + FedGEM, but we could not measure its accuracy there.
The revised submission will report this comparison in a new appendix, including where DisCGS wins.
Scaling, the merge with large clients, 2D shapes, NMI, AMI and ACC (2/2)
---- Comment 2/2 ----
Scaling. On the 2D data of comment 1/2, we grew the total from 100K to 2M points over 10 clients (10K–240K points per client) and spread 1M points over 10–200 clients. ASM (sample), from our closing comment's scorecard, chooses its settings on a 10K sample of each client and reads its count from that fit. ARI after FedGEM, means over both families and seeds 42–44:
| Points (10 clients) | 100K | 200K | 500K | 1M | 2M |
|---|---|---|---|---|---|
| ASM (sample) + FedGEM | 0.78 | 0.79 | 0.75 | 0.73 | 0.67 |
| FedGEM, true counts | 0.78 | 0.80 | 0.75 | 0.65 | 0.68 |
ASM (sample) matches the true-count level at every size, with a count error of 0.4 per client. It takes about 100–120 s and under 0.1 GB per client, and the complete run takes about 4 minutes at 1M points and 6 at 2M. With 100–200 clients it reaches 0.69–0.73, against 0.66–0.71 with the true counts (seed 42).
The merge with large clients. With MNIST, FMNIST and CIFAR-10 split over 3, 5 or 10 clients (about 1,000–5,000 points per cluster on each), the merge significantly reduces local and global count errors and raises ARI, winning 32 of the 40 cases where it changes anything (see our reply to Reviewer TtzZ). It still leaves the local count too high there, so ASM remains below the true-count result (0.27 against 0.39). Reading the count from a 10K sample, as ASM (sample) does, helps only slightly on these clients (0.28; local error 12 against 16 per client). On our synthetic large clients it removes the over-count: on 2D clients of 10K–240K points its ARI matches FedGEM given the true counts, and at 50K points per client in 64 dimensions it recovers every count (ARI 0.91). We will state the over-count on large image clients as a limitation.
2D shapes. Federated ARI:
| Shape | ASM-S | DP-GMM | X-means | G-means | Known count |
|---|---|---|---|---|---|
| Isotropic blobs | 0.903 | 0.652 | 0.869 | 0.902 | 0.924 |
| Anisotropic blobs | 0.440 | 0.390 | 0.278 | 0.454 | 0.506 |
| Two moons | 0.207 | 0.241 | 0.187 | 0.217 | 0.424 |
| Circles | 0.016 | 0.129 | 0.136 | 0.155 | −0.001 |
| Spirals | 0.012 | 0.011 | 0.005 | 0.002 | 0.005 |
Circles and spirals defeat every method, FedGEM given the true counts included, so the limit there is the Gaussian aggregation phase, not the count or the merge; the revised submission will state this as a scope limitation.
NMI, AMI and ACC. Averages over the eight datasets, partition A / partition B (†: over the datasets where G-means finished):
| Method | ARI | NMI | AMI | ACC |
|---|---|---|---|---|
| ASM-S | 0.333 / 0.347 | 0.437 / 0.444 | 0.435 / 0.442 | 0.465 / 0.479 |
| DP-GMM | 0.214 / 0.240 | 0.416 / 0.431 | 0.409 / 0.425 | 0.345 / 0.361 |
| X-means | 0.256 / 0.299 | 0.420 / 0.444 | 0.414 / 0.439 | 0.385 / 0.425 |
| G-means† | 0.162 / 0.190 | 0.395 / 0.437 | 0.378 / 0.425 | 0.266 / 0.268 |
| Known count | 0.361 / 0.342 | 0.440 / 0.423 | 0.437 / 0.421 | 0.511 / 0.503 |
Beyond the changes in our general response, the revised submission will add the DisCGS comparison, the scaling study, the 2D shapes and the merge experiments as appendices, report NMI, AMI and ACC alongside ARI throughout, and state the limitations above. We would be glad to discuss any of these further.
Conclusion, summarizing all the experiments run so far
This comment gathers the results from all threads.
- The contribution is the framework (general response): the setting's two requirements, a modular two-phase design and an evaluation under these constraints.
- Of seven first phases, only ASM and Ward's method stay at or near the reference in every setting, when both read their count from a 10K sample on large clients; for ASM this is the fix promised in the general response.
- ASM leads when one class dominates every client, and unlike Ward it has a minimum cluster size, which the second requirement needs.
1. Scorecard
Reference: FedGEM given the true local counts. Accuracy (benchmarks: mean of partitions A and B): ● within 0.03 ARI of the reference or above; ◐ 0.03–0.10 below; ○ more than 0.10 below; ✗ fails. Time and peak memory per client at 120K–300K points: ● under 30 s, under 0.25 GB; ◐ 30–300 s, 0.25–1 GB; ○ over 300 s, over 1 GB; ✗ out of memory. (sample): fitted on a 10K sample of each larger client, with the count read from that fit. ASM (refit), as submitted, also chooses its settings on the sample but then refits on the whole client; Ward (full) runs on the whole client.
| Method | Benchmarks | High dim. | Large clients | 100–200 clients | Dominant class | Time | Memory |
|---|---|---|---|---|---|---|---|
| ASM (refit) | ● | ● (○ at 64) | ◐ | ○ | ◐ (−0.04) | ◐ | ● |
| ASM (sample) | ● | ● | ● | ● | ◐ (−0.08) | ◐ | ● |
| Ward (full) | ● | ● | ● to 70K, then ✗ | ● | ◐ (−0.08) | ○, then ✗ | ✗ |
| Ward (sample) | ● | ● | ● | ● | ◐ (−0.08) | ● | ◐ |
| HDBSCAN (sample) | ● | ○ | ● | ● | ◐ (−0.10) | ● | ● |
| DBSCAN (sample) | ○ | ✗ from 64 | ● | ● | ○ (−0.12) | ● | ● |
| DP-GMM (sample) | ○ | ✗ from 256 | ○ | ● | ○ (−0.13) | ◐ | ● |
| X-means | ◐ | ● | ○ / ✗ | ◐ | ◐ (−0.06) | ◐ | ● |
| G-means | ○ | ✗ | ✗ | ✗ | ○ (−0.12) | ◐ | ● |
Large clients: 2-D, 10K–200K points each; X-means' ✗: FedGEM timed out on its counts from 500K points. Dominant class: section 2, ARI gap in brackets.
On the benchmarks, ASM as submitted and Ward tie (paired p = 0.60): Ward leads in partition A, ASM in partition B. The other methods each fall short somewhere: HDBSCAN falls well behind in high dimension, DBSCAN and G-means collapse, DP-GMM breaks down from 256 dimensions, and FedGEM times out on X-means' counts at scale. Sampling makes every method cheap on large clients; Ward is faster than ASM, and ASM uses less memory than Ward.
2. New: clients dominated by one class
Partition B decouples client size from the number of classes; here one class is held by every client and makes up 30%, 50% or 70% of its data, as normal operation would at every site (MNIST, FMNIST, CIFAR-10; 5 or 10 clients; 10 seeds; 180 paired runs per method):
| Method | ARI | Final global count (true 10) | Local count error (signed) | ASM significantly ahead? (p) |
|---|---|---|---|---|
| Reference | 0.298 | 12.1 | 0 | – |
| ASM | 0.257 | 11.5 | 2.9 (−1.1) | – |
| X-means | 0.242 | 25.9 | 15.9 (+13.0) | No (0.27) |
| Ward | 0.214 | 8.5 | 3.8 (−2.9) | Yes (4 × 10⁻⁸) |
| HDBSCAN | 0.201 | 6.9 | 3.6 (−3.4) | Yes (1 × 10⁻¹⁰) |
| G-means | 0.182 | 118.5 | 69.5 (+68.4) | Yes (3 × 10⁻⁵) |
| DBSCAN | 0.182 | 5.9 | 4.1 (−3.9) | Yes (1 × 10⁻¹⁴) |
| DP-GMM | 0.169 | 7.1 | 3.9 (−3.3) | Yes (4 × 10⁻¹²) |
ASM has the highest ARI, the lowest local count error and the final count closest to the reference's; X-means comes close on ARI only by over-counting. HDBSCAN, DBSCAN and DP-GMM end with too few global clusters because they under-count on most clients, reporting the dominant class and little else; FedGEM cannot split these components back apart. ASM under-counts too, but by less. Against Ward the gap widens with dominance: the two tie at 30%, and ASM leads 0.250 to 0.194 at 50% and 0.150 to 0.098 at 70%, where Ward's silhouette choice often collapses to the dominant class against the rest.
3. Other points
- Minimum cluster size. Ward returned a cluster of fewer than 10 points on 29 of 1,350 clients, one a single point whose mean is the point itself; as for DisCGS (general response), the second requirement rules this out. ASM's minimum mass prevents it.
- DisCGS (pSMT): competitive in accuracy, but needs a concentration setting shared by all sites; about 11–19 hours at 1M points against 4–5 minutes.
- The merge (pSMT, TtzZ): it raises ARI where splitting over-fragments, most on large clients, but cannot fully undo it there.
- ASM or FedGEM (TtzZ): FedGEM does not correct wrong local counts, and under-counting costs the most.
- 2-D shapes (pSMT): circles and spirals defeat every method, even with the true counts, a limit of FedGEM's Gaussian phase.
- NMI, AMI and ACC (pSMT): the same conclusions as ARI.
The revised submission will add all of these results, both versions of ASM and the limitations above.
We clarify the problem setting and its two requirements, the contributions (the modular framework, ASM and its analysis, and partition B), and how the work differs from DC-DPM, DisCGS and clustered federated learning.
We thank all three reviewers. Their feedback has improved our work. Some common questions were related to the novelty, contribution and positioning of the work. This response answers these points together. Follow-up responses will answer the methodological and analysis questions and compare all the methods on accuracy and cost.
The problem setting
An OEM supplies equipment to independently operated sites around the world and needs to learn how that equipment behaves across all of them (Section 1, lines 35–51). The data stay with the sites, which do not communicate with one another, run their own operational and maintenance regimes, and exchange only parameters and summaries with the OEM. Two requirements follow:
Each site therefore estimates its count alone, without labels, and federation happens in the aggregation phase. This answers Reviewer utyU's point that the first phase does not use federation.
Novelty and contributions
What is new is the framework, the first contribution listed in the submission (lines 76–80): the constraints of the setting (the two requirements described above), a modular two-phase design in which any method that estimates the number of clusters can serve as the first phase, and a mechanism for evaluating methods under these constraints. Partition B, which decouples client size from the number of classes a client holds, is part of this mechanism and the submission's fourth contribution (lines 90–94).
ASM itself combines established techniques, as Reviewers TtzZ and utyU note, but the parts are not an ad hoc assembly. The analysis of Section 4, which all three reviewers list as a strength, accounts for each of them, including why the merge is needed; the follow-up responses report what the merge does and where it fails.
As our results in the submission also show, ASM is a strong instance of per-client label-free count selection, but not the only one. We understand the reviewers' concerns and ran a comprehensive evaluation; the follow-up comments report it, and our closing comment summarises it. In brief:
To address ASM's weakness on large clients, we added ASM (sample), which reads its count from a 10K sample of each client; sampling is a standard way to scale hierarchical clustering (closing comment, scorecard).
Positioning
DisCGS is more accurate than ASM + FedGEM on MNIST, on both Frog datasets in partition B and, with the better of its two settings, in 2D runs. These results rely on conditions our setting rules out:
Since our setting rules these out, we do not consider it a like-for-like comparison.
Clustered federated learning. Sattler et al. (2021) and Vardhan et al. (2023) group clients by their models rather than data points, and their procedures also differ from ASM's in structure. Sattler et al. only split: a group is divided recursively and never recombined. ASM follows its splits with a merge, which our experiments show is essential. Vardhan et al. take the opposite route: they first group clients by a distance threshold and then repeatedly reassign and merge them, with no split step. ASM is the only one of the three that splits first and then merges. The revised submission will discuss both papers.
Changes in the revised submission