acceptodds
Under review as a conference paper at ICLR 2027

Federated Clustering with Unknown Local and Global Cluster Cardinalities

Abstract

Federated clustering methods that do not require the global number of clusters still assume that each client knows its local number . This assumption is hard to justify when clients know no more about their data than the server does, as in fault diagnosis across independently operated industrial sites. We propose a two-phase framework in which neither count is known: each client first estimates from its own data, and an aggregator that requires local counts, such as FedGEM, then uses these estimates in place of the true values. For the first phase we introduce Adaptive Split–Merge (ASM), which grows a spherical Gaussian mixture by BIC-driven splitting and then merges excess components. ASM uses no labels, selects its hyperparameters on held-out client data only, and makes no assumption about how clusters are shared across clients. We derive a closed-form split criterion whose critical cluster size falls with anisotropy and rises with dimension, and show empirically that over-fragmentation grows with the number of points per cluster, which federation divides among clients. Across eight datasets, ASM with FedGEM attains a mean ARI of 0.333, against 0.256 for the next best label-free estimator and 0.361 when the true local counts are supplied. It also gives the most reliable global estimates of and is robust when client size is decoupled from local cardinality.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Federated learning, clustering, model selection, estimating the number of clusters, unsupervised learning, split-merge

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_pSMTOpenReview ↗
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
AuthorsOpenReview ↗

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:

  • No joint tuning (lines 46–48). No site sees another's data, so settings cannot be tuned across sites or between a site and the OEM.
  • *Each site decides how much detail it shares (lines 57–62). The more components a site reports, the more of its operation it reveals, and one component per data point would hand over the raw data, so the site must choose this level itself.

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:

  • on the real benchmarks ASM is within about 0.02 ARI of the best first-phase method on average, and best in partition B;
  • on 2,000-point clients its median count error is zero from 16 to 512 dimensions, while DP-GMM and G-means break down as dimension grows, X-means at 512, and HDBSCAN and DBSCAN under-count throughout;
  • its cost per client stays nearly flat as clients grow, and at 1M points the complete pipeline takes about 4 minutes, against an estimated 11–19 hours for DisCGS.

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:

  • DC-DPM and DisCGS share one prior across workers, which DisCGS centres on all sites' pooled data (its Section 5.1), and re-draw local clusters every round with no minimum size, so a one-point cluster sends the point itself. Both requirements forbid this.
  • DisCGS gives no rule for its concentration (its Section 5.5), and its two released settings swap places between our data families, with no label-free way to choose.
  • It is also 3–16 times slower.

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

  • Related Work: DC-DPM, DisCGS and clustered federated learning; a sentence that overstated the gap in the literature will be corrected.
  • Table 1: a new column for per-client tuning without shared settings.
  • The contributions restated as above, with the split step presented as standard.
AuthorsOpenReview ↗

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:

DatasetPart.DisCGSASM-S
WaveformA0.0000.253
AbaloneA0.0980.097
Frog AA0.6220.639
Frog BA0.3880.376
MNISTA0.4730.429
WaveformB0.0000.283
AbaloneB0.1020.095
Frog AB0.8680.563
Frog BB0.5820.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:

FamilyPointsDisCGS, synthetic setting (ARI, time)DisCGS, real-data setting (ARI, time)ASM + FedGEM (ARI, time)
Easy100K0.849, 8.3 min0.630, 6.9 min0.811, 1.9 min
Easy200K0.872, 29 min0.760, 22 min0.862, 2.4 min
Hard100K0.639, 12.5 min0.781, 7.1 min0.727, 2.3 min
Hard200K0.503, 39 min0.742, 29 min0.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.

AuthorsOpenReview ↗

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)100K200K500K1M2M
ASM (sample) + FedGEM0.780.790.750.730.67
FedGEM, true counts0.780.800.750.650.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:

