# FedCO: Communication-Efficient Federated Learning via Clustering Optimization +
## 4 Proposed Approach
The Server aggregates the received local models \(\{\mathcal{M}_{t+1}^{i}\mid w_{i}\in W_{t+1}\}\) uploaded by the representatives to update the global model through the FedAvg algorithm; i.e., an updated global model \(\mathcal{M}_{t+1}\) is produced (Equation (2)) (line 16 in Algorithm 1). 5. The Server adapts \(C_{t}\) to the newly arrived local updates by conducting the following operations: 1. SI invokes the Silhoutite function (lines 17, 23-37 in Algorithm 1), which assesses whether each representative \(w_{i}\in W_{t+1}\) is still adequately tight with its current cluster (Equation (6)). The updated clustering \(C_{t+1}\) of \(W_{t}\) is produced, and the clusters in \(C_{t+1}\) may contains a set of workers different from \(C_{t}\). Note that \(k_{(t+1)}\geq k_{t}\), where \(k_{(t+1)}=\mid C_{t+1}\mid\), since new singleton clusters may appear due to the updating operation. This happens when the Silhouette coefficient \(s(w_{i})\) of a representative for all clusters gives a negative value (lines 28-30 in Algorithm 1), which means that this representative cannot be assigned to any existing cluster. Hence, this representative could be considered as a new cluster with a single item (singleton). If there is a cluster \(C_{(t+1)j}\in C_{t+1}\), such that \(C_{(t+1)j}=\emptyset\), then \(C_{t+1}=C_{t+1}\setminus\{C_{(t+1)j}\}\), and therefore, \(\mid C_{t+1}\mid<\mid C_{t}\mid\). This condition/event triggers the optimization of the number of clusters by invoking the ClusterOptimization function (lines 18-20 in Algorithm 1). This operation is repeated for each empty cluster of \(C_{t+1}\). A schematic illustration (flowchart) of the overall processes of the proposed FedCO algorithm is given in Figure 2.

Figure 2: A schematic illustration of the entire process of the FedCO algorithm in two global communication rounds: Initialization Phase and Iteration Phase. ### Cluster Optimization

The ClusterOptimization algorithm works in what follows (cf. Algorithm 2):

1. Firstly, the SI score of the whole clustering solution \(C_{t+1}\) is computed. This score is used to check whether the splitting operation really improves the quality of the clustering solution (line 2 in Algorithm 2). 2. Then, the SI score is calculated for each cluster \(C_{(t+1)j}\in C_{t+1}\), such that \(\mid C_{(t+1)j}\mid>1\) using Equation (8). If \(s(C_{(t+1)j})<0\), then this cluster is a candidate to be split into two clusters, and the following operations are performed (lines 4-6 in Algorithm 2): 1. The two most distant points in the cluster \(C_{(t+1)j}\) are found. They are used to seed 2-medoids clustering, which is applied to split the cluster \(C_{(t+1)j}\) into two clusters (function KMEDoids at line 7 in Algorithm 2). 2. The clustering solution \(C_{t+1}\) is updated by replacing cluster \(C_{(t+1)j}\) with the two clusters obtained due to the splitting operation (line 8 in Algorithm 2), and stored in the set \(C_{t+1}\). 3. The SI score of the updated clustering solution \(C_{t+1}\) is computed (line 9 in Algorithm 2 (7)). 4. If the SI score of the new clustering solution \(C_{t+1}\) is higher than the one before splitting, the new clustering solution is adopted and stored in the set \(C_{t+1}^{\prime}\); otherwise, the clustering solution \(C_{t+1}\) is kept (lines 10-13 in Algorithm 2). Steps 1-5 of the _iteration_ phase are repeated until a certain number of training rounds \(T\) is reached. Figure 3 shows a flowchart depicting the cluster optimization algorithm in a single round of communication. The proposed FedCO implementation, at each training round, always selects the top performing representative; i.e., the size of the clusters is not reflected in the aggregated global model, and the size of the cluster does not impact the selection/importance of the representative. The FedCO design, however, allows from each cluster the selection of several top-ranked representatives, i.e., more than one, proportionally to the cluster size. In that way, the bigger clusters will have more weight in the building of the global model.