Federated Hierarchical Clustering with Automatic Selection of Optimal Cluster Numbers

This paper proposes Fed-$k^*$-HC, a novel federated clustering framework that automatically determines the optimal number of clusters by generating client-side micro-subclusters and performing density-based hierarchical merging on the server, effectively addressing challenges related to unknown cluster counts, imbalanced cluster sizes, and privacy constraints.

The Gist

Imagine you are the mayor of a huge country, and you want to organize a national festival. You need to group millions of citizens into different "clubs" based on their hobbies (like hiking, cooking, or gaming) so you can send them the right invitations.

However, there's a catch: Privacy.

The citizens live in thousands of different towns (clients). They are very protective of their personal data and refuse to send you a list of their names and hobbies. They only agree to send you a few "summary notes" about their town's vibe.

This is the challenge of Federated Clustering. Most existing methods try to solve this by assuming:

1. Everyone has roughly the same number of people in each hobby group (e.g., exactly 100 hikers, 100 cooks).
2. You, the mayor, already know exactly how many clubs exist (e.g., "We need 5 clubs").

The Problem: In the real world, these assumptions are wrong. Some hobbies are huge (millions of hikers), while others are tiny (just 50 people who collect rare stamps). Also, you often don't know how many clubs actually exist until you look at the data. If you force everyone into equal-sized groups, you ruin the tiny, unique clubs.

The Solution: Fed-k*-HC (The "Smart Town Planner")

The authors of this paper propose a new method called Fed-k-HC*. Think of it as a two-step process involving "Micro-Planners" and a "Grand Architect."

Step 1: The Micro-Planners (The Clients)

Instead of sending you a messy list of everyone's hobbies, each town (client) does a quick, local organization first.

• The Trick: They break their town down into tiny, manageable "micro-groups." Imagine a town of 1,000 people is broken into 50 tiny circles of 20 people each.
• The Privacy Shield: They don't send you the names of the people. Instead, they create fake "dummy" people that perfectly mimic the average behavior of those 20-person circles. It's like sending a silhouette or a mannequin that looks and acts exactly like the group, but reveals no real identity.
• The Result: You get a pile of these "dummy" representatives from every town. They are small, precise, and safe.

Step 2: The Grand Architect (The Server)

Now, you (the server) have thousands of these dummy representatives from all over the country. You need to group them into the final clubs.

• The "Uniform Effect" Trap: Old methods would try to force these groups into equal sizes, crushing the tiny "stamp collector" groups into the giant "hiker" groups.
• The New Approach (Hierarchical Merging): The Grand Architect uses a "Lego" strategy.
  1. Look at all the tiny dummy groups.
  2. Find the two that are most similar (e.g., two groups of stamp collectors from different towns) and snap them together.
  3. Keep snapping similar groups together, one by one.
  4. The Magic Stop: The system has a special sensor (called SNC) that watches how the groups are merging. It knows when to stop. It says, "Okay, we've merged all the stamp collectors into one big club. Now we have 5 distinct clubs. Let's stop!"

Why is this special?

• It finds the number automatically: You don't need to guess "5 clubs." The system figures out, "Oh, there are actually 5 distinct groups here," all by itself.
• It handles the "Small Guys": Because it starts with tiny micro-groups and merges them slowly, it doesn't accidentally swallow the small, rare clubs. It protects the minority groups.
• One-Shot: The towns only send their dummy data once. No back-and-forth chatting. This saves time and keeps privacy tight.

A Simple Analogy: The Mystery Puzzle

Imagine you have a giant jigsaw puzzle, but the pieces are scattered in locked boxes in different houses. You can't open the boxes to see the picture.

• Old Way: You ask each house to guess which picture they have and send you a blurry photo. If one house has a tiny piece of a rare bird and another has a huge piece of a sky, the blurry photos get mixed up, and you miss the bird.
• Fed-k-HC Way:* Each house takes their pieces and glues them into small, tight clusters (micro-groups). They then send you a "shadow" of that cluster. You take all the shadows, and because they are small and precise, you can slowly snap the similar shadows together. Eventually, you realize, "Ah, these shadows form a bird, and those form a sky." You discover the picture and the number of distinct objects in it without ever seeing the original pieces.

The Bottom Line

This paper introduces a smarter, more flexible way to organize data in a privacy-friendly world. It stops us from forcing "one-size-fits-all" groups and allows us to discover the true number of groups, even when some are huge and some are tiny. It's like finally being able to organize a festival where the 50 stamp collectors get their own special tent, rather than being shoved into the giant hiking tent.

Technical Summary

1. Problem Statement

Federated Clustering (FC) aims to discover data distribution patterns from distributed, privacy-sensitive data without sharing raw samples. However, existing FC methods face three critical limitations:

• Unknown Cluster Count: Most methods require the number of clusters ($k$) to be pre-specified, which is rarely known in real-world scenarios.
• Imbalanced Data: Real-world data often exhibits imbalanced cluster sizes (some clusters are tiny, others massive). Existing methods often suffer from the "uniform effect," where algorithms force clusters into equal sizes, failing to detect minority groups.
• Privacy vs. Information Trade-off: Federated constraints limit data transmission. Methods that encrypt raw data incur high computational costs, while methods that transmit only centroids often lose the granularity needed to identify complex, imbalanced distributions.
• Non-IID Data: Data distributions vary significantly across clients (Non-IID), making global aggregation difficult.