ShapeASM-SDP-GMMX-meansG-meansKnown count
Isotropic blobs0.9030.6520.8690.9020.924
Anisotropic blobs0.4400.3900.2780.4540.506
Two moons0.2070.2410.1870.2170.424
Circles0.0160.1290.1360.155−0.001
Spirals0.0120.0110.0050.0020.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):

MethodARINMIAMIACC
ASM-S0.333 / 0.3470.437 / 0.4440.435 / 0.4420.465 / 0.479
DP-GMM0.214 / 0.2400.416 / 0.4310.409 / 0.4250.345 / 0.361
X-means0.256 / 0.2990.420 / 0.4440.414 / 0.4390.385 / 0.425
G-means†0.162 / 0.1900.395 / 0.4370.378 / 0.4250.266 / 0.268
Known count0.361 / 0.3420.440 / 0.4230.437 / 0.4210.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.

AuthorsOpenReview ↗

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.

MethodBenchmarksHigh dim.Large clients100–200 clientsDominant classTimeMemory
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):

MethodARIFinal global count (true 10)Local count error (signed)ASM significantly ahead? (p)
Reference0.29812.10–
ASM0.25711.52.9 (−1.1)–
X-means0.24225.915.9 (+13.0)No (0.27)
Ward0.2148.53.8 (−2.9)Yes (4 × 10⁻⁸)
HDBSCAN0.2016.93.6 (−3.4)Yes (1 × 10⁻¹⁰)
G-means0.182118.569.5 (+68.4)Yes (3 × 10⁻⁵)
DBSCAN0.1825.94.1 (−3.9)Yes (1 × 10⁻¹⁴)
DP-GMM0.1697.13.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.

Reviewer_TtzZOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper addresses federated clustering when neither local nor global cluster cardinalities are known. The authors propose a two-stage framework that uses Adaptive Split–Merge (ASM) to estimate local cluster counts, followed by FedGEM for global aggregation. The paper also provides a theoretical analysis of the splitting behavior and evaluates the approach on eight datasets. Experimental results show competitive clustering performance without requiring the true local cluster cardinalities.

Critical strengths
  1. The paper addresses a meaningful limitation of existing federated clustering methods, which often require clients to know their local cluster counts. The experimental results demonstrate that competitive clustering performance can be achieved without this prior knowledge.
  2. The analysis provides useful insights into how data geometry, dimensionality, and sample size affect the splitting behavior. The experiments further investigate the role of merging and the robustness of the proposed approach under different client data partitions.
Critical weaknesses
  1. ASM mainly combines established techniques, including PCA-based initialization, EM fitting, BIC-driven splitting, and merging. Although the combination is reasonable, the methodological contribution appears somewhat incremental.
  2. While the authors provide merging ablations in the centralized setting, a direct comparison between ASM with and without merging in the federated pipeline is missing. Such experiments would help clarify the contribution of the merging stage to the final performance.
  3. Although the final ARI approaches that of Oracle-K, the reported local cardinality estimation errors remain relatively large. It is therefore unclear whether the performance improvements primarily result from accurate local cardinality estimation or from FedGEM’s ability to tolerate estimation errors.
Questions for authors
  1. Could the authors provide an end-to-end comparison between ASM-SplitOnly and ASM-SplitMerge under the same FedGEM aggregator, reporting local cardinality errors, global cardinality errors, and global ARI?
  2. Given the relatively large local cardinality estimation errors, could the authors clarify whether the near-oracle performance mainly comes from ASM’s estimation capability or FedGEM’s robustness to inaccurate local cluster counts?
