PaperlayerView exact revision on arXiv

Source-linked AI summary

Federated Clustering with Unknown Local and Global Cluster Cardinalities

Mitushi Goyal, Tarun S., Riddhanya Senapathi, Arun Raman

arXiv:2609.36762v1cs.LGcs.DCstat.ML

TL;DR

Federated clustering methods that avoid a known global count may still require clients to know their local counts, even when sites cannot share raw data or reliably label it. The paper estimates local counts with a label-free split–merge method before federated aggregation. Across eight datasets, ASM-S with FedGEM attains a mean ARI of 0.333, compared with 0.256 for the next best label-free method and 0.361 with true local counts.

  • Problem

    FedGEM avoids requiring global K but assumes each client knows K_g, which is difficult to justify when sites know no more about fault classes than the OEM and cannot share raw sensor data.

    Source: §1 · p. 2

  • Method

    The framework has clients estimate K_g independently, then uses those estimates in a federated aggregator; ASM performs label-free BIC-driven splitting and merging with hyperparameters selected on held-out client data.

    Source: §1 · p. 2

  • Results

    0.333 mean ARI for ASM-S with FedGEM across eight datasets, versus 0.256 for the next best label-free method and 0.361 with true local counts; it also gives the most reliable global estimates and is robust to client size decoupled from K_g.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The framework lets a centralized local-count estimator and a federated aggregator that requires local counts be paired without modifying either phase.

    Source: §1 · p. 3

    On pooled image datasets, no single merge factor recovers the true count, and the silhouette objective does not always select the most accurate setting.

    Source: §6 · p. 12

Abstract

from arXiv · show

Federated clustering methods that do not require the global number of clusters $K$ still assume that each client knows its local number $K_g$. 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 $K_g$ 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 $K$ and is robust when client size is decoupled from local cardinality.

1 Introduction

The paper addresses federated clustering where neither clients nor the server can assume the local and global cluster counts are known. It proposes estimating local counts independently before aggregation, using ASM as a label-free local estimator.

1 Introduction

  • FedGEM does not require the global count K, but still assumes clients know K_g, an assumption that is difficult to justify when site operators know no more about fault classes than the OEM.Labels may be unreliable across sites, and raw sensor data cannot be shared.Source: §1 · p. 2
  • The framework separates local count estimation from federated reconciliation, allowing a client to choose its data granularity before the OEM reconciles descriptions through repeated parameter exchange.The phases reflect that sites cannot jointly tune hyperparameters but can exchange parameters and summaries.Source: §1 · pp. 2–3
  • ASM estimates local cardinality without labels by recursively splitting a spherical Gaussian mixture using BIC, merging excess components, and selecting hyperparameters on held-out client data.Candidate splits are initialized along the principal direction and fitted by EM.Source: §1 · pp. 2–3
  • The split criterion’s critical cluster size falls with anisotropy and rises with dimension; empirically, over-fragmentation grows with points per cluster and federation divides those points among clients.Beyond the critical size, splitting continues until the minimum-mass constraint binds.Source: §1 · p. 3
  • 0.333 mean ARI for ASM-S with FedGEM across eight datasets, versus 0.256 for the next best label-free method and 0.361 with true local counts.It also gives the most reliable global estimates, with |K_hat − K*| ≤21 versus up to 188 for DP-GMM and 263 for G-means, and is unaffected when client size is independent of K_g.Source: §1 · p. 3

2 Related work

Prior federated clustering methods address known or unknown global cardinality, while retaining other count inputs or targeting a different clustering task. The paper’s framework estimates both local and global counts from data.