2. Methodology: Fed-k∗-HC

The authors propose Fed-k∗-HC, a one-shot federated clustering framework that automatically determines the optimal number of clusters ($k^*$) and handles imbalanced data through a Client-Side Micro-Partitioning and Server-Side Hierarchical Merging paradigm.

A. Client-Side Automated Micro-Partitioning

Instead of transmitting raw data or a single global centroid, each client performs local clustering to generate "micro-subclusters."

• Algorithm: Uses Selection of Number of Prototypes (SNP), a competitive learning method. It adaptively divides local data into many fine-grained, compact subclusters of similar sizes.
• Privacy Preservation: To protect privacy, clients do not upload raw data. Instead, they calculate the mean ($\mu$) and covariance ($\Gamma$) of each micro-subcluster.
• Synthetic Data Generation: Clients generate an equivalent amount of synthetic data using a multivariate normal distribution $N(\mu, \Gamma)$ based on the calculated statistics. This synthetic data preserves the statistical distribution of the original data without revealing individual samples.
• Transmission: Clients upload the synthetic data and subcluster statistics (radius, standard deviation, count) to the server in a single communication round (one-shot).

B. Server-Side Hierarchical Merging

The server aggregates the synthetic data from all clients to determine the global structure.

• Automatic $k^*$ Determination (SNC): The server uses a Selection of Number of Clusters (SNC) algorithm.
  • It employs Loose Natural Neighbors (LNN) to find a suitable neighbor parameter ($b$).
  • It refines this using Strict Natural Neighbors (SNN), where points must be mutual $m$-th nearest neighbors. This strict criterion prevents small, sparse clusters from being incorrectly merged with dense neighbors.
  • The algorithm constructs an adjacency graph based on neighbor relationships and counts the connected components to determine the optimal $k^*$.
• Hierarchical Merging: Once $k^*$ is identified, the server performs bottom-up hierarchical merging.
  • Distance Metric: A specialized distance formula is used to merge subclusters, considering:
    1. Centroid distance.
    2. Overlap degree ($o$): Based on the ratio of distance between centers to the sum of radii.
    3. Similarity ($sim$): Based on the difference in standard deviations.
  • The process iteratively merges the closest subclusters until exactly $k^*$ clusters remain. This avoids the "uniform effect" by allowing clusters of varying sizes and shapes to coexist.

3. Key Contributions

1. Automatic Cluster Number Estimation: Unlike prior work requiring a fixed $k$, Fed-k∗-HC automatically infers the optimal $k^*$ based on data distribution using the SNC algorithm.
2. Handling Imbalanced Data: By using micro-partitioning and hierarchical merging, the method mitigates the "uniform effect," successfully detecting minority clusters that are often ignored by centroid-based methods.
3. One-Shot Privacy-Preserving Framework: The method achieves high-quality clustering with only one round of communication. It uses synthetic data generation to balance privacy protection with the need for detailed distribution information.
4. Novel Paradigm: It shifts the FC paradigm from "global averaging of centroids" to "hierarchical merging of micro-subclusters," offering a more robust solution for Non-IID and imbalanced scenarios.

4. Experimental Results

The method was evaluated on 11 datasets (5 real-world, 6 synthetic) including highly imbalanced and Non-IID settings, comparing against SOTA methods like KFed, MUFC, F3KM, and Orchestra.

• Performance Metrics: Fed-k∗-HC achieved the best average rank across F-measure, Accuracy, NMI, ARI, and DCV (a metric specifically for imbalanced data).
• Imbalanced Data: On datasets like ids2 and yeast (highly imbalanced), Fed-k∗-HC significantly outperformed competitors, which often failed to identify minority clusters.
• Non-IID Scenarios: In experiments where clients held only subsets of clusters (cluster absence), Fed-k∗-HC maintained high accuracy, whereas other methods struggled to reconstruct the global distribution.
• Ablation Studies:
  • Replacing the custom SNC with standard Natural Neighbors resulted in less accurate $k^*$ estimation.
  • The method proved robust on balanced data but showed its true superiority on imbalanced data.
• Efficiency: The method demonstrated linear scalability with respect to data size and client count. The one-shot nature significantly reduced communication overhead compared to iterative methods.

5. Significance and Limitations

Significance:
This work bridges a critical gap in Federated Learning by enabling unsupervised, privacy-preserving analysis of complex, imbalanced data without requiring prior knowledge of the number of clusters. It offers a practical solution for real-world applications (e.g., medical diagnosis, fraud detection) where data is skewed and cluster counts are unknown.

Limitations:

• Server Efficiency: As the number of clients or samples grows, the hierarchical merging process on the server may become computationally expensive.
• Extreme Imbalance: If a minority cluster is smaller than the "micro-subclusters" generated on the client, the method may fail to detect it.
• Privacy Enhancements: While the synthetic data approach protects raw samples, the paper notes that additional mechanisms (like Differential Privacy or Homomorphic Encryption) could be integrated for stricter privacy requirements.

Future Work:
The authors suggest extending the method to high-dimensional and sparse data via dimensionality reduction and integrating differential privacy to further enhance security.