5 comments
AuthorsOpenReview ↗

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:

  • No joint tuning (lines 46–48). No site sees another's data, so settings cannot be tuned across sites or between a site and the OEM.
  • Each site decides how much detail it shares (lines 57–62). The more components a site reports, the more of its operation it reveals, and one component per data point would hand over the raw data, so the site must choose this level itself.

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:

  • on the real benchmarks ASM is within about 0.02 ARI of the best first-phase method on average, and best in partition B;
  • on 2,000-point clients its median count error is zero from 16 to 512 dimensions, while DP-GMM and G-means break down as dimension grows, X-means at 512, and HDBSCAN and DBSCAN under-count throughout;
  • its cost per client stays nearly flat as clients grow, and at 1M points the complete pipeline takes about 4 minutes, against an estimated 11–19 hours for DisCGS.

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:

  • DC-DPM and DisCGS share one prior across workers, which DisCGS centres on all sites' pooled data (its Section 5.1), and re-draw local clusters every round with no minimum size, so a one-point cluster sends the point itself. Both requirements forbid this.
  • DisCGS gives no rule for its concentration (its Section 5.5), and its two released settings swap places between our data families, with no label-free way to choose.
  • It is also 3–16 times slower.

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

  • Related Work: DC-DPM, DisCGS and clustered federated learning; a sentence that overstated the gap in the literature will be corrected.
  • Table 1: a new column for per-client tuning without shared settings.
  • The contributions restated as above, with the split step presented as standard.
AuthorsOpenReview ↗

Answer to Question 1

We thank the reviewer for their careful reviews.

Split-only versus split–merge under the same FedGEM aggregator. We used the same clients, the same per-client split settings and the same FedGEM radius, and changed only the merge: switched off (S, α = 0) or set by the label-free rule (S+M). The data are benchmark partitions A and B, with 400 to 2,600 points per client, over 10 seeds. Each cell reads S → S+M.

Dataset (K)Local error, AGlobal error, AARI, ALocal error, BGlobal error, BARI, B
Waveform (3)5.12 → 1.1014.6 → 1.50.158 → 0.2587.40 → 1.0421.5 → 1.40.139 → 0.280
Abalone (8)1.80 → 1.803.1 → 3.10.089 → 0.0892.04 → 2.004.0 → 4.20.093 → 0.092
Frog A (10)3.04 → 2.684.2 → 3.70.644 → 0.6342.48 → 2.582.2 → 2.30.573 → 0.651
Frog B (8)3.40 → 2.705.9 → 3.40.344 → 0.4013.54 → 3.164.6 → 3.00.435 → 0.442
MNIST (10)2.35 → 2.5412.7 → 8.50.390 → 0.4182.67 → 2.6810.0 → 4.70.419 → 0.420
CIFAR-10 (10)2.50 → 2.8123.7 → 20.90.383 → 0.3802.53 → 2.7523.3 → 21.70.372 → 0.379
FMNIST (10)2.37 → 2.377.0 → 7.00.250 → 0.2502.62 → 2.624.4 → 4.40.274 → 0.274
EMNIST (47)10.97 → 13.4013.9 → 7.30.247 → 0.23713.87 → 15.6429.5 → 7.10.253 → 0.240
Average3.94 → 3.6810.6 → 6.90.313 → 0.3334.64 → 4.0612.4 → 6.10.320 → 0.347
p0.80< 10⁻⁵0.070.93< 10⁻⁹0.04
  • Global count error reduces in both partitions. It falls by about a third in partition A, and by about half in partition B. This is the merge’s clearest effect on the federated output.
  • ARI improves on average: by 0.020 in A and 0.027 in B, and p = 0.006 over both partitions together. The gains are largest where clients are over-split (Waveform +0.10 and +0.14), and no dataset loses more than 0.013.
  • Local count error changes little on these small clients, where the split mostly under-splits. The merge sharply corrects over-split clients (Waveform 5.1 → 1.1) and slightly raises the error on EMNIST, MNIST and CIFAR-10. Even there the global error falls, because the duplicates it removes would otherwise have reached the server.

On large clients splitting tends to over-split, so the merge matters more. Here clients hold 1,700 to 15,500 points, in 3, 5 or 10 clients or with one dominant class, over 5 seeds, and the true K is 10:

DatasetLocal errorGlobal errorARIKnown-count ARI
MNIST25.1 → 10.468.9 → 34.60.258 → 0.3010.427
CIFAR-1024.6 → 20.254.8 → 47.10.260 → 0.2810.527
FMNIST20.1 → 20.125.5 → 25.50.226 → 0.2260.209
All (p)23.3 → 16.9 (p ≤ 0.001)49.7 → 35.7 (p ≤ 0.001)0.248 → 0.269 (p ≤ 0.001)0.388

The merge reduces all three errors significantly and wins 32 of the 40 runs it changes; on FMNIST it triggers no merges. On clients of 70K to 200K points, splitting alone leaves 25 to 311 components per client for 5 to 7 true clusters, and the merge brings all 16 tested clients to within 0 to 3 of the truth. At this scale ASM still falls short of the known-count result, because its count stays too high after merging. The merge is necessary and helpful, but the current rule is not in its most optimized form, and we will state this as a limitation.

Revisions. We will add both split-only versus split–merge tables to the appendix of the revised submission and state the merge rule's limits on large clients as a limitation. We will answer the reviewer's remaining questions in a follow-up comment.

AuthorsOpenReview ↗

Answer to Question 2

Does the accuracy come from ASM's estimates or from FedGEM's tolerance? (Q2)

Mainly from ASM's estimates. FedGEM does not correct wrong local counts, and it absorbs error in one direction only: it loses little when counts are too high by up to about half, and much more when they are too low.

How FedGEM responds to wrong local counts. We changed every client's true count at once by the same percentage, on all eight datasets, both partitions and 10 seeds (800 runs), with everything else fixed. After rounding to whole clusters, the actual changes average ±30% and ±53%. Change from FedGEM given the true counts (Oracle-K), mean over the 16 dataset–partition pairs:

Change to every local count−50%−25%+25%+50%
ARI−0.110−0.061−0.005−0.015
ARI, without Waveform−0.078−0.021+0.005−0.006
Global count, relative to Oracle-K0.490.721.301.51

The global count moves in proportion to the local counts. Waveform, whose clients hold two classes each, collapses to one cluster under any under-count.

ASM's errors. ASM's local error is 3.7 clusters per client in partition A and 4.1 in B, about half the true local count (relative error 0.47 and 0.51, Table 12). It is, however, among the lowest of the label-free first phases. Means over the eight datasets (G-means: six datasets in A and partial seeds on CIFAR-10 and EMNIST in B, where FedGEM timed out.):

First phaseLocal count error per client (A, B)ARI (A, B)
Ward2.9, 3.20.355, 0.330
HDBSCAN3.6, 4.10.337, 0.341
ASM3.7, 4.10.333, 0.347
DBSCAN5.6, 5.70.248, 0.245
X-means9.4, 7.50.256, 0.299
DP-GMM10.1, 11.90.214, 0.240
G-means45.4, 35.10.162, 0.190
Oracle-K0, 00.361, 0.342

Two more results point the same way. Giving every client the same count of 2, 5 or 10 instead of ASM's estimate lowers ARI in partition A from 0.333 to 0.203, 0.312 and 0.291, and each fixed count fails on some dataset. On Waveform, ASM's error is about one cluster per client, and its ARI (0.258 in A, 0.280 in B) is close to that of FedGEM given one extra cluster on every client (0.254, 0.266).

The revised submission will add FedGEM's response to wrong counts and the local count errors of every first-phase method.

Why a split followed by a merge. ASM is not an ad-hoc combination of techniques. As shown, FedGEM needs local counts within the range it can absorb, and ASM is designed to try to keep them there.

In an idealised setting (isotropic Gaussian clusters with a known common covariance, well separated, each holding a minimum share of the client’s data), a fitted mixture at which EM has stopped can be wrong in only six ways. ASM’s split step handles five:

  • label permutation is only a relabelling,
  • covariance collapse cannot occur, since covariances are fixed (isotropic),
  • saddle points are unstable, and the split’s eigenvector perturbation moves the fit off them,
  • empty components are blocked by the minimum-mass threshold,
  • one component covering several clusters is removed by the BIC split test, whose likelihood gain grows linearly with the number of points while its penalty grows only logarithmically.