2 Related work

  • Methods requiring a shared global K include k-FED, FedKmeans, and the federated fuzzy c-means variants FFCM-avg1 and FFCM-avg2.They differ in their procedures, but all require K at the server.Source: §2 · p. 3, Table 1 · p. 4
  • Among methods that do not require global K, FedGEM still takes each K_g as given, SPAHM aggregates models whose sizes were fixed beforehand, and published AFCL experiments initialize seeds using [K, 2K].AFCL’s initial seed count is set with reference to K, although it does not take K_g as input.Source: §2 · p. 4, Table 1 · p. 4
  • The paper presents its framework as estimating both K_g and K from data without cardinality inputs, supplying local counts to aggregators such as FedGEM.The authors state that, to their knowledge, no federated clustering method does both.Source: §2 · p. 4
  • ASM shares BIC-driven recursive splitting with X-means and principal-direction initialization with G-means, but adds EM fitting under a spherical Gaussian model, merging, and client-only hyperparameter selection.Its analysis of when BIC splitting fragments a single cluster applies to X-means-type estimators generally.Source: §2 · pp. 4–5
  • Clustered federated learning groups clients to train separate models, rather than clustering data points, so it is complementary to this paper’s problem.Source: §2 · p. 5

3 Problem setting

Clients hold non-IID data drawn from subsets of global clusters, and neither clients nor server know the local or global cardinalities. The goal is to estimate the global count and partition the pooled data without moving observations between clients.

3 Problem setting

  • Client-server communication is limited to parameters and summary statistics, and each client must select its hyperparameters using its own data alone.The local phase requires no iteration with the server.Source: §3 · p. 5
  • Clients differ in which global clusters they hold and in their cluster proportions, making local data distributions non-IID.Source: §3 · p. 5
  • The objective is to partition pooled data into global clusters and estimate K without moving data between clients.Source: §3 · p. 5
  • Each client first estimates K_g from its data; an aggregator such as FedGEM then uses those estimates to return global cluster parameters and K_hat.ASM uses Gaussian components as a working model, but neither the method nor experiments require Gaussian-mixture data; labels are used only to construct client subsets and evaluate results.Source: §3 · p. 5

4 Adaptive split–merge (ASM) algorithm and Analysis

ASM-S grows a client’s mixture through BIC-driven splits and greedy merges, with a split threshold that depends on cluster anisotropy and dimension. In pooled benchmarks, sample size drives over-fragmentation, and the merge rule works more reliably on tabular than image datasets.

4.1 Algorithm and Analysis

  • ASM starts with one component, splits along its leading covariance eigenvector when a two-component EM fit improves BIC and both children meet the minimum-mass threshold, then greedily merges nearby components.The surviving component count is the estimated local K_g; the merge criterion compares centroid distance with combined spread.Source: §4.1 · p. 6
  • The closed-form split rule is scale-invariant: its critical cluster size falls with anisotropy and rises with dimension, so sufficiently large elongated single clusters can be split spuriously.Because every cluster has a finite critical size, larger client datasets split more readily, making the merge stage essential.Source: §4.1 · p. 6
  • In the single-Gaussian tests, sample anisotropy explains the low-dimensional split-onset mismatch; recursive splitting then produced about 50 components at d = 8 and 20 at d = 16 from 500 points before merging.Using sample-measured anisotropy, the closed form reproduced the idealized split decision in 94–97% of draws.Source: §4.1 · p. 7

4.2 ASM on pooled benchmark data

  • On tabular datasets, ASM-S estimates stay close to K*, but on image datasets it overestimates K by a factor of 4 to 15.On Waveform and Abalone, ASM-S ARI matches k-means given K*; on Frog datasets it recovers the count but reaches about half the oracle ARI.Source: Table 2 · p. 8, §4.2 · p. 8
  • Reducing each image dataset to 25% of its points lowers ASM-S’s estimate by a factor of 3 to 5 and raises ARI on all four datasets, while oracle k-means is unchanged.The subsample is not an easier clustering problem; the reported comparison also re-selects hyperparameters on the subsample.Source: §4.2 · pp. 8–9, Table 3 · p. 9
  • Without merging, the split stage overestimates K on every pooled dataset by 1.5 to 15 times; on Waveform, merging reduces 28.8 components to three and triples ARI.The anisotropy-based bound predicts merge onset within one grid step on seven of eight datasets, but does not establish whether merging will stop at the correct count.Source: §4.2 · pp. 9–10
  • On image datasets, no single merge factor recovers K*: merging is absent over the tested range on FMNIST, while MNIST and EMNIST estimates can drop from tens of components to about one.The paper identifies the single-parameter merge rule as a possible main limitation of ASM-S on these data.Source: §4.2 · pp. 9–10

