cs.LGMar 13, 2026
SaveFederated Hierarchical Clustering with Automatic Selection of Optimal Cluster Numbers
Organizations: School of Computer Science, Guangdong Polytechnic Normal University, Guangzhou, China · School of Computer Science and Technology, Guangdong University of Technology, Guangzhou, China · Department of Computer Science, Hong Kong Baptist University, Hong Kong SAR, China
Abstract
Federated Clustering (FC) is an emerging and promising solution in exploring data distribution patterns from distributed and privacy-protected data in an unsupervised manner. Existing FC methods implicitly rely on the assumption that clients are with a known number of uniformly sized clusters. However, the true number of clusters is typically unknown, and cluster sizes are naturally imbalanced in real scenarios. Furthermore, the privacy-preserving transmission constraints in federated learning inevitably reduce usable information, making the development of robust and accurate FC extremely challenging. Accordingly, we propose a novel FC framework named Fed--HC, which can automatically determine an optimal number of clusters based on the data distribution explored through hierarchical clustering. To obtain the global data distribution for determination, we let each client generate micro-subclusters. Their prototypes are then uploaded to the server for hierarchical merging. The density-based merging design allows exploring clusters of varying sizes and shapes, and the progressive merging process can self-terminate according to the neighboring relationships among the prototypes to determine . Extensive experiments on diverse datasets demonstrate the FC capability of the proposed Fed--HC in accurately exploring a proper number of clusters.
Figures & tables
| Method | Non-IID | Imbalance | Auto- | One-shot |
| KFed [ 9 ] | ✓ | ✗ | ✗ | ✓ |
| MUFC [ 32 ] | ✓ | ✗ | ✗ | ✓ |
| F3KM [ 48 ] | ✓ | ✓ | ✗ | ✗ |
| Orchestra [ 27 ] | ✓ | ✗ | ✗ | ✗ |
| FedET [ 23 ] | ✓ | ✓ | ✗ | ✗ |
| FedGT [ 45 ] | ✓ | ✓ | ✗ | ✗ |
Table 1: Comparison of key characteristics of existing FC methods.
Figure 1: Overview of the proposed Fed- -HC framework. Each client first applies the SNP algorithm to partition its local data (black dots) into multiple micro-subclusters (colored dots) and computes the centroid of each subcluster (black stars). These centroids are then uploaded to the server. The server aggregates all client subclusters (colored dots), reinitializes global centroids (colored stars), and performs clustering using corresponding neighborhood-based algorithms. The number of clusters is automatically estimated via a neighborhood-based method, without requiring manual specification.
Figure 2: To intuitively illustrate the construction process of SNN, a simplified example is presented using several sample points, and their nearest neighbor (NN) structures are visualized under different neighborhood sizes. In the SNN definition, a pair of points is considered an SNN pair only if they are mutual nearest neighbors, i.e., each lies in the -nearest neighbor list of the other. In the diagram, such mutually connected pairs are denoted with solid lines. For example, under = 2, the neighbors are as follows: A → {B, C}, B → {A, D}, C → {A, E}, D → {A, B}, E → {A, C},F → {G, H}, G → {F, H}, H → {I, J}, I → {H, J}, J → {H, I}. Only pairs that appear in both nodes’ neighbor lists qualify as SNN pairs. For instance, since A and B connect each other, the pair (A, B) is an SNN pair, according to Definition 2. In contrast, although D has A as a neighbor, A does not connect D. As a result, (A, D) is not judged as an SNN pair. Accordingly, the identified SNN pairs under = 2 are: (A, B), (A, C), (B, D), (C, E), (F, G), (H, I), (H, J), (I, J), which form three clusters .
| No. | Dataset | Cluster statistics | |||
| 1 | ids2 | 2 | 3200 | 5 | |
| 2 | gaussian | 2 | 2000 | 4 | |
| 3 | ids2_22 | 2 | 400 | 2 | |
| 4 | ids2_2k22 | 2 | 2400 | 3 | |
| 5 | ids2_non_iid | 2 | 3200 | 5 | |
| 6 | gaussian_non_iid | 2 | 2000 | 4 |
Table 3: Information of the datasets involved in our experiments, including five real-world datasets and six synthetic datasets, all of which are imbalanced.
| Dataset | Measurement | Fed- -HC (ours) | KFed | MUFC | F3KM | Orchestra | Fed-AP | Fed-MS | Fed-KDPC | |
| pageblock | F-measure | 0.9040 0.0177 | 0.8514 0.0724 | 0.8579 0.0007 | 0.4630 0.0000 | 0.2857 0.0132 | 0.5602 0.0289 | 0.8877 0.0000 | 0.8869 0.0000 | 0.8219 0.0000 |
| Accuracy | 0.9610 0.0430 | 0.9252 0.1366 | 0.9311 0.0012 | 0.8199 0.0000 | 0.4065 0.0199 | 0.8449 0.0200 | 0.9985 0.0000 | 0.9989 0.0000 | 0.8391 0.0000 | |
| NMI | 0.1543 0.0630 | 0.0390 0.0356 | 0.0206 0.0004 | 0.1170 0.0000 | 0.0493 0.0086 | 0.2019 0.0438 | 0.0891 0.0000 | 0.0744 0.0000 | 0.0202 0.0000 | |
| ARI | 0.2933 0.1154 | 0.0260 0.0161 | 0.0175 0.0013 | 0.1133 0.0000 | 0.0105 0.0018 | 0.3533 0.0566 | 0.0312 0.0000 | 0.0234 0.0000 | 0.0502 0.0000 | |
| DCV | 0.1130 0.0174 | 0.1793 0.1661 | 0.0384 0.0029 | 1.1189 0.0000 | 0.0510 0.0316 | 1.0038 0.0431 | 0.2103 0.0000 | 0.2112 0.0000 | 0.1837 0.0000 | |
| yeast | F-measure | 0.5791 0.0316 | 0.4826 0.0401 | 0.4994 0.0027 | 0.4478 0.0000 | 0.3582 0.0152 | 0.4348 0.0225 | 0.4657 0.0315 | 0.4125 0.0000 | 0.5229 0.0020 |
Table 4: Clustering performance comparison on the seven datasets evaluated by the five validity metrics. The best and second-best results are indicated by boldface and underline, respectively. The “Avg. Rank” row represents the average rank of the methods across different datasets.
| Dataset | Measurement | Fed- -HC (ours) | KFed | MUFC | F3KM | Orchestra | Fed-AP | Fed-MS | Fed-KDPC | |
| ids2_non_iid | F-measure | 0.9984 0.0000 | 0.9840 0.0004 | 0.7413 0.0034 | 0.5435 0.0000 | 0.5058 0.0092 | 0.6034 0.0551 | 0.7177 0.0373 | 0.9871 0.0000 | 0.7696 0.0100 |
| Accuracy | 0.9984 0.0000 | 0.9836 0.0004 | 0.6873 0.0038 | 0.6231 0.0000 | 0.5217 0.0089 | 0.7100 0.0447 | 0.6806 0.0393 | 0.9869 0.0000 | 0.7163 0.0128 | |
| NMI | 0.9917 0.0000 | 0.9411 0.0011 | 0.7486 0.0012 | 0.7440 0.0000 | 0.4664 0.0388 | 0.4339 0.0357 | 0.6799 0.0301 | 0.9496 0.0000 | 0.7770 0.0077 | |
| ARI | 0.9952 0.0000 | 0.9534 0.0010 | 0.5270 0.0011 | 0.5279 0.0000 | 0.2124 0.0266 | 0.4809 0.0089 | 0.4571 0.0336 | 0.9624 0.0000 | 0.5467 0.0024 | |
| DCV | 0.0041 0.0000 | 0.0461 0.0009 | 0.7246 0.0015 | 0.4242 0.0000 | 0.0421 0.0132 | 0.7376 0.0543 | 0.7686 0.0802 | 0.0369 0.0000 | 0.6942 0.0024 | |
| gaussian_non_iid | F-measure | 0.9960 0.0000 | 0.9873 0.0005 | 0.8663 0.0021 | 0.7318 0.0000 | 0.4616 0.0570 | 0.7218 0.0377 | 0.8923 0.0267 | 0.9921 0.0000 | 0.8352 0.0213 |
Table 5: Clustering performance comparison on the two Non-IID datasets.
| Dataset | Measurement | Fed- -HC (ours) | KFed | MUFC | F3KM | Orchestra | Fed-AP | Fed-MS | Fed-KDPC | |
| ids2_22 (balanced) | F-measure | 1.0000 0.0000 | 1.0000 0.0000 | 1.0000 0.0000 | 1.0000 0.0000 | 0.9690 0.0185 | 1.0000 0.0000 | 0.6017 0.0487 | 0.6656 0.0000 | 1.0000 0.0000 |
| Accuracy | 1.0000 0.0000 | 1.0000 0.0000 | 1.0000 0.0000 | 1.0000 0.0000 | 0.9690 0.0185 | 1.0000 0.0000 | 0.6700 0.0158 | 0.9950 0.0000 | 1.0000 0.0000 | |
| NMI | 1.0000 0.0000 | 1.0000 0.0000 | 1.0000 0.0000 | 1.0000 0.0000 | 0.8100 0.1054 | 1.0000 0.0000 | 0.0261 0.0406 | 0.0235 0.0000 | 1.0000 0.0000 | |
| ARI | 1.0000 0.0000 | 1.0000 0.0000 | 1.0000 0.0000 | 1.0000 0.0000 | 0.8801 0.0704 | 1.0000 0.0000 | 0.0331 0.0552 | 0.0001 0.0000 | 1.0000 0.0000 | |
| DCV | 0.0000 0.0000 | 0.0000 0.0000 | 0.0000 0.0000 | 0.0000 0.0000 | 0.0220 0.0380 | 0.0000 0.0000 | 0.3492 0.2067 | 1.4001 0.0000 | 0.0000 0.0000 | |
| ids2_2k22 (imbalanced) | F-measure | 0.9963 0.0000 | 0.6942 0.0733 | 0.6630 0.0090 | 0.7326 0.0000 | 0.4989 0.0197 | 0.5871 0.0067 | 0.6647 0.0321 | 0.8963 0.0000 | 0.7672 0.0056 |
Table 6: Clustering performance comparison on two datasets with balanced (ids2_22) and imbalanced (ids2_2k22) clusters.
| Dataset | GCS + NN | SNC (ours) | |
| pageblock | 3 | 1 | 3 |
| yeast | 6 | 4 | 6 |
| abalone | 4 | 3 | 4 |
| breast | 2 | 3 | 5 |
| digits | 10 | 6 | 9 |
| ids2_22 | 2 | 3 | 2 |
Table 7: Result of ablation studies on the SNC algorithm. The table lists the number of clusters obtained through different methods on various datasets, with results matching the real value indicated in bold. The values in the column represent the ground-truth number of clusters in the corresponding dataset.
Figure 3: p-values of the Wilcoxon signed rank test in comparing our method against the other methods on five metrics.
Figure 4: Parameter sensitivity analysis on . The symbol denotes the ground-truth number of clusters in each dataset. The results are plotted demonstrating how the proposed method can automatically infer the correct cluster number across datasets.
Figure 5: The variation curve of as changes on different datasets. The impact of the -nearest neighbor parameter ( ) used in the SNC algorithm on the proportion of short-distance point pairs ( ) across different datasets. From the graph, it can be seen that the proportion of short-distance point pairs ( ) shows a similar trend as increases across all datasets, which aligns with our expectations.
Figure 6: Parameter sensitivity analysis on . The impact of using different values on the clustering results of the global clustering algorithm across each dataset was studied. The five lines represent the results of the F-measure, Accuracy, NMI, ARI, and DCV metrics, where a smaller DCV value indicates better performance, and the higher the value of the other four metrics, the better the performance.
Figure 7: Time overhead analysis under two different settings: (a) varying the dataset size from to with 30 clients; (b) varying the number of clients from 3 to 60 with a fixed dataset size of 32,000.