The sixth failure, several components covering one cluster, needs a merge. Splitting creates it: recursive binary splits of {A, B, C} can end as {A, B₁, B₂, C}. Splitting also cannot detect it, because each duplicate holds a single cluster, so a test on one component at a time leaves it alone. ASM therefore merges after splitting. In the analysis the merge uses FedGEM’s own overlap radius locally, and under the separation FedGEM already assumes it merges every pair of duplicates and never merges distinct clusters (we will add this result to the revised submission). On the other hand, the implemented ASM merges two components when their means are within α(σᵢ + σⱼ), with α chosen per client by the label-free silhouette rule (α = 0 switches the merge off).

Our contribution is a modular two-phase framework for federated clustering, and a first-phase algorithm with a theoretical analysis of when it works and when it fails, and the exact failure modes our design is aimed to tackle. In our experiments this first phase algorithm proposed is also competitive in accuracy and scales easily to large clients.

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

The paper handles the problem of federated clustering where both the local and the global number of clusters is not known. Existing methods, like FedGEM, require the knowledge of local number of clusters to run.

The authors propose the approach ASM (Algorithm 1) to estimate the local number of clusters on each client. The first step of ASM is a split step wherein the authors use fit a single cluster to all the client data. Then, using the mean and largest singular value and vector of covariance, the authors propose 2 initial means. Using these initial means, the authors use EM to fit two clusters to a single cluster. If the 2 cluster fit obtains better BIC (Bayesian Information Criterion) than a single cluster for the given data, the authors split the cluster, and if not then they retain a single cluster. They repeat this process until no cluster can be split on the client and the mass of each of the split clusters is greater than a threshold. After the split step, the authors merge clusters whose means are close to each other according to Eq (2).

Finally, the authors use ASM as the first stage and an algorithm that doesn't require local number of clusters like FedGEM as the second stage to obtain both the local and global number of clusters.

The authors compare their method of obtaining local number of clusters on a gaussian baseline, where they can exactly map out the theoretical impacts of splitting and merging in Fig 1 and 2. An important consequence of this analysis is the impact of cluster size, dimension and impact of anisotropy on the splitting scheme.

In Table 1, the authors compare their algorithm ASM to other algorithms that determine number of clusters like X-Means, G-Means, DP-GMM and K-Means with correct number of clusters. They compare the ARI (Adjusted Rand Index) of these methods and the estimated number of clusters. They consider 4 tabular datasets (Waveform, Abalone, FrogA and FrogB) where their performance in terms of estimated number of clusters is best. They also test on 4 image datasets (MNIST, FMNIST, EMNIST, CIFAR-10), where their performance is not the best.

In Federated settings, they consider two regimes A and B where A considers client cluster sizes to grow with local number of clusters and B does not. Under regime A, in Table 4, their method obtains smallest deviation to actual cluster size for most datasets, however, some baselines, like DP-GMM obtain a smaller deviation for some datasets. Similar results hold under Regime B in Table 9.

Critical strengths
  • The authors identify a key problem of local number of clusters being unknown. Several federated clustering algorithms seem to ignore this information, but the authors sufficiently motivate this as a fundamental issue.
  • The analysis for single gaussian case provides some theoretical backing to their scheme and reveals the role of anisotropy, dimension and cluster sizes.
  • The supplementary experiments seem very exhaustive.