5 ASM in the Federated Setting

The federated evaluation tests whether locally estimated cluster counts support FedGEM across two client partitions, including one that decouples client size from local cardinality. ASM-S has the strongest mean ARI among label-free methods, reliable global-count estimates, and the lowest mean Phase 1 runtime.

Evaluation setup

  • Each client estimates its local cardinality on its own data, selects hyperparameters using held-out points, and passes only its estimate to FedGEM.The full pipeline compares ASM-S, DP-GMM, X-means, and G-means with an oracle supplying true local counts.Source: §5 · p. 10

Results under partition A

  • ASM-S’s global-count error never exceeds 21 and averages 6.9, compared with maxima of 188 for DP-GMM and 263 for G-means.The oracle’s average global-count error is 5.4.Source: §5 · p. 10
  • On MNIST, FMNIST, and CIFAR-10, ASM-S ARI rises from 0.162, 0.070, and 0.156 pooled to 0.418, 0.250, and 0.380 federated.The passage describes this pattern as consistent with smaller per-client cluster sizes.Source: §5 · p. 11
  • 0.333 mean ARI for ASM-S with FedGEM compares with 0.256 for X-means and 0.361 for the oracle supplying true local counts.ASM-S is within 0.03 of the oracle on five datasets and exceeds it on FrogA.Source: §5 · p. 10, Table 4 · p. 11

Results under partition B

  • ASM-S’s global-count relative error is statistically equivalent across partitions within ±0.2, while X-means and G-means change significantly on three and four datasets, respectively.Partition B draws client sizes independently of local cardinality; under partition A, client size grows almost in proportion to local cardinality.Source: §5 · pp. 10–11

Computational cost

  • 339 ms mean Phase 1 time per client makes ASM-S the fastest on six of eight datasets and the lowest-mean method.The mean is 558 ms for G-means, 1,110 ms for DP-GMM, and 1,943 ms for X-means; G-means is faster on MNIST and FMNIST.Source: §5 · p. 11, Table 5 · p. 12

6 Conclusion

The conclusion presents ASM as a label-free local estimator in a two-phase framework for federated clustering with unknown local and global counts. Its analysis and experiments identify when splitting fragments clusters and report strong federated results, alongside limitations in merge selection, privacy guarantees, and modeling assumptions.

Conclusion

  • The two-phase framework has clients estimate local counts independently and a federated aggregator reconcile them; ASM combines BIC-driven splitting with a merge stage.The setting assumes independent sites know no more about their cluster structure than the server.Source: §6 · p. 12
  • The critical cluster size falls with anisotropy and rises with dimension; beyond it, a single cluster fragments until the minimum-mass constraint binds.In that regime, the merge stage rather than the split criterion determines the final count.Source: §6 · p. 12
  • With FedGEM, ASM-S comes within 0.03 ARI of the oracle on five of eight datasets, gives the most reliable label-free global estimates, is robust to decoupled client size, and is fastest on average.On pooled benchmarks, over-fragmentation grows with points per class and shrinks when the sample is reduced.Source: §6 · p. 12

Limitations

  • On pooled image datasets, no single merge factor recovers the true count, and the silhouette objective does not always select the most accurate setting.Clusters dominating a site can exceed the critical size at every site, leaving their fragmentation to be corrected by merging or aggregation.Source: §6 · pp. 12–13
  • The paper provides no formal privacy guarantees and analyzes idealized Gaussian clusters, hard assignments, and population moments, quantifying their effects empirically rather than bounding them.Source: §6 · p. 13

