Encryption-Compatible Clustered Federated Learning via Distributed Expectation-Maximization over Metadata
arXiv:2607.28338v1 [cs.LG] 30 Jul 2026
Michael Ben Ali UT3, IRIT, CNRS Toulouse, France [email protected]
Imen Megdiche INU Champollion, ISIS, IRIT, CNRS Castres, France [email protected]
André Péninou UT2J, IRIT, CNRS Toulouse, France [email protected]
Olivier Teste UT2J IRIT, CNRS Toulouse, France [email protected]
Abstract Clustered Federated Learning (CFL) addresses data heterogeneity in federated settings by grouping clients with similar data distributions to enable effective training. Existing methods face a trade-off between privacy preservation, communication cost, and computational efficiency. We formalize this as the CFL trilemma, according to which improving two of these dimensions comes at the expense of the third. A prominent paradigm relies on metadata (i.e., low-dimensional representations of client datasets shared with the server) to enable communication- and computation-efficient clustering. However, such approaches are not compatible with standard FL privacy-preserving mechanisms. To address this limitation, we propose FLAMECHE, which reformulates metadata-based CFL as a distributed Expectation-Maximization (EM) procedure, restricting server updates to additive operations while preserving efficiency. This design enables compatibility with practical secure FL schemes. We conducted extensive experiments on multiple datasets under various heterogeneous scenarios. Results show that FLAMECHE improves the effectiveness of client models. It enables encryption-compatible metadata-based clustering, enhancing its positioning within the CFL trilemma.
1
Introduction
Federated Learning (FL) enables collaborative training of machine learning models without sharing raw data [26]. However, under non-IID (non-independent and identically distributed) data distributions, training a single global model leads to degraded performance [36]. Clustered Federated Learning (CFL) was introduced to address this limitation by partitioning clients into groups with similar data distributions, enabling the training of more specialized models [30]. Existing CFL methods can be classified into three families [3, 4]. Server-side approaches [30, 12, 37] cluster clients based on similarities between model updates at each communication round, incurring quadratic computational complexity in the number of clients. Client-side approaches [14, 22, 24] shift the clustering process to the clients, where each client must download and evaluate multiple models at each round to determine matching cluster assignment. This increases communication cost and exacerbates the straggler effect, where slower clients delay each round of communication and increase total training time. Metadata-based approaches [9, 23, 32] cluster clients using compact dataset representations, requiring metadata to be shared in plaintext, which raises privacy concerns [3, 4]. Preprint.
Taken together, these approaches reveal a trade-off in CFL design. Identifying client groups requires either performing complex computations, repetitively refining assignments, or relying on compact representations, each constraining one of three key dimensions: computation, communication, or privacy. We define the CFL trilemma as the difficulty of jointly optimizing these three dimensions within current CFL paradigms. As illustrated in Figure 1, each CFL family lies along one edge of the triangle, favoring two dimensions while sacrificing the third. This tension arises from the clustering task: the server only observes model updates, which are high-dimensional and vary across communication rounds. Inferring stable client groupings requires repeated comparFigure 1: The CFL Trilemma is govisons over time, increasing server-side computation, while erned by three competing constraints: repeated evaluation of candidate models on the client inPrivacy, Computation, and Communicreases communication. Metadata sidesteps these costs by cation. sharing representations directly, at the expense of privacy. As clustering relies on non-linear operations that are costly under encryption, metadata-based approaches conflict with secure FL mechanisms. These are most efficient under additive-only computations [5, 7, 38], while supporting complex operations inflate computational cost, highlighting the tension of the trilemma. Thus, we investigate the following question. Can metadata-based CFL be made more practical under the trilemma issues? Our contribution is to reformulate metadata-based clustering as a distributed ExpectationMaximization (EM) procedure, limiting the server to additive operations. Building on this insight, we propose FLAMECHE, a CFL framework designed to cluster clients using metadata while remaining compatible with secure FL. Metadata is computed using randomly initialized neural networks, avoiding distribution-aware design and prior knowledge of client heterogeneity. This solution operates within widely adopted Secure FL constraint (i.e., it neither introduces nor modifies any protocol) [5, 34, 7]. It complies with the additive operations efficiently supported by these schemes (e.g., Secure Aggregation and Homomorphic Encryption) while remaining agnostic to their specific implementation. The paper is structured as follows. Section 2 gives state-of-the-art insights and issues on CFL. Section 3 presents our framework formalization background. Section 4 discusses FLAMECHE theoretical costs and its position in the CFL trilemma. Sections 5 and 6 challenge our framework against classical CFL methods and strengthen results with an ablation study.
2
Related Work
2.1
Clustered Federated Learning for Non-IID Data
Since the introduction of Federated Learning (FL) [26], handling non-IID data remains a central challenge [18, 36, 20]. Clustered Federated Learning (CFL) addresses this by grouping clients with similar data distributions and training one model per cluster. Existing methods can be categorized into three families based on how clustering is performed [3, 4]. Server-side approaches cluster clients using similarities between model updates. Early works [15, 6] assume full participation and perform one-shot clustering, while later methods [30, 12, 22, 37] extend this to partial participation across rounds. However, updates are high-dimensional, evolve over time, and are computed on different client subsets, requiring repeated clustering. To mitigate this, methods such as FedGroup [12] use dimensionality reduction (e.g., SVD), FeSEM [22] adopts a K-Means-like clustering procedure on model parameters, while StoCFL [37] relies on gradients computed from a frozen anchor model (e.g., the randomly initialized global model) to obtain more stable clustering signals. Client-side approaches delegate clustering to clients by allowing them to select the most suitable model locally. IFCA [14], the seminal representative of this family, assigns each client to the model minimizing its local loss. Subsequent client-side methods [4] mainly extend this core mechanism through additional components, such as soft cluster assignments or cross-cluster knowledge transfer, 2
without fundamentally changing the client-driven model selection process. While this avoids explicit server-side clustering, it increases communication by requiring clients to download multiple models each round and raises local computation, potentially leading to client stragglers and higher latency. Metadata-based approaches rely on compact dataset representations. The effectiveness of these methods is influenced by the choice of metadata. K-Fed [9] uses local centroids, while PACFL [32] constructs low-dimensional subspaces. These methods reduce dimensionality and provide stable representations, but typically require sharing metadata with the server, relaxing standard FL privacy assumptions that restrict communication to model updates. 2.2
Clustering under Privacy Constraints in FL
The confidentiality of clients’ data is fundamental in FL. As, even model updates can reveal sensitive information [27], several mechanisms have been proposed to strengthen privacy. Differential Privacy (DP) [1] perturbs shared information with noise. Its interaction with CFL has received limited attention [23, 13], and noisy signals may make clustering challenging [25]. Furthermore, DP mechanisms still expose information in plaintext [27]. Differential privacy in the CFL setting is outside the scope of this work. In Secure Multi-Party Computation (SMPC), multiple parties jointly compute a function over their inputs without revealing them. In FL, protocols such as Secure Aggregation [5] enable practical deployments in which clients apply masks that cancel out during additive aggregation, revealing only the final result. This approach adapts to dynamic FL settings with varying client participation. Homomorphic Encryption (HE) allows each client to encrypt its data before transmission, enabling the server to perform computations directly on encrypted values without decryption. Schemes such as Paillier [34, 33] encryption support only integer additive operations. CKKS [7, 29] is efficient under linear operations, while non-linear ones incur significant computational overhead. These constraints have important implications for CFL methods that rely on the server for cluster calculation (i.e., Server-side and Metadata-based CFL). While clustering on encrypted information is theoretically possible, as noted by Zhang et al. [38], “even clustering low-dimensional representations can lead to prohibitive runtime and memory usage”. Our trilemma highlights that existing approaches favor two dimensions while sacrificing the third. In particular, metadata-based methods achieve top computational and communication efficiency at the cost of relaxed privacy. Improving this privacy dimension remains, to our knowledge, unexplored. This gap emphasizes a fundamental limitation: while metadata-based clustering is efficient, it is hardly compatible with encryption mechanisms. This work addresses this limitation by reformulating clustering to restrict on-server operations to additions.
3
Efficient Clustered Federated Learning over Encrypted Metadata
Consider a federated learning setup with N clients, where each client i holds a local dataset Di = i {(xij , yij )}nj=1 drawn from an unknown distribution Pi (X, Y ). In CFL, these local distributions are assumed to arise from K(K < N ) latent distributions {Pk }K k=1 [30]. The main challenge in CFL is to cluster clients with similar data, enabling training of specialized models. To retain the efficiency of metadata-based clustering under privacy-preserving mechanisms, FLAMECHE enforces a key constraint: all server-side computations are limited to additions. This ensures compatibility with widely used schemes such as Paillier [34], CKKS [7], or Secure Aggregation [5], where non-linear operations are either unsupported or expensive. Thus, FLAMECHE decomposes clustering into three steps repeated over communication rounds: (1) the server broadcasts parameters of the K distributions; (2) each client evaluates its likelihood of belonging to each cluster using its metadata; (3) the server aggregates metadata weighted by these likelihoods to update the distribution parameters. This design isolates all non-linear computations to clients while restricting the server to additive operations. This formulation is equivalent to maximum-likelihood estimation in a finite mixture model solved via the Expectation-Maximization (EM) algorithm [8]. The E-step is performed locally by clients to compute cluster assignments, while the M-step is executed by the server to update cluster parameters. When the mixture components 3
belong to the exponential family [8, 28], the M-step depends only on aggregating sufficient statistics weighted by assignments, and thus requires only additions (Section 3.2). This preserves the efficiency of metadata-based CFL while enabling compatibility with standard encryption mechanisms. 3.1
Problem Formulation
We define a local extractor Φ, which maps a client dataset into a compact vector of dimension d: Φ : D → Rd ,
ϕi = Φ(Di ).
The specific instantiation of the metadata ϕi is a flexible design parameter (e.g., statistical summaries). We model {ϕi }N i=1 as samples drawn from a mixture distribution with K components (each component corresponding to a cluster in CFL), where πk are the mixing coefficients and θk are the cluster-specific parameters. The objective is to estimate the parameters Θ = {πk , θk }K k=1 by maximizing the log-likelihood. ! N K X X L(Θ) = log πk P (ϕi | θk ) . (1) i=1
k=1
This objective is classically optimized using the Expectation-Maximization (EM) algorithm [8]. Thus, we introduce FLAMECHE (Federated Learning Algorithm with Expectation-Maximization Clustering over Hidden Metadata), a distributed EM framework that clusters clients based on their metadata representations {ϕi }N i=1 . It is not the first FL method to leverage EM, but differs fundamentally in objective and design. FedEM [11] applies EM at the data level, where latent assignments associate individual samples with a mixture of global models. This objective fundamentally differs from CFM, whose goal is to cluster clients according to their data distributions in order to improve the downstream task. FeSEM [22] performs a K-means-like EM procedure over client model parameters, alternating one E-step (client assignment) and one M-step (cluster centroid update) directly on the server at each communication round. In contrast, FLAMECHE performs EM over low-dimensional metadata representations, where the E-step is executed locally on-client while the server performs only the M-step. This design enables compatibility with Secure FL mechanisms. 3.2
FLAMECHE as a Distributed Expectation-Maximization Algorithm
To ensure compatibility with additive-only server-side operations, we restrict the clustering model to likelihoods whose M-step can be expressed in terms of additive sufficient statistics. This limits modelization to mixture models from the exponential family : Assumption 1 (Exponential Family Mixture Model). Clients’ metadata (ϕi )1≤i≤N are modeled as samples from a finite mixture of distributions belonging to the exponential family. Under Assumption 1, the M-step reduces to computing empirical expectations of sufficient statistics weighted by the responsibilities, which can be expressed as additive aggregations [8, 28, 11]. Let tj (ϕi ) denote the components of the sufficient statistics for j = 1, . . . , s, where s is the number of such components. Correspondingly, distributions in the exponential family are fully characterized by their expectation parameters. For instance, in a Gaussian Mixture Model (GMM), this representation includes both the mean and uncentered covariance components, yielding s = 2 and t(ϕi ) = (ϕi , ϕi ϕ⊤ i ). Similarly, discrete metadata (e.g. per-class sample counts) can be modeled using a Multinomial mixture. In this case, ϕi represents the sufficient statistics. FLAMECHE clustering proceeds as follows. At the initial step, the server randomly initializes the (0) parameters Θ(0) = (θk )1≤k≤K . Once each participating client i locally extracts its static metadata vector ϕi , the EM procedure then alternates between two steps at each communication round. E-Step (Client-Side). Given the current global parameter estimates Θ(r−1) broadcast by the server, at round r, each client i computes its responsibilities (i.e., the posterior probabilities that ϕi belongs to each cluster k): (r−1) (r−1) π P (ϕi | θk ) (r) γi,k = PK k (r−1) , ∀k ∈ [1..K]. (2) (r−1) P (ϕi | θl ) l=1 πl 4
(r−1)
(r−1)
where πk denotes the mixing coefficient and θk the corresponding parameters associated with cluster k, both obtained from the M-step at round r − 1. For example, in the Gaussian case, (r−1) P (ϕi | θk ) is computed by evaluating the Gaussian density of cluster k at ϕi . This step is performed entirely on-client using its metadata and global distribution parameters. While (r) the metadata ϕi represents a static signature of the local dataset, the responsibilities γi,k update (r)
dynamically at each round. Under an encryption mechanism, each client sends to the server γi,k and (r)
encrypted vectors ([[γi,k tj (ϕi )]])1≤j≤s . M-Step (Server-Side). (j)
Sk =
N X
(r)
The server aggregates encrypted vectors using only additive operations:
[[γi,k tj (ϕi )]],
∀j ∈ [1..s],
Nk =
i=1
N X
(r)
γi,k
i=1
and
Nk (r) π k = PK
l=1 Nl
(3)
(j)
Here, Sk denotes the aggregated sufficient statistics for cluster k, and Nk the corresponding effective (r) cluster mass. Each component of the new parameters θk (e.g., means and covariances in case of (j) GMM) are updated via a deterministic mapping of the form fj (Sk /Nk ). For instance, in the (1) Gaussian case, this mapping reduces to computing the mean and covariance as µk = Sk /Nk and (2) Σk = Sk /Nk − µk µ⊤ k . Importantly, this step does not need to be performed on the server and can be applied after aggregation wherever plaintext values are available (e.g., on the client side at the start of the next E-step). While this procedure defines how cluster parameters are estimated, its effectiveness ultimately depends on the quality of the metadata representations ϕi used for clustering. In particular, the ability to correctly separate client groups relies on how well these representations capture underlying data differences. This raises the following question. How can we design metadata representations to distinguish client groups, without relying on prior knowledge of their data distribution? While FLAMECHE offers the flexibility of choosing a metadata, in this paper, we address this challenge with a zero-shot extractor based on randomized neural networks, strictly grounded in the distance-preserving properties of deep networks with random Gaussian weights [16]. 3.3
Zero-Shot Metadata Extraction via Randomized Latent Space Projection
We construct a compact representation ϕi of each client dataset Di directly from the target model architecture, ensuring alignment with the learning task. For classification, the global model W is decomposed as W (x) = H(F (x)), where F is the feature extractor and H the classifier head. We derive metadata from F by truncating the network before the final linear layer, yielding a dfeat -dimensional embedding (e.g., 512 for ResNet-18, 84 for LeNet-5). To avoid reliance on trained or pre-trained weights, using a shared random seed, each client initializes F with random Gaussian weights using the well-established Kaiming initialization [17]. We justify this zero-shot representation under the following condition. Assumption 2. Samples from the same distribution exhibit smaller angular separation than samples from different distributions. Under this condition, a randomly initialized ReLU Neural Network (NN) approximately preserves angular relationships, mapping closer inputs to more similar representations in the latent space. This design is supported by [16], which demonstrates that random ReLU networks preserve the angular structure of input. Thus, enabling meaningful representations for grouping without NN training. To summarize each local dataset, we extract metadata ϕi by computing class-wise empirical means in F induced latent space. X 1 ϕi = [µi,1 , . . . , µi,C ], with µi,c = F (xj ), ∀c ∈ {1, . . . , C} (4) |Di,c | (xj ,yj )∈Di,c
where Di,c is the subset of class c. This representation has fixed dimension d = C · dfeat , independent of dataset size. It is computed once per client, requires no optimization, and remains significantly 5
smaller than model parameters, ensuring low overhead. In case a client has missing labels, it is handled via a simple imputation strategy during E-step (Appendix C.1). The metadata captures variations in the underlying class-conditional feature distribution P (X | Y ) rather than differences in label distributions. While we focus on class-wise means, richer statistics (e.g., higher-order moments) could be incorporated. While FLAMECHE is not the first to leverage statistics computed in a feature space induced by a neural extractor [13, 31], prior approaches rely on stronger assumptions. CP-CFL [31] assumes access to a pretrained encoder aligned with the learning task, while FLUX [13] trains the model and requires one full-participation round to align client representations. In contrast, FLAMECHE adopts a fully agnostic approach, relying on randomly initialized extractors and operating strictly under partial participation. Its effectiveness is validated in Section 6. 3.4
From EM to a Practical CFL Instantiation
While the EM framework in Section 3.2 is general, we adopt a practical and efficient instantiation. We consider a spherical K-means-like variant of EM [10], corresponding to a limit case of GMM [28]. (r)
The client-side responsibility calculation reduces to γi,k = 1{k=arg minj d(ϕi ,θ(r−1) )} , where 1(·) is j
the indicator function and d the cosine dissimilarity. We adopt this dissimilarity because, unlike Euclidean distance, it focuses on angular differences, which are more stable in high-dimensional representation spaces and better align with Assumption 2. Server-Side (M-Step)
Client-Side
Initialise K centroids
Extract Metadata
5. Update centroids*
1. Broadcast Centroids*
4. Additive Aggregation
3. Upload to Server
Initialization steps
(E-Step) 2. Compute cluster assignment (On-client)
Communication steps at round r
Upload to Server
Figure 2: Algorithm 1 clustering mechanism. During initialization, the server initializes centroids and clients extract metadata. At each round r: (1) the server broadcasts centroids; (2) clients compute cluster assignments; (3) clients upload metadata (once) and assignments; (4) the server aggregates updates; (5) centroids are updated. * Depending on the encryption scheme, the server may broadcast (r) (Sk , |Ck |) instead of centroids, allowing clients to compute them locally (see Appendix D). For simplified notation, we denote by ki the latest cluster assignment of client i, which is updated (r) whenever the client participates and remains unchanged otherwise, and Ck the set of clients in cluster k at round r. Server-side computation reduces to aggregating metadata over cluster members. Each client assigned to cluster k securely contributes its optionally protected metadata [[ϕi ]], and the server computes the aggregated sum. X Sk (r) Sk = [[ϕi ]], θk = (r) , ∀k ∈ [1..K] (5) |Ck | (r) i∈Ck
(r)
Depending on the secure mechanism, if Sk is not recovered in plaintext, θk can be computed on-client (see Appendix D). As metadata remains fixed across rounds, clients upload it only once and subsequently transmit only their cluster assignments in later rounds. We denote as V the set of seen clients by the server. Each time a client i enters the federation for the first time, the server adds i to V and the M-step is performed over all clients in V using their stored metadata and latest assignments. This practical implementation is detailed in Algorithm 1. It includes partial participation with rate p (i.e., the clients participating in round r denoted by P (r) ). We also introduce a dynamic reclustering strategy to mitigate empty cluster configurations, a well-known issue in EM algorithms [39]. At 6
(r−1)
each round, client i computes the latest error ei = d(ϕi , θki ), corresponding to the distance to its currently assigned centroid. We then perform aP periodic check every τ rounds; the cluster with the 1 highest average error, k ∗ = arg maxk∈E (r) ei , redistribute its clients uniformly among / (r) i∈C |Ck |
k
(r)
Ck∗ and the empty clusters (We denote by E the set of indices of all empty clusters), followed by an update of the corresponding centroids. For stronger privacy, this procedure can be implemented under the same encryption mechanisms as the metadata. In such a setting, the server is restricted to additive aggregation, while clients assist with decryption and the arg max computation. An ablation study of this reclustering strategy is provided in Appendix C.2. Algorithm 1 FLAMECHE: Federated Learning Algorithm with distributed ExpectationMaximization Clustering over Hidden Metadata 1: Input: Number of clusters K, Number of rounds R, Reclustering frequency τ . 2: (0) (0) K 3: Initializes centroids {θk }K k=1 , models {wk }k=1 , and seen client set V = ∅ 4: for round r = 1 to R do 5: Sample participating clients P (r) ⊆ {1..N } with rate p (r−1) K 6: Server broadcasts {θk }k=1 to all clients i ∈ P (r) 7: for all clients i ∈ P (r) in parallel do 8: if i ∈ / V then 9: Extract local metadata ϕi using Equation 4 10: Upload encrypted metadata [[ϕi ]] to the server once 11: end if (r−1) 12: Compute assignment ki = arg mink d(ϕi , θk ) (r−1)
13:
Compute local assignment error ei = d(ϕi , θk
14:
(r−1) (r) Download model wk and train locally on Di to obtain wi i (r) Upload model update wi , assignment ki , and error ei to the server
i
▷ Server ▷ Server ▷ Server
▷ Client ▷ Client ▷ (E-Step) Client
)
▷ Client ▷ Client ▷ Client
15: 16: 17: 18: 19: 20:
end for Update seen clients V ← V ∪ P (r) (r) Update cluster assignments Ck = {i ∈ V : ki = k}, ∀k ∈ [1..K] for each non-empty cluster k do P (r) (r) (r) (r) 1 where Pk = P (r) ∩ Ck Aggregate cluster models wk = (r) (r) wi
21: 22: 23: 24: 25: 26:
end for if r mod τ = 0 then (r) Set of empty clusters E = {k ∈ [1..K] : Ck = ∅} if E ̸= ∅ then Find cluster with the highest average error k∗ = arg maxk∈E /
27:
i∈Pk |Pk | (r) Compute metadata centroid θk using Equation 5
▷ Server ▷ (M-Step) Server/Client
▷ (Reclustering Step) Server ▷ Server P 1 (r) ei (r) i∈Ck |Ck |
(r) Distribute the clients of Ck∗ uniformly among clusters indexed by E ∪ {k∗ } (r) Recompute θk , ∀k ∈ E ∪ {k∗ } using Equation 5
28: 29: end if 30: end if 31: end for
4
▷ Server ▷ Server
▷ Server/Client ▷ Server ▷ Server
Positioning FLAMECHE within the CFL Trilemma
We position FLAMECHE along the three axes of the CFL trilemma: computational overhead, communication cost, and compatibility with cryptographic constraints. Table 1 reports the additional clustering overhead compared to standard FedAvg [26] of CFL paradigms. Overhead excludes specific secure protocol costs, as approaches are not dependent on them (additional details in Appendix D). The complexity of Algorithm 1 depends on the metadata dimension d and the number of clusters K. Server-side and metadata-based don’t take account of clustering cost, as it is algorithm-dependent. Server-side approaches [37, 12] rely on pairwise model similarities, yielding at least O(R · Np2 · M ) complexity and requiring non-linear operations incompatible with efficient FL encryption. In contrast, FLAMECHE operates in low-dimensional metadata space with linear scaling O(R · Np · K · d), 7
Table 1: Added clustering complexity compared to FedAvg over R rounds. N Number of clients, Np = p × N : Number of participating clients per round, K: Number of clusters, M : model dimension, d: metadata dimension with d << M . CFL Paradigm
Server Computation
Client Computation
Upstream Communication
Downstream Communication
Server-side CFL Client-side CFL Metadata-based CFL
O(R · Np2 · M ) − O(N 2 · d)
− O(R · K · M ) −
− − O(d)
− O(R · K · M ) −
FLAMECHE (Ours)
O(R · Np · K · d)
O(R · K · d)
O(d)
O(R · K · d)
removing both the quadratic dependence on Np and the reliance on M . FLAMECHE’s client-side and communication overhead remains marginal compared to standard model training and transmission. Client-side methods, represented by IFCA [14], require evaluating K full models per round, leading to O(R · K · M ) computation and O(R · K · M ) communication. Subsequent client-side variants [4] retain this core mechanism while introducing additional components (e.g., soft assignments or crosscluster knowledge transfer). In contrast, FLAMECHE performs assignments in metadata space, reducing costs to O(R · K · d) computation and O(R · K · d) communication, with d ≪ M . Metadata-based approaches [9, 23, 32] achieve low overhead but rely on non-linear server-side clustering, limiting compatibility with standard encryption schemes. FLAMECHE introduces minimal additional overhead while remaining compatible with such mechanisms. Unlike methods that require collecting sufficient metadata before clustering [9, 23], FLAMECHE operates continuously as clients join. The additional server-side overhead is limited to simple additive aggregation. Decoupling Clustering from Training. FLAMECHE clusters solely rely on static metadata {ϕi }N i=1 , independently of model training. This enables exploring clustering configurations (e.g., K, metadata design) before training using suitable heuristics (see Appendix. B), avoiding repeated FL runs and reducing exploration cost. Overall, FLAMECHE achieves a favorable trade-off in the CFL trilemma by combining low overhead with compatibility with encrypted computation.
5
Results and Discussion
We evaluate FLAMECHE on five datasets: MNIST, Fashion-MNIST, CIFAR-10 (well-established benchmark in CFL), as well as two real-world medical datasets, TissueMNIST and PathMNIST [35]. We simulate three non-IID settings across five random seeds (100 clients, 50 samples per label, 4 latent clusters). These include concept shift on labels, feature distribution skew, and concept shift on features with label skew (a more challenging combined setting). While isolated concept shift via image rotation is generally considered a "solved" baseline in CFL [37, 14, 32], our combined setting deliberately stresses the setup. To induce concept shift in the rotation-invariant medical datasets, we apply channel permutations (PathMNIST) and zooming with grayscale inversion (TissueMNIST). Comprehensive dataset and hyperparameter details are provided in Appendix A. Table 2: Aggregated model performance (accuracy %) across all non-IID settings. Values represent the pooled mean and standard deviation across the three distinct heterogeneity setups and all random seeds. (s) denote server-side, (c) client-side, and (m) metadata-based methods. Algorithm Oracle
MNIST
Fashion-MNIST
CIFAR-10
TissueMNIST
PathMNIST
96.29 ± 1.41
83.70 ± 1.70
66.05 ± 7.65
32.08 ± 5.92
49.09 ± 7.52
FedAvg
81.86 ± 6.28
66.93 ± 4.62
54.42 ± 8.69
21.62 ± 10.28
30.96 ± 7.82
FedGroup (s) StoCFL (s) FeSEM (s) IFCA (c) K-Fed (m) PACFL (m) FLAMECHE (m)
89.52 ± 10.01 83.83 ± 13.82 90.81 ± 8.13 92.96 ± 2.68 89.43 ± 3.01 80.79 ± 7.13 94.82 ± 2.32
78.30 ± 10.56 69.83 ± 14.08 78.33 ± 9.66 78.55 ± 1.99 73.22 ± 2.32 66.75 ± 7.99 82.61 ± 2.46
56.82 ± 10.39 44.34 ± 11.07 54.57 ± 8.47 51.21 ± 7.36 48.06 ± 9.11 40.07 ± 7.24 64.73 ± 6.59
29.56 ± 4.88 24.86 ± 7.81 25.27 ± 7.13 30.33 ± 9.86 30.76 ± 4.70 23.28 ± 11.60 32.74 ± 4.51
44.62 ± 7.83 30.84 ± 7.25 43.24 ± 8.47 33.23 ± 4.83 46.23 ± 4.90 34.49 ± 7.20 45.46 ± 6.87
We conducted comparisons of FLAMECHE against FedAvg [26], an Oracle (known partition), server-side methods (FedGroup [12], StoCFL [37], FeSEM [22]), the client-side method IFCA [14], 8
and metadata-based methods (K-Fed [9], PACFL [32]). The selected baselines are restricted to methods that operate strictly under partial participation, without requiring any full-participation rounds, ensuring a fair comparison under consistent system constraints. All models (LeNet-5 or ResNet-18) are trained over 100 rounds with a participation rate p = 20% per round.
Average Aligned Rank (Lower is Better)
A. Overall Aligned Rank FLAMECHE FedGroup FeSem K-Fed IFCA StoCFL FedAvg PACFL
B. Aligned Rank per Dataset 100
0 20 40 60 80 Average Aligned Rank (Lower is Better)
80 60 40 20 0
Average Aligned Rank (Lower is Better)
Table 2 reports the pooled average local test accuracy across all heterogeneity settings, while Figure 3 presents aligned rankings [21] to emphasize statistically consistent improvements. FLAMECHE achieves the highest overall performance in 4 out of 5 datasets, closely matching the theoretical Oracle. Crucially, FLAMECHE exhibits exceptional robustness (low variance) across different shift types, whereas baselines like FedGroup, StoCFL, and PACFL suffer severe degradation under the combined heterogeneity stress tests. This highlights the fundamental advantage of our approach: conducting EM clustering in a stable, randomized metadata space rather than relying on the noisy, evolving trajectory of model updates. C. Aligned Rank per Heterogeneity Algorithm FLAMECHE FeSem FedAvg FedGroup IFCA K-Fed PACFL StoCFL
100 80 60 40 20
ST ST ST ST 10 MNI F-MNI CIFAR- ueMNI thMNI Tiss Pa
0
CSL
CSF
FDS
Figure 3: Aligned ranking [21] across all datasets and heterogeneity settings. FLAMECHE achieves the best overall rank, maintaining consistent performance across concept shift on features (CSF) with label skew, concept shift on labels (CSL), and features distribution skew (FDS). Baselines that perform well on isolated shifts (e.g., PACFL) suffer severe degradation under combined heterogeneity.
6
Ablation Study: Impact of Metadata Representations
Table 3 evaluates FLAMECHE under various metadata representations: our default random neural projections (Gaussian/Uniform), raw class-wise average images similar to K-fed (Mean), reduced averages (Mean + PCA), and subspace representations (PACFL). Clustering quality is measured via ARI (agreement with the Oracle partition) and DBI (cluster compactness, lower is better). Random projections yield strong stability, and near-optimal clustering (ARI ≈ 0.97) across all datasets. While raw Mean images perform similarly in multiple setups, they operate in a higherdimensional, highly interpretable (and thus privacy-sensitive) space. Conversely, PCA reduction and PACFL-style subspaces fail in this additive EM setting, likely because simple additive aggregation destroys their underlying geometric structures. This confirms that untrained random projections offer a highly effective, zero-shot metadata extraction strategy without requiring dataset-specific engineering. Table 3: Impact of FLAMECHE metadata representation on clustering performance. Results are averaged over 5 seeds and 3 heterogeneity settings. MNIST Metadata Gaussian Uniform Mean Mean + PCA PACFL
7
Fashion-MNIST
CIFAR-10
TissueMNIST
PathMNIST
ARI
DBI
ARI
DBI
ARI
DBI
ARI
DBI
ARI
DBI
0.97 ± 0.04 0.97 ± 0.04 0.98 ± 0.04 0.21 ± 0.18 0.00 ± 0.01
0.60 ± 0.07 0.57 ± 0.10 0.83 ± 0.09 2.53 ± 0.47 6.63 ± 0.64
0.97 ± 0.04 0.97 ± 0.04 0.97 ± 0.04 0.57 ± 0.47 0.02 ± 0.04
0.47 ± 0.07 0.45 ± 0.08 0.52 ± 0.12 1.65 ± 0.63 6.26 ± 0.48
0.97 ± 0.04 0.94 ± 0.14 0.97 ± 0.04 0.43 ± 0.39 0.00 ± 0.02
1.53 ± 0.39 1.63 ± 0.58 1.91 ± 0.17 3.04 ± 0.58 5.90 ± 0.95
0.97 ± 0.04 0.97 ± 0.04 0.97 ± 0.04 0.49 ± 0.32 0.10 ± 0.16
1.15 ± 0.53 1.15 ± 0.51 1.38 ± 0.61 2.80 ± 0.60 6.63 ± 0.64
0.97 ± 0.04 0.97 ± 0.04 0.91 ± 0.13 0.47 ± 0.38 0.01 ± 0.02
1.04 ± 0.40 1.10 ± 0.43 1.30 ± 0.34 2.00 ± 0.61 7.01 ± 0.20
Conclusion
By reformulating metadata-based CFL as a distributed EM procedure, FLAMECHE confines nonadditive operations to clients, restricting server updates to additive aggregation. This enables compatibility with encryption FL mechanisms without sacrificing efficiency. Evaluations show that our framework delivers accuracy and robustness across diverse and complex data heterogeneities. Even 9
though FLAMECHE provides a practical solution, our analysis is empirical. While our framework is designed to satisfy additive constraints, it does not assume a specific cryptographic infrastructure (see Appendix D). Although its EM formulation is general, current evaluations are restricted to hard clustering; extending them to soft settings (e.g., GMM) is left for future work. The use of partial participation relaxes standard EM convergence, leaving convergence proof as an open question. Finally, even if metadata can be protected via encryption, it remains a structured summary of local data, and its potential privacy implications should be considered.
References [1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308–318, 2016. [2] David Arthur, Sergei Vassilvitskii, et al. k-means++: The advantages of careful seeding. In Soda, volume 7, pages 1027–1035, 2007. [3] Zouheir Belfeki, Moez Krichen, and Salah Zidi. A systematic survey on clustering in federated learning. Multimedia Tools and Applications, 85(5):429, 2026. [4] Michael Ben Ali, Omar El-Rifai, Imen Megdiche, André Peninou, and Olivier Teste. A survey on clustered federated learning: Taxonomy, analysis and applications. arXiv preprint arXiv:2501.17512, 2025. [5] Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy-preserving machine learning. In proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 1175–1191, 2017. [6] Christopher Briggs, Zhong Fan, and Peter Andras. Federated learning with hierarchical clustering of local updates to improve training on non-iid data. In 2020 International Joint Conference on Neural Networks (IJCNN), pages 1–9. IEEE, 2020. [7] Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arithmetic of approximate numbers. In International conference on the theory and application of cryptology and information security, pages 409–437. Springer, 2017. [8] Arthur P Dempster, Nan M Laird, and Donald B Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the royal statistical society: series B (methodological), 39(1):1–22, 1977. [9] Don Kurian Dennis, Tian Li, and Virginia Smith. Heterogeneity for the win: One-shot federated clustering. In International Conference on Machine Learning, pages 2611–2620. PMLR, 2021. [10] Inderjit S Dhillon and Dharmendra S Modha. Concept decompositions for large sparse text data using clustering. Machine learning, 42(1):143–175, 2001. [11] Aymeric Dieuleveut, Gersende Fort, Eric Moulines, and Geneviève Robin. Federated-em with heterogeneity mitigation and variance reduction. Advances in Neural Information Processing Systems, 34:29553–29566, 2021. [12] Moming Duan, Duo Liu, Xinyuan Ji, Yu Wu, Liang Liang, Xianzhang Chen, Yujuan Tan, and Ao Ren. Flexible clustered federated learning for client-level data distribution shift. IEEE Transactions on Parallel and Distributed Systems, 33(11):2661–2674, 2021. [13] Dario Fenoglio, Mohan Li, Pietro Barbiero, Nicholas D. Lane, Marc Langheinrich, and Martin Gjoreski. Flux: Efficient descriptor-driven clustered federated learning under arbitrary distribution shifts. In Advances in Neural Information Processing Systems (NeurIPS), 2025. [14] Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran. An efficient framework for clustered federated learning. Advances in neural information processing systems, 33:19586– 19597, 2020. 10
[15] Avishek Ghosh, Justin Hong, Dong Yin, and Kannan Ramchandran. Robust federated learning in a heterogeneous environment. arXiv:1906.06629, 2019. [16] Raja Giryes, Guillermo Sapiro, and Alex M Bronstein. Deep neural networks with random gaussian weights: A universal classification strategy? IEEE Transactions on Signal Processing, 64(13):3444–3457, 2016. [17] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pages 1026–1034, 2015. [18] Peter Kairouz and H Brendan McMahan. Advances and open problems in federated learning. Foundations and trends in machine learning, 14(1-2):1–210, 2021. [19] Mikhail Khodak, Renbo Tu, Tian Li, Liam Li, Maria-Florina F Balcan, Virginia Smith, and Ameet Talwalkar. Federated hyperparameter tuning: Challenges, baselines, and connections to weight-sharing. Advances in Neural Information Processing Systems, 34:19184–19197, 2021. [20] Bingyan Liu, Nuoyan Lv, Yuanchun Guo, and Yawen Li. Recent advances on federated learning: A systematic survey. Neurocomputing, 597:128019, 2024. [21] Jie Liu and Yubo Xu. T-friedman test: A new statistical test for multiple comparison with an adjustable conservativeness measure. International Journal of Computational Intelligence Systems, 15(1):29, 2022. [22] Guodong Long, Ming Xie, Tao Shen, Tianyi Zhou, Xianzhi Wang, and Jing Jiang. Multi-center federated learning: clients clustering for better personalization. World Wide Web, 26(1):481– 500, 2023. [23] Guixun Luo, Naiyue Chen, Jiahuan He, Bingwei Jin, Zhiyuan Zhang, and Yidong Li. Privacypreserving clustering federated learning for non-iid data. Future Generation Computer Systems, 154:384–395, 2024. [24] Jie Ma, Tianyi Zhou, Guodong Long, Jing Jiang, and Chengqi Zhang. Structured federated learning through clustered additive modeling. Advances in Neural Information Processing Systems, 36:43097–43107, 2023. [25] Saber Malekmohammadi, Afaf Taik, and Golnoosh Farnadi. Differentially private clustered federated learning. Transactions on Machine Learning Research, 2025. [26] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273–1282. PMLR, 2017. [27] Viraaji Mothukuri, Reza M Parizi, Seyedamin Pouriyeh, Yan Huang, Ali Dehghantanha, and Gautam Srivastava. A survey on security and privacy of federated learning. Future Generation Computer Systems, 115:619–640, 2021. [28] Kevin P Murphy. Machine learning: a probabilistic perspective. MIT press, 2012. [29] Yao Pan, Zheng Chao, Wang He, Yang Jing, Li Hongjia, and Wang Liming. Fedshe: privacy preserving and efficient federated learning with adaptive segmented ckks homomorphic encryption. Cybersecurity, 7(1):40, 2024. [30] Felix Sattler, Klaus-Robert Müller, and Wojciech Samek. Clustered federated learning: Modelagnostic distributed multitask optimization under privacy constraints. IEEE transactions on neural networks and learning systems, 32(8):3710–3722, 2020. [31] Ye Lin Tun, Minh NH Nguyen, Chu Myaet Thwal, Jinwoo Choi, and Choong Seon Hong. Contrastive encoder pre-training-based clustered federated learning for heterogeneous data. Neural Networks, 165:689–704, 2023. 11
[32] Saeed Vahidian, Mahdi Morafah, Weijia Wang, Vyacheslav Kungurtsev, Chen Chen, Mubarak Shah, and Bill Lin. Efficient distribution similarity identification in clustered federated learning via principal angles between client data subspaces. In Proceedings of the AAAI conference on artificial intelligence, volume 37, pages 10043–10052, 2023. [33] Gang Wang, Li Zhou, Qingming Li, Xiaoran Yan, Ximeng Liu, and Yuncheng Wu. Fvfl: A flexible and verifiable privacy-preserving federated learning scheme. IEEE Internet of Things Journal, 11(13):23268–23281, 2024. [34] Lulu Wang, Mirko Polato, Alessandro Brighente, Mauro Conti, Lei Zhang, and Lin Xu. Priverifl: Privacy-preserving and aggregation-verifiable federated learning. IEEE Transactions on Services Computing, 18(2):998–1011, 2024. [35] Jiancheng Yang, Rui Shi, Donglai Wei, Zequan Liu, Lin Zhao, Bilian Ke, Hanspeter Pfister, and Bingbing Ni. Medmnist v2-a large-scale lightweight benchmark for 2d and 3d biomedical image classification. Scientific data, 10(1):41, 2023. [36] Mang Ye, Xiuwen Fang, Bo Du, Pong C Yuen, and Dacheng Tao. Heterogeneous federated learning: State-of-the-art and research challenges. ACM Computing Surveys, 56(3):1–44, 2023. [37] Dun Zeng, Xiangjing Hu, Shiyu Liu, Yue Yu, Qifan Wang, and Zenglin Xu. Stocfl: A stochastically clustered federated learning framework for non-iid data with dynamic client participation. Neural Networks, 187:107278, 2025. [38] Mengyu Zhang, Long Wang, Xiaoping Zhang, Zhuotao Liu, Yisong Wang, and Han Bao. Efficient clustering on encrypted data. In International Conference on Applied Cryptography and Network Security, pages 213–236. Springer, 2024. [39] Zhihua Zhang, Chibiao Chen, Jian Sun, and Kap Luk Chan. Em algorithms for gaussian mixtures with split-and-merge operation. Pattern recognition, 36(9):1973–1983, 2003.
A
Experimental Details and Additional Results
Experimental Setup. We consider 100 clients, each initially holding balanced local datasets with 50 samples per label before applying heterogeneity transformations. Clients are partitioned into 4 groups of 25, corresponding to K = 4 latent data-generating distributions. All experiments are conducted over 100 communication rounds with a client sampling rate of 20% per round. For each random seed, both the data distribution across clients and the client participation schedule are randomly generated. Each seed therefore jointly determines the client data partitioning and the per-round client sampling sequence. For a given seed, all compared methods share the exact same sampled clients at each round, ensuring strict comparability. Results are reported as the average over 5 independent random seeds. We evaluate three heterogeneity settings in the following order: (1) concept shift on labels, (2) features distribution skew, and (3) concept shift on features combined with label skew. While the main paper reports results aggregated across heterogeneity types, we provide here detailed results for each setting (Tables 4, 5, and 6). We use LeNet-5 for MNIST and Fashion-MNIST, and ResNet-18 for CIFAR-10, TissueMNIST, and PathMNIST. Local training is performed for 5 epochs (LeNet-5) and 10 epochs (ResNet-18) using the Adam optimizer with learning rate 10−3 and default parameters. Batch size is set to 128 for grayscale datasets and 256 for RGB datasets. All methods use identical architectures and initialization schemes when applicable. Heterogeneity Construction. Heterogeneity is introduced through controlled transformations applied at the group level. (1) Concept shift on labels. Each group is assigned a specific label permutation. For instance, in CIFAR-10, different groups apply swaps such as (0 ↔ 2), (1 ↔ 7), (0 ↔ 5), and (4 ↔ 7). This creates distinct label semantics across groups while preserving input distributions. 12
(2) Features distribution skew. Feature distributions are modified without altering labels. Four groups are constructed using image transformations: erosion with a 3 × 3 kernel, dilation with a 3 × 3 kernel, dilation with an 8 × 8 kernel, and a last group without transformation. This induces distributional skew in the features space while preserving label consistency. (3) Concept shift on features + label skew. This setting combines feature-level transformations and label imbalance. Feature transformations are dataset-specific: rotations (0°, 90°, 180°, 270°) for MNIST, Fashion-MNIST, and CIFAR-10; morphological and intensity transformations for TissueMNIST (normal, zoomed, inverted grayscale, inverted grayscale with zoom); and channel permutations for PathMNIST. Each concept group is further subdivided into five label distributions: the original (unskewed) distribution, and four skewed variants (normal, anti-normal, left-skewed, and rightskewed). This results in 4 × 5 = 20 distinct empirical client distributions overall.
Choice of the Number of Clusters. The number of clusters is fixed at K = 4 for all algorithms that require this parameter as input. This matches the number of underlying class-conditional feature variations (P (X|Y )) in our experimental construction. While selecting K is a non-trivial problem in CFL, our goal here is to evaluate clustering methods under controlled and known heterogeneity. Importantly, in the combined setting (concept shift on features with label skew), the additional label distributions introduce intra-group variability without necessarily corresponding to distinct clusters. Empirically, we observe that modeling K = 4 clusters remains the most effective choice in this setting (Appendix B). We therefore adopt K values as a consistent experimental configuration across all methods, rather than claiming it to be universally optimal.
Evaluation Metrics. Algorithm effectiveness is measured by the average test accuracy across clients’ test sets. Clustering quality is evaluated using the Adjusted Rand Index (ARI) and the Davies–Bouldin Index (DBI). ARI measures agreement with the ground-truth client partition (used by the Oracle baseline), while DBI evaluates cluster compactness and separation (lower is better). All metrics are reported at the final communication round.
Baselines. For all comparisons, we exclusively consider representative hard clustering CFL methods [4], whose primary objective is to discover the underlying client cluster structure. We intentionally exclude approaches combining clustering with additional mechanisms such as personalization, crosscluster knowledge transfer, or auxiliary optimization modules, as these improvements are orthogonal to the clustering strategy itself and could theoretically be incorporated into most hard clustering methods. Restricting the comparison to pure hard clustering approaches therefore isolates the contribution of the clustering mechanism and enables a fair evaluation. FedAvg [26] follows the standard federated averaging procedure. Oracle corresponds to FedAvg trained independently within ground-truth clusters. Server-side methods : FedGroup [12] is implemented using the recommended Euclidean Distance of Cosine dissimilarity (EDC) metric and a cold-start phase using 40% of clients (equivalent to two rounds of participation). StoCFL [37]) requires threshold selection; we perform a grid search over the full similarity matrix using a binary search procedure to identify the threshold that best separates clients into 4 clusters, as default values were not suitable in our setting. FeSEM [22] performs a K-means-like clustering procedure on client model parameters. Client-side methods : IFCA [14] is sensitive to initialization; we run 5 parallel initializations and retain the model achieving the best validation accuracy. Metadata-based methods : K-Fed [9] follows a one-shot clustering strategy, in which a global FedAvg model is first trained until metadata (local dataset centroids) from all clients have been collected, then used to perform one-shot clustering. PACFL [32]) is implemented with the recommended hyperparameters, using 5 components for subspace decomposition. FLAMECHE: FLAMECHE uses a randomly initialized feature extractor with Kaiming Gaussian weights, use the same initialization shared across all clients. Reclustering is triggered every τ = 10 rounds. 13
Results Discussion. Detailed results for each heterogeneity setting are reported in Tables 4, 5, and 6. While FLAMECHE is not always the top-performing method in every individual configuration, it consistently achieves strong performance across all heterogeneity types. Table 4: Clustering Performance under Concept Shift on Labels MNIST Algorithm Oracle FedAvg FedGroup (s) StoCFL (s) FeSEM (s) IFCA (c) K-Fed (m) PACFL (m) FLAMECHE (m)
Fashion-MNIST
CIFAR-10
TissueMNIST
PathMNIST
ARI
Accuracy
ARI
Accuracy
ARI
Accuracy
ARI
Accuracy
ARI
Accuracy
1.00 ± 0.00
97.90 ± 0.19
1.00 ± 0.00
85.80 ± 0.34
1.00 ± 0.00
75.02 ± 0.54
1.00 ± 0.00
37.44 ± 2.82
1.00 ± 0.00
49.29 ± 7.84
—
73.92 ± 2.95
—
64.56 ± 0.62
—
56.05 ± 6.92
—
24.72 ± 9.93
—
34.00 ± 7.64
1.00 ± 0.00 1.00 ± 0.00 1.00 ± 0.00 1.00 ± 0.00 1.00 ± 0.00 0.00 ± 0.01 0.96 ± 0.05
97.78 ± 0.19 96.42 ± 0.32 97.90 ± 0.17 95.69 ± 0.34 93.37 ± 0.48 71.66 ± 1.34 95.60 ± 3.03
1.00 ± 0.00 1.00 ± 0.00 1.00 ± 0.00 1.00 ± 0.00 1.00 ± 0.00 −0.01 ± 0.01 0.97 ± 0.05
85.59 ± 0.33 81.38 ± 0.71 85.75 ± 0.41 81.31 ± 0.13 75.83 ± 1.13 55.58 ± 0.83 83.96 ± 3.22
0.54 ± 0.15 0.33 ± 0.01 0.31 ± 0.08 0.55 ± 0.15 1.00 ± 0.00 0.00 ± 0.00 0.92 ± 0.07
66.07 ± 3.64 54.89 ± 3.89 61.25 ± 2.02 56.89 ± 1.64 56.59 ± 3.02 43.00 ± 3.81 70.94 ± 4.45
0.99 ± 0.02 0.80 ± 0.17 0.78 ± 0.08 0.34 ± 0.08 1.00 ± 0.00 0.00 ± 0.01 1.00 ± 0.00
31.78 ± 2.93 27.90 ± 0.88 30.76 ± 2.92 34.42 ± 0.53 33.41 ± 2.61 25.60 ± 3.93 34.94 ± 2.56
0.60 ± 0.15 0.62 ± 0.17 0.45 ± 0.09 0.10 ± 0.08 0.67 ± 0.01 0.00 ± 0.01 0.90 ± 0.19
48.99 ± 6.72 33.84 ± 7.66 46.46 ± 3.53 35.78 ± 3.50 47.44 ± 4.46 34.63 ± 8.12 46.07 ± 8.68
Table 5: Clustering Performance under Features Distribution Skew MNIST Algorithm Oracle FedAvg FedGroup (s) StoCFL (s) FeSEM (s) IFCA (c) K-Fed (m) PACFL (m) FLAMECHE (m)
Fashion-MNIST
CIFAR-10
TissueMNIST
PathMNIST
ARI
Accuracy
ARI
Accuracy
ARI
Accuracy
ARI
Accuracy
ARI
Accuracy
1.00 ± 0.00
94.53 ± 0.23
1.00 ± 0.00
83.39 ± 0.40
1.00 ± 0.00
66.61 ± 1.01
1.00 ± 0.00
31.43 ± 2.87
1.00 ± 0.00
52.40 ± 3.58
—
88.00 ± 1.52
—
72.82 ± 0.53
—
61.56 ± 2.62
—
27.09 ± 8.35
—
28.90 ± 9.98
1.00 ± 0.00 0.88 ± 0.16 0.95 ± 0.12 0.64 ± 0.15 1.00 ± 0.00 0.27 ± 0.02 0.97 ± 0.04
94.43 ± 0.15 90.40 ± 0.98 94.39 ± 0.58 89.58 ± 1.40 86.36 ± 0.28 81.86 ± 0.79 93.92 ± 1.09
1.00 ± 0.00 1.00 ± 0.00 0.95 ± 0.13 0.76 ± 0.12 1.00 ± 0.00 0.73 ± 0.13 0.95 ± 0.05
83.37 ± 0.25 78.07 ± 0.63 83.41 ± 0.68 77.26 ± 0.51 72.38 ± 1.06 72.28 ± 1.50 82.86 ± 1.04
0.28 ± 0.07 0.08 ± 0.17 0.18 ± 0.10 0.48 ± 0.12 1.00 ± 0.00 0.01 ± 0.00 0.98 ± 0.04
61.47 ± 1.59 47.09 ± 6.30 59.62 ± 1.41 54.53 ± 2.63 51.68 ± 0.51 43.67 ± 1.42 66.19 ± 1.06
0.07 ± 0.05 0.04 ± 0.00 0.08 ± 0.09 0.19 ± 0.00 1.00 ± 0.00 0.01 ± 0.02 1.00 ± 0.00
31.89 ± 4.47 32.25 ± 0.00 24.55 ± 9.48 39.83 ± 0.00 32.11 ± 4.05 33.66 ± 10.42 33.73 ± 6.20
0.99 ± 0.02 0.71 ± 0.19 0.77 ± 0.14 0.11 ± 0.04 1.00 ± 0.00 0.21 ± 0.12 0.98 ± 0.04
46.38 ± 7.09 32.31 ± 7.75 49.53 ± 5.85 36.38 ± 1.40 48.49 ± 4.51 31.65 ± 4.73 46.20 ± 7.35
Table 6: Clustering Performance under Concept Shift on Features (Label Skew) MNIST Algorithm Oracle FedAvg FedGroup (s) StoCFL (s) FeSEM (s) IFCA (c) K-Fed (m) PACFL (m) FLAMECHE (m)
Fashion-MNIST
CIFAR-10
TissueMNIST
PathMNIST
ARI
Accuracy
ARI
Accuracy
ARI
Accuracy
ARI
Accuracy
ARI
Accuracy
1.00 ± 0.00
96.45 ± 0.38
1.00 ± 0.00
81.90 ± 0.82
1.00 ± 0.00
56.52 ± 1.57
1.00 ± 0.00
27.37 ± 6.12
1.00 ± 0.00
45.57 ± 8.49
—
83.65 ± 1.81
—
63.41 ± 3.26
—
45.64 ± 6.39
—
13.06 ± 6.01
—
29.99 ± 3.31
0.02 ± 0.07 −0.02 ± 0.00 0.04 ± 0.08 1.00 ± 0.00 1.00 ± 0.00 1.00 ± 0.00 0.96 ± 0.04
76.35 ± 5.87 64.67 ± 1.88 80.13 ± 4.57 93.62 ± 0.29 88.56 ± 1.09 88.86 ± 0.56 94.95 ± 2.07
0.19 ± 0.26 −0.01 ± 0.01 0.20 ± 0.13 1.00 ± 0.00 1.00 ± 0.00 1.00 ± 0.00 0.99 ± 0.03
65.94 ± 10.13 50.05 ± 1.17 65.83 ± 6.50 77.07 ± 0.42 71.44 ± 1.76 72.38 ± 1.30 81.02 ± 1.52
−0.02 ± 0.01 −0.03 ± 0.00 −0.00 ± 0.01 0.36 ± 0.10 1.00 ± 0.00 0.00 ± 0.00 0.97 ± 0.03
42.93 ± 2.77 31.04 ± 4.12 42.84 ± 1.09 42.21 ± 5.33 35.90 ± 2.40 33.53 ± 8.73 57.07 ± 3.13
0.40 ± 0.22 −0.02 ± 0.00 0.26 ± 0.06 0.23 ± 0.00 1.00 ± 0.00 0.48 ± 0.00 1.00 ± 0.00
25.02 ± 3.46 14.43 ± 3.10 20.50 ± 0.81 16.75 ± 0.00 26.77 ± 4.28 10.59 ± 2.37 29.56 ± 0.00
0.14 ± 0.07 −0.03 ± 0.01 0.14 ± 0.14 0.09 ± 0.08 1.00 ± 0.00 0.35 ± 0.18 0.96 ± 0.05
38.50 ± 5.39 26.37 ± 2.81 33.74 ± 5.34 27.54 ± 2.63 42.76 ± 3.65 37.20 ± 7.21 44.11 ± 3.11
In contrast, several baselines exhibit high sensitivity to the type of distribution shift. Methods such as PACFL or StoCFL perform well under isolated setups but degrade significantly on more complex datasets with combined heterogeneity. For example, under CIFAR-10 with concept shift on features combined with label skew, algorithms become confused and cluster clients based on label distribution rather than concept shift, which significantly impacts performance. Similarly, K-Fed achieves strong clustering quality once clustering is performed, but its one-shot strategy delays cluster formation, as it requires collecting metadata from all clients before clustering. Because it performs standard FedAvg prior to clustering, this suboptimal training dynamic negatively affects model learning in subsequent rounds. FLAMECHE, by contrast, identifies cluster structure early through its EM formulation and continuously refines clusters during training. It starts clustering as soon as clients enter the federation, relying on rich low-dimensional metadata, which facilitates early structure discovery. Clustering in this space relies on simple distance computations, making it computationally efficient and avoiding the challenges of high-dimensional representations. This leads to stable performance across all settings and improved robustness to heterogeneous data distributions. These observations are consistent with the aggregated results reported in the main paper (Table 2) and the aligned rank analysis (Figure 3), where FLAMECHE achieves the best overall ranking across datasets and heterogeneity types.
B
Hyperparameter Selection via Unsupervised Metrics
Hyperparameter tuning is costly in federated settings [19]. The introduction of clustering in CFL further increases the number of hyperparameters, making this process even more costly. Selecting the 14
number of clusters K (or threshold-based hyperparameters that implicitly determine this number) in CFL typically requires running multiple end-to-end federated training procedures. Under most CFL algorithms (server-side and client-side), each configuration can only be evaluated using downstream metrics (e.g., test accuracy), leading to substantial communication and computation overhead dedicated solely to hyperparameter tuning. Since FLAMECHE decouples clustering from model training, hyperparameters can be evaluated directly on static metadata before any optimization, providing a satisfying heuristic. We use the Davies-Bouldin Index (DBI) as an unsupervised selection criterion. DBI measures the ratio of intra-cluster dispersion to inter-cluster separation and can be computed from metadata alone while respecting privacy requirements.
1.00
Adjusted Rand Index (ARI)
CIFAR10 FASHION-MNIST CIFAR10 (Concept Shift Features) (Concept Shift Features) (Concept Shift Labels)
Davies-Bouldin Index (DBI) FASHION-MNIST (Concept Shift Labels)
Target Clusters (K=4)
CIFAR10 (Feature Skew)
FASHION-MNIST (Feature Skew) 3
0.75
DBI (Red)
Score [0 to 1] (Accuracy & ARI)
Accuracy (Mean ± STD)
2
0.50 0.25 0.00
1
2
4
6
8
Clusters (K)
10
2
4
6
8
Clusters (K)
10
2
4
6
8
Clusters (K)
10
2
4
6
8
Clusters (K)
10
2
4
6
8
Clusters (K)
10
2
4
6
8
Clusters (K)
10
Figure 4: Hyperparameter selection before FL training. The Davies-Bouldin Index (DBI) is evaluated over different K. In most cases, low DBI aligns with the best ARI and accuracy. As shown in Figure 4, lower DBI values generally correspond to higher-quality clusterings, with good alignment to the best ARI and accuracy in most settings. While the configuration with the minimum DBI is not always the optimal one (e.g., under CIFAR10 with feature-distribution skew), DBI consistently narrows the search space to a small set of competitive candidates. This should be viewed as an empirical observation consistent across our experimental setups rather than a general guarantee. This enables efficient hyperparameter selection without accessing labels or performing additional training rounds. Crucially, DBI can be evaluated without exposing plaintext metadata. Each client computes its intracluster and inter-cluster distances locally and encrypts these quantities before transmission. The server then performs only additive aggregations over encrypted values, while non-linear operations (e.g., divisions and ratios) are deferred to the client side. This decomposition ensures full compatibility with privacy-preserving constraints.
C
Robustness Analysis
C.1
Handling Missing Labels
FLAMECHE relies on metadata that capture class-wise feature statistics, corresponding to the relationship between features and labels (P (X|Y )). As defined in Equation 4, each client represents its data through class-wise empirical means in the latent space of the feature extractor. In practice, some clients may not observe all labels. To handle this, missing entries in the metadata vector are accounted for during the E-step by computing responsibilities only over the indices corresponding to observed classes. This ensures that the assignment step remains well-defined despite incomplete metadata. To maintain a consistent representation dimensionality across clients, missing entries are then imputed using the nearest cluster centroid. Concretely, for a client representation ϕi = [µi,1 , . . . , µi,C ], if a class c∗ is missing, the corresponding feature µi,c∗ is replaced by the value from the assigned centroid θki at round r. Since centroids are computed as the average of clients’ metadata within a cluster at round r − 1, this procedure amounts to replacing missing features with those of similar clients. Empirically, this strategy preserves clustering quality even in the presence of missing labels. In Table 7, we evaluate a setting with concept shift on features where each client is missing one label. Results show that FLAMECHE remains competitive and is able to recover the correct clustering structure despite incomplete local label support. Figure 5 further illustrates that, although K-Fed can 15
identify the true clusters, repeated training rounds with FedAvg degrade model performance in this setting. Table 7: Illustration of robustness under concept shift on features with one missing label per client. Performance comparison of FLAMECHE against baselines on Fashion-MNIST and CIFAR-10 datasets. Fashion-MNIST CIFAR-10 Method
ARI
Accuracy (%)
ARI
Accuracy (%)
StoCFL FedGroup FeSEM IFCA PACFL K-fed FLAMECHE
1.00 1.00 1.00 1.00 1.00 1.00 1.00
81.96 ± 0.65 86.34 ± 0.59 86.11 ± 0.61 81.21 ± 3.91 76.86 ± 0.57 75.61 ± 0.47 86.33 ± 1.01
0.00 0.07 0.18 0.71 0.07 1.00 1.00
52.33 ± 8.61 57.01 ± 7.30 60.01 ± 6.77 58.88 ± 4.30 36.26 ± 5.72 50.00 ± 9.28 69.90 ± 2.93
FLAMECHE
70
FeSEM IFCA FedGroup K-Fed StoCFL
Accuracy (%)
60 50 40
PACFL
30 20 10 0
20
40
60
Communication Rounds
80
100
Figure 5: Accuracy per round under concept shift on features with missing labels under CIFAR10 C.2
Reclustering
FLAMECHE relies on a distributed EM procedure over client metadata. In standard EM algorithms, empty cluster configurations are a known issue [39], i.e., clusters that receive no assignments during the E-step. While transient empty clusters may occur without affecting the procedure, clusters that remain empty across iterations lead to degenerate solutions. This is particularly critical in our setting, as FLAMECHE cannot leverage methods that require direct observation of metadata [2, 39]; metadata representations are preferably not directly accessible. To mitigate this limitation, we introduce a reclustering mechanism (in Algorithm 1) that periodically reinitializes empty clusters. Specifically, every τ communication rounds, empty clusters and clusters with maximum average error are reinitialized. This allows the algorithm to prevent clusters from remaining inactive throughout training. Table 8 reports the impact of different reclustering frequencies (τ ∈ {10, 20, 30}) as well as the case without reclustering. Results are averaged over 3 random seeds across different heterogeneity settings. Overall, reclustering consistently improves clustering quality compared to no reclustering, especially under more complex heterogeneity, such as combined concept shift on features with label skew and feature distribution skew. Without reclustering, dead clusters persist in several runs, leading to degraded ARI and higher DBI (i.e., poorer cluster compactness). 16
Heterogeneity
Fashion-MNIST
Reclustering
PathMNIST
CIFAR-10
ARI
DBI
ARI
DBI
ARI
DBI
Concept Shift on Features + Label Skew
τ = 10 τ = 20 τ = 30 No
0.97 ± 0.05 0.97 ± 0.05 1.00 ± 0.00 0.89 ± 0.18
0.50 ± 0.02 0.47 ± 0.04 0.43 ± 0.04 0.70 ± 0.51
0.97 ± 0.05 0.96 ± 0.04 1.00 ± 0.00 0.80 ± 0.18
0.92 ± 0.25 0.92 ± 0.26 0.79 ± 0.10 0.72 ± 0.12
0.96 ± 0.04 0.97 ± 0.05 1.00 ± 0.00 1.00 ± 0.00
1.53 ± 0.16 1.53 ± 0.14 1.45 ± 0.17 1.50 ± 0.18
Concept Shift on Labels
τ = 10 τ = 20 τ = 30 No
0.97 ± 0.05 0.97 ± 0.05 1.00 ± 0.00 1.00 ± 0.00
0.41 ± 0.07 0.39 ± 0.09 0.33 ± 0.08 0.33 ± 0.08
0.97 ± 0.05 0.97 ± 0.05 1.00 ± 0.00 1.00 ± 0.00
1.51 ± 0.13 1.69 ± 0.28 1.67 ± 0.28 1.67 ± 0.28
0.97 ± 0.05 0.97 ± 0.05 1.00 ± 0.00 0.88 ± 0.21
1.95 ± 0.11 1.93 ± 0.15 1.87 ± 0.13 2.20 ± 0.56
Features Distribution Skew
τ = 10 τ = 20 τ = 30 No
0.97 ± 0.05 0.97 ± 0.05 1.00 ± 0.00 0.87 ± 0.22
0.51 ± 0.05 0.52 ± 0.03 0.49 ± 0.03 1.02 ± 0.92
0.97 ± 0.05 0.97 ± 0.05 1.00 ± 0.00 1.00 ± 0.00
0.68 ± 0.11 0.76 ± 0.11 0.73 ± 0.10 0.73 ± 0.10
0.98 ± 0.04 0.97 ± 0.05 1.00 ± 0.00 0.89 ± 0.19
1.08 ± 0.05 1.07 ± 0.11 1.03 ± 0.06 1.41 ± 0.69
Table 8: Reclustering comparison for different heterogeneity classes and parameters tested over 3 random seeds. Reclustering happens every τ rounds when having empty clusters.
Across all settings, moderate reclustering frequencies (τ = 20 or τ = 30) provide the most stable results. Smaller values (e.g., τ = 10) already mitigate dead clusters but may introduce slight instability due to more frequent reinitializations. In contrast, larger values cause reclustering to happen late in the federation, with risks of negative impact on learning. These results highlight that such reclustering is a simple yet effective mechanism to improve the robustness of FLAMECHE. C.3
Metadata Accumulation and Partial Participation.
In FLAMECHE, we recommend computing cluster centroids during the M-step over the full set of seen clients, with their metadata stored at the server. Because client metadata representations remain static across communication rounds, the server can accumulate and store these representations over time, even in encrypted form. As new clients participate, their metadata and cluster assignments are incorporated, allowing the clustering structure to refine progressively. At each communication round, only the assignments of participating clients are updated. However, accumulating metadata across rounds may introduce complexities under certain cryptographic protocols. For instance, in Secure Aggregation [5], masks are designed to cancel within a single round, making persistent cross-round statistics less straightforward to maintain without additional mechanisms. As a result, this setting does not constitute a direct application of standard Secure Aggregation workflows. To ensure easier compatibility with such protocols, FLAMECHE can be restricted to computing the M-step using only the metadata of clients participating in the current round. Table 9 provides an illustrative comparison between these two strategies. While using only current-round participants may lead to slightly degraded clustering quality in some settings, leveraging the full set of seen clients generally provides more stable results. Overall, the differences remain limited in our experiments, indicating that the partial variant remains a viable alternative when required by the deployment setting. This observation, however, may not hold under very low participation rates, where limited client coverage per round can affect the stability of the estimated cluster statistics.
Table 9: Example of comparison of FLAMECHE clustering performance (ARI and DBI) using all seen metadata (normal) versus only round participants (partial) for the maximization step. Results are shown for an independent run that highlight the difference between the two approaches. Fashion-MNIST
TissueMNIST
PathMNIST
CIFAR-10
Algorithm
Metadata Aggregation
ARI
MNIST DBI
ARI
DBI
ARI
DBI
ARI
DBI
ARI
DBI
FLAMECHE
Normal (All seen) Partial (Participants)
1.00 1.00
0.58 0.58
1.00 1.00
0.42 0.42
1.00 1.00
1.15 1.15
1.00 0.98
0.97 1.03
1.00 0.97
1.53 1.67
17
D
FLAMECHE under Different Cryptographic Settings
While FLAMECHE is agnostic to specific additive cryptographic schemes, it is essential to discuss the potential implications of each deployment context. In this section, we consider three of the most practical secure FL schemes [27]: Secure Aggregation [5], Paillier Homomorphic Encryption [34], and CKKS Homomorphic Encryption [7]. In this Appendix section, we focus on enabling encryption for metadata only; encryption of model updates follows the standard FedAvg setting and is therefore not discussed further. D.1
Secure Aggregation
In standard Secure Aggregation protocols [5], masking terms cancel out exactly during aggregation, allowing the server to directly recover the sum of the metadata in plaintext. Consequently, the server can update the centroids in Equation 5 without relying on clients. Masks are constructed to cancel pairwise between clients, and in practice, this cancellation is ensured within each round among participating clients. As clients join and leave the federation, the protocol naturally guarantees correct cancellation for current-round participants. In the CFL setting, this implies that masking must be established accordingly: at a given round, clients should form masks only with other participants assigned to the same cluster. As mentioned in Appendix C.3, under FLAMECHE with Secure Aggregation, this is achieved by restricting the M-step to current-round participants. In this case, since the original Secure Aggregation protocol already accounts for dynamic participation, applying it in the CFL setting amounts to considering each cluster as a separate FL instance, where clients join and leave over time. We emphasize that this requirement concerns the more complex, potentially persistent masking management of the Secure Aggregation protocol under M-step over all seen clients, rather than a flaw in the FLAMECHE algorithm. D.2
Homomorphic Encryption
Under Homomorphic Encryption (HE), the server operates entirely on encrypted values and cannot decrypt aggregated results. In this case, the server have to rely on clients to update the centroids in Equation 5. For each cluster, because the aggregate [[Sk ]] remains encrypted, the server needs to (r) broadcast [[Sk ]] and |Ck | instead of the centroids. Clients can decrypt and compute Equation 5 locally to proceed to E-step. Because the updated centroids are only utilized by the clients during the E-step, this delegation does not disrupt the clustering workflow. Paillier Homomorphic Encryption. Paillier is an additive homomorphic encryption scheme defined over integers. In practice, real-valued quantities (e.g., gradients or metadata) must therefore be encoded into integers via fixed-point scaling before encryption. While the management of key initialization is a well-studied problem in the literature [27]. The computational cost of Paillier is non-trivial [34], especially if used over extreme dimension model updates. While protocols [34, 33] exist to take account of those high dimensions, as shown in our timing analysis ( D.3), in FLAMEHCE the latency overhead is manageable exclusively because it operates on low-dimensional metadata rather than full model weights. Paillier results use fixed-point encoding (109 scale), hence represent approximate real-valued aggregation. Empirically, this quantization has no observable impact on FLAMECHE performance across all evaluated datasets, yielding results identical to the plaintext baseline. CKKS Homomorphic Encryption. CKKS [7, 29] is an efficient partial HE scheme designed for floating-point arithmetic, which introduces a small numerical perturbation (noise) during encoding, rescaling, and aggregation. Table 10 highlights the empirical impact of this CKKS noise on FLAMECHE’s clustering performance. For this evaluation, CKKS is implemented using the TenSEAL Python library with standard parameters (N = 16384, {60, 50, 50, 60}, ∆ = 250 ), while Paillier uses the phe Python library. The numerical perturbation affecting client assignments is negligible in most datasets (typically ≤ 0.02 ARI difference). However, the perturbation has a slightly more pronounced effect on the TissueMNIST dataset. This occurs because the decision boundaries between heterogeneous groups 18
in this specific setting are more subtle and thus more sensitive to cryptographic noise. Refining the reclustering mechanism or increasing the precision of the CKKS parameters could further mitigate these effects. Table 10: Impact of CKKS numerical noise on clustering performance of FLAMECHE. Results compare the unencrypted baseline (no-CKKS) against execution under Partial Homomorphic Encryption (CKKS). MNIST
Fashion-MNIST
CIFAR-10
TissueMNIST
PathMNIST
Setting
ARI
DBI
ARI
DBI
ARI
DBI
ARI
DBI
ARI
DBI
no-CKKS CKKS
0.96 ± 0.04 0.94 ± 0.13
0.60 ± 0.09 0.61 ± 0.12
0.97 ± 0.05 0.96 ± 0.11
0.43 ± 0.09 0.46 ± 0.15
0.97 ± 0.05 0.96 ± 0.11
1.49 ± 0.37 1.59 ± 0.36
1.00 ± 0.00 0.85 ± 0.17
1.09 ± 0.52 1.35 ± 0.46
0.95 ± 0.11 0.93 ± 0.14
1.02 ± 0.58 1.07 ± 0.53
D.3
Discussion of Cryptographic Implications
This section provides a high-level discussion of cryptographic implications. The reported costs are intended to give general insights and do not account for implementation-specific optimizations or protocol-level communication details, which are outside the scope of this work. Table 11: Per-round cryptographic overhead for 100 clients on a standard workstation (Intel Core i7, 16 threads). Results are reported for full-model updates and metadata-based aggregation. Secure Aggregation reports masking and aggregation costs. CKKS is implemented using TenSEAL, encrypting each vector as a single ciphertext. Paillier results are obtained using our optimized C++ implementation (2048-bit keys, GMP backend). ResNet-18 metadata timings are measured; LeNet-5 metadata timings are linearly scaled from these measurements (†). Implementations follow standard libraries for each scheme and are therefore representative rather than strictly implementation-matched. Secure Aggregation Architecture
Representation
LeNet-5 ResNet-18
HE (CKKS)
HE (Paillier)
Client (Mask)
Server (Sum)
Client (Enc)
Server (Sum)
Client (Dec)
Client (Enc)
Server (Sum)
Client (Dec)
Full Model Metadata
27.72 ms 0.35 ms
2.80 ms 0.05 ms
60.70 ms 6.90 ms
99.20 ms 12.40 ms
14.90 ms 1.80 ms
– 9.57 s†
– 0.33 s†
– 6.22 s†
Full Model Metadata
5.39 s 2.54 ms
0.93 s 0.26 ms
10.33 s 9.00 ms
16.93 s 12.40 ms
2.60 s 1.80 ms
– 58.30 s
– 2.01 s
– 37.89 s
Table 12: On-client communication cost for metadata and full-model representations. Secure Aggregation assumes 64-bit masks (8 bytes per parameter). CKKS is evaluated using TenSEAL (N = 16384, scale 250 ), encrypting each vector as a single ciphertext. Paillier uses our C++ implementation with per-element encryption; ciphertext sizes are measured via hex encoding. Reported sizes exclude protocol-specific overhead. Architecture
Representation
Dimension
Plaintext Size
Secure Aggregation (mask)
HE (CKKS)
HE (Paillier)
LeNet-5
Full Model Metadata
61,706 840
0.2404 MB 0.0032 MB
– 0.0064 MB
– 0.6996 MB
– 0.4095 MB
ResNet-18
Full Model Metadata
11,176,512 5,120
42.7280 MB 0.0195 MB
– 0.0391 MB
– 0.6996 MB
– 2.4963 MB
Table 11 reports the wall-clock time for applying Secure Aggregation, Paillier, and CKKS HE protocols, evaluated on a standard workstation (Intel Core i7, 16 threads). Encrypting full model weights introduces substantial latency. For Paillier, this cost is further amplified by the lack of vector encryption and the need for per-element encoding; as a result, full-model encryption with Paillier is prohibitively expensive and is therefore not reported. In our implementation, encryption and decryption of metadata are not cheap, but depending on the setup, this may appear acceptable compared to local model training. Methods exist to lower these costs [34, 33, 27], but their study and impact on FLAMECHE are out of the scope of this paper. For CKKS HE specifically, large models exceed single-CKKS ciphertext capacity (e.g., 8, 192 slots in TenSEAL CKKS), requiring severe fragmentation that drives server-side summation times up to 17 seconds for ResNet-18. In contrast, FLAMECHE metadata fits comfortably within a single ciphertext. This results in millisecond-scale overhead for encryption, masking, and aggregation. As detailed in Table 12, the additional payload of encrypted metadata becomes negligible compared to multiple model sharings as models become increasingly larger. This dimensionality reduction ensures that 19
strictly encrypted clustering remains highly practical without requiring modifications to standard cryptographic pipelines. Ultimately, these benchmarks highlight how FLAMECHE effectively navigates the CFL trilemma. Historically, deploying HE or SMPC for server-side clustering was considered prohibitively expensive, forcing practitioners to either abandon strong privacy guarantees (by sharing plaintext metadata) or accept severe computational bottlenecks (by relying on encrypted clustering). By compressing the clustering signal into low-dimensional metadata and strictly bounding server-side operations to linear aggregations, FLAMECHE bridges this gap. It demonstrates that metadata-based clustering can be deployed efficiently under standard privacy-preserving FL protocols.
20