Federated Learning (FL) is an emerging distributed machine learning approach that preserves client privacy by storing data on edge devices. However, data heterogeneity among clients presents challenges in training models that perform well on all local distributions. Recent studies have proposed clustering as a solution to tackle client heterogeneity in FL by grouping clients with distribution shifts into different clusters. However, the diverse learning frameworks used in current clustered FL methods make it challenging to integrate various clustered FL methods, gather their benefits, and make further improvements.

To this end, this paper presents a comprehensive investigation into current clustered FL methods and proposes a four-tier framework, namely , to encompass and extend existing approaches. Based on the , we identify the remaining challenges associated with current clustering methods in each tier and propose an enhanced clustering method called to address these challenges. Through extensive numerical evaluations, we showcase the effectiveness of our clustering framework and the improved components. Our code will be publicly available.

§ INTRODUCTION

Federated Learning (FL) is a privacy-focused distributed machine learning approach. In FL, the server shares the model with clients for local training, and the clients send parameter updates back to the server. The clients will not share their raw data with servers, ensuring privacy. However, the non-iid client data distribution leads to significant performance drops for FL algorithms [McMahan et al., 2016, Li et al., 2018, Karimireddy et al., 2020, Karimireddy et al., 2019].
To address data heterogeneity, traditional FL focuses on training a single global model that performs well across all local distributions [Li et al., 2021, Li et al., 2018, Tang et al., 2022, Guo et al., 2023]. However, relying solely on a global model may not adequately handle the heterogeneous client distributions. As a remedy, clustered FL methods have been proposed to group clients into different clusters based on their local distributions. Numerous studies have demonstrated the superiority of clustered FL methods over single-model FL approaches [Long et al., 2023, Sattler et al., 2020, Ghosh et al., 2020, Marfoq et al., 2021, Guo et al., 2023].

Overview of the .
The encompasses the existing clustered FL algorithms through the design of four tiers,
including cluster formulations, which maximize conditional distribution, joint distribution, or variable relationships;
cluster weights calculation, including soft clustering and hard clustering; adaptive clustering procedure, including using a predefined number of clusters, automatically adding new clusters, or merge and remove existing clusters; client distance metrics, including using distance on clients' local gradients, clients' local model parameters, or clients' local feature norms. The four tiers collaborate to form a comprehensive clustered FL learning process, as shown in the left part of the figure. For instance, CFL can be described by the A, D, G, and J, while A, E, and F cover FedEM.=-1

Diverse learning frameworks pose challenges on enhancing the clustered FL.
Despite the success of current clustered FL methods, the use of diverse learning frameworks poses challenges in integrating different algorithms, gathering their advantages, and achieving further improvements.
For instance, FedEM [Marfoq et al., 2021] excels in addressing complex mixture distribution scenarios and performs admirably on challenging tasks. However, it necessitates a predefined number of clusters, constraining its practicality.
In contrast, adaptive clustering techniques such as CFL [Sattler et al., 2020] can autonomously determine the number of clusters. Nonetheless, CFL cannot be seamlessly integrated with soft clustering methods like FedEM, thereby limiting its effectiveness in handling complex mixture distribution tasks.

Consolidating existing methods as a solution.
To tackle these challenges, our aim is to establish a holistic learning framework for clustered FL methods, allowing us to seamlessly combine their advantages. Once accomplished, we can easily incorporate existing methods such as FedEM and CFL to develop an improved approach (see Table <ref>).

Therefore, we first revisit and summarize existing clustered FL methods. We then introduce , a holistic clustered FL algorithm framework with four tiers (as shown in Figure <ref>). These tiers address the primary tasks in clustering methods: (1) Cluster Learning and Assignment (tiers 1 and 2), which assigns clients to optimal clusters and learns cluster-specific parameters; (2) Cluster Number Determination (tiers 3 and 4), which decides the number of clusters.
The four tiers within constitute a comprehensive clustered FL learning process that incorporates existing methods and allows for flexible modifications in each tier (see Algorithm <ref>). It is evident that the enhanced algorithms exhibit significant performance improvements compared to the original methods, as demonstrated in Table <ref>.

In light of the , we have identified the remaining challenges within each tier that were previously overlooked by existing clustered FL, as illustrated in Figure <ref> in Section <ref>. We then introduce , an enhanced algorithm designed to tackle these remaining challenges.
Numerical results confirm that effectively extends existing methods, achieving a superior balance between personalization and generalization while delivering strong performance.

We summarize the contribution of this paper as follows:

* We introduce , a holistic framework for clustered FL that encompass the existing methods. enables the integration of existing methods' benefits by adjusting techniques in each tier.=-1

* We identify four remaining challenges in clustered FL algorithms within each tier of , and introduce an improved algorithm called to address these challenges.

* Extensive experiments on different datasets (CIFAR10, CIFAR100, and Tiny-Imagenet) and various architectures (MobileNet-V2 and ResNet18) demonstrate the effectiveness of our framework and the improved components of .=-1

§ RELATED WORKS

In the field of Federated Learning, FedAvg serves as the de-facto algorithm, employing local Stochastic Gradient Descent (local SGD) techniques [McMahan et al., 2016, Lin et al., 2020] to reduce communication costs and protect client privacy. However, FL faces significant challenges due to distribution shifts among clients, which can hinder the performance of FL algorithms [Li et al., 2018, Wang et al., 2020, Karimireddy et al., 2020, Jiang & Lin, 2023, Guo et al., 2021].
Traditional FL methods primarily focus on improving the convergence speed of global models and incorporate bias reduction techniques [Tang et al., 2022, Guo et al., 2023, Li et al., 2021, Li et al., 2018]. However, these single-model approaches are often inadequate for handling heterogeneous data distributions, especially in cases involving concept shifts [Ke et al., 2022, Guo et al., 2023, Jothimurugesan et al., 2023].
To address these challenges, researchers have introduced clustered FL algorithms to enhance the performance of FL algorithms.=-1

Clustered FL groups clients based on their local data distribution, addressing the distribution shift problem. Most methods employ hard clustering with a fixed number of clusters, grouping clients by measuring their similarities [Ghosh et al., 2020, Long et al., 2023, Wang et al., 2022, Stallmann & Wilbik, 2022]. However, hard clustering may not adequately capture complex relationships between local distributions, and soft clustering paradigms have been proposed to address this issue [Marfoq et al., 2021, Wu et al., 2023, Ruan & Joe-Wong, 2022, Guo et al., 2023].
In this paper, we propose a generalized formulation for clustered FL that encompasses current methods and improves them by addressing issues related to intra-client inconsistency and efficiency.=-1

Another line of research focuses on automatically determining the number of clusters. Current methods utilize hierarchical clustering [Sattler et al., 2020, Sattler et al., 2020, Zhao et al., 2020, Briggs et al., 2020, Zeng et al., 2023, Duan et al., 2021, Duan et al., 2021], which measures client dissimilarity using model parameters or local gradient distances. Some papers enhance these distance metrics by employing various techniques, such as eigenvectors [Yan et al., 2023] and local feature norms [Wei & Huang, 2023]. FEDCOLLAB [Bao et al., 2023] quantifies client similarity through client discriminators. However, the requirement for discriminators between every client pair in FEDCOLLAB hinders scalability for cross-device scenarios with numerous clients.
In this paper, we concentrate on cross-device settings, introducing a holistic adaptive clustering framework enabling cluster splitting and merging. We also present enhanced weight updating for soft clustering and finer distance metrics for various clustering principles. For further discussions on related works, please refer to Appendix <ref>.

§ : REVISITING AND EXTENDING CLUSTERED FL METHODS

Current clustered FL methods typically employ diverse learning frameworks. As a result, existing methods often face challenges in gathering the advantages of different algorithms for potential enhancements.
To address this issue, as shown in Figure <ref>, we introduce the , consisting of four tiers designed to tackle the primary tasks of clustering methods:
(1) Cluster Learning and Assignment (tiers 1 and 2): Identify which clients should belong to the same clusters and learns parameters for each cluster.
(2) Cluster Number Determinant (tiers 3 and 4): Decide the number of clusters.
As a result, the four tiers of the form a comprehensive learning process (Algorithm <ref>), enabling flexible improvements and the integration of advantages from different algorithms (Table <ref>).=-1

§.§ Tiers 1 & 2: The and

We introduce the first two tiers: and . defines the objective functions of the clustering methods, aiming to learn the underlying distributions of each cluster.
orthogonally helps find the suitable clusters for each client, whereas hard clustering assigns each client to one cluster, while soft clustering allows clients to contribute to multiple clusters.
We propose the following optimization framework to encompass these two tiers.

Optimization framework of clustered FL methods.
The clustered FL methods can be expressed as a dual-variable optimization problem that maximizes $\cL(\mTheta, \mOmega)$, with $K$ clusters and $M$ data sources represented as $\cD_1, \cdots, \cD_M$:

\begin{align}
\label{equ:general-objective}
\textstyle
\cL(\mTheta, \mOmega) & = \frac{1}{N} \sum_{i=1}^{M} \sum_{j=1}^{N_i} \log \left( \sum_{k=1}^{K} \omega_{i;k} \cL_k(\xx_{i,j}, y_{ij}; \mtheta_k) \right) \,, \quad \text{s.t.} \quad
\sum_{k=1}^{K} \omega_{i;k} = 1, \forall i  \,,
\end{align}

where $N = \sum_{i=1}^{M} N_i$ and $N_i := |\cD_i|$.
The parameters to be optimized are clustering weights $\mOmega = [\omega_{1;1}, \cdots, \omega_{M, K}]$, and model parameters $\mTheta = [\mtheta_1, \cdots, \mtheta_K]$.

Tier 1: Incorporate existing .
The existing methods employ clustering to address diverse tasks, which results in the proposal of various formulations. Our Algorithm <ref> encompasses the existing clustering formulations by selecting $\cL_k(\xx_{i,j}, y_{ij}; \mtheta_k)$ as follows:

* $\cP_{\mtheta_k}(y_{i,j} | \xx_{i,j})$.
Most existing methods [Marfoq et al., 2021, Ghosh et al., 2020, Long et al., 2023] can be recovered using this conditional distribution (likelihood functions).

* $\cP_{\mtheta_k} (\xx_{i,j}, y_{i,j})$.
FedGMM [Wu et al., 2022] uses this joint probability. [In FedGMM [Wu et al., 2023], $\mtheta_k$ is split into $[\mtheta_{k_1}, \mnu_{k_2}]$, and it uses $\cL_k(\xx_{i,j}, y_{i,j}; \mtheta_k) = \cP_{\mtheta_{k_1}}(y_{i,j}|\xx_{i,j})\cP_{\mnu_{k_2}}(\xx_{i,j})$ to model the joint probability.]

* $\frac{\cP_{\mtheta_k}(\xx_{i,j},y_{i,j})}{\cP_{\mtheta_k}(\xx_{i,j})\cP_{\mtheta_k}(y_{i,j})}$.
FedRC [Guo et al., 2023] relies on correlations between variables $\xx$ and $y$. =-1

Tier 2: Incorporate existing .
Various methods employ distinct mechanisms for calculating clustering weights $\omega_{i;k}$.
The choice of $\omega_{i;k}$, with either binary values $\omega_{i;k} \in \{0, 1\}$ or continuous values $\omega_{i;k} \in [0, 1]$, characterizes the dynamic clustering procedure.

* Hard clustering methods employ binary values $\omega_{i;k} \in {0, 1}$.
In these methods, $\omega_{i;k}$ is determined using heuristic techniques, such as parameter distance [Long et al., 2023, Zeng et al., 2023, Sattler et al., 2020] or local loss function values [Ghosh et al., 2020].=-1

* Soft clustering approaches permit $\omega_{i;k} \in [0, 1]$, determined by maximizing $\cL(\mTheta, \mOmega)$[Marfoq et al., 2021, Guo et al., 2023, Wu et al., 2023], or by normalizing local loss values[Ruan & Joe-Wong, 2022]. Soft clustering methods do not assume separated clients' local distributions and can thus handle complex scenarios, such as mixture distributions [Marfoq et al., 2021, Wu et al., 2023].

§.§ Tiers 3 & 4: The Adaptive Clustering Procedure and Distance Metrics

[1]
Number of communication rounds $T$, initial number of clusters $K^{0}$, initial parameters $\mphi^{0}$, and $\mTheta^{0}$.
Number of clusters $K^{T}$, trained parameters $\mphi^{T}$, and $\mTheta^{T}$.
$t = 0, \cdots, T-1$
Sample a subset of clients $\cS^{t}$, and send $\mTheta^{t+1}$ to the clients.
Client $i$ in $\cS^{t}$
Local updates by solving (<ref>).Tiers 1 and 2
Upload local gradients $\gg_{i;k}^{t+1}$ to the server.
$\mtheta_{k}^{t+1} = \mtheta_{k}^{t} - \eta_g \sum_{i \in \cS^{t}} \gg_{i;k}^{t+1}$, $\forall k$.
Calculate distance matrix $\mD^{t}$, and $\mD_k^{t}$ for each cluster $k$. Tier 4
Detect cluster $k_{s}$ need to be split Tier 3
Split clients in cluster $k_{s}$ into two sub-clusters $\cS_{s, 1}$ and $\cS_{s, 2}$ based on $\mD_{k_s}^{t}$ or $\mD^{t}$.
$\mtheta_{k_s}^{t+1} = \mtheta_{k}^{t} - \eta_g \sum_{i \in \cS_{s, 1}} \gg_{i;k}^{t+1}$.
$\mtheta_{K^{t} + 1}^{t+1} = \mtheta_{k}^{t} - \eta_g \sum_{i \in \cS_{s, 2}} \gg_{i;k}^{t+1}$.
Update $\omega_{i;k}$ for corresponding clients.
Detect cluster $k_{d}$ need to be deletedTier 3
Delete cluster $k_{d}$.
Update $\omega_{i;k}$ for corresponding clients.
Update $K^{t+1}$ by the current number of clusters.

algorithm: holistic Algorithm Framework of clustered FL.

Tiers 3 and 4 illustrate the techniques for Cluster Number Determination. In detail, the adaptive clustering procedures automatically adjust the number of clusters, while distance metrics control the adaptive clustering procedures, determining whether clusters should split or merge.
The allows for different techniques at each tier, enhancing flexibility in choosing the optimal adaptive clustering methods or converting methods that rely on fixed cluster numbers to adaptive ones.

Tier 3: Adaptive clustering procedures demonstrate how to modify cluster numbers.
To automatically determine the number of clusters, current approaches can be categorized into two orthogonal methods:
(1) Splitting clusters to increase the number of clusters [Sattler et al., 2020, Sattler et al., 2020].
(2) Merging clusters to reduce the number of clusters [Zeng et al., 2023].
We unify these approaches at tier 3.