Critical weaknesses
  • Scheme doesn't use federation: Their scheme doesn't rely on federation, and the only effective way to use it is via another algorithm like FedGEM. This might not be the best way to utilize the fact that different clients do have similar data that could potentially help in just estimating the number of clusters rather than fully clustering.

  • Local cluster sizes can be small for real federated datasets: Their scheme heavily depends on the cluster sizes being reasonable. This might not often be the scenario in FL where some local clients can have very few points from a given cluster. As their experiments did not cover any real federated datasets, for instance FEMNIST in the Leaf database (Caldas et al 2019), it is unclear if their methods would work for real federated learning applications. Note that several real federated datasets are designed to mimic such small local cluster sizes.

  • Core Novelty is only the merge step: Algorithmically, the split step in their method is extremely similar to the baselines of X-Means and G-Means. The only novelty in the whole scheme is then to use the merge step. This severely limits the contribution. The authors do justify the necessity of a merge step, but, in the current form, I feel this is insufficient.

  • Comparisons are lacking: Several competing methods for this problem have not been applied. First, there are methods that perform bottom-up agglomerative clustering methods like Ward's method (Ward, 1963), that can be applied appropriately to compute the number of clusters by merging datapoints instead of splitting and merging. Second, to solve the clustering problem, methods like DBSCAN (Ester et al 1996) also do not require the number of clusters, rather only the distance between them and their minimum size. Third, for clustered FL, similar to (Ghosh et al 2020), there have been methods (Sattler et al 2021, Vardhan et al 2021) that don't require the number of clusters. Although these are clustered FL where models are clustered, the ideas in these papers like the split and merge steps resemble those used here.

  • Performance of ASM is not always better in both estimated cluster sizes and ARI: For image datasets, ASM-S doesn't seem to be the best method in either ARI or estimated number of clusters for any dataset. DP-GMM is much better on estimated number and G-Means is much better on ARI. Also, if ARI of K-Means is poor on image datasets than other methods, does it not mean that ARI is not the correct metric or K-Means is not the correct algorithm for image datasets. Clustering raw pixels using K-Means does not seem like a reasonable approach. In the federated cases of Regime A and B, ASM seems to be best or close to best for most cases. Why is there a difference in Table 1 and Table 4 or 9? Does ASM have more benefit than these baselines in Federated Setting.

  • Presentation issues: The main algorithm and one of the main results in Table 9 have been moved to the appendix although there is space in the main draft.

  • Computational Cost: ASM and X-Means/G-Means are methods that need to perform full EM updates at every split. This might not be computationally feasible. Although, the authors compare the wall-clock time in Table 5 and complexity in Table 13, for high-dimensional datasets where the base clustering algorithm is not computationally efficient like K-Means, such methods might be very slow. Can the authors comment on this ?

References

  • (Caldas et al 2019) LEAF: A Benchmark for Federated Settings.
  • (Ward 1963) Hierarchical Grouping to Optimize an Objective Function.
  • (Ester et al 1996) A density-based algorithm for discovering clusters in large spatial databases with noise.
  • (Sattler et al 2021) Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints.
  • (Vardhan et al 2023) An Improved Federated Clustering Algorithm with Model-based Clustering.
Questions for authors

Please see weaknesses.

4 comments
AuthorsOpenReview ↗

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:

  • No joint tuning (lines 46–48). No site sees another's data, so settings cannot be tuned across sites or between a site and the OEM.
  • Each site decides how much detail it shares (lines 57–62). The more components a site reports, the more of its operation it reveals, and one component per data point would hand over the raw data, so the site must choose this level itself.

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:

  • on the real benchmarks ASM is within about 0.02 ARI of the best first-phase method on average, and best in partition B;
  • on 2,000-point clients its median count error is zero from 16 to 512 dimensions, while DP-GMM and G-means break down as dimension grows, X-means at 512, and HDBSCAN and DBSCAN under-count throughout;
  • its cost per client stays nearly flat as clients grow, and at 1M points the complete pipeline takes about 4 minutes, against an estimated 11–19 hours for DisCGS.

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:

  • DC-DPM and DisCGS share one prior across workers, which DisCGS centres on all sites' pooled data (its Section 5.1), and re-draw local clusters every round with no minimum size, so a one-point cluster sends the point itself. Both requirements forbid this.
  • DisCGS gives no rule for its concentration (its Section 5.5), and its two released settings swap places between our data families, with no label-free way to choose.
  • It is also 3–16 times slower.

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

  • Related Work: DC-DPM, DisCGS and clustered federated learning; a sentence that overstated the gap in the literature will be corrected.
  • Table 1: a new column for per-client tuning without shared settings.
  • The contributions restated as above, with the split step presented as standard.