Generative AI Usage Statement

The statement describes language-model assistance in writing, literature review, theory, methodology, implementation, and interpretation. The authors report checking derivations and numbers and taking responsibility for the paper’s content.

Generative AI Usage Statement

  • A language model assisted with drafting and editing text across the paper and suggesting keywords and the primary area.Source: Generative AI Usage Statement · p. 13
  • The assistant suggested related work and contributed to deriving the BIC split criterion, anisotropy threshold, merge-factor bound, and termination argument.Source: Generative AI Usage Statement · p. 13
  • The assistant proposed diagnostic experiments, wrote code and figures for one validation experiment, and assisted with ASM and pipeline implementation and debugging.The authors say they checked all derivations and reported numbers and take responsibility for the paper’s content.Source: Generative AI Usage Statement · p. 13

Supplementary material

ASM recursively tests component splits with a local BIC-style criterion, then greedily merges nearby components. Its closed-form analysis links the split threshold to cluster anisotropy and dimension.

A The ASM Algorithm pseudocode

  • ASM initializes one component, tests principal-direction binary splits with EM, accepts BIC-improving splits when both children meet the minimum effective mass, then greedily merges nearby components.Splitting repeats until no candidate is accepted; merging repeats until no eligible pair remains.Source: A The ASM Algorithm pseudocode · p. 16

B.1 The criterion

  • The split decision compares one- and two-component spherical Gaussian fits on the component’s own points, using a BIC-style score and the component term of the EM objective as its local log-likelihood.For two components, this likelihood omits the mixing-weight term.Source: §B.1 · p. 17

B.2 Closed form under hard assignment

  • A split adds d + 2 free parameters under the spherical model, and the hard-assignment criterion is invariant to feature rescaling because its gain depends on variance ratios.Fixing covariance at the identity changes the penalty; retaining the mixing-weight term would also change the split criterion.Source: §B.1 · p. 17, §B.2 · p. 18

B.3 Reduction to an anisotropy threshold

  • The threshold analysis considers a median cut along the leading eigenvector and defines anisotropy as r = λ1/λ̄; the split condition becomes more permissive as anisotropy increases.The analysis bounds the split gain using the anisotropy ratio and is near equality when 2r/(πd) is small.Source: §B.3 · p. 18

B.4 Consequences

A component’s critical split size falls with anisotropy and rises with dimension. Finite-sample anisotropy inflation and the minimum-mass rule qualify how far this analysis predicts splitting.

B.4 Consequences

  • The critical size decreases roughly as 1/r, so elongated clusters are fragmented at smaller sizes than isotropic clusters of the same dimension.No cluster larger than about 2τthresh is protected at every size; isotropic clusters split when nk/log nk exceeds (d + 2)/g(1, d).Source: §B.4 · p. 18
  • The critical size rises with dimension because the BIC penalty grows with the number of parameters while the gain per point from a one-direction cut does not grow with d.Thus isotropic clusters in high dimension are split only at large sample sizes.Source: §B.4 · p. 19
  • For a fixed cluster shape, larger per-client samples meet the split criterion more readily, making ASM better matched to moderately sized clients than to a centralized dataset.The minimum-mass constraint guarantees termination: neither child can have effective mass below τthresh, and the pre-merge count satisfies Kg ≲ ng/τthresh.Source: §B.4 · p. 19
  • Finite-sample anisotropy inflation can keep recursion going to the minimum-mass constraint, while the merge stage must reunite fragments and may need larger α for elongated clusters.A larger α also risks merging genuinely distinct clusters.Source: §B.4 · p. 19

B.5 Approximations

  • The analysis assumes hard assignments and population moments; when nk is not much larger than d, sample anisotropy exceeds its population value and splits can occur at smaller sizes than predicted.The 2/π factor is exact only for a median cut of a Gaussian parent and is approximate beyond the first level.Source: §B.5 · pp. 19–20

C Synthetic Validation of the Split Analysis

