Clustered federated learning

Overview

Clustered federated learning (CFL) is federated learning in which the server first groups the clients, then averages within each group [arxiv:2101.07511 §3.1]. The problem it targets is that clients can hold data of different kinds, and a single average over all of them mixes those kinds together. Plain federated learning already has this difficulty with non-identical client data 2101.07511 §2.2. The clustering idea is credited by the paper to Sattler et al. 2101.07511 §3, whose work is not in this wiki.

Three sources sit under this slug, and they cluster different things. The first clusters clients that each train a model, then averages the models per cluster. The second clusters data points across devices, with k-means, and returns a grouping of the data; it trains no per-cluster model. The third is a survey of personalized federated learning. It describes iterative cluster-specific models (IFCA among them) without experiments of its own 2103.00710 §IV-B. All three are variants of "group the devices, then combine within the group", so the page covers all of them.

Variants

Cluster by known data type, two-level averaging (the paper's CFL)

Clients are assigned to clusters by a property they know about their data, here the imaging modality 2101.07511 §3.1. The clusters are fixed in advance and not learned from the data. Per round, clients train locally and the server averages inside each cluster, then averages the clusters [arxiv:2101.07511 alg. 1]. Within a cluster, weights are averaged across clients. Across clusters, the cluster means are averaged together, so each cluster counts once, whatever its size 2101.07511 alg. 1. The paper's written equation averages over all clients instead, so the two forms differ when cluster sizes differ 2101.07511 eq. 1.

The model is a VGG16-based binary classifier with an extra convolutional layer and three dense layers 2101.07511 §3.2.2. Loss is focal loss, to handle class imbalance 2101.07511 eq. 2. Card: Collaborative Federated Learning For Healthcare.

Author-reported results on the two modalities, with F1 per class 2101.07511 tab. 3:

• X-ray, COVID-19: 0.76 with CFL, 0.77 with one federated model per modality, 0.41 with conventional federated learning on mixed data.
• Ultrasound, COVID-19: 0.94 with CFL, 0.97 per modality, 0.84 conventional.

The abstract reports overall F1 16% and 11% higher than conventional multi-modal federated learning on X-ray and ultrasound [arxiv:2101.07511 §Abstract]. The text does not give the overall figures, and the card reads them by eye from a bar chart 2101.07511 fig. 4.

Experiments are simulated and on two small datasets; the test splits are small, with 30 to 269 images per class 2101.07511 tab. 1. Runs are single, with no seeds or intervals 2101.07511 §4.

One-shot federated k-means (k-FED)

Each device runs a local k-means once, with its own cluster count, and sends only its few local centers to the server 2103.00697 §3.2 alg. 1. The server seeds k groups from those centers with a farthest-point rule, then makes one assignment round 2103.00697 alg. 2. Each data point takes the group of its device's center 2103.00697 §3.2. The output is a clustering of the data, not a trained model. Card: Heterogeneity for the Win: One-Shot Federated Clustering.

The guarantee depends on heterogeneity. If each device holds data from at most sqrt(k) clusters, a pair of clusters that never share a device needs separation of about k^(1/4), against sqrt(k) for centralized clustering [arxiv:2103.00697 §3.2]. When each device holds close to k clusters, the requirement becomes stricter than the centralized one, of order k against sqrt(k) [arxiv:2103.00697 §3.2]. The guarantee assumes well-separated cluster means, which the paper says real-data separation does not reach 2103.00697 §4.2. The real-data results are therefore practical evidence, not a check of the bound.

Author-reported results, all with the paper's own setup:

• Synthetic mixtures, accuracy from 98.40 to 100.00 across the settings tested. The data is generated so the separation conditions hold, so this is a best case 2103.00697 tab. 1.
• Rotated MNIST, personalized federated learning, test accuracy [arxiv:2103.00697 tab. 2]: with 100 devices and at most one cluster per device, k-FED 98.0 and IFCA 98.0; with 200 devices, 97.8 and 97.2; with two clusters per device, 97.1 and 95.6 (100 devices), 96.4 and 95.1 (200 devices). The metric's scale is not stated.
• Real federated datasets: the text reports k-means cost and communication behaviour as qualitative curves, without a numeric table [arxiv:2103.00697 §4.2] fig. 2 fig. 3.

Iterative cluster-specific models (IFCA, as the PFL survey describes it)

Here the clusters are learned, and each cluster keeps its own model over many rounds. The survey places this family under personalized federated learning. It names IFCA, multi-center learning with EM, recursive bi-partitioning and hierarchical clustering, and gives IFCA as one broadcast of K cluster models per round 2103.00710 §IV-B. Each client is assigned to the cluster whose model fits its data best, and the models are averaged within each cluster 2103.00710 §IV-B. The survey gives no algorithm box and no value for K, and no rule for choosing it 2103.00710 §IV-B. Card: Towards Personalized Federated Learning. The survey runs no experiments, so it offers no measured results for this variant.

The survey's communication claim is analytic: IFCA's overhead is K times that of FedAvg 2103.00710 §IV-B. The k-FED paper compares with IFCA on Rotated MNIST, but only as author-reported accuracy 2103.00697 tab. 2 (see above).

When to use which

The rows below cover what the sources compare. The paper's CFL is compared with per-modality federated learning and with one mixed-modality model. k-FED is compared with naive distributed k-means and with IFCA. The IFCA paper itself is not in this wiki; the PFL survey describes IFCA without results.

Implementation sketch

Two loops follow from the two sources. The first is the CFL loop, which follows the paper's algorithm 2101.07511 alg. 1. The one choice left open is how to weight clients and clusters, which the paper does not state 2101.07511 eq. 1.

# Clustered federated learning, R rounds  [arxiv:2101.07511 alg. 1]
# clusters: list of client groups, fixed by data type in advance
def clustered_round(clusters, global_w, E, B, eta):
    # send the current global weights to every client, train locally
    cluster_means = []
    for cluster in clusters:
        # average the client weights within one cluster
        # [arxiv:2101.07511 alg. 1]; client weights are not stated
        local = [train_local(global_w, c, E, B, eta) for c in cluster]
        cluster_means.append(mean(local))
    # average the cluster means, so each cluster counts once
    # [arxiv:2101.07511 alg. 1]
    return mean(cluster_means)

The second is the k-FED server step. Each device's local clustering follows 2103.00697 alg. 1 and is left out here.

# k-FED: one-shot clustering across devices  [arxiv:2103.00697 alg. 2]
# device_centers: per device, the (k_z, d) local centers from alg. 1
def kfed_server(device_centers, k):
    # every device sends only its centers, once  [arxiv:2103.00697 alg. 2]
    all_centers = concatenate(device_centers)
    # seed with one device's centers, then add the farthest center
    # until there are k seeds  [arxiv:2103.00697 alg. 2, steps 2-6]
    seeds = device_centers[0]
    while len(seeds) < k:
        far = argmax(distance_to_set(all_centers, seeds))
        seeds = append(seeds, all_centers[far])
    # one assignment round: each center joins its nearest seed
    # [arxiv:2103.00697 alg. 2, step 7]
    return nearest_seed(all_centers, seeds)

The IFCA-style variant has no sketch here, because the survey gives no algorithm for it 2103.00710 §IV-B. Read the original IFCA paper before implementing it.

The paper's CFL equation averages over all clients in one step, which gives a different result when clusters differ in size 2101.07511 eq. 1. In k-FED, the paper's public code differs from the algorithm in several steps, for example by running k-means to convergence at the server; see the card's paper-vs-code section.

Contradictions

Between the two measuring sources, no shared quantity is reported with conflicting values. CFL reports classifier F1, and k-FED reports clustering accuracy and k-means cost, so their numbers do not compare directly. The PFL survey reports no measured clustering results, so it has no numbers to conflict. Within the CFL paper, three conflicts affect reproduction:

• Learning rate: the text gives 0.0001 for the model and baselines, but Table II lists 1e-3 for the CFL runs. The value behind Table III is not stated 2101.07511 §3.2.2 tab. 2.
• Batch size: §4 says the specialized baselines use 32, then trains all methods at 16 for the comparison 2101.07511 §4 tab. 2.
• Averaging: the equation and Algorithm 1 weight clients and clusters differently 2101.07511 eq. 1 alg. 1.

Within the k-FED paper, the text and the public code differ in several steps. These are listed in the card linked above, not repeated here 2103.00697 §4.

Papers

• Collaborative Federated Learning For Healthcare: clusters clinics by X-ray or ultrasound modality, averages within and across clusters, and compares with per-modality and mixed-modality federated models.
• Heterogeneity for the Win: One-Shot Federated Clustering: one-shot federated k-means that clusters data split across devices, with a separation guarantee that depends on how many clusters each device holds.
• Towards Personalized Federated Learning: a survey that places iterative cluster-specific models (IFCA and others) within personalized federated learning. It runs no experiments of its own.