AuthorsOpenReview ↗

Ward, DBSCAN and HDBSCAN as the first phase (1/2)

We thank the reviewer for the careful review and the suggested comparisons. Our general response answers the points on the use of federation, novelty and clustered federated learning.

1. Ward, DBSCAN and HDBSCAN as the first phase. Each chooses its settings per client with the same label-free held-out silhouette as ASM, and FedGEM's setting is chosen without labels. Federated ARI, seeds 42–51, as (partition A, partition B):

DatasetDBSCANHDBSCANWardASM-S
Waveform0.074, 0.0590.290, 0.3040.339, 0.3360.258, 0.280
Abalone0.082, 0.0680.081, 0.0810.062, 0.0770.089, 0.092
Frog A0.603, 0.5870.635, 0.6710.651, 0.6240.634, 0.651
Frog B0.377, 0.3510.399, 0.3820.474, 0.3750.401, 0.442
MNIST0.205, 0.2150.395, 0.3910.421, 0.3840.418, 0.420
FMNIST0.184, 0.1910.260, 0.2580.272, 0.2390.250, 0.274
EMNIST0.123, 0.1130.238, 0.2410.243, 0.2390.237, 0.240
CIFAR-100.336, 0.3760.395, 0.4010.380, 0.3620.380, 0.379
Average0.248, 0.2450.337, 0.3410.355, 0.3300.333, 0.347

ASM and Ward tie overall (paired Wilcoxon p = 0.60): Ward leads in partition A, and ASM in partition B on 7 of 8 datasets. HDBSCAN is close, and DBSCAN well behind. In our other experiments:

  • High dimension (16–256 dimensions). Ward matches FedGEM given the true counts, and ASM as submitted is close except at 64 dimensions (0.804 against 0.917). HDBSCAN and DBSCAN under-count (exact on 0–27% of clients), and DBSCAN collapses to one cluster from 64 dimensions.
  • Large and many clients (2D, up to 240K points per client or up to 200 clients). Here we scale ASM and Ward the standard way for hierarchical clustering: each chooses its settings on a 10K sample of the client and reads the count from that fit. These sampled versions tie over all 39 designs (p = 0.83), and both reach the true-count level.

Tuned by the same label-free rule, Ward's method matches ASM in accuracy, although one returns a partition and the other a Gaussian mixture. We see this as support for the framework rather than against ASM: the modular design, the submission's first contribution, lets any label-free count estimator serve as the first phase, and here two quite different ones both come close to the true-count level. However, Ward's method requires candidate counts to be fixed in advance (we searched k = 2 to 50), and cannot return a count outside it. ASM needs no such bound and finds the count from the site's data alone and yet performs competitively.

AuthorsOpenReview ↗

Computational cost; centralized versus federated results (2/2)

2. Computational cost. ASM does not run a full EM at every split: a split test fits one and two components with at most 15 EM steps each, on the points of one component only (Table 13). Its components are spherical, so no covariance matrix is formed and the cost per EM step grows linearly with dimension; on 2,000-point clients a complete ASM fit, tuning included, takes 8–91 s up to 512 dimensions. On large clients ASM, like every baseline, can choose its settings on a 10K sample and read its count from that fit. It then takes about 2 minutes and under 0.1 GB per client at 240K points, and the complete pipeline at 1M points takes around 4 minutes. The scorecard in our closing comment compares the time and memory of every method.

Overall, ASM and Ward, both tuned without labels, are the most consistently accurate first phases across our experiments (closing comment, scorecard), and either can instantiate the framework. Unlike Ward, ASM needs no candidate range for the count, and its minimum mass keeps it from reporting a cluster small enough to expose raw data.