Synthetic tests support the split analysis while showing that a single round cluster can fragment substantially before merging. Results also indicate that sample size per client and merge settings affect the resulting count.

C Synthetic Validation of the Split Analysis

  • 97%, 94% and 97% of draws at d = 8, 16 and 64 were predicted by the criterion using sample anisotropy, versus 90%, 85% and 92% using population anisotropy.For a round cluster at d = 64, the sample-anisotropy onset was about 250 points, near the idealized hard-split onset of 248 and below the population-value prediction of 671.Source: C Synthetic Validation of the Split… · p. 20
  • At d = 64, soft EM raises the round-cluster split onset from 248 to about 450 points; for elongated clusters the onsets coincide, and δ ∈ {0.5, 1, 2} leaves onset unchanged.Source: C Synthetic Validation of the Split… · p. 20
  • For a single round cluster, the split-stage component count grows roughly with n before merging, reaching about 470 at d = 8, 320 at d = 16 and 16 at d = 64 for n = 5000.The figure compares component count with the dashed n/(2τthresh) minimum-mass bound; in low dimension the recursion reaches that bound, while in high dimension the BIC penalty limits it.Source: C Synthetic Validation of the Split… · p. 21, Figure 2 · p. 21
  • In pooled low-dimensional data, a single cluster can reach the merge stage as tens to hundreds of fragments, so final-count accuracy depends on the merge rule and α.The fragments are reunited only when α ≳ 0.8√r.Source: C Synthetic Validation of the Split… · p. 21
  • Smaller per-client datasets produce fewer spurious components because split-stage component counts grow with points per cluster.Source: C Synthetic Validation of the Split… · p. 21

D Analysis of ASM Merge

  • On Waveform, merging reduces 28.8 components to the three classes and triples ARI; Table 6 reports held-out ARI and mean component counts across merge thresholds.The ablation evaluates pooled ASM-S data over a range of α settings.Source: Table 6 · p. 22

E Our FedGEM implementation and the released code

The authors change three FedGEM implementation steps after identifying departures from the cited algorithm and a possible sign error. Their implementation gives different accuracy in both directions but closer global cardinality estimates than the published results on seven of eight datasets.

Why a separate implementation

  • The implementation changes the uncertainty-radius bisection, the direction used to move overlapping components, and the stopping rule.The authors report that their intersection-point formula places ν inside both balls in all 20,000 sampled pairs, versus 5.9% for the published formula.Source: E Our FedGEM implementation and the… · pp. 22–23

Our implementation's results

  • On seven of eight datasets, the implementation's |K̂ − K⋆| is smaller than the published results; CIFAR-10 is the exception.For example, FrogA is 7.9 versus 23.9 with K⋆ = 10, and EMNIST is 49.5 versus 58.7 with K⋆ = 47.Source: E Our FedGEM implementation and the… · p. 23
  • Accuracy differs in both directions: the implementation is higher on Waveform, Abalone, FMNIST, and CIFAR-10, and lower on FrogA and FrogB.For the released code comparison, its global-count error is smaller on six of seven tested datasets, except Waveform.Source: E Our FedGEM implementation and the… · p. 23
  • On FMNIST, the released script gives K̂ = 90 with T = 20, versus 9.1 with T = 10.The authors use T = 10; the released FMNIST script uses T = 20.Source: E Our FedGEM implementation and the… · p. 23
  • The authors report that their Section 5 comparisons use Oracle-Kg through the same implementation, so those comparisons do not depend on these FedGEM differences.Table 7's personalized-ARI comparisons also vary in partition, repetitions, and feature standardization.Source: E Our FedGEM implementation and the… · p. 23, Table 7 · p. 24

F Implementation and protocol details

The evaluation uses client-held data, local-only hyperparameter selection, and two partitions that either preserve or decouple client size from local cardinality. The results show that decoupling substantially changes points per cluster on image datasets, while effects vary for datasets whose classes differ in size.