Tier 4: Client distance metrics dictate when cluster numbers should be adjusted.
The client's distances are utilized to determine whether the current number of clusters should be adjusted. For instance, when the distance within a cluster is large, the cluster will divide into sub-clusters. Conversely, if the distances between two clusters are small, these two clusters should be merged. Existing clustering methods use various metrics such as cosine similarity of local gradients [Sattler et al., 2020], gradients from a globally shared network [Zeng et al., 2023], and local feature norms [Wei & Huang, 2023].

Remaining challenges in clustered FL methods.
We identify four key issues in clustered FL algorithms: (1) inconsistent intra-client clustering weights, (2) efficiency concerns, (3) the absence of adaptive clustering for soft clustering methods, and (4) the lack of fine-grained distance metrics for various clustering principles. Clustering principles and differ in their approach as follows: assigns clients with any shifts into different clusters, while only assigns clients with concept shifts to different clusters."

§ : TACKLING REMAINING CHALLENGES IN CLUSTERED FL

Section <ref> introduces a holistic clustering framework with four tiers to encompass existing methods. However, each tier still presents challenges that current methods cannot address. In this section, we outline four key remaining challenges in Figure <ref> and introduce to tackle them. Due to space constraints, we summarize the improved algorithm in Algorithm <ref>.

§.§ Remaining Challenges of the Clustering in FL

In this subsection, we identify four remaining challenges of the . We categorize these challenges by tiers in the , as shown in Figure <ref>. The details are provided below.

Challenges on tier 1: Inconsistent intra-client clustering weights and efficiency concerns.
These challenges can be addressed by improving the clustering formulations.

* Inconsistent intra-client clustering weights.
Existing approaches use the same clustering weights $\omega_{i;k}$ for all the samples belonging to client $i$ [Sattler et al., 2020, Ghosh et al., 2020, Marfoq et al., 2021, Guo et al., 2023]. However, they overlook cases where the optimal clustering weights of different samples within the same client can be inconsistent, implying that $\omega_{i,j_1;k} \neq \omega_{i,j_2;k}$ for certain samples $(\xx_{i,j_1}, y_{i, j_1})$ and $(\xx_{i,j_2}, y_{i, j_2})$.
See our example here[
When client $i$'s local distribution is a mixture of two distributions, namely, $(\xx_{i,j_1}, y_{i, j_1})$ sampled from the first distribution and $(\xx_{i,j_2}, y_{i, j_2})$ from the second distribution, the optimal clustering weights for $(\xx_{i,j_1}, y_{i, j_1})$ and $(\xx_{i,j_2}, y_{i, j_2})$ should be distinct.

* Efficiency. The current clustered FL methods [Marfoq et al., 2021, Long et al., 2023, Guo et al., 2023] require K-fold higher communication or computation costs, hindering overall algorithm efficiency during deployment.

Challenges on tiers 2 & 3: The absence of adaptive clustering for soft clustering methods.
Current adaptive clustering methods primarily address hard clustering [Sattler et al., 2020, Sattler et al., 2020, Zeng et al., 2023].
Hence, there exists a gap between research and practice, as there is a need to automatically determine the number of clusters for soft clustering methods [Marfoq et al., 2021, Guo et al., 2023].

Challenges on tier 4: Lack of fine-grained distance metrics for various clustering principles.
The clustering principles determine which clients should be assigned to the same clusters. Existing clustering methods may use different clustering principles, as described by and below: =-1

* (Any Shift Type Clustering Principle): clients with any distribution shifts are placed into separate clusters [Marfoq et al., 2021, Wu et al., 2023].

* (Concept Shift Only Clustering Principle): only clients with concept shifts are assigned to separate clusters [Guo et al., 2023].

As discussed in Section <ref>, client distances determine whether the current number of clusters should be changed, aligning with the role of clustering principles: if the current number of clusters cannot meet the requirements of the clustering principles, the cluster number should be adjusted.
Consequently, we advocate for distance metrics to be closely tied to distribution shifts, ultimately aligning with clustering principles. Unfortunately, existing distance metrics, such as those based on local gradients or local model parameters [Sattler et al., 2020, Zeng et al., 2023, Long et al., 2023, Yan et al., 2023], cannot establish a clear link to distribution shifts. As a result, current methods struggle to satisfy diverse and detailed clustering principles.

§.§ Improve Tier1: Inconsistency and Efficiency Aware Objective Functions

To address tier 1 challenges, specifically, (i) inconsistent intra-client clustering weights and (ii) efficiency, we propose an extension of the objective function (Eq. (<ref>)), which is defined as $\mathcal{L}(\boldsymbol{\phi}, \boldsymbol{\Theta}, \boldsymbol{\Omega}, \tilde{\boldsymbol{\Omega}})$ and includes the parameters $\boldsymbol{\phi}$, $\boldsymbol{\Theta}$, $\boldsymbol{\Omega}$, and $\tilde{\boldsymbol{\Omega}}$.

* Global shared feature extractor $\mphi$, and cluster-specific predictors $\mTheta = [\mtheta_1, \cdots, \mtheta_K]$.
Dividing the feature extractor $\mphi$ and the predictors $\{ \mtheta_k \}$ reduces communication and computation costs since the predictors are lightweight architectures, like linear classifier layers.

* Sample-wise clustering weights $\mOmega = [\omega_{1,1;1} \cdots, \omega_{M, N_M; K}]$
for enhanced training stage and client-wise clustering weights $\tilde{\mOmega} = [\tilde{\omega}_{1;1} \cdots, \tilde{\omega}_{M;K}]$ for testing stage [Experiments on the effectiveness of sample-wise clustering weights in Figures <ref> and <ref>.].
We employ sample-specific clustering weights ($\omega_{i,j;k}$) during training to ensure that data samples from the same clients can contribute to different cluster models, resolving the issue of inconsistent intra-client clustering weights. Furthermore, during testing, when test-time label information is unavailable, we utilize client-specific weights ($\tilde{\omega}_{i;k}$) for each client and cluster.

* Enhance the optimization of $\omega_{i,j;k}$ by regularizing the distance between $\tilde{\omega}_{i;k}$ and $\omega_{i,j;k}$.
Motivated by the intuition that “if data from the same clients have similar distributions, the corresponding clustering weights should be similar”,
we encourage $\tilde{\omega}_{i;k}$ and $\omega_{i,j;k}$ to be close to each other.

The following objective function is designed to meet our requirements.

\begin{align}
\textstyle
& \cL(\mphi, \mTheta, \mOmega, \tilde{\mOmega}) = \underbrace{\frac{1}{N} \sum_{i=1}^{M} \sum_{j=1}^{N_i} \log \left( \sum_{k=1}^{K} \omega_{i,j;k} \cL_k(\xx_{i,j}, y_{ij}; \mphi, \mtheta_k) \right)}_{\cA_1}
- \underbrace{\mu \sum_{i=1}^{M} \sum_{j=1}^{N_i} \left( \sum_{k=1}^{K} \tilde{\omega}_{i;k} \log \frac{\tilde{\omega}_{i;k}}{\omega_{i,j;k}} \right)}_{\cA_2} \label{equ:fedias-objective}                      \\
& \text{s.t.}
\sum_{k=1}^{K} \omega_{i,j;k} = 1, \, \forall i, j  \,,  \sum_{k=1}^{K} \tilde{\omega}_{i;k} = 1, \, \forall i \,, \quad
\tilde{\mOmega} = \argmin_{\tilde{\mOmega}} \left| \max_{\mOmega} \cL(\mphi, \mTheta, \mOmega, \tilde{\mOmega}) -  \cL(\mphi, \mTheta, \tilde{\mOmega}, \tilde{\mOmega}) \right| \,, \label{equ:obtain-cluster-weights}
\end{align}

where $\cA_1$ term is extended from (<ref>) by using the global shared feature extractor $\mphi$ and the sample-wise weights $\omega_{i,j;k}$.
$\cA_2$ focuses on regularizing the difference between the sample-wise clustering weights $\omega_{i,j;k}$ and the client-wise clustering weights $\tilde{\omega}_{i;k}$.
The $\mu$ controls the strength of this regularization.
We obtain $\tilde{\omega}_{i;k}$ by solving (<ref>), where we aim to minimize the impact of replacing $\omega_{i,j;k}$ with $\tilde{\omega}_{i;k}$.

Optimization of the proposed objective function.
Different from heuristic methods used in most studies to optimize (<ref>) [IFCA [Ghosh et al., 2020] sets $\omega_{i,j;k_{i, \text{min}}} = 1, \forall j$ when $k_{i, \text{min}} = \argmin_k \E_{D_i} \left[f_{i;k}(\xx_{i,j}, y_{i,j}, \mphi, \mtheta_k)\right]$, where $f_{i;k}$ is the local loss function. FeSEM [Long et al., 2023] sets $k_{i, \text{min}} = \argmin_k \norm{\mtheta_k - \mtheta_i}_2$, where $\mtheta_k, \mtheta_i$ represents the model parameters of cluster $k$ and client $i$, respectively.=-1].
we aim to introduce a more interpretable approach here.
In this approach, we maximize the objective functions (Eq. (<ref>)) to obtain optimization steps.
Specifically, we can update $\tilde{\omega}_{i;k}$, $\omega_{i,j;k}$, $\mtheta_k$, and $\mphi$ by (<ref>)–(<ref>).

\begin{align}
\textstyle
\gamma_{i,j;k}^{t+1}       & = \frac{ \omega_{i,j;k}^{t} \cL_k(\xx_{i,j}, y_{ij}; \mphi^{t}, \mtheta_k^{t})}{\sum_{n=1}^{K} \omega_{i,j;n}^{t} \cL_k(\xx_{i,j}, y_{ij}; \mphi^{t}, \mtheta_n^{t})} \,, \quad     \label{equ:uptate-gamma}
\tilde{\gamma}_{i,j;k}^{t+1} = \frac{ \tilde{\omega}_{i;k}^{t} \cL_k(\xx_{i,j}, y_{ij}; \mphi^{t}, \mtheta_k^{t})}{\sum_{n=1}^{K} \omega_{i;n}^{t} \cL_k(\xx_{i,j}, y_{ij}; \mphi^{t}, \mtheta_n^{t})} \,,                                                                                \\
\tilde{\omega}_{i;k}^{t+1} & = \frac{1}{N_i} \sum_{j=1}^{N_i} \tilde{\gamma}_{i,j;k}^{t+1} \,, \quad                                                                                \omega_{i,j;k}^{t+1}         = \frac{\gamma_{i,j;k}^{t+1}}{1 + \mu N} + \frac{\mu N}{1 + \mu N} \tilde{\omega}_{i;k}^{t+1}  = \tilde{\mu} \gamma_{i,j;k}^{t+1} + (1 - \tilde{\mu}) \tilde{\omega}_{i;k}^{t+1} \, , \label{equ:update-omega} \\
\mtheta_k^{t+1}            & = \mtheta_k^{t} - \eta \sum_{i=1}^{M} \sum_{j=1}^{N_i} \frac{\gamma_{i,j;k}^{t+1}}{\cL_k(\xx_{ij}, y_{ij}, \mphi^{t}, \mtheta_k^{t})} \nabla_{\mtheta_k} \cL_k (\xx_{ij}, y_{ij}, \mphi^{t}, \mtheta_k^{t}) \, ,   \label{equ:update-theta}                                                                                \\
\mphi^{t+1}                & = \mphi^{t} - \eta \sum_{i=1}^{M} \sum_{j=1}^{N_i} \sum_{k=1}^{K} \frac{\gamma_{i,j;k}^{t+1}}{\cL_k(\xx_{ij}, y_{ij}, \mphi^{t}, \mtheta_k^{t})} \nabla_{\mphi} \cL_k (\xx_{ij}, y_{ij}, \mphi^{t}, \mtheta_k^{t+1}) \label{equ:update-mphi}\, ,
\end{align}

where $\gamma_{i,j;k}$ and $\tilde{\gamma}_{i,j;k}$ are intermediate results for calculating $\omega_{i,j;k}$ and $\tilde{\omega}_{i;k}$.
More detailed proofs can be found in Appendix <ref>.
$\tilde{\mu} = \frac{1}{1 + \mu N}$ serves as a hyperparameter to control the strength of the penalty term in Equation (<ref>).=-1

Theoretical Results on Linear Representation Learning Case.
We examine the convergence of a linear representation learning problem, as extended from the settings in Collins et al., 2021, Tziotis et al., 2022. We assume that the clustering weights, denoted as $\omega_{i,j;k}$, are obtained in each communication round.
We assume that local data $\xx_{i,j} \in \R^{d}$, and the global shared feature extractor is parameterized by $\mB \in \R^{d \times c}$. For each underlying cluster $k$, we define $\mtheta_k \in \R^{c}$, and the labels for data $\xx_{i,j}$ belonging to cluster $k$ are given by $y_{i,j} = (\mtheta_k^{*})^{T}(\mB^{*})^{T} \xx_{i,j} + z_{k}$, where $z_{k} \sim \cN(0, \sigma^2)$ captures the heterogeneous between $K$ underlying clusters.
The global empirical risk is defined as the mean square error=-1

\begin{align}
\textstyle
\min_{\mB, \mTheta} \frac{1}{2N} \sum_{i=1}^{M} \sum_{j=1}^{N_i} \left( y_{i,j} - \sum_{k=1}^{K} \omega_{i,j;k} \mtheta_{k}^{T} \mB^{T} \xx_{i,j} \right)^{2} \,,
\label{equ: linear objective function}
\end{align}

where $\mTheta = [\mtheta_1, \cdots, \mtheta_K]$. Then we can derive the convergence of given the following theorem. Detailed definitions, assumptions proofs, and discussions refer to Appendix <ref>.

Under Assumption <ref>- <ref>, when we have $N \ge \frac{K^2}{d+c}$, and $\min_{k} \hat{N}_k \ge \cC \frac{c^3(1 + \sigma^2)^4 \log(M)}{E_0^2} \min \left \{ \frac{1}{\kappa^2}, \bar{\sigma}_{\min}^2 \right \}$ for some constant $\cC$, we have

\begin{align}
\textstyle
\text{dist}(\hat{\mB}^{t+1} \!, \hat{\mB}^{*})
& \le \text{dist}(\hat{\mB}^{t} \!, \hat{\mB}^{*}) (1 \!-\! c_{\text{min}} \!+\! \frac{57}{200} c_{\text{max}} ) ( 1 \!-\! \frac{1}{2} c_{\text{max}} )^{-\nicefrac{1}{2}}
\!+\! ( \frac{7}{100} c_{\text{max}} ) ( 1 \!-\! \frac{1}{2} c_{\text{max}} )^{- \nicefrac{1}{2}}
\,,
\end{align}

with the probability at least $1 \!-\! \exp(-90(d+c)) \!-\! \exp(-90c^2\log(M))$.
Here $\hat{N}_k = \sum_{i\!=\!1}^{M} \sum_{j\!=\!1}^{N_i} \omega_{i,j;k}$, $E_0 = 1 - \text{dist}^2(\hat{\mB}^{0}, \hat{\mB}^{*})$, $c_{\text{min}} = \eta K \frac{\min_k \hat{N}_k}{N} \bar{\sigma}_{\min, *}^2 E_0$, and $c_{\text{max}} = \eta K \frac{\max_k \hat{N}_k}{N} \bar{\sigma}_{\min, *}^2 E_0$.

§.§ Improve Tiers 2 & 3: Adaptive Clustering for Soft Clustering Paradigms

Given the limitations of existing adaptive clustering methods, we have extended the clustering weight update mechanisms to incorporate soft clustering and have verified its effectiveness in Figures <ref> and <ref>.
The overall process is summarized in Algorithms <ref> and <ref>.
In Algorithm <ref>, the clustering weights are adjusted after splitting cluster $k$ into two sub-clusters, denoted by $k_1$ and $k_2$. Then we set $\omega_{i,j,k_1} = \omega_{i,j,k_2} = \omega_{i,j,k} / 2$ for all $i$ and $j$.
In Algorithm <ref>, the clustering weights are updated when removing cluster $k$. For all $k^{'} \neq k$, we modify $\omega_{i,j;k^{'}}$ as $\omega_{i,j;k^{'}} = \frac{\omega_{i,j;k^{'}}}{\sum_{n \neq k} \omega_{i,j;n}}$.=-1