3. Centralized versus federated results. The image datasets are the variational-autoencoder embeddings released with the FedGEM benchmark (Section 5), not raw pixels. We use two references, not upper bounds. In the pooled benchmark (Table 2), k-means given the true K has the highest ARI on every image dataset (0.33–0.65), so the embeddings do separate the classes. In the federated tables, the reference is FedGEM given each client's true count. Because FedGEM's accuracy does not rise steadily as local counts improve, on some image datasets a label-free method scores slightly higher, by at most 0.03 ARI.

The centralized and federated tables differ because they test different amounts of data per cluster. In the centralized results one client holds an entire dataset, with thousands of points per cluster; in the federated partitions, each client holds a few hundred to a few thousand points. Section 4 shows that the split test becomes more permissive as the points per cluster grow, and on the pooled image embeddings ASM over-estimates K by a factor of 4 to 15. Federation divides each cluster among clients, which brings each client back to the range where ASM's count is accurate. For clients far larger than our benchmark's, the sample-based version of ASM chooses its settings on a fixed-size sample and takes the count from that fit, and on 50K-point clients it recovers every count exactly.

4. The merge step. We agree that the split step is standard. In an idealised Gaussian setting, a fitted mixture can be wrong in six ways. The split step handles five; the sixth, several components covering one cluster, is created by splitting and cannot be detected by it, so it needs a merge. In the federated pipeline, the merge cuts the global count error by a third in partition A and by half in B and raises ARI (p = 0.006); on large clients it wins 32 of the 40 runs it changes. (Please refer to our response to TtzZ reviewer for a more detailed explanation).

5. Small local clusters. Our evaluation already contains small local clusters, in two places:

  • Partition B decouples client size from the number of classes, so a client holding many classes holds small ones. On MNIST, FMNIST, CIFAR-10 and EMNIST, 16–36% of local clusters hold fewer than 50 points (the smallest 20–24). ASM has the highest ARI of any label-free first phase in partition B (0.347; HDBSCAN 0.341, Ward 0.33; true counts 0.342).
  • Frog A and Frog B have small clusters in both partitions: 38–41% of local clusters hold fewer than 50 points, the smallest 5–12. On Frog B in partition B ASM leads (0.442; next best 0.382), and on Frog A it is within 0.02 of the best.
  • Clients dominated by one class (closing comment) leave the other classes small on each client, and ASM has the highest ARI there.

FEMNIST is more extreme: its clients average about 230 points over 62 classes, about 4 points per class. In our setting a cluster of a few points would also come close to revealing raw data, which is why ASM's minimum mass rejects it. A class too rare on one client can still reach the server through clients that hold more of it.

Beyond our general response, the revised submission will add these comparisons, both versions of ASM, NMI, AMI and ACC, and the scaling study.

AuthorsOpenReview ↗

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.

MethodBenchmarksHigh dim.Large clients100–200 clientsDominant classTimeMemory
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):

MethodARIFinal global count (true 10)Local count error (signed)ASM significantly ahead? (p)
Reference0.29812.10–
ASM0.25711.52.9 (−1.1)–
X-means0.24225.915.9 (+13.0)No (0.27)
Ward0.2148.53.8 (−2.9)Yes (4 × 10⁻⁸)
HDBSCAN0.2016.93.6 (−3.4)Yes (1 × 10⁻¹⁰)
G-means0.182118.569.5 (+68.4)Yes (3 × 10⁻⁵)
DBSCAN0.1825.94.1 (−3.9)Yes (1 × 10⁻¹⁴)
DP-GMM0.1697.13.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.

Comments on the paper

1 comment

Dear Reviewers,

Thank you for your reviews.

The authors have posted their response. As the rebuttal period nears its end, could you please let us know whether the authors' responses address your main concerns? Also, would you consider updating your ratings based on the responses? If not, what are your main remaining concerns?

Your feedback would be appreciated.

Regards, AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.