F Implementation and protocol details

  • Each client chooses its Phase 1 configuration using the silhouette of its own validation points; client training data are split 80/20, with no information pooled across clients.For the pooled regime, selection uses a random subsample of up to 30,000 points split 80/20.Source: F Implementation and protocol details · p. 26

G Regime A and B

  • The evaluation distributes training data to fixed client counts by dataset, with every client's local cardinality defined as the number of distinct clusters in its assigned points.The test data are held out; evaluation uses seeds 42–51.Source: G Regime A and B · p. 26
  • Regime A assigns every training point and gives clients nearly equal points per class; client size consequently grows with the number of classes held.The Spearman correlation between client size and cardinality is 0.98–0.99 on image datasets and 0.85 on Abalone.Source: G Regime A and B · pp. 26, 29
  • Regime B preserves each client's class set but draws target client sizes independently of cardinality over 0.5–2 times the Regime A median.Unlike Regime A, it may leave training points unused; clients receiving fewer than 60 points retain their Regime A data.Source: G Regime A and B · p. 29
  • Table 9 reports Regime B global ARI with 95% confidence-interval half-widths and, on a second line, estimated global K and its absolute error; its mean is unweighted across eight datasets.The table uses per-client hyperparameter selection and ten evaluation seeds.Source: Table 9 · p. 30

G.1 Points per cluster in Regime A and B

  • On image datasets, the points-per-cluster CV rises from 0.04 in Regime A to 0.48–0.50 in Regime B, while the size–cardinality correlation shifts from 0.98–0.99 to −0.01–0.04.The mean points per class is essentially unchanged, while dispersion grows about twelvefold.Source: §G.1 · p. 30
  • On six of eight datasets, Regime B has higher points-per-cluster dispersion in all ten seeds; image-dataset CV ratios are 11–13, while Waveform and Abalone ratios are about 3.The increase is significant after Holm correction (p = 0.008); FrogA and FrogB do not show significant CV increases.Source: §G.1 · pp. 31–32
  • Image-dataset elasticity shifts from b = 1.00–1.03 in Regime A to −0.03–0.05 in Regime B, indicating size proportional to cardinality in A and no such relationship in B.Abalone shifts from b = 0.85 to 0.11; Waveform's elasticity is undefined because every client has two classes.Source: §G.1 · pp. 31–32

G.2 Robustness of cardinality prediction to the partition

The section tests whether decoupling client size from local cardinality changes cardinality estimation, using paired partitions and seed-level comparisons. ASM and Oracle-K are reported as robust to the partition, while X-Means and G-Means change and DP-GMM's high variable errors prevent an equivalence conclusion.

G.2 Robustness of cardinality prediction to the partition

  • ASM's pooled global-count error is statistically equivalent across the two partitions, with no dataset showing a significant difference after Holm correction.ASM-S mean relative local error changes from 0.47 to 0.51; removing size information therefore does not hurt it.Source: §G.2 · p. 33, Table 12 · p. 33
  • Oracle-K is equivalent on seven of eight datasets (pooled D = +0.04, CI [−0.01, 0.08]), indicating that Phase 2 aggregation is insensitive to the partition.Oracle-K receives true local cardinalities, so its error change reflects Phase 2 aggregation.Source: §G.2 · p. 33, Table 12 · p. 33
  • X-Means changes significantly on three datasets, while G-Means changes on four; DP-GMM's large, variable errors prevent establishing equivalence despite no significant change.The DP-GMM relative errors are 10 to 19 on FMNIST and CIFAR-10.Source: §G.2 · p. 33

H Runtime complexity

  • ASM processes every point once per split-test round, with leading cost O(Nd^2) plus O(INd) for at most 15 EM steps; balanced splitting yields about log2 K̂ rounds.Its merge is quadratic in K̂ and matters when splitting overshoots; X-Means and G-Means refit all K̂ means after each split round.Source: H Runtime complexity · p. 35, Table 13 · p. 35

Related papers

Loading 2609.36762v1…