We use the hyperparameter $\rho$ to control cluster splitting.
As evidenced in Table <ref>, a higher $\rho$ results in fewer clusters, signifying enhanced generalization but reduced personalization.
In detail, the cluster $k$ will split if the following condition is met:

\begin{align}
\textstyle
\max (\mD_k) - \operatorname{mean} (\mD_k) \ge \rho \,,
\end{align}

where $\mD_k$ is the distance matrix of cluster $k$.
We identify the need for cluster removal when the cluster no longer receives the highest clustering weights from any clients.
Additional details about the enhanced adaptive process can be found in Algorithm <ref>.

§.§ Improve Tier4: Fine-Grained Distance Metric Design

Due to the page limitations, we include most of the details about the method design and practical implements in Appendix <ref>.
As discussed in Section <ref>, various algorithms may group clients into different clusters based on different clustering principles.
Therefore, in this section, we design the following fine-grained distance metrics for these different clustering principles:

\begin{align}
\textstyle
\mD_{i,j}^{k}
\begin{split} =
\left \{
\begin{array}{ll}
\max \left \{ d_c, d_{lf} \right \}
\E_{D_i} \left[\tilde{\cL}_k(\zz, y;\mtheta_k) \right]
\E_{D_j} \left[\tilde{\cL}_k(\zz, y;\mtheta_k) \right] \label{equ:theory-distance} \, , & \text{\cpA} \, , \\
\E_{D_i} \left[\tilde{\cL}_k(\zz, y;\mtheta_k) \right]
\E_{D_j} \left[\tilde{\cL}_k(\zz, y;\mtheta_k) \right] \, ,                             & \text{\cpB} \, ,
\end{array}
\right.
\end{split}
\end{align}

where $\text{dist}$ is the cos-similarity, $d_c \!=\! \max_{y} \left\{ \text{dist} \left( \E_{D_i} \left[\cP(\zz | \xx, y;\mphi) \right], \E_{D_j} \left[\cP(\zz| \xx, y; \mphi) \right] \right) \right\}$, and $d_{lf} \!=\! \text{dist} \left( \E_{D_i} \left[\cP(\zz | \xx;\mphi) \right], \E_{D_j} \left[\cP(\zz| \xx; \mphi) \right] \right)$.
The distances above become large only when the following conditions occur together:
(1) Large values of $d_c$ indicate concept shifts between clients $i$ and $j$;
(2) Large $d_{lf}$ indicate significant feature and label distribution differences.
(2) Large values of $\E_{D_i} \left[\tilde{\cL}_k(\zz, y;\mtheta_k) \right] \E_{D_j} \left[\tilde{\cL}_k(\zz, y;\mtheta_k) \right]$ indicate incorrect clustering weights with high confidence.
The effectiveness of the above distance metrics design is evidenced in Table <ref>.

§ NUMERICAL RESULTS

In this section, we evaluate the performance of and other clustered FL methods.
Additional experiment results, including hyper-parameter ablation studies, different model architectures, and additional scenarios, can be found in Appendix <ref>.=-1

Performance of the adaptive clustering methods on CIFAR10, CIFAR100, and Tiny-Imagenet datasets.
For each algorithm, we present the best Validation and Test accuracies.
For clustering methods that require a fixed number of clusters, we set $K = 3$.
The hyperparameters $\text{tol}_1$, $\text{tol}_2$, $\alpha^{*}(0)$, $\tau$, and $\rho$ in adaptive clustering methods govern the balance between personalization and generalization, as well as the cluster number. For instance, lower $\tau$ in StoCFL or lower $\rho$ in indicate improved personalization and reduced generalization.
$K^{T}$ denotes the cluster number in the final training round, where a larger $K^{T}$ suggests enhanced personalization and reduced generalization.
We emphasize the best results in bold and the worst results in blue.

2*Algorithm                       3cCIFAR10, $\beta = 0.2$                         3cCIFAR100, $\beta = 0.2$                        3cTiny-Imagenet, $\beta = 0.2$

(lr)2-4 (lr)5-7 (lr)8-10
Val                                                                Test                                                               $K^{T}$                                              Val                                                                Test                                                              $K^{T}$     Val                                                       Test                                                               $K^{T}$

FedAvg                                           $49.19$ 0.5 $\pm 2.15$                       $45.42$ 0.5 $\pm 2.42$                       $1$                                                  $\textcolor{blue}{26.01}$ 0.5 $\pm 1.15$     $27.87$ 0.5 $\pm 2.12$                      $1$         $38.83$ 0.5 $\pm 0.20$              $39.07$ 0.5 $\pm 0.44$                       $1$

FeSEM                                            $45.30$ 0.5 $\pm 0.40$                       $29.01$ 0.5 $\pm 0.79$                       $3$                                                  $26.37$ 0.5 $\pm 0.64$                       $24.50$ 0.5 $\pm 0.28$                      $3$         $37.10$ 0.5 $\pm 0.80$              $30.00$ 0.5 $\pm 2.02$                       $3$

IFCA                                             $\textcolor{blue}{34.46}$ 0.5 $\pm 2.06$     $\textcolor{blue}{23.18}$ 0.5 $\pm 2.55$     $3$                                                  $26.99$ 0.5 $\pm 3.89$                       $26.20$ 0.5 $\pm 1.56$                      $3$         $38.52$ 0.5 $\pm 0.30$              $29.92$ 0.5 $\pm 0.30$                       $3$

FedEM                                            $66.49$ 0.5 $\pm 0.69$                       $53.64$ 0.5 $\pm 1.61$                       $3$                                                  $29.75$ 0.5 $\pm 0.47$                       $24.18$ 0.5 $\pm 0.03$                      $3$         $42.00$ 0.5 $\pm 0.74$              $39.25$ 0.5 $\pm 0.31$                       $3$

FedRC                                            $63.65$ 0.5 $\pm 2.95$                       $59.41$ 0.5 $\pm 0.19$                       $3$                                                  $34.56$ 0.5 $\pm 0.79$                       $\mathbf{37.62}$ 0.5 $\pm 0.16$             $3$         $38.93$ 0.5 $\pm 0.18$              $39.73$ 0.5 $\pm 0.04$                       $3$

$\quad \text{tol}_1 =0.4, \text{tol}_2 =1.6$     $61.55$ 0.5 $\pm 1.74$                       $46.88$ 0.5 $\pm 0.35$                       $6$                                                  $35.05$ 0.5 $\pm 0.35$                       $24.84$ 0.5 $\pm 2.50$                      $4$         $37.41$ 0.5 $\pm 1.87$              $30.25$ 0.5 $\pm 0.55$                       $3$

$\quad \text{tol}_1 =0.4, \text{tol}_2 =0.8$     $65.06$ 0.5 $\pm 3.34$                       $45.74$ 0.5 $\pm 4.01$                       $9$                                                  $36.98$ 0.5 $\pm 3.37$                       $22.00$ 0.5 $\pm 1.88$                      $5$         $40.36$ 0.5 $\pm 3.55$              $28.82$ 0.5 $\pm 0.71$                       $4$

$\quad \text{tol}_1 =0.2, \text{tol}_2 =0.8$     $58.92$ 0.5 $\pm 2.09$                       $55.02$ 0.5 $\pm 0.97$                       $4$                                                  $37.73$ 0.5 $\pm 7.68$                       $31.47$ 0.5 $\pm 0.09$                      $3$         $35.74$ 0.5 $\pm 0.57$              $34.41$ 0.5 $\pm 1.92$                       $1$

$\quad \alpha^{*} (0) =0.85$                     $77.59$ 0.5 $\pm 0.04$                       $57.38$ 0.5 $\pm 1.91$                       $98$                                                 $52.73$ 0.5 $\pm 1.03$                       $32.77$ 0.5 $\pm 0.28$                      $100$       $64.72$ 0.5 $\pm 0.30$              $34.73$ 0.5 $\pm 0.39$                       $87$

$\quad \alpha^{*} (0) =0.98$                     $60.58$ 0.5 $\pm 1.07$                       $61.18$ 0.5 $\pm 0.78$                       $14$                                                 $41.49$ 0.5 $\pm 4.11$                       $33.57$ 0.5 $\pm 1.56$                      $40$        $53.05$ 0.5 $\pm 2.57$              $35.09$ 0.5 $\pm 0.25$                       $42$

$\quad \tau=0.05$                                $59.79$ 0.5 $\pm 1.34$                       $57.35$ 0.5 $\pm 0.92$                       $15$                                                 $29.97$ 0.5 $\pm 0.47$                       $31.40$ 0.5 $\pm 2.16$                      $4$         $31.85$ 0.5 $\pm 0.08$              $31.39$ 0.5 $\pm 0.87$                       $1$

$\quad \tau=0.10$                                $70.84$ 0.5 $\pm 1.58$                       $51.72$ 0.5 $\pm 0.07$                       $54$                                                 $\mathbf{69.76}$ 0.5 $\pm 2.57$              $\textcolor{blue}{9.42}$ 0.5 $\pm 0.07$     $89$        $\mathbf{67.48}$ 0.5 $\pm 1.53$     $\textcolor{blue}{13.03}$ 0.5 $\pm 0.67$     $91$

$\rho=0.05$                                $\mathbf{87.77}$ 0.5 $\pm 1.11$              $41.85$ 0.5 $\pm 4.11$                       $58$                                                 $\mathbf{69.25}$ 0.5 $\pm 0.69$              $14.24$ 0.5 $\pm 1.93$                      $67$        $60.44$ 0.5 $\pm 0.86$              $23.14$ 0.5 $\pm 1.46$                       $32$

$\rho=0.1$                                 $85.08$ 0.5 $\pm 0.11$                       $43.34$ 0.5 $\pm 0.94$                       $44$                                                 $62.32$ 0.5 $\pm 0.23$                       $16.67$ 0.5 $\pm 2.97$                      $38$        $52.18$ 0.5 $\pm 2.90$              $32.97$ 0.5 $\pm 1.27$                       $14$

$\rho=0.3$                                 $79.31$ 0.5 $\pm 3.95$                       $47.62$ 0.5 $\pm 2.90$                       $17$                                                 $44.49$ 0.5 $\pm 1.57$                       $28.03$ 0.5 $\pm 0.85$                      $8$         $45.76$ 0.5 $\pm 0.09$              $36.08$ 0.5 $\pm 1.25$                       $4$

$\rho=0.05$                                $82.45$ 0.5 $\pm 0.13$                       $57.73$ 0.5 $\pm 1.70$                       $22$                                                 $60.36$ 0.5 $\pm 1.47$                       $22.95$ 0.5 $\pm 1.44$                      $40$        $63.41$ 0.5 $\pm 0.05$              $34.24$ 0.5 $\pm 0.33$                       $33$

$\rho=0.1$                                 $84.64$ 0.5 $\pm 1.47$                       $60.90$ 0.5 $\pm 0.61$                       $16$                                                 $62.98$ 0.5 $\pm 0.42$                       $26.17$ 0.5 $\pm 1.22$                      $34$        $59.88$ 0.5 $\pm 0.11$              $37.17$ 0.5 $\pm 0.37$                       $20$

$\rho=0.3$                                 $83.67$ 0.5 $\pm 0.72$                       $62.43$ 0.5 $\pm 0.71$                       $10$                                                 $50.72$ 0.5 $\pm 2.97$                       $32.13$ 0.5 $\pm 0.18$                      $9$         $45.53$ 0.5 $\pm 0.53$              $38.64$ 0.5 $\pm 0.23$                       $3$

$\rho=0.05$                                $69.16$ 0.5 $\pm 0.65$                       $67.37$ 0.5 $\pm 0.42$                       $8$                                                  $39.20$ 0.5 $\pm 0.31$                       $34.38$ 0.5 $\pm 0.64$                      $11$        $43.78$ 0.5 $\pm 0.31$              $38.75$ 0.5 $\pm 0.54$                       $10$

$\rho=0.1$                                 $71.67$ 0.5 $\pm 0.83$                       $68.64$ 0.5 $\pm 0.76$                       $8$                                                  $39.56$ 0.5 $\pm 0.14$                       $34.62$ 0.5 $\pm 0.78$                      $8$         $44.26$ 0.5 $\pm 0.10$              $38.82$ 0.5 $\pm 0.77$                       $6$

$\rho=0.3$                                 $69.33$ 0.5 $\pm 0.24$                       $\mathbf{69.67}$ 0.5 $\pm 1.27$              $3$                                                  $39.97$ 0.5 $\pm 0.21$                       $\mathbf{36.50}$ 0.5 $\pm 0.28$             $4$         $42.60$ 0.5 $\pm 0.21$              $\mathbf{40.65}$ 0.5 $\pm 0.36$              $3$

§.§ Datasets and Experiment settings

Diverse distribution shifts scenarios.
We establish clients with three types of distribution shifts.
For label distribution shifts, we employ LDA with $\alpha = 1.0$, as introduced by Yoshida et al., 2019, Hsu et al., 2019, Reddi et al., 2021.
For feature distribution shifts, we adopt the methodology from CIFAR10-C and CIFAR100-C creation [Hendrycks & Dietterich, 2019].
Regarding concept shift, we draw inspiration from Guo et al., 2023, Jothimurugesan et al., 2023, and selectively swap labels based on the parameter $\beta$.
For example, with $\beta = 0.1$ for CIFAR10, two labels per concept are swapped, while the remaining eight labels remain unchanged. By default, we create three concepts in the experiments. More details about the construction of scenarios are included in Appendix <ref>.

We use FedAvg [McMahan et al., 2016] as a single-model FL example.
We consider the most recently published clustered FL methods as our baselines.
For clustered FL with fixed cluster number, we select IFCA [Ghosh et al., 2020], FedEM [Marfoq et al., 2021], FeSEM [Long et al., 2023], and FedRC [Guo et al., 2023].
For the adaptive clustering FL methods, we choose CFL [Sattler et al., 2020], ICFL [Yan et al., 2023], and StoCFL [Zeng et al., 2023].

Experiment settings.
Unless specifically mentioned, we divide the datasets into 100 clients and execute all algorithms for 200 communication rounds.
Additional settings are provided in Appendix <ref>.
We conducted all experiments using MobileNet-V2 [Sandler et al., 2018] and results on ResNet18 defer to Table <ref> of Appendix <ref>.

Evaluation metrics.
We present the following metrics to evaluate the personalization and generalization abilities of the algorithms:
(1) Validation Accuracy for evaluating personalization: The average accuracy on local validation datasets that match the distribution of local training sets.
(2) Test Accuracy evaluating generalization: The average accuracy on global shared test datasets.

§.§ Results on diverse distribution shifts scenarios

In this section, we compare the performance of with other clustered FL methods. We also perform ablation studies to confirm the effectiveness of 's proposed components.

achieves better personalization-generalization trade-offs and comparable performance.
We highlight some key observations in Table <ref>.
A. consistently achieves superior test accuracy, with validation accuracy surpassing that of baseline methods with a similar number of clusters. This demonstrates improved efficiency and a better balance between personalization and generalization.
B. Soft clustering methods like (FedEM) and (FedRC) outperform hard clustering methods in test accuracy, showcasing their superior generalization capabilities.
C. While baseline methods may achieve higher validation accuracy by separating every client into different clusters (namely when the value of $K^{T}$ is close to 100), these trained clusters tend to overfit local distributions, resulting in significantly lower test accuracy.
D. The extended algorithms, namely (FeSEM), (FedEM), and (FedRC), outperform the original methods that rely on fixed cluster numbers significantly.
Additionally, these extended algorithms can automatically adjust the number of clusters, making the algorithms more practical, as we illustrated in Figure <ref>.

Ablation studies on Sec <ref>.
We perform ablation studies on $\tilde{\mu}$, which control the distance between sample-wise weights $\omega_{i,j;k}$ and client-wise weights $\tilde{\omega}_{i;k}$ in Figures <ref> and <ref>.
A larger $\tilde{\mu}$ signifies a greater difference between $\omega_{i,j;k}$ and $\tilde{\omega}_{i;k}$.
Our results show that (FedEM) prefers smaller distance between $\omega_{i,j;k}$ and $\tilde{\omega}_{i;k}$.
However, (FedRC) prefers larger $\tilde{\mu}$ values, highlighting the necessity of different clustering weights among samples within the same clients.

Number of clusters in over communication rounds. We illustrate changes in cluster numbers across communication rounds for various $\rho$ values using the CIFAR-10 dataset in our experiments.=-1

Ablation studies on Sec <ref>.
In Figures <ref> and <ref>, we perform ablation studies on the soft clustering weight updating mechanism (w/ SCWU) introduced in Section <ref>.
The term w/o SCWU refers to using the traditional clustering weight updating mechanism as described in Sattler et al., 2020, Zeng et al., 2023.
The results demonstrate that our proposed SCWU consistently achieves better performance in terms of both validation and test accuracies.

[Validation Acc]

[Test Acc]

Ablation studies on Sections <ref> and <ref>. For Sec <ref>, we evaluated test accuracies of using different backbones (FedEM and FedRC) and varying values of $\tilde{\mu}$, as shown in Figures <ref> and <ref>. For Sec <ref>, we present the best Val and Test accuracy achieved by with either FedEM or FedRC as backbones. “w/ SCWU” indicates the use of soft clustering weight updating mechanisms introduced in Section <ref>. More detailed results can be found in Tables <ref> and <ref> in Appendix <ref>.

Ablation studies on techniques in Sec <ref>.
We perform ablation studies to demonstrate the effectiveness of the designed distance metrics in Sec <ref>.
The ablation studies include:
192 Using gradient similarity, as in previous works [Sattler et al., 2020, Yan et al., 2023], instead of distance on $\cP(\zz|x;\mphi)$ and $\cP(\zz|x, y;\mphi)$, as we proposed in Equation <ref>;
193 Remove $\E_{D_i}[\tilde{\cL}_k(\zz,y;\mtheta_k)]$ and $\E_{D_i}[\tilde{\cL}_k(\zz,y;\mtheta_k) ]$ in (<ref>);
194 Using mean distances instead of maximum distances in (<ref>).
The results show that consistently achieves the highest test accuracy and produces a number of clusters closer to the ideal number than other ablation studies.

Ablation studies on Sec <ref>. We conducted experiments on the CIFAR10 and CIFAR100 datasets, showcasing the highest test accuracies, the maximum number of clusters during training ($\max_{t} K^{t}$), and the final number of clusters ($K^{T}$) or each algorithm while maintaining a fixed value of $\rho = 0.3$. We used FedRC as the backbone, with 3 clusters identified as ideal by .=-1

2*Algorithm     3cCIFAR10, $\beta = 0.2$                3cCIFAR10, $\beta = 0.4$     3cCIFAR100, $\beta = 0.2$     3cCIFAR100, $\beta = 0.4$

(lr)2-4 (lr)5-7 (lr)8-10 (lr)11-13
Test Acc                                                  $\max_{t} K^{t}$                               $K^{T}$
Test Acc                                                  $\max_{t} K^{t}$                               $K^{T}$
Test Acc                                                  $\max_{t} K^{t}$                               $K^{T}$
Test Acc                                                  $\max_{t} K^{t}$                               $K^{T}$

$\mathbf{69.67}$ 0.5 $\pm 1.27$     $\mathbf{4.5}$                                 $\mathbf{3.0}$                                  $\mathbf{70.13}$ 0.5 $\pm 0.42$     $\mathbf{7.0}$     $\mathbf{6.0}$     $\mathbf{36.50}$ 0.5 $\pm 0.28$     $\mathbf{3.5}$     $\mathbf{3.5}$     $\mathbf{32.22}$ 0.5 $\pm 0.20$     $5.0$              $\mathbf{4.0}$

$\;$ + 192              $67.83$ 0.5 $\pm 1.70$              $9.5$                                          $7.0$                                           $64.53$ 0.5 $\pm 0.23$              $10.5$             $10.0$             $\mathbf{36.77}$ 0.5 $\pm 0.67$     $9.5$              $8.5$              $31.33$ 0.5 $\pm 2.12$              $11.0$             $7.5$

$\;\;\;\;$ + 193        $56.14$ 0.5 $\pm 8.11$              $10.5$                                         $5.5$                                           $50.87$ 0.5 $\pm 2.26$              $12.5$             $8.5$              $34.11$ 0.5 $\pm 1.58$              $10.0$             $6.0$              $\mathbf{32.75}$ 0.5 $\pm 0.67$     $7.5$              $6.5$

$\;$ + 193              $68.52$ 0.5 $\pm 0.64$              $8.0$                                          $6.0$                                           $69.47$ 0.5 $\pm 0.15$              $11.0$             $8.5$              $34.65$ 0.5 $\pm 1.16$              $8.5$              $5.5$              $31.61$ 0.5 $\pm 0.54$              $11.0$             $7.5$

$\;$ + 194              $68.82$ 0.5 $\pm 0.59$              $5.5$                                          $3.5$                                           $65.74$ 0.5 $\pm 0.09$              $\mathbf{7.0}$     $7.0$              $35.97$ 0.5 $\pm 0.80$              $4.0$              $\mathbf{3.5}$     $31.72$ 0.5 $\pm 0.59$              $\mathbf{4.5}$     $\mathbf{4.0}$

§ CONCLUSION

In this paper, we introduce , a comprehensive clustered FL framework that unifies existing methods while enabling the integration of diverse algorithms to gather the advantages of various clustered FL approaches.
Additionally, we identify persistent challenges unaddressed by current algorithms and propose as a solution.
The is flexible and can generate numerous clustered FL methods by altering techniques in each tier.
Though we have chosen some typical components and demonstrated their effectiveness, conducting further performance verification with more choices in each tier would be beneficial.

[Bao et al., 2023]
Bao, W., Wang, H., Wu, J., and He, J.
Optimizing the collaboration structure in cross-silo federated

[Briggs et al., 2020]
Briggs, C., Fan, Z., and Andras, P.
Federated learning with hierarchical clustering of local updates to
improve training on non-iid data.
In 2020 International Joint Conference on Neural Networks
(IJCNN), pp.  1–9. IEEE, 2020.

[Collins et al., 2021]
Collins, L., Hassani, H., Mokhtari, A., and Shakkottai, S.
Exploiting shared representations for personalized federated
In International Conference on Machine Learning, pp.  2089–2099. PMLR, 2021.

[Duan et al., 2021]
Duan, M., Liu, D., Ji, X., Liu, R., Liang, L., Chen, X., and Tan, Y.
FedGroup: Efficient federated learning via decomposed
similarity-based clustering.
In 2021 IEEE Intl Conf on Parallel & Distributed Processing
with Applications, Big Data & Cloud Computing, Sustainable Computing &
Communications, Social Computing & Networking
(ISPA/BDCloud/SocialCom/SustainCom), pp.  228–237. IEEE,

[Duan et al., 2021]
Duan, M., Liu, D., Ji, X., Wu, Y., Liang, L., Chen, X., Tan, Y., and Ren, A.
Flexible clustered federated learning for client-level data
distribution shift.
IEEE Transactions on Parallel and Distributed Systems,
330 (11):0 2661–2674, 2021b.

[Fang & Ye, 2022]
Fang, X. and Ye, M.
Robust federated learning with noisy and heterogeneous clients.
In Proceedings of the IEEE/CVF Conference on Computer Vision
and Pattern Recognition, pp.  10072–10081, 2022.

[Gan et al., 2021]
Gan, S., Mathur, A., Isopoussu, A., Kawsar, F., Berthouze, N., and Lane, N.
FRuDA: Framework for distributed adversarial domain adaptation.
IEEE Transactions on Parallel and Distributed Systems, 2021.

[Ghosh et al., 2020]
Ghosh, A., Chung, J., Yin, D., and Ramchandran, K.
An efficient framework for clustered federated learning.
Advances in Neural Information Processing Systems,
33:0 19586–19597, 2020.

[Guo et al., 2021]
Guo, Y., Lin, T., and Tang, X.
Towards federated learning on time-evolving heterogeneous data.
arXiv preprint arXiv:2112.13246, 2021.

[Guo et al., 2023]
Guo, Y., Tang, X., and Lin, T.
FedBR: Improving federated learning on heterogeneous data via local
learning bias reduction.

[Guo et al., 2023]
Guo, Y., Tang, X., and Lin, T.
FedRC: Tackling diverse distribution shifts challenge in federated
learning by robust clustering.
arXiv preprint arXiv:2301.12379, 2023b.

[Hendrycks & Dietterich, 2019]
Hendrycks, D. and Dietterich, T.
Benchmarking neural network robustness to common corruptions and
arXiv preprint arXiv:1903.12261, 2019.

[Hsu et al., 2019]
Hsu, T.-M. H., Qi, H., and Brown, M.
Measuring the effects of non-identical data distribution for
federated visual classification.
arXiv preprint arXiv:1909.06335, 2019.

[Jain et al., 2013]
Jain, P., Netrapalli, P., and Sanghavi, S.
Low-rank matrix completion using alternating minimization.
In Proceedings of the forty-fifth annual ACM symposium on
Theory of computing, pp.  665–674, 2013.

[Jiang & Lin, 2023]
Jiang, L. and Lin, T.
Test-time robust personalization for federated learning.
In International Conference on Learning Representations, 2023.

[Jothimurugesan et al., 2023]
Jothimurugesan, E., Hsieh, K., Wang, J., Joshi, G., and Gibbons, P. B.
Federated learning under distributed concept drift.
pp.  5834–5853, 2023.

[Karimireddy et al., 2019]
Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S. J., Stich, S. U., and
Suresh, A. T.
SCAFFOLD: Stochastic controlled averaging for federated learning,
URL <https://arxiv.org/abs/1910.06378>.

[Karimireddy et al., 2020]
Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S., and Suresh,
A. T.
SCAFFOLD: Stochastic controlled averaging for federated learning.
In International Conference on Machine Learning, pp.  5132–5143. PMLR, 2020.

[Ke et al., 2022]
Ke, S., Huang, C., and Liu, X.
Quantifying the impact of label noise on federated learning.
arXiv preprint arXiv:2211.07816, 2022.

[Li et al., 2021]
Li, Q., He, B., and Song, D.
Model-contrastive federated learning.
In Proceedings of the IEEE/CVF Conference on Computer Vision
and Pattern Recognition, 2021.

[Li et al., 2018]
Li, T., Sahu, A. K., Zaheer, M., Sanjabi, M., Talwalkar, A., and Smith, V.
Federated optimization in heterogeneous networks.
arXiv preprint arXiv:1812.06127, 2018.

[Lin et al., 2020]
Lin, T., Stich, S. U., Patel, K. K., and Jaggi, M.
Don't use large mini-batches, use local sgd.
In International Conference on Learning Representations, 2020.
URL <https://openreview.net/forum?id=B1eyO1BFPr>.

[Long et al., 2023]
Long, G., Xie, M., Shen, T., Zhou, T., Wang, X., and Jiang, J.
Multi-center federated learning: clients clustering for better
World Wide Web, 260 (1):0 481–500, 2023.

[Marfoq et al., 2021]
Marfoq, O., Neglia, G., Bellet, A., Kameni, L., and Vidal, R.
Federated multi-task learning under a mixture of distributions.
Advances in Neural Information Processing Systems,
34:0 15434–15447, 2021.

[McMahan et al., 2016]
McMahan, H. B., Moore, E., Ramage, D., Hampson, S., and Arcas, B. A. y.
Communication-efficient learning of deep networks from decentralized
URL <https://arxiv.org/abs/1602.05629>.

[Peng et al., 2019]
Peng, X., Huang, Z., Zhu, Y., and Saenko, K.
Federated adversarial domain adaptation, 2019.
URL <https://arxiv.org/abs/1911.02054>.

[Reddi et al., 2021]
Reddi, S. J., Charles, Z., Zaheer, M., Garrett, Z., Rush, K.,
Konečný, J., Kumar, S., and McMahan, H. B.
Adaptive federated optimization.
In International Conference on Learning Representations, 2021.
URL <https://openreview.net/forum?id=LkFG3lB13U5>.

[Ruan & Joe-Wong, 2022]
Ruan, Y. and Joe-Wong, C.
FedSoft: Soft clustered federated learning with proximal local
In Proceedings of the AAAI Conference on Artificial
Intelligence, volume 36, pp.  8124–8131, 2022.

[Sandler et al., 2018]
Sandler, M., Howard, A., Zhu, M., Zhmoginov, A., and Chen, L.-C.
MobileNetV2: Inverted residuals and linear bottlenecks.
In Proceedings of the IEEE conference on computer vision and
pattern recognition, pp.  4510–4520, 2018.

[Sattler et al., 2020]
Sattler, F., Müller, K.-R., and Samek, W.
Clustered federated learning: Model-agnostic distributed multitask
optimization under privacy constraints.
IEEE transactions on neural networks and learning systems,
320 (8):0 3710–3722, 2020a.

[Sattler et al., 2020]
Sattler, F., Müller, K.-R., Wiegand, T., and Samek, W.
On the byzantine robustness of clustered federated learning.
In ICASSP 2020-2020 IEEE International Conference on Acoustics,
Speech and Signal Processing (ICASSP), pp.  8861–8865. IEEE,

[Shen et al., 2021]
Shen, Y., Du, J., Zhao, H., Zhang, B., Ji, Z., and Gao, M.
FedMM: Saddle point optimization for federated adversarial domain
arXiv preprint arXiv:2110.08477, 2021.

[Stallmann & Wilbik, 2022]
Stallmann, M. and Wilbik, A.
Towards federated clustering: A federated fuzzy $ c $-means algorithm
arXiv preprint arXiv:2201.07316, 2022.

[Sun et al., 2022]
Sun, Y., Chong, N., and Hideya, O.
Multi-source domain adaptation based on federated knowledge
arXiv preprint arXiv:2203.11635, 2022.

[Tang et al., 2022]
Tang, Z., Zhang, Y., Shi, S., He, X., Han, B., and Chu, X.
Virtual homogeneity learning: Defending against data heterogeneity in
federated learning.
International Conference on Machine Learning, pp.  21111–21132, 2022.

[Tziotis et al., 2022]
Tziotis, I., Shen, Z., Pedarsani, R., Hassani, H., and Mokhtari, A.
Straggler-resilient personalized federated learning.
arXiv preprint arXiv:2206.02078, 2022.

[Vahidian et al., 2023]
Vahidian, S., Morafah, M., Wang, W., Kungurtsev, V., Chen, C., Shah, M., and
Lin, B.
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, pp.  10043–10052, 2023.

[Vershynin, 2018]
Vershynin, R.
High-dimensional probability: An introduction with applications
in data science, volume 47.
Cambridge university press, 2018.

[Wang et al., 2022]
Wang, B., Li, G., Wu, C., Zhang, W., Zhou, J., and Wei, Y.
A framework for self-supervised federated domain adaptation.
EURASIP Journal on Wireless Communications and Networking,
20220 (1):0 1–17, 2022a.

[Wang et al., 2020]
Wang, H., Yurochkin, M., Sun, Y., Papailiopoulos, D., and Khazaeni, Y.
Federated learning with matched averaging.
arXiv preprint arXiv:2002.06440, 2020.

[Wang et al., 2022]
Wang, Z., Xu, H., Liu, J., Xu, Y., Huang, H., and Zhao, Y.
Accelerating federated learning with cluster construction and
hierarchical aggregation.
IEEE Transactions on Mobile Computing, 2022b.

[Wei & Huang, 2023]
Wei, X.-X. and Huang, H.
Edge devices clustering for federated visual classification: A
feature norm based framework.
IEEE Transactions on Image Processing, 32:0 995–1010,

[Wu et al., 2022]
Wu, S., Li, T., Charles, Z., Xiao, Y., Liu, Z., Xu, Z., and Smith, V.
Motley: Benchmarking heterogeneity and personalization in federated
arXiv preprint arXiv:2206.09262, 2022.

[Wu et al., 2023]
Wu, Y., Zhang, S., Yu, W., Liu, Y., Gu, Q., Zhou, D., Chen, H., and Cheng, W.
Personalized federated learning under mixture of distributions.

[Yan et al., 2023]
Yan, Y., Tong, X., and Wang, S.
Clustered federated learning in heterogeneous environment.
IEEE Transactions on Neural Networks and Learning Systems,

[Yoshida et al., 2019]
Yoshida, N., Nishio, T., Morikura, M., Yamamoto, K., and Yonetani, R.
Hybrid-FL: Cooperative learning mechanism using non-iid data in
wireless networks.
arXiv preprint arXiv:1905.07210, 2019.

[Zeng et al., 2023]
Zeng, D., Hu, X., Liu, S., Yu, Y., Wang, Q., and Xu, Z.
Stochastic clustered federated learning.
arXiv preprint arXiv:2303.00897, 2023.

[Zhao et al., 2020]
Zhao, F., Huang, Y., Sai, A. M. V. V., and Wu, Y.
A cluster-based solution to achieve fairness in federated learning.
In 2020 IEEE Intl Conf on Parallel & Distributed Processing
with Applications, Big Data & Cloud Computing, Sustainable Computing &
Communications, Social Computing & Networking
(ISPA/BDCloud/SocialCom/SustainCom), pp.  875–882. IEEE, 2020.

§ PROOF OF OPTIMIZATION STEPS

Given objective function $\cL(\mphi, \mTheta, \mOmega, \tilde{\mOmega})$

\begin{align}
\cL(\mphi, \mTheta, \mOmega, \tilde{\mOmega}) & = \frac{1}{N} \sum_{i=1}^{M} \sum_{j=1}^{N_i} \log \left( \sum_{k=1}^{K} \omega_{i,j;k} \cL_k(\xx_{i,j}, y_{ij}; \mphi, \mtheta_k) \right) \nonumber \\
& + \sum_{i=1}^{M} \sum_{j=1}^{N_i} \lambda_{i,j} \left( \sum_{k=1}^{K} \omega_{i,j;k} - 1 \right) \nonumber                                           \\
& - \mu \sum_{i=1}^{M} \sum_{j=1}^{N_i} \left( \sum_{k=1}^{K} \tilde{\omega}_{i;k} \log \frac{\tilde{\omega}_{i;k}}{\omega_{i,j;k}} \right)  \, ,
\end{align}

and we define $\tilde{\mOmega} = \{ \tilde{\omega}_{i;k} | \forall i, k \}$, then $\tilde{\mOmega}$ is obtained by

\begin{align}
\tilde{\mOmega} & = \argmin_{\tilde{\mOmega}} \left| \max_{\mOmega} \cL(\mphi, \mTheta, \mOmega, \mOmega) -  \cL(\mphi, \mTheta, \tilde{\mOmega}, \tilde{\mOmega}) \right| \, .
\end{align}

Then E-M steps are obtained by maximizing $\cL(\mphi, \mTheta, \mOmega, \tilde{\mOmega})$.

\begin{align}
\gamma_{i,j;k}^{t+1}         & = \frac{ \omega_{i,j;k}^{t} \cL_k(\xx_{i,j}, y_{ij}; \mtheta_k^{t})}{\sum_{n=1}^{K} \omega_{i,j;n}^{t} \cL_k(\xx_{i,j}, y_{ij}; \mtheta_n^{t})} \, ,                                                                 \\
\tilde{\gamma}_{i,j;k}^{t+1} & = \frac{ \tilde{\omega}_{i;k}^{t} \cL_k(\xx_{i,j}, y_{ij}; \mtheta_k^{t})}{\sum_{n=1}^{K} \omega_{i;n}^{t} \cL_k(\xx_{i,j}, y_{ij}; \mtheta_n^{t})} \, ,                                                             \\
\tilde{\omega}_{i;k}^{t+1}   & = \frac{1}{N_i} \sum_{j=1}^{N_i} \tilde{\gamma}_{i,j;k}^{t+1} \, ,                                                                                \\
\omega_{i,j;k}^{t+1}         & = \frac{\gamma_{i,j;k}^{t+1}}{1 + \mu N} + \frac{\mu N}{1 + \mu N} \tilde{\omega}_{i;k}^{t+1} \, ,                                                                                \\
\mtheta_k^{t+1}              & = \mtheta_k^{t} - \eta \sum_{i=1}^{M} \sum_{j=1}^{N_i} \frac{\gamma_{i,j;k}^{t+1}}{\cL_k(\xx_{ij}, y_{ij}, \mphi^{t}, \mtheta_k^{t})} \nabla_{\mtheta_k} \cL_k (\xx_{ij}, y_{ij}, \mphi^{t}, \mtheta_k^{t}) \, ,     \\
\mphi^{t+1}                  & = \mphi^{t} - \eta \sum_{i=1}^{M} \sum_{j=1}^{N_i} \sum_{k=1}^{K} \frac{\gamma_{i,j;k}^{t+1}}{\cL_k(\xx_{ij}, y_{ij}, \mphi^{t}, \mtheta_k^{t})} \nabla_{\mphi} \cL_k (\xx_{ij}, y_{ij}, \mphi^{t}, \mtheta_k^{t+1})
\end{align}

Let's begin by assuming $\tilde{\omega}_{i;k}^{t+1}$ is given for each round $t$, then we will discuss how to compute $\omega_{i,j;k}^{t+1}$. Consider the objective function $\cL(\mphi, \mTheta, \mOmega, \tilde{\mOmega})$, we have

\begin{align}
\derive{\cL(\mphi, \mTheta, \mOmega, \tilde{\mOmega})}{\omega_{i,j;k}}
= \frac{1}{N} \frac{\cL_k(\xx_{i,j}, y_{ij}; \mtheta_n)}{\sum_{n=1}^{K} \omega_{i,j;n} \cL_n(\xx_{i,j}, y_{ij}; \mtheta_n)} + \lambda_{i,j} + \mu \frac{\tilde{\omega}_{i;k}}{\omega_{i,j;k}} \, .
\end{align}

Then define

\begin{align}
\gamma_{i,j;k} = \frac{\omega_{i,j;k} \cL_k(\xx_{i,j}, y_{ij}; \mtheta_n)}{\sum_{n=1}^{K} \omega_{i,j;n} \cL_n(\xx_{i,j}, y_{ij}; \mtheta_n)} \, ,
\end{align}

and take $\derive{\cL(\mTheta, \mOmega)}{\omega_{i,j;k}} = 0$ we have

\begin{align}
\frac{\gamma_{i,j;k}}{N} + \mu \tilde{\omega}_{i;k} = - \lambda_{i,j} \omega_{i,j;k} \, .
\end{align}

Then we have

\begin{align}
\omega_{i,j;k} = - \frac{1}{\lambda_{i,j}} \left( \frac{\gamma_{i,j;k}}{N} + \mu \tilde{\omega}_{i;k} \right) \, .
\end{align}

Because we have $\sum_{k=1}^{K} \omega_{i,j;k} = 1$, we have

\begin{align}
1             & = - \frac{1}{\lambda_{i,j}} \left( \frac{1}{N} + \mu \right) \\
\lambda_{i,j} & = - \frac{1 + \mu N}{N} \, .
\end{align}

Then we have

\begin{align}
\omega_{i,j;k} = \frac{\gamma_{i,j;k}}{1 + \mu N} + \frac{\mu N}{1 + \mu N} \tilde{\omega}_{i;k} \, .
\end{align}

Then consider to optimize $\mtheta_k$, we have,

\begin{align}
& \derive{\cL (\mphi, \mathbf{\Theta}, \mOmega, \tilde{\mOmega}) }{\mtheta_k}  \nonumber                                                                                \\
& = \frac{1}{N} \sum_{i=1}^{M} \sum_{j=1}^{N_i} \frac{\omega_{i,j;k} }{\sum_{n=1}^{K} \omega_{i,j;n} \cL_n (\xx_{ij}, y_{ij}; \mphi, \mtheta_n)} \cdot \derive{\cL_k (\xx_{ij}, y_{ij}; \mphi, \mtheta_k)}{\mtheta_k} \, , \\
& = - \frac{1}{N} \sum_{i=1}^{M} \sum_{j=1}^{N_i} \frac{\gamma_{i,j;k}^{t+1}}{\cL_k(\xx_{ij}, y_{ij}; \mphi, \mtheta_k)} \nabla_{\mtheta_k} \cL_k (\xx_{ij}, y_{ij}; \mphi, \mtheta_k) \, .
\end{align}

Finally, consider to optimize $\mphi$, we have

\begin{align}
& \derive{\cL (\mphi, \mathbf{\Theta}, \mOmega, \tilde{\mOmega}) }{\mphi} \nonumber                                                                                \\
& = \frac{1}{N} \sum_{i=1}^{M} \sum_{j=1}^{N_i} \sum_{k=1}^{K} \frac{\omega_{i,j;k} }{\sum_{n=1}^{K} \omega_{i,j;n} \cL_n (\xx_{ij}, y_{ij}; \mphi, \mtheta_n)} \cdot \derive{\cL_k (\xx_{ij}, y_{ij}; \mphi, \mtheta_k)}{\mphi}
\, ,                                                                                \\
& = - \frac{1}{N} \sum_{i=1}^{M} \sum_{j=1}^{N_i} \sum_{k=1}^{K} \frac{\gamma_{i,j;k}^{t+1}}{\cL_k(\xx_{ij}, y_{ij}; \mphi, \mtheta_k)} \nabla_{\mphi} \cL_k (\xx_{ij}, y_{ij}; \mphi, \mtheta_k)
\, .
\end{align}

Because if hard to find a close-form solution to $\derive{\cL (\mphi, \mathbf{\Theta}, \mOmega, \tilde{\mOmega}) }{\mtheta_k} = 0$ when $\mtheta_k$ is the parameter of deep neural networks, we use gradient ascent to optimize $\mtheta_k$. The same method is used for feature extractors $\mphi$.

Then the remaining thing is how to decide $\tilde{\omega}_{i;k}$. From the formulation of objective function, the $\tilde{\omega}_{i;k}$ is decided by

\begin{align}
\tilde{\mOmega} & = \argmin_{\tilde{\mOmega}} \left| \max_{\mOmega} \cL(\mphi, \mTheta, \mOmega, \mOmega) -  \cL(\mphi, \mTheta, \tilde{\mOmega}, \tilde{\mOmega}) \right| \, .
\end{align}

To solve this problem, firstly, we can transform the definition of $\cL(\mphi, \mTheta, \tilde{\mOmega}, \tilde{\mOmega})$ to

\begin{align}
\cL(\mphi, \mTheta, \tilde{\mOmega}, \tilde{\mOmega}) & = \frac{1}{N} \sum_{i=1}^{M} \sum_{j=1}^{N_i} \log \left( \sum_{k=1}^{K} \omega_{i,j;k} \cL_k(\xx_{i,j}, y_{ij}; \mphi, \mtheta_k) \right) \nonumber \\
& + \sum_{i=1}^{M} \sum_{j=1}^{N_i} \lambda_{i,j} \left( \sum_{k=1}^{K} \omega_{i,j;k} - 1 \right) \nonumber                                           \\
& - \mu \sum_{i=1}^{M} \sum_{j=1}^{N_i} \left( \sum_{k=1}^{K} \tilde{\omega}_{i;k} \log \frac{\tilde{\omega}_{i;k}}{\omega_{i,j;k}} \right)  \, ,      \\
s.t.\;                                                & \; \omega_{i,j;k} = \tilde{\omega}_{i;k}, \; \forall i,j,k \, .
\end{align}

Then by removing the constrains, we can always find

\begin{align}
\max_{\mOmega} \cL(\mphi, \mTheta, \mOmega, \tilde{\mOmega}) \ge \tilde{\cL}(\mphi, \mTheta, \tilde{\mOmega}, \tilde{\mOmega}) \, .
\end{align}

Then we have

\begin{align}
\tilde{\mOmega} & = \argmin_{\tilde{\mOmega}} \left| \max_{\mOmega} \cL(\mphi, \mTheta, \mOmega, \tilde{\mOmega}) -  \cL(\mphi, \mTheta, \tilde{\mOmega}, \tilde{\mOmega}) \right| \\
& = \argmin_{\tilde{\mOmega}} \left( \max_{\mOmega} \cL(\mphi, \mTheta, \mOmega, \tilde{\mOmega}) -  \cL(\mphi, \mTheta, \tilde{\mOmega}, \tilde{\mOmega}) \right) \\
& = \argmax_{\tilde{\mOmega}} \cL(\mphi, \mTheta, \tilde{\mOmega}, \tilde{\mOmega})
\end{align}

Then we can obtain the results by directly use the proof in [Guo et al., 2023] and [Marfoq et al., 2021].

§ RELATED WORKS

Federated Learning.
As the de-facto algorithm in FL, FedAvg employs local SGD [McMahan et al., 2016, Lin et al., 2020] to reduce communication costs and protect client privacy.
However, distribution shifts among clients pose a significant challenge in FL and hinder the performance of FL algorithms [Li et al., 2018, Wang et al., 2020, Karimireddy et al., 2020, Jiang & Lin, 2023, Guo et al., 2021].
Traditional FL methods primarily aim to improve the convergence speed of global models and incorporate bias reduction techniques [Tang et al., 2022, Guo et al., 2023, Li et al., 2021, Li et al., 2018].
At the same time, some studies investigate feature distribution shifts using domain generalization techniques [Peng et al., 2019, Wang et al., 2022, Shen et al., 2021, Sun et al., 2022, Gan et al., 2021].
However, single-model approaches are inadequate for handling heterogeneous data distributions, especially when dealing with concept shifts [Ke et al., 2022, Guo et al., 2023, Jothimurugesan et al., 2023].
To tackle these challenges, clustered FL algorithms are introduced to enhance FL algorithm performance.=-1

Clustered FL with fixed cluster numbers. Clustered FL groups clients based on their local data distribution, tackling the distribution shift problem. Most methods employ hard clustering with a fixed number of clusters, grouping clients by various similarity metrics, such as local loss values [Ghosh et al., 2020], local model parameter differences [Long et al., 2023], communication time/local calculation time [Wang et al., 2022], and fuzzy $c$-Means [Stallmann & Wilbik, 2022]. However, hard clustering may not capture complex relationships between local distributions adequately, and soft clustering paradigms have been proposed to address this issue.
For instance, FedEM [Marfoq et al., 2021] employs Expectation-Maximization techniques to maximize likelihood functions. FedGMMcitepwu2023personalized suggests using joint distributions instead of conditional distributions. FedRC[Guo et al., 2023] introduces Robust Clustering, assigning clients with concept shifts to different clusters to enhance model generalization. FedSoft [Ruan & Joe-Wong, 2022] calculates weights based on the distances between clients' local model parameters and cluster model parameters, with smaller distances indicating larger weights for that cluster.
In this paper, we propose a generalized formulation for clustered FL that encompasses the current methods and improves them by addressing issues related to intra-client inconsistency and efficiency.

Clustered FL with adaptive clustering numbers. Another line of research focuses on automatically determining the number of clusters.
Current methods utilize hierarchical clustering, which measures client dissimilarity using model parameters or local gradient distances. Most current methods modify cluster numbers by splitting them when client distances within clusters are large [Sattler et al., 2020, Sattler et al., 2020, Zhao et al., 2020, Briggs et al., 2020, Duan et al., 2021, Duan et al., 2021]. Recently, StoCFL [Zeng et al., 2023] suggests initially setting cluster numbers equal to the client count and merging clusters with small distances.
In addition to model parameter distances, some papers employ alternative distance metrics for improved performance.
For instance, Yan et al., 2023 employ principal eigenvectors of model parameters. Vahidian et al., 2023 use truncated singular value decomposition (SVD) to obtain a reduced set of principal vectors for distance measurement. Meanwhile, Wei & Huang, 2023 focus on the distance of normalized local features.
FEDCOLLAB [Bao et al., 2023] focuses on cross-silo scenarios with a limited number of clients
and quantifies client similarity by training client discriminators. However, the need for discriminators between every pair of clients in FEDCOLLAB makes it challenging to expand to cross-device scenarios with numerous clients.
In this paper, we concentrate on cross-device settings, introducing a holistic adaptive clustering framework enabling cluster splitting and merging. We also present enhanced weight updating for soft clustering and finer distance metrics for various clustering principles.=-1

§ ALGORITHMS

Details of the . In Algorithm <ref>, we present a concise summary of the comprehensive algorithm that integrates all the enhanced components of , as introduced in Section <ref>. Specifically, during each communication round, the algorithm performs the following steps:
(1) Randomly selects a subset of clients.
(2) Calculates prototypes using Equations (<ref>) and (<ref>).
(3) Performs local updates using Algorithm <ref>.
(4) The server aggregates local updates, updates cluster model parameters, and computes client distance metrics using Equation (<ref>) for each cluster $k$.
(5) Identifies $k_{max}$ as the cluster with the highest average distance.
(6) Checks if the maximum distance within $k_{max}$ significantly exceeds the average distance in this cluster.
(7) If the following condition is met, splits the clusters using Algorithm <ref>.

\begin{align}
\max (D_{k_{max}}^{t}) - \operatorname{mean} (D_{k_{max}}^{t}) \ge \rho \, .
\end{align}

(8) Mark and remove the empty clusters no clients will assign large clustering weights to using Algorithm <ref>.

Intuitions on the distance metrics design.
From the objective function (Eq. (<ref>)), we should assign higher clustering weights $\omega_{i,j;k}$ to clusters with greater $\cL_k(\xx_{i,j}, y_{i,j}, \mphi, \mtheta_k)$ to maximize the objective function.
Because the ultimate goals of the clustering algorithms are solving the objective functions, we analyse the $\cL_k(\xx_{i,j}, y_{i,j}, \mphi, \mtheta_k)$ to check the key factors influencing the value of $\cL_k(\xx_{i,j}, y_{i,j}, \mphi, \mtheta_k)$, and the relationships between these factors and the clustering principles.

We use the following algorithms as examples. For FedEM [Marfoq et al., 2021] and IFCA [Ghosh et al., 2020],  $\cL_k(\xx, y, \mphi, \mtheta_k) = \cP_{\mphi, \mtheta_k}(y | \xx)$;
For FedRC [Guo et al., 2023], $\cL_k(\xx, y, \mphi, \mtheta_k) = \frac{\cP_{\mphi, \mtheta_k}(\xx, y)}{\cP_{\mphi, \mtheta_k}(\xx)\cP_{\mphi, \mtheta_k}(y)}$.
Defining $\zz = g(\xx;\mphi)$ as the local features extracted by $\mphi$, assuming a $\xx \to \zz \to y$ Probabilistic Graphical Model (with $\xx$ and $y$ being independent given $\zz$), we obtain:=-1

\begin{align*}
\textstyle
\cL_k(\xx, y, \mphi, \mtheta_k)
\begin{split}
\left \{
\begin{array}{ll}
\cP(y|\xx; \mphi, \mtheta_k) =  \frac{\cP(y | \zz; \mtheta_k) \cP(\zz |\xx; \mphi)}{ \cP(\zz | \xx, y; \mphi) }
\,                                                                                & \text{\tiny (FedEM, IFCA)} \\
\frac{\cP(\xx, y; \mphi, \mtheta_k)}{\cP(y; \mphi, \mtheta_k) \cP(\xx; \mphi, \mtheta_k)} = \frac{\cP(y | \zz; \mtheta_k) \cP(\zz |\xx; \mphi)}{\cP(y; \mphi, \mtheta_k) \cP(\zz | \xx, y; \mphi) } \, & \text{\tiny (FedRC)}
\end{array}
\right \}
= \frac{\tilde{\cL}_k(\zz, y;\mtheta_k) \cP(\zz | \xx; \mphi)}{ \cP(\zz | \xx, y; \mphi) } \,.
\end{split}
\end{align*}

Then we aim to give the following explanations of the three terms $\cP(\zz | \xx; \mphi)$, $\cP(\zz | \xx; \mphi)$, and $\tilde{\cL}_k(\zz, y;\mtheta_k)$, which align with the terms considered in Sec <ref>.

* $\cP(\zz | \xx; \mphi)$ for feature and label shifts. Feature shifts introduce significant distances in $\xx$. Additionally, $\xx$ with different $y$ values generally exhibit substantial distances in the feature space. Without this, classifiers cannot distinguish samples with different labels. Hence, we employ $\cP(\zz | \xx; \mphi)$ to assess both feature and label shifts.

* $\cP(\zz | \xx, y; \mphi)$ for concept shifts. Concept shifts signify alerted $\xx-y$ correlations. Hence, samples with concept shifts but have the same $y$ should exhibit a significant difference in $\cP(\zz | \xx, y; \mphi)$.

* $\tilde{\cL}_k(\zz, y;\mtheta_k)$ for the quality of clustering. The $\tilde{\cL}_k(\zz, y;\mtheta_k)$ is defined using features $\zz = g(\xx;\mphi)$ instead of data $\xx$ in $\cL_k(\xx, y, \mphi, \mtheta_k)$. This term evaluates if features $\zz$ can be correctly assigned to clusters given the current $\mTheta$; otherwise, the objectives in (<ref>) cannot be achieved.

Finally, we propose the following distance metric:

\begin{align}
\textstyle
\mD_{i,j}^{k}
\begin{split} =
\left \{
\begin{array}{ll}
\max \left \{ d_c, d_{lf} \right \}
\E_{D_i} \left[\tilde{\cL}_k(\zz, y;\mtheta_k) \right]
\E_{D_j} \left[\tilde{\cL}_k(\zz, y;\mtheta_k) \right] \, , & \text{\cpA} \\
\E_{D_i} \left[\tilde{\cL}_k(\zz, y;\mtheta_k) \right]
\E_{D_j} \left[\tilde{\cL}_k(\zz, y;\mtheta_k) \right] \, ,                             & \text{\cpB}
\end{array}
\right.
\end{split}
\label{equ:theory-distance-appendix}
\end{align}

where $\text{dist}$ is the cos-similarity in this paper, $d_c \!=\! \max_{y} \left\{ \text{dist} \left( \E_{D_i} \left[\cP(\zz | \xx, y;\mphi) \right], \E_{D_j} \left[\cP(\zz| \xx, y; \mphi) \right] \right) \right\}$, and $d_{lf} \!=\! \text{dist} \left( \E_{D_i} \left[\cP(\zz | \xx;\mphi) \right], \E_{D_j} \left[\cP(\zz| \xx; \mphi) \right] \right)$.
The distances above become large only when the following conditions occur together:
(1) Large values of $d_c$ indicate concept shifts between clients $i$ and $j$;
(2) Large $d_{lf}$ indicate significant feature and label distribution differences.
(2) Large values of $\E_{D_i} \left[\tilde{\cL}_k(\zz, y;\mtheta_k) \right] \E_{D_j} \left[\tilde{\cL}_k(\zz, y;\mtheta_k) \right]$ indicate incorrect clustering weights with high confidence.

Approximation of the distance metrics in practice.
When calculating the distance metrics (Equation (<ref>)) in practice, to avoid training extra generative networks and transmitting more data between servers and clients, we substitute $\tilde{\omega}_{i;k}$ for $\tilde{\cL}_k(\zz, y;\mtheta_k)$ since $\tilde{\omega}_{i;k}$ is positively correlated with $\tilde{\cL}_k(\zz, y;\mtheta_k)$ [Marfoq et al., 2021, Guo et al., 2023]. Additionally, we approximate $\E_{D_i} \left[\cP(\zz | \xx, y;\mphi) \right]$ and $\E_{D_i} \left[\cP(\zz | \xx, y;\mphi) \right]$ using feature prototypes.
The prototypes are defined by the following equation:

\begin{align}
\tilde{d}_c = Dist(\mP_{c, i}, \mP_{c, j}) \, ,
\tilde{d}_{lf} = Dist(\mP_{lf, i}, \mP_{lf, j}) \, ,
\end{align}

\begin{align}
\mP_{c, i} \in \R^{d \times C}
& = [\frac{1}{N_{i, 1}} \sum_{j=1}^{N_i} \mathbf{1}_{y_{i,j}=1} g(\xx_{i,j}, \mphi), \cdots, \frac{1}{N_{i, C}} \sum_{j=1}^{N_i} \mathbf{1}_{y_{i,j}=C} g(\xx_{i,j}, \mphi)] \, ,
\label{equ:get-the-prototypes}                                                                                \\
\mP_{lf, i} \in \R^{d} & = \frac{1}{N_{i}} \sum_{j=1}^{N_i} g(\xx_{i,j}, \mphi) \, ,
\label{equ:get-the-mean-prototypes}
\end{align}

$N_{i,c} = \sum_{j=1}^{N_i} \mathbf{1}_{y_{i,j}=c}$, $g(\xx_{i,j}, \mphi)$ is the function parameterized by $\mphi$,
$Dist$ is a function to measure the distance between prototypes, which we use the cosine similarity as an example in this paper.

[1]
Local datasets $D_1, \dots, D_N$, number of local iterations $\mathcal{T}$, number of communication rounds $T$, number of clients chosen in each round $S$, initial number of clusters $K^{0}$, number of classes $C$, and hyper-parameter $\rho$.
Trained global feature extractor $\mphi^{T}$, final number of clusters $K^{T}$, and cluster-specific predictors $\mTheta^{T} = [\mtheta_1^{T}, \cdots, \mtheta_{K^{T}}^{T}]$.
Initialize $\mphi^{0}, \mTheta^{0} = [\mtheta_1^{0}, \cdots, \mtheta_{K^{0}}^{0}]$.
$t = 0, \dots, T-1$
Choose a subset of clients $\mathcal{S}^{t}$, where $|\mathcal{S}^{t}| = S$.
chosen client $i \in \mathcal{S}^{t}$
Calculate client prototypes $\mP_{i}^{t}$ by Equation (<ref>)- (<ref>).
$\mathcal{F}_{i}^{t+1}, \tilde{\omega}_{i;k}^{t+1}, \mphi_{i}^{\mathcal{T}}, \mtheta_{k, i}^{\mathcal{T}} \gets$ Local updates by Algorithm <ref>.
Send $\mP_{i}^{t}$, $\mathcal{F}_{i}^{t+1}$, and  $\tilde{\omega}_{i;k}^{t+1}, \mphi_{i}^{\mathcal{T}}, \mtheta_{k, i}^{\mathcal{T}}$, $\forall k \le K^{t}$ to the server.
$\mathcal{F}_{i}^{latest} \gets \mathcal{F}_{i}^{t+1}$.
$\mphi^{t+1} = \frac{1}{\sum_{i \in \cS^{t}}} \sum_{i \in \cS^{t}} N_i \mphi_i^{\cT}$.
$\mtheta_k^{t+1} = \frac{1}{\sum_{i \in \cS^{t}}} \sum_{i \in \cS^{t}} N_i \mtheta_{k,i}^{\cT}$, $\forall k \le K^{t}$.
$\cF_{g}^{t+1} \gets [ \cF_{g, 1}^{t+1}, \cdots, \cF_{g, K^{t}}^{t+1} ]$, where $\cF_{g, k}^{t+1} \gets [\sum_{i} \cF_{i, k, 1}^{latest}, \cdots, \sum_{i} \cF_{i, k, C}^{latest}]$.
Initialize $\cC_{k}^{t} = \emptyset$, $\forall k \le K^t$.
all client $i$
$c_i \gets \argmax_{k} \tilde{\omega}_{i;k}$.
$\cC_{c_{i}}^{t} \gets \cC_{c_i}^{t} \cup i$.
$\cR^{t} \gets \emptyset$.
$k \le K^{t}$
$\cC_{k}^{t}$ is empty
$\cR^{t} \gets \cR^{t} \cup k$.
Get the cluster-specific distance matrix $\mD_k \in \R^{|\tilde{\cS}_{k}^{t}| \times |\tilde{\cS}_{k}^{t}|}$, $\forall k \le K^{t}$ by Equation (<ref>).
$k_{min} \gets \argmax_{k} \max(\mD_{k}^{t})$.
$\max(\mD_{k_{min}}^{t}) - mean(\mD_{k_{min}}^{t}) \ge \rho$
Split $\cC_{k_{min}}^{t}$ into two clusters $\cC_{k_{min}, 1}^{t}$ and $\cC_{k_{min}, 2}^{t}$.
$\mtheta_{k_{min}}^{t+1} = \frac{1}{\sum_{i \in \cC_{k_{min}, 1}^{t}}} \sum_{i \in \cC_{k_{min}, 1}^{t} } N_i \mtheta_{k_{min}, i}^{\cT} $.
Add new cluster and update $\cF_g$ by server side of Algorithm <ref>.
$K^{t+1} \gets K^{t} + 1$.
$K^{t+1} \gets K^{t}$.
cluster $k_r \in \cR^{t}$
Remove cluster $k_r$ and update $\cF_g$ by server side of Algorithm <ref>.
$K^{t+1} \gets K^{t+1} - 1$.
Send $\mphi^{t+1}$, $\mTheta^{t+1} = [\mtheta_1^{t+1}, \cdots, \mtheta_{K^{t+1}}^{t+1}]$, and information about add/remove cluster to clients.

algorithmAlgorithm Framework of

[1]
Number of local iterations $\mathcal{T}$, current number of clusters $K^{t}$, number of classes $C$, local dataset $D_i$, global feature extractor $\mphi^{t}$, cluster-specific predictors $\mTheta^{t} = [\mtheta_1^{t}, \cdots, \mtheta_{K^{t}}^{t}]$.
Trained feature extractor $\mphi_{i}^{\mathcal{T}}$, predictors $\mTheta_{i}^{\mathcal{T}} = [\mtheta_{i,1}^{\mathcal{T}}, \cdots, \mtheta_{i,K^{t}}^{\mathcal{T}}]$, $\tilde{\mOmega}_{i}^{t+1} = [\tilde{\omega}_{i;k}, \cdots, \tilde{\omega}_{i;K^{t}}]$, and $\mathcal{F}_{i}^{t+1} = [\mathcal{F}_{i, 1}^{t+1}, \cdots, \mathcal{F}_{i, K^{t}}^{t+1}]$, where $\mathcal{F}_{i, k}^{t+1} = [\mathcal{F}_{i, k, 1}^{t+1}, \cdots, \mathcal{F}_{i, k, C}^{t+1}]$.
Update $\gamma_{i,j;k}^{t+1}, \tilde{\gamma}_{i,j;k}^{t+1}, \omega_{i,j;k}^{t+1}, \tilde{\omega}_{i;k}^{t+1}$ by Equations (<ref>)-(<ref>), $\forall j \le N_i, k \le K^{t}$.Tier 2
$\tau = 1, \dots, \mathcal{T}$Tier 1
Update $\mtheta_{k, i}^{\tau}$ by Equation (<ref>), $\forall k \le K^{t}$.
Update $\mphi_{i}^{\tau}$ by Equation (<ref>).
$\mathcal{F}_{i, k, c}^{t+1} \gets \sum_{j=1}^{N_i} \mathbf{1}_{y_{i,j}=c} \gamma_{i,j;k}^{t+1}$.

algorithmLocal Updates of

[1]
$k_{min}$, set of clients $\cC_{k_{min}, 2}^{t}$, the corresponding $\mtheta_{k_{min}, i}^{\cT}$ for each client $i \in \cC_{k_{min}, 2}^{t}$, and $\cF_g$.
New $\cF_g^{t+1}$, and predictor of the new cluster $\mtheta_{K^{t} + 1}^{t+1}$.
Server Side:
$\mtheta_{K^{t} + 1}^{t+1} = \frac{1}{\sum_{i \in \cC_{k_{min}, 2}^{t}}} \sum_{i \in \cC_{k_{min}, 2}^{t} } N_i \mtheta_{k_{min}, i}^{\cT} $.
Add $\cF_{g, K^{t} + 1} \gets \cF_{g, k_{min}}$ to $\cF_g^{t+1}$.
Add $\cF_{i, K^{t} + 1}^{latest} \gets \cF_{i, k_{min}}^{latest}$ to $\cF_{i}^{latest}$, $\forall i$.
Client Side:
$\omega_{i,j;K^{t} + 1} \gets \omega_{i,j;k_{min}} / 2$, $\forall j \le N_i$.
$\omega_{i,j;k_{min}} \gets \omega_{i,j;k_{min}} / 2$, $\forall j \le N_i$.
$\tilde{\omega}_{i;K^{t} + 1} \gets \tilde{\omega}_{i;k_min} / 2$.
$\tilde{\omega}_{i;k_{min}} \gets \tilde{\omega}_{i;k_min} / 2$.

algorithmCluster Adding of

[1]
The cluster needs to be removed $k_r$, and $\cF_g^{t+1}$.
Server Side:
Remove $\cF_{g, k_r}^{t+1}$ from $\cF_g^{t+1}$.
Remove $\cF_{i, k_r}^{latest}$ from $\cF_{i}^{latest}$, $\forall i$.
Client Side:
$\omega_{i,j;k} \gets \frac{\omega_{i,j;k}}{\sum_{n \not = k_r} \omega_{i,j;n}}$, $\forall j \le N_i, k \not = k_r$.
$\tilde{\omega}_{i;k} \gets \frac{\omega_{i;k}}{\sum_{n \not = k_r} \omega_{i;n}}$, $\forall k \not = k_r$.
Remove $\gamma_{i,j;k_r}, \tilde{\gamma}_{i,j;k_r}, \omega_{i,j;k_r}, \tilde{\omega}_{i,j;k_r}$, $\forall j \le N_i$.

algorithmCluster Removing of

§ EXPERIMENT RESULTS

§.§ Datasets and Models

Diverse distribution shifts scenarios. Similar to previous work [Guo et al., 2023], the diverse distribution shift scenario construct clients with three types of distribution shifts with each other:

* Label Distribution Shifts: We use the idea introduced Yoshida et al., 2019, Hsu et al., 2019, Reddi et al., 2021, where we leverage the Latent Dirichlet Allocation (LDA) with $\alpha = 1.0$. We split datasets to 100 clients by default.

* Feature Distribution Shifts: We utilize the idea of constructing CIFAR10-C, CIFAR100-C, and ImageNet-C [Hendrycks & Dietterich, 2019]. In detail, we apply random augmentations to client samples, selecting from 20 types, including 'Original', 'Gaussian Noise', 'Shot Noise', 'Impulse Noise', 'Defocus Blur', 'Glass Blur', 'Motion Blur', 'Zoom Blur', 'Snow', 'Frost', 'Fog', 'Brightness', 'Contrast', 'Elastic', 'Pixelate', 'JPEG', 'Speckle Noise', 'Gaussian Blur', 'Spatter', and 'Saturate'. Augmentation types remain consistent within each client.

* Concept Shifts: For label $y \le C_{\beta}$, it becomes $y$, $(1 + y) \% C_{\beta}$, and $(2 + y) \% C_{\beta}$ across concepts, where $C_{\beta} = \lfloor C * \beta \rfloor$, and $C$ is the number of classes.

Noisy label scenarios. We follow the methodology of previous works [Fang & Ye, 2022, Ke et al., 2022] to construct noisy label scenarios. Our approach involves two types of noisy labels: symmetric flip and pair flip. Symmetric flip entails randomly flipping the original class label to any wrong class label with equal probability. Pair flip involves flipping the original class label only to a very similar wrong category. We use the parameter $\chi$ to control the noisy rate, where $\chi = 0.1$ indicates that $10\%$ of the data have wrong labels.

§.§ Baselines and Hyper-Parameter Settings

Detailed implementations and hyper-parameter settings for all the algorithms Unless special mentioned, we split each dataset to 100 clients with 3 concepts. The learning rates are chosen in $\{0.03, 0.06, 1.0\}$, and we report the best results for each algorithm. We run the algorithms for 200 communication rounds and set the number of local epochs to 1.

Detailed implementations and hyper-parameter settings of baseline algorithms. The details of the settings and hyper-parameters we used for the baseline methods a summarized below. We exclude the algorithms that do not require additional hyper-parameters here.

* CFL [Sattler et al., 2020]. We use the public code provided by [Marfoq et al., 2021] for the CFL algorithm. The hyper-parameters $\text{tol}_1$ and $\text{tol}_2$ are tuned, and we report how the hyper-parameters affect the results of the algorithm in Table <ref>.

* ICFL [Yan et al., 2023]. Follow the same setting as the original paper, we set the hyper-parameter $\alpha*(0)$ to $\{0.85, 0.98\}$, and $\epsilon_1 = 4.0$.

* stoCFL [Zeng et al., 2023]. We choose $\tau = \{0, 0.05, 0.1, 0.15\}$ to control the trade-off between personalization and generalization as suggested by the original paper. In addition, we choose $\lambda = 0.5$, which always achieve the best performance as reported in the original paper.

* (FedRC) [Guo et al., 2023]. We set $\tilde{\mu} = 0.4$, and choose $\rho = \{0.05, 0.1, 0.3\}$. The distance between clients are calculated by Equation (<ref>).

* (FedEM) [Marfoq et al., 2021]. We set $\tilde{\mu} = 0.4$, and choose $\rho = \{0.05, 0.1, 0.3\}$. The distance between clients are calculated by Equation (<ref>).

* (FeSEM) [Long et al., 2023]. We choose $\rho = \{0.05, 0.1, 0.3\}$. Follow the original paper, we use hard clustering paradigms that does not require the hyper-parameter $\tilde{\mu}$. The model splitting process is the same as Sattler et al., 2020 that designed for hard clustering paradigms.
The distance between clients are calculated by Equation (<ref>).

§.§ Additional Experiment Results

Results on noisy data scenarios
In Table <ref>, we show the performance of clustered FL emthods on noisy data scenarios. Results show that consistently outperform other methods by a large margin.

Performance of algorithms on noisy data scenarios. We evaluated the performance of algorithms using the CIFAR10 dataset split into 100 clients. For each algorithm, we report the best test accuracy for all 200 communication rounds.

2*Algorithm     4cCIFAR10 (MobileNetV2)

(lr)2-5 (lr)6-7
Pairflip, $\chi=0.1$                             Pairflip,$\chi=0.2$                              Symflip, $\chi=0.2$                              Symflip, $\chi=0.4$

FedAvg                         $54.75$ 0.5 $\pm 1.45$              $52.35$ 0.5 $\pm 1.65$              $52.60$ 0.5 $\pm 0.50$              $41.80$ 0.5 $\pm 0.50$

FeSEM                          $32.60$ 0.5 $\pm 1.30$              $35.25$ 0.5 $\pm 2.95$              $32.40$ 0.5 $\pm 2.80$              $29.70$ 0.5 $\pm 0.01$

IFCA                           $24.95$ 0.5 $\pm 7.05$              $20.55$ 0.5 $\pm 4.65$              $30.35$ 0.5 $\pm 2.05$              $36.05$ 0.5 $\pm 4.45$

FedEM                          $64.40$ 0.5 $\pm 1.10$              $57.55$ 0.5 $\pm 2.95$              $53.00$ 0.5 $\pm 1.90$              $43.10$ 0.5 $\pm 0.20$

FedRC                          $67.90$ 0.5 $\pm 1.00$              $59.95$ 0.5 $\pm 1.05$              $55.25$ 0.5 $\pm 2.05$              $42.00$ 0.5 $\pm 0.40$

$\mathbf{66.70}$ 0.5 $\pm 0.40$     $\mathbf{62.70}$ 0.5 $\pm 0.30$     $\mathbf{59.95}$ 0.5 $\pm 1.15$     $\mathbf{47.20}$ 0.5 $\pm 0.20$

Additional results on diverse distribution shift scenarios. In Table <ref>, we show the performance of algorithms with $\beta = 0.4$. Results show always achieve the best test accuracy, and achieve a good local-global balance.

Performance of the adaptive clustering methods. We evaluated algorithm performance on CIFAR10 and CIFAR100 datasets, employing 100 clients. For each algorithm, we present the highest validation and test accuracies across 200 communication rounds, and the final number of clusters during training denoted as $K^{T}$. All experiments utilized MobileNet-V2 [Sandler et al., 2018].

2*Algorithm                       3cCIFAR10, $\beta = 0.4$       3cCIFAR100, $\beta = 0.4$

(lr)2-4 (lr)5-7
Val                                              Test                                             $K^{T}$     Val                                              Test                                             $K^{T}$

FedAvg                                           $48.16$ 0.5 $\pm 1.64$     $49.93$ 0.5 $\pm 0.80$     3.0         $22.77$ 0.5 $\pm 0.01$     $24.62$ 0.5 $\pm 0.55$     3.0

FeSEM                                            $46.08$ 0.5 $\pm 4.54$     $35.99$ 0.5 $\pm 4.59$     3.0         $23.56$ 0.5 $\pm 1.52$     $22.31$ 0.5 $\pm 1.08$     3.0

IFCA                                             $36.15$ 0.5 $\pm 3.45$     $24.79$ 0.5 $\pm 1.18$     3.0         $27.72$ 0.5 $\pm 0.82$     $21.37$ 0.5 $\pm 1.33$     3.0

FedEM                                            $60.26$ 0.5 $\pm 1.10$     $54.44$ 0.5 $\pm 0.04$     3.0         $25.80$ 0.5 $\pm 0.20$     $22.88$ 0.5 $\pm 0.19$     3.0

FedRC                                            $57.99$ 0.5 $\pm 0.29$     $56.75$ 0.5 $\pm 0.38$     3.0         $30.94$ 0.5 $\pm 0.88$     $31.63$ 0.5 $\pm 0.20$     3.0

$\quad \text{tol}_1 =0.4, \text{tol}_2 =1.6$     $61.86$ 0.5 $\pm 5.29$     $51.15$ 0.5 $\pm 0.82$     6.0         $34.11$ 0.5 $\pm 6.35$     $21.04$ 0.5 $\pm 2.21$     5.0

$\quad \text{tol}_1 =0.4, \text{tol}_2 =0.8$     $60.42$ 0.5 $\pm 0.31$     $41.59$ 0.5 $\pm 2.14$     8.0         $36.23$ 0.5 $\pm 3.58$     $16.03$ 0.5 $\pm 2.69$     6.0

$\quad \text{tol}_1 =0.2, \text{tol}_2 =0.8$     $49.14$ 0.5 $\pm 6.11$     $49.88$ 0.5 $\pm 4.21$     3.0         $34.20$ 0.5 $\pm 7.13$     $26.42$ 0.5 $\pm 0.73$     2.5

$\quad \alpha^{*} (0) =0.85$                     $77.73$ 0.5 $\pm 0.47$     $52.03$ 0.5 $\pm 0.10$     100.0       $49.71$ 0.5 $\pm 0.55$     $28.55$ 0.5 $\pm 0.03$     100.0

$\quad \alpha^{*} (0) =0.98$                     $63.69$ 0.5 $\pm 3.58$     $54.02$ 0.5 $\pm 1.11$     81.5        $45.72$ 0.5 $\pm 1.10$     $28.45$ 0.5 $\pm 0.82$     70.0

$\quad \tau=0.00$                                $48.55$ 0.5 $\pm 0.95$     $51.25$ 0.5 $\pm 1.16$     1.5         $24.50$ 0.5 $\pm 0.03$     $25.70$ 0.5 $\pm 1.51$     1.0

$\quad \tau=0.05$                                $57.84$ 0.5 $\pm 2.26$     $50.42$ 0.5 $\pm 0.97$     20.5        $26.24$ 0.5 $\pm 1.46$     $26.60$ 0.5 $\pm 1.17$     4.0

$\quad \tau=0.10$                                $72.91$ 0.5 $\pm 2.25$     $47.84$ 0.5 $\pm 2.60$     59.0        $67.67$ 0.5 $\pm 1.68$     $9.89$ 0.5 $\pm 0.45$      86.0

$\quad \tau=0.15$                                $77.19$ 0.5 $\pm 2.31$     $41.49$ 0.5 $\pm 0.97$     92.0        $70.13$ 0.5 $\pm 0.27$     $7.77$ 0.5 $\pm 0.23$      94.0

$\rho=0.1$                                 $85.30$ 0.5 $\pm 1.05$     $45.20$ 0.5 $\pm 0.28$     $47.0$      $58.61$ 0.5 $\pm 4.14$     $18.29$ 0.5 $\pm 2.38$     $35.5$

$\rho=0.3$                                 $80.34$ 0.5 $\pm 1.33$     $48.25$ 0.5 $\pm 2.72$     20.5        $44.65$ 0.5 $\pm 0.35$     $21.73$ 0.5 $\pm 1.27$     12.0

$\rho=0.05$                                $80.31$ 0.5 $\pm 1.60$     $53.62$ 0.5 $\pm 4.36$     $18.5$      $62.19$ 0.5 $\pm 1.54$     $21.15$ 0.5 $\pm 0.88$     $44.5$

$\rho=0.1$                                 $82.89$ 0.5 $\pm 0.92$     $56.27$ 0.5 $\pm 1.08$     26.5        $59.08$ 0.5 $\pm 0.06$     $21.29$ 0.5 $\pm 0.87$     31.5

$\rho=0.3$                                 $80.72$ 0.5 $\pm 1.90$     $55.77$ 0.5 $\pm 1.93$     10.0        $49.84$ 0.5 $\pm 6.85$     $28.62$ 0.5 $\pm 0.78$     11.0

$\rho=0.05$                                $68.48$ 0.5 $\pm 0.25$     $66.77$ 0.5 $\pm 0.28$     9.5         $38.75$ 0.5 $\pm 0.98$     $30.45$ 0.5 $\pm 0.07$     10.0

$\rho=0.1$                                 $68.56$ 0.5 $\pm 3.56$     $65.75$ 0.5 $\pm 5.40$     6.0         $40.30$ 0.5 $\pm 1.19$     $30.23$ 0.5 $\pm 0.85$     11.0

$\rho=0.3$                                 $70.86$ 0.5 $\pm 0.31$     $70.13$ 0.5 $\pm 0.42$     5.5         $39.62$ 0.5 $\pm 0.34$     $32.22$ 0.5 $\pm 0.20$     5.0

Ablation studies on techniques in Sec <ref>. We evaluated algorithm performance on CIFAR10 and CIFAR100 datasets, showcasing the top Validation and Test accuracies for each. We kept $\rho = 0.3$ consistent across all algorithms and varied $\tilde{\mu}$ to adjust the penalty term's strength in the objective function. The best results in each block are highlighted.

2*Algorithm     2cCIFAR10, $\beta = 0.2$                2cCIFAR10, $\beta = 0.4$                2cCIFAR100, $\beta = 0.2$               2cCIFAR100, $\beta = 0.4$

(lr)2-3 (lr)4-5 (lr)6-7 (lr)8-9
Val                                                       Test                                                      Val                                                       Test                                                      Val                                                       Test                                                      Val                                                       Test

$\tilde{\mu} = 0.0$      $\mathbf{83.67}$ 0.5 $\pm 0.72$     $\mathbf{62.43}$ 0.5 $\pm 0.71$     $\mathbf{80.72}$ 0.5 $\pm 1.90$     $\mathbf{55.77}$ 0.5 $\pm 1.93$     $\mathbf{50.72}$ 0.5 $\pm 2.97$     $\mathbf{32.13}$ 0.5 $\pm 0.18$     $\mathbf{49.84}$ 0.5 $\pm 6.85$     $\mathbf{28.62}$ 0.5 $\pm 0.78$

$\tilde{\mu} = 0.1$      $81.60$ 0.5 $\pm 0.59$              $60.48$ 0.5 $\pm 0.50$              $80.36$ 0.5 $\pm 2.40$              $55.10$ 0.5 $\pm 1.75$              $48.78$ 0.5 $\pm 0.62$              $30.50$ 0.5 $\pm 0.33$              $48.56$ 0.5 $\pm 1.10$              $25.80$ 0.5 $\pm 1.17$

$\tilde{\mu} = 0.4$      $79.52$ 0.5 $\pm 0.11$              $53.33$ 0.5 $\pm 2.97$              $76.50$ 0.5 $\pm 0.34$              $49.97$ 0.5 $\pm 2.26$              $44.85$ 0.5 $\pm 0.48$              $28.39$ 0.5 $\pm 0.12$              $41.52$ 0.5 $\pm 0.08$              $22.83$ 0.5 $\pm 0.42$

$\tilde{\mu} = 0.0$      $\mathbf{70.82}$ 0.5 $\pm 0.25$     $69.15$ 0.5 $\pm 0.35$              $69.95$ 0.5 $\pm 1.99$              $67.09$ 0.5 $\pm 1.01$              $39.55$ 0.5 $\pm 1.29$              $35.49$ 0.5 $\pm 0.16$              $38.77$ 0.5 $\pm 1.20$              $31.87$ 0.5 $\pm 1.13$

$\tilde{\mu} = 0.1$      $69.91$ 0.5 $\pm 0.16$              $68.77$ 0.5 $\pm 1.56$              $69.53$ 0.5 $\pm 0.21$              $68.54$ 0.5 $\pm 1.08$              $39.38$ 0.5 $\pm 0.40$              $35.95$ 0.5 $\pm 0.59$              $\mathbf{39.77}$ 0.5 $\pm 2.33$     $31.52$ 0.5 $\pm 0.45$

$\tilde{\mu} = 0.4$      $69.33$ 0.5 $\pm 0.24$              $\mathbf{69.67}$ 0.5 $\pm 1.27$     $\mathbf{70.86}$ 0.5 $\pm 0.31$     $\mathbf{70.13}$ 0.5 $\pm 0.42$     $\mathbf{39.97}$ 0.5 $\pm 0.21$     $\mathbf{36.50}$ 0.5 $\pm 0.28$     $39.62$ 0.5 $\pm 0.34$              $\mathbf{32.22}$ 0.5 $\pm 0.20$

Ablation studies on techniques in Sec <ref>. We evaluated algorithm performance on CIFAR10 and CIFAR100 datasets, displaying their highest Validation and Test accuracies. We kept $\rho$ consistent at 0.3 for all algorithms. "w/ SCWU" denotes the use of soft clustering weight updating mechanisms designed in Section <ref>.

2*Algorithm     2cCIFAR10, $\beta = 0.2$                2cCIFAR10, $\beta = 0.4$                2cCIFAR100, $\beta = 0.2$               2cCIFAR100, $\beta = 0.4$

(lr)2-3 (lr)4-5 (lr)6-7 (lr)8-9
Val                                                       Test                                                      Val                                                       Test                                                      Val                                                       Test                                                      Val                                                       Test

w/ SCWU                  $\mathbf{83.67}$ 0.5 $\pm 0.72$     $62.43$ 0.5 $\pm 0.71$              $\mathbf{80.72}$ 0.5 $\pm 1.90$     $55.77$ 0.5 $\pm 1.93$              $\mathbf{50.72}$ 0.5 $\pm 2.97$     $32.13$ 0.5 $\pm 0.18$              $\mathbf{49.84}$ 0.5 $\pm 6.85$     $28.62$ 0.5 $\pm 0.78$

w/o SCWU                 $82.11$ 0.5 $\pm 2.39$              $63.84$ 0.5 $\pm 0.19$              $80.08$ 0.5 $\pm 0.99$              $58.83$ 0.5 $\pm 2.12$              $49.77$ 0.5 $\pm 1.93$              $32.90$ 0.5 $\pm 1.11$              $47.91$ 0.5 $\pm 2.67$              $27.40$ 0.5 $\pm 1.17$

w/ SCWU                  $69.33$ 0.5 $\pm 0.24$              $\mathbf{69.67}$ 0.5 $\pm 1.27$     $70.86$ 0.5 $\pm 0.31$              $\mathbf{70.13}$ 0.5 $\pm 0.42$     $39.97$ 0.5 $\pm 0.21$              $\mathbf{36.50}$ 0.5 $\pm 0.28$     $39.62$ 0.5 $\pm 0.34$              $\mathbf{32.22}$ 0.5 $\pm 0.20$

w/o SCWU                 $69.88$ 0.5 $\pm 0.30$              $68.83$ 0.5 $\pm 0.71$              $70.77$ 0.5 $\pm 0.47$              $68.87$ 0.5 $\pm 0.23$              $40.96$ 0.5 $\pm 1.24$              $35.72$ 0.5 $\pm 1.01$              $39.18$ 0.5 $\pm 0.13$              $32.08$ 0.5 $\pm 0.78$

Performance of algorithms with Resnet18. We evaluated algorithm performance on CIFAR10 datasets with $\beta = 0.2$, displaying their highest Validation and Test accuracies. All algorithms utilize ResNet18 and run for 200 communication rounds.

Algorithm                                          Val                                              Test

$\text{tol}_1 = 0.4, \text{tol}_2 = 0.6$     $63.07$ 0.5 $\pm 7.42$     $53.65$ 0.5 $\pm 2.33$

$\text{tol}_1 = 0.4, \text{tol}_2 = 0.8$     $61.14$ 0.5 $\pm 1.87$     $54.87$ 0.5 $\pm 1.32$

$\alpha^{*}(0) = 0.85$                       $80.46$ 0.5 $\pm 0.99$     $45.28$ 0.5 $\pm 6.56$

$\alpha^{*}(0) = 0.98$                       $82.34$ 0.5 $\pm 0.28$     $44.08$ 0.5 $\pm 0.40$

$\tau = 0.1$                                 $57.41$ 0.5 $\pm 6.69$     $48.95$ 0.5 $\pm 1.95$

$\tau = 0.15$                                $66.54$ 0.5 $\pm 1.05$     $47.77$ 0.5 $\pm 0.14$

$\rho = 0.05$                                $86.90$ 0.5 $\pm 0.20$     $50.34$ 0.5 $\pm 5.99$

$\rho = 0.1$                                 $85.55$ 0.5 $\pm 0.24$     $49.38$ 0.5 $\pm 6.15$

$\rho = 0.05$                                $83.88$ 0.5 $\pm 0.25$     $58.92$ 0.5 $\pm 1.11$

$\rho = 0.1$                                 $83.83$ 0.5 $\pm 0.01$     $60.27$ 0.5 $\pm 3.11$

$\rho = 0.05$                                $67.72$ 0.5 $\pm 1.30$     $64.13$ 0.5 $\pm 0.37$

$\rho = 0.1$                                 $67.51$ 0.5 $\pm 0.24$     $63.15$ 0.5 $\pm 0.78$