# Towards Effective Clustered Federated Learning: A Peer-to-peer Framework
with Adaptive Neighbor Matching

Zexi Li, Jiaxun Lu, Shuang Luo, Didi Zhu, Yunfeng Shao, Yinchuan Li, Zhimeng
Zhang, Yongheng Wang, and Chao Wu Zexi Li and Didi Zhu are with the College of
Computer Science and Technology, Zhejiang University, Hangzhou, China. E-mail:
{zexi.li<EMAIL_ADDRESS>Jiaxun Lu, Yunfeng Shao and Yinchuan Li are
with Huawei Noah’s Ark Lab, Beijing, China. E-mail: {lujiaxun, shaoyunfeng,
<EMAIL_ADDRESS>Chao Wu and Shuang Luo are with the School of Public
Affairs, Zhejiang University, Hangzhou, China. E-mail: {luoshuang,
<EMAIL_ADDRESS>Zhimeng Zhang is with the School of Software Technology,
Zhejiang University, Hangzhou, China. E-mail<EMAIL_ADDRESS>Yongheng
Wang is with the Big Data Intelligence Research Center, Zhejiang Lab,
Hangzhou, China. E-mail<EMAIL_ADDRESS>Corresponding Author: Chao Wu
and Yongheng Wang.

###### Abstract

In federated learning (FL), clients may have diverse objectives, and merging
all clients’ knowledge into one global model will cause negative transfer to
local performance. Thus, clustered FL is proposed to group similar clients
into clusters and maintain several global models. In the literature,
centralized clustered FL algorithms require the assumption of the number of
clusters and hence are not effective enough to explore the latent
relationships among clients. In this paper, without assuming the number of
clusters, we propose a peer-to-peer (P2P) FL algorithm named PANM. In PANM,
clients communicate with peers to adaptively form an effective clustered
topology. Specifically, we present two novel metrics for measuring client
similarity and a two-stage neighbor matching algorithm based Monte Carlo
method and Expectation Maximization under the Gaussian Mixture Model
assumption. We have conducted theoretical analyses of PANM on the probability
of neighbor estimation and the error gap to the clustered optimum. We have
also implemented extensive experiments under both synthetic and real-world
clustered heterogeneity. Theoretical analysis and empirical experiments show
that the proposed algorithm is superior to the P2P FL counterparts, and it
achieves better performance than the centralized cluster FL method. PANM is
effective even under extremely low communication budgets.

###### Index Terms:

Federated learning, peer-to-peer communication, distributed learning,
clustered federated learning.

##  1 Introduction

The proliferation of smart devices such as mobile phones, cameras, and sensors
has dramatically expanded the perception of edge intelligence, increasingly
forming an Internet of Things (IoT) network [1, 2, 3]. The massive data from
edge devices is key in generating powerful predictive models to provide better
services to users. However, transferring the edge data to the data server
poses a high privacy risk and high communication traffic burden, which renders
the traditional centralized training ineffective. Therefore, Federated
Learning (FL) [4, 5, 6, 7] is proposed to facilitate collaborative training
among edge clients without transferring the data to the cloud server. FL
guarantees user privacy, reduces communication latency, and enhances learning
performance, and it has broad and promising applications in IoT systems [2,
3].

In the real-world practice of FL, heterogeneity is an inherent problem (i.e.
the Non-IID problem) since clients may have heterogeneous data distributions
and thus diverse optimization objectives (learning tasks) [8]. Clustered
heterogeneity is prevalent in users’ data, which means that a small group of
clients has similar data distributions while there is dominant inconsistency
among different groups. It is very common in applications such as
recommendation systems [9, 10]. Therefore, clustered FL methods [11, 12, 13,
14] are proposed for better personalization by grouping clients into clusters
and maintaining a global model in each cluster. The main challenge of
clustered heterogeneity is that the latent similarity relationship among
clients is unknown. Existing clustered FL researches adopt the conventional
server-client communication pattern and estimate clients’ cluster identities
by iterative [11] or hierarchical [13] methods. These centralized clustered FL
methods highly rely on the assumed number of clusters or the assumed
hierarchical level. However, in the real-world environment, the clustered
relationship is latent, and it is impossible to know the number of clusters as
prior knowledge. Inappropriate estimations of clusters’ numbers will cause bad
convergence. Besides, other concerns, like the reliability and communication
bandwidth issues [15], brought by the central server, also hinder the
performance of these centralized clustered FL methods.

To address these challenges, in this paper, we transform the client clustering
problem into a binary classification problem from a peer-to-peer (P2P)
perspective. Under P2P communication, each client decides whether to accept an
accessible client as its neighbor based on local similarity measurement.
Clients will select the most similar peers as their neighbors to realize
personalization. Once the neighbor estimation is established, a clustered
communication topology will be inherently built without assuming the number of
clusters. Our method is named as Personalized Adaptive Neighbour Matching
(PANM) and it is proved to be effective and robust in various clustered
heterogeneity.

In addition to the advantages compared with centralized clustered FL, PANM has
superior performance over P2P FL counterparts. In previous works, most P2P FL
algorithms assume random or fixed communication topologies [16, 17] and they
focus on reaching the global consensus by optimization techniques [18, 19].
But in clustered heterogeneity, the global consensus does not exist, and
random or fixed communications will harm personalization and decrease the
accuracy. On the contrary, our method achieves partial group consensus by
realizing the adaptive topology.

Our main contributions are as follows.

  * •

We propose two efficient, effective, and privacy-preserving metrics to
evaluate the pair-wise similarity of client objectives in P2P FL. They are
based on losses and gradients, respectively.

  * •

We present PANM, a novel clustered FL algorithm based on P2P communication.
PANM enables clients to match neighbors with consistent objectives (same
cluster identity), improving local performance.

  * •

We devise two stages in PANM, the first is neighbor selection based on Monte
Carlo, and the second is neighbor augmentation based on Gaussian Mixture
Model. We provide theoretical guarantees of PANM.

  * •

We conduct extensive experiments on different datasets, Non-IID degrees, and
network settings under both synthetic and real-world clustered heterogeneity.
It is shown that PANM outperforms all P2P baselines, including Oracle that has
the prior knowledge of cluster identities. Compared with centralized clustered
FL algorithms, PANM is more effective in exploring latent cluster structure
and has better performance.

The rest of this paper is organized as follows. Section 2 reviews related
works in clustered FL and P2P FL. Section 3 provides basic formulation about
P2P clustered FL. Section 4 elaborates the technical details of PANM,
including the two metrics for measuring client similarity and the two-stage
neighbor matching algorithm. Theoretical analysis is also included in Section
4. Section 5 presents the experimental results. Sections 6 and 7 provide
further discussions and the conclusion of this paper.

##  2 Related Works

Clustered Federated Learning. Clustered FL holds the Non-IID assumption that
different groups of clients have their own optimization objectives, and it is
usually used to realize better accuracy performance [11, 13] or better
compression of model updates [20, 21]. In this paper, we focus on the
effectiveness of clustered FL on test accuracy, especially local
personalization. In personalized clustered FL [11, 13], aggregating models in
the same cluster will bring better personalization while aggregation among
different clusters will cause negative transfer111In some works, it is found
that generalized knowledge can be transferred among cluster centroids [22,
14]. However, this only happens when the clustered heterogeneity is not
dominant. In this paper, we focus on more heterogeneous clustered FL, where
negative transfer exists among different clusters..

To group clients into clusters, the main challenge of clustered FL is
measuring client similarity. There are mainly three types of measurement,
based on losses[11], gradients [13, 23, 14], model weights [13, 22, 12, 24],
respectively. In loss-based measurement, clients receive several models and
infer them on the local dataset, and the one with the smallest loss has
maximal similarity [11]. For model weight and gradient measurement, cosine
distance [13, 12] or Euclidean distance [24, 22, 12] are used in previous
works. It is verified that clients with similar data distributions will have
small Euclidean distances and large cosine similarities in gradients or model
weights.

The methods for clustering in previous works can be divided into two streams,
the K-means-based and the hierarchical. For the K-means-based approaches,
FedSEM [12] first implements the K-means method based on clients’ Euclidean
distances of model weights on the server to cluster clients. However, server-
side K-means clustering is computationally expensive. To solve this issue,
Duan et al. [23, 14] use decomposed cosine similarity to speed up computation
and design an efficient newcomer device cold start mechanism. Additionally,
Ghosh et al.[11] propose an efficient algorithm IFCA by inherently applying
K-means to the client side. IFCA keeps several global models, and clients
iteratively choose which global model it is prone to contribute to based on
local losses of global models. In another stream of works, hierarchical
clustering methods are used to achieve better personalization. Sattler et al.
[13] use a hierarchical optimal bi-partitioning algorithm based on cosine
similarity of weights or gradients. By bi-partitioning, the method realizes a
model tree from personalization to generalization. Further, Briggs et al. [24]
design a hierarchical algorithm for a wider range of Non-IID settings, and the
method separates clusters of clients by the similarity of their local models
to the global model. Additionally, Dem-AI is developed for building large-
scale distributed and democratized machine learning systems [22], and it
realizes a bottom-up hierarchical clustering with specialized–generalized
duality.

Note that all the algorithms mentioned above in clustered FL rely on the
assumption of the number of clusters (the K-means-based methods) or the level
of hierarchy (the hierarchical techniques). However, the number of clusters is
latent and cannot be obtained as prior knowledge, and if the hyperparameters
are set inappropriately, the clustering performance will degrade.

Peer-to-peer Federated Learning. Peer-to-peer federated learning (P2P FL, also
known as decentralized FL) alters the centralized topology of conventional FL,
and it allows clients to communicate with limited neighbors [25, 16]. There is
a study comparing decentralized algorithms like gossip learning with
centralized FL in terms of communication efficiency. It is found that the best
gossip variants perform comparably to the best centralized FL algorithms
overall [26]. Early works related to P2P FL introduce the P2P FL problem under
privacy constraints and provide theoretical guarantees. Lalitha et al. [16,
17] use a Bayesian-like approach to let clients collectively learn a model
that best fits the observations over the entire network. Bellet et al. [27]
make P2P FL differentially private and analyze the trade-off between utility
and privacy. They mainly study P2P FL under the IID data assumption, but
heterogeneity is prevalent in FL practices.

Recent works mostly discuss class imbalance heterogeneity and communication
problems. First, to tackle class imbalance, Li et al. [28] use mutual
knowledge distillation instead of weight averaging. Bellet et al. [29]
elaborately design a topology from holistic perspective. However, without a
central server, the holistic perspective is impractical, and it is hard for
clients to form such topology with limited observations. Second, communication
of P2P FL can be more efficient by sparsification [30], adaptive partial
gradient aggregation [31], and using max-plus linear system theory to compute
throughput [32]. Most recently, swarm learning [25] has been brought up as a
P2P FL customized for medical research, utilizing edge computing and
blockchain as infrastructures, and it has attracted wide attention. It
provides strong application practices of P2P FL.

While we are formulating this paper, we find a related same-time work (PENS)
that has the same motivation as ours but uses different methods [33]. PENS
adopts a two-stage strategy. In the first stage, clients select top $k$ peers
as neighbors for aggregation from randomly sampled $l$ neighbor candidates in
each round. After the first stage, clients select the peers that were selected
from as neighbors more than “the expected amount of times” in the first stage
as permanent neighbors. In the second stage, in each round, clients randomly
choose $k$ neighbors for aggregation from permanent neighbors. It is possible
for PENS to have noisy neighbor estimations, and we analyze the superiority of
PANM to PENS in Section 4 and 5.

TABLE I: Important notations in this paper. Notation | Meaning
---|---
n | Number of all clients
r | Number of clusters
a | Number of clients within a cluster
d | Number of data samples in a client
c |  Assumed number of clusters in IFCA [11]
k | Size of aggregation neighbor list
l | Size of neighbor candidate list
$\tau$ |  Round interval of NAEM in the second stage
$\alpha$ | Hyperparameter in the gradient-based metric
${\rm N}_{i}^{t}$ |  Neighbor list of client i in round t
${\rm B}_{i}^{t}$ |  Neighbor bag of client i in round t
${\rm C}_{i}^{t}$ |  Neighbor candidate list of client i in round t
${\rm S}_{i}^{t}$ | Selected neighbors in EM-step
${\rm M}_{i}^{t}$ |  Union set of ${\rm C}_{i}^{t}$ and ${\rm S}_{i}^{t}$
${\rm H}_{i}^{t}$ |  Neighbor estimation list in EM-step of client i

##  3 Problem Formulation

We first set up the clustered heterogeneity following previous works [11].
There are $r$ different data distributions (clusters),
$\mathcal{D}^{1},\dots,\mathcal{D}^{r}$, and that the $n$ clients are
partitioned into $r$ disjoint clusters. It is assumed that every client $i\
(i\in[n])$ which belongs to cluster $j\ (j\in[r])$ contains IID data samples
$\mathcal{D}_{i}$ drawn from $\mathcal{D}^{j}$. For simplicity, we assume
every client has the same number of samples that $\forall
i,j\in[n],|\mathcal{D}_{i}|=|\mathcal{D}_{j}|=d$.

We solve clustered FL by forming it into a personalized P2P FL problem, in
which we learn the personalized models
$\mathbf{w}=(\mathbf{w}_{1},\dots,\mathbf{w}_{n})$ and the neighbor graph
matrix G. The expression is borrowed from personalized decentralized joint
learning [17], and the key difference is that we set binary elements instead
of continuous elements in G, because in clustered heterogeneity, the task is
to form a neighbor graph where the same-cluster clients should be connected
(set as 1) while the different-cluster should be disconnected (set as 0). The
neighbor graph matrix G is an $n\times n$ square matrix, $G_{i,j}$ refers to
the $(i,j).$th entry of the matrix, and it indicates whether client $j$ is in
the neighbor bag of client $i$, 1 for true and 0 for false. The diagonal
elements $G_{i,i}$ are all set to 1. To optimize $\mathbf{w}$ and G, the joint
optimization objective is

$\begin{split}\min_{\mathbf{w}\in(\mathbb{R}^{d})^{n}\atop\textbf{G}\in\mathbb{R}^{n\times
n}}J(\mathbf{w},\textbf{G})&=\sum_{i=1}^{n}F_{i}(\mathbf{w}_{i})+\frac{\nu}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}G_{i,j}\|\mathbf{w}_{i}-\mathbf{w}_{j}\|^{2},\\\
&s.t.\quad g(\textbf{G})=0.\end{split}$ (1)

There are two terms in this objective function. The first one is the sum of
loss functions, each involving the personalized model and the local dataset.
$F_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is the loss function of client $i\
(i\in[n])$ on its local dataset, given by:
$F_{i}(\mathbf{w}_{i})\coloneqq\mathbb{E}_{\xi_{i}\sim\mathcal{D}_{i}}\left[f(\mathbf{w}_{i},\xi_{i})\right]$,
where $\xi_{i}\sim\mathcal{D}_{i}$ denotes a random sample drawn from the
local dataset, $\mathbb{E}(\cdot)$ means expectation, and
$f(\mathbf{w}_{i},\xi_{i})$ refers to the loss function of $\mathbf{w}_{i}$ on
a sample $\xi_{i}$. The second term enables collaboration by encouraging two
clients to have a similar model if they are in neighborhood relationship. The
condition $g(\textbf{G})=0$ regularizes the graph matrix regarding the network
topology. For instance, the matrix should have diagonal vector to be
$\mathbf{1}$ and the Frobenius norm222The Frobenius norm of G indicates the
number of connections in the graph. should be assigned to meet the network
setup. Other functions that regularize the degree of each node, both in-degree
and out-degree, can also be integrated in $g(\textbf{G})$. In this paper, we
solve the objective in Equation 1 by adaptively matching neighbors.

We then introduce the model update protocol in P2P FL. In P2P FL, each client
$i$ first updates its local model by local training and receives models from
the neighbors. Then it averages the neighbors’ models together with its local
model into a new one and starts a next-round training. The process of one
communication round in P2P FL can be formulated into the following:

$\mathbf{w}_{i}^{t+1}=\mathbf{w}_{i}^{t}-\eta\nabla
F_{i}\left(\mathbf{w}_{i}^{t}\right)+\sum_{j\in{\rm
N}_{i}^{t}}\left(\mathbf{w}_{j}^{t}-\eta\nabla
F_{j}\left(\mathbf{w}_{j}^{t}\right)\right).$ (2)

${\rm N}_{i}^{t}$ is the round $t$’s aggregation neighbors of client $i$,
randomly sampled from the neighbor bag ${\rm B}_{i}^{t},({\rm
N}_{i}^{t}\subseteq{\rm B}_{i}^{t},|{\rm N}_{i}^{t}|=k,|{\rm
B}_{i}^{t}|=m,k\leqslant m)$. The neighbor bag of client $i$ is defined as the
set of indexes $j$ where $G_{i,j}=1,i\neq j$, as ${\rm
B}_{i}^{t}=\\{j:G_{i,j}=1;j\in[n],j\neq i\\}$. The process that aggregating
with random sampled peers from the neighbor bag is known as random gossip
communication [33, 26]. In previous P2P FL works, the neighbor bag for each
client includes all the remaining peers, but in clustered heterogeneity, such
communication is noisy. In PANM, we keep the neighbor bag small but pure in
the first stage and augment the neighbor bag in the second stage.

To improve readability, we summarize our main notations mentioned before or
soon later as in Table I.

Figure 1: Schematic diagram of optimization paths in centralized FL (a) and
P2P FL (b), respectively. In the figure, objective of client a is similar with
client b and dissimilar with client c.

##  4 Method

In this section, we will present two metrics for client similarity measurement
in Section 4.1, neighbor selection based on Monte Carlo (first stage of PANM)
in Section 4.2, and neighbor augmentation based on EM-GMM in Section 4.3
(second stage of PANM). Then we will combine the similarity metrics, neighbor
selection, and neighbor augmentation to devise PANM in Section 4.4. Lastly, we
will provide theoretical analysis in 4.5.

###  4.1 Metrics for Measuring Client Similarity

Metrics for measuring the consistency of optimization objectives are needed to
enable clients to select same-cluster peers and filter out outliers. However,
due to privacy concerns, in FL, we cannot use data distance measurements like
maximum mean discrepancy distance [34], since sharing data is forbidden. Loss
evaluation is a simple metric, commonly used in the literature [11, 33]. In
P2P FL, client $i$ receives client $j$’s model and infers the model on its
local dataset. If the loss is small, it means client $j$ has a similar
learning task with client $i$. We can use the reciprocal of loss as the
similarity so that smaller loss indicates higher similarity, as

${\rm s}_{i,j}=1/F_{i}(\mathbf{w}_{j}^{t}),$ (3)

where ${\rm s}_{i,j}$ is the similarity between client $i$ and $j$ and
$F_{i}(\mathbf{w}_{j}^{t})$ is the loss value of client $j$’s model validated
on client $i$’s local dataset. Since this metric is simple, we adopt this
metric in our PANM, named as PANMLoss.

However, calculating loss value is computation-consuming because it requires
inferring models on the training dataset. Moreover, local data may not be
available for extra computation. Hence, we develop a more efficient metric
based on gradients and accumulated weight updates.

In centralized clustered FL, Sattler et al. [13] use the cosine similarity of
gradients to measure the consistency of optimization objectives, the function
can be formulated as

${\rm
cos}~{}\theta_{i,j}^{1}=\frac{\langle\textbf{g}_{i}^{t},\textbf{g}_{j}^{t}\rangle}{\|\textbf{g}_{i}^{t}\|\cdot\|\textbf{g}_{j}^{t}\|}.$
(4)

In Equation 4,
$\textbf{g}_{i}^{t}=\mathbf{w}_{i}^{t}-\mathbf{w}_{i}^{t-1},\textbf{g}_{j}^{t}=\mathbf{w}_{j}^{t}-\mathbf{w}_{j}^{t-1}$.
$\textbf{g}_{i}^{t}$ is the vectorized gradient of client $i$ in round $t$.
$\textbf{g}_{i}^{t}$ and $\textbf{g}_{j}^{t}$ have $e$ dimensions, and $e$ is
usually large in neural networks. ${\rm cos}~{}\theta_{i,j}^{1}$ is the cosine
function of the two gradient vectors, where $\theta_{i,j}^{1}$ refers to the
angle of two vectors in the high-dimensional space. In centralized FL, models
are initialized as the same global model at the beginning of local training in
each round that $\mathbf{w}_{i}^{t-1}=\mathbf{w}_{j}^{t-1}=\mathbf{w}^{t-1}$,
so the cosine function of gradients can effectively imply the consistency. We
draw a 2-dimensional toy example to intuitively show the optimization
trajectories and the angles of vectorized updates in Figure 1. The trajectory
of centralized FL is shown in (a) of Figure 1. Although in P2P FL, client
model weights diverge since the first round, the measurement of gradients will
be noisy. The angle of gradients in P2P FL is shown as $\theta^{1}$ in (b) of
Figure 1.

To solve this issue, we notice the accumulated weight updates from the initial
model can signify the history optimization directions, and the cosine
similarity of the weight updates can also imply the consistency of objectives.

${\rm
cos}~{}\theta_{i,j}^{2}=\frac{\langle\textbf{h}_{i}^{t},\textbf{h}_{j}^{t}\rangle}{\|\textbf{h}_{i}^{t}\|\cdot\|\textbf{h}_{j}^{t}\|},$
(5)

where
$\textbf{h}_{i}^{t}=\mathbf{w}_{i}^{t}-\mathbf{w}_{0},\textbf{h}_{j}^{t}=\mathbf{w}_{j}^{t}-\mathbf{w}_{0}$.
$\textbf{h}_{i}^{t}$ is the vectorized accumulated weight updates of client
$i$ from the initial model to the model in round $t$. Analogical to
$\theta_{i,j}^{1}$, $\theta_{i,j}^{2}$ is the angle of two vectorized
accumulated updates in the $e$-dimensional space, and we show $\theta^{2}$ in
(b) of Figure 1.

According to Equations 4 and 5, we combine the cosine functions of
$\theta^{1}$ and $\theta^{2}$ to formulate our new metric as

${\rm s}_{i,j}=\alpha\cos\theta_{i,j}^{1}+(1-\alpha)\cos\theta_{i,j}^{2},$ (6)

where $\alpha$ is the hyperparameter controlling the weight of two cosine
functions, $\alpha\in[0,1]$, we adopt the metric in Equation 6 in PANM,
notated as PANMGrad. We note that $\cos\theta_{i,j}^{1}$ has the same range as
$\cos\theta_{i,j}^{2}$, which is $[-1,1]$, so the outputs of two functions
will have similar volumes. Thus, it is appropriate to set $\alpha$ around 0.5.
Additionally, we notice that larger $\alpha$ will be beneficial when the P2P
network is more densely connected. In a denser network, the clients’ models
are more synchronized, and it is more similar to the centralized FL,
therefore, $\cos\theta_{i,j}^{1}$ will be more effective. Conversely, when the
network is sparse, smaller $\alpha$ will help.

Figure 2: Ablation study of PANMGrad. CIFAR10 with two rotations {0°,180°}, 50
clients in each cluster, $l=10,k=5$, trainset size is 400. PANMGrad refers to
PANM with metric in Equation 6 ($\alpha=0.5$), PANMGrad-theta1 refers to PANM
with metric based on $\theta_{1}$, and PANMGrad-theta2 refers to PANM with
metric based on $\theta_{2}$.

Notably, the combination of cosines $\theta_{1}$ and $\theta_{2}$ is more
robust and effective compared with using one cosine function alone. We
implement an ablation experiment as illustrated in Figure 2. It is obvious
that PANMGrad surpasses PANMGrad-theta1 and PANMGrad-theta2 by a large margin
in accuracy curves. Besides, the curve of PANMGrad is stable and robust in
both training stages (we will introduce the stages in Section 4.2 and 4.3)
while there are disturbances in the baseline curves. We explain the robustness
and effectiveness of our metric by the complementarity of $\cos\theta^{1}$ and
$\cos\theta^{2}$. $\cos\theta^{1}$ indicates the gradient direction of current
round while $\cos\theta^{2}$ reflects historical neighbor-ship and
optimization direction in previous rounds.

Moreover, we found the newly proposed gradient-based metric is computation-
efficient compared with the loss-based metric. Without loss of generality, to
simplify the analysis, we suppose the model is a $1\times e$ vector, and a
data sample is a $e\times 1$ vector, thus the computation of the inner product
of gradients equals the computation of one data sample’s inference. For client
$i$, the number of local samples is $d$ and the number of neighbor candidates
is $l$. To calculate the candidates’ similarity, the loss-based metric has
$\mathcal{O}(dl)$ computation complexity while the gradient-based metric has
$\mathcal{O}(l)$ complexity. Usually, we have $d\gg l$, therefore the
gradient-based metric is more efficient in computation. Although the loss-
based metric can be more computation-efficient by reducing the dataset size,
it will also reduce the effectiveness of measurement.

###  4.2 Neighbor Selection Based on Monte Carlo

Based on the similarity metrics mentioned in the last subsection, we can
devise our P2P FL algorithm PANM. We introduce the first stage of PANM in this
subsection.

In P2P FL, clients have access to receive models from randomly sampled peers
(${\rm C}_{i}^{t},|{\rm C}_{i}^{t}|=l$), and they need to select neighbors for
model aggregation from these candidates. A natural way is to choose the top
$k$ candidates with maximal similarities in each round, which is adopted in
PENS [33]. However, this method has constant expectation on the probability of
correct neighbor estimation during the training process (we will theoretically
prove it in Theorem 1 and Corollary 1). If $l,k$ are not appropriately set or
the environment is more heterogeneous, the neighbor estimation will be
constantly noisy. We solve this challenge by resorting to Monte Carlo method.
We formulate the objective of the first stage as: for each client, find the
most similar peers as its neighbors. To reach this objective, the Monte Carlo
method adds the neighbors in the last round together with the random sampled
peers in the current round to the candidate list. As the number of rounds
increases, the expected probability of the most similar neighbors increases,
and if the similarity measurement is effective, these similar neighbors are
the same-clustered peers. We name this method as Neighbor Selection Based on
Monte Carlo (NSMC). We summarize both the first stage of PENS and NSMC in one
equation, as

$\begin{split}{\rm N}_{i}^{t}&=\mathop{\arg\max}_{{\rm
N}}\sum\limits_{j\in{\rm N}}{\rm s}_{i,j}\\\ &s.t.\ {\rm N}\subsetneqq{\rm
C}_{i}^{t}\cup{\rm L},|{\rm N}|=k.\end{split}$ (7)

In Equation 7, for PENS, it has ${\rm L}=\emptyset$ in all rounds; and for
CNI, it has ${\rm L}=\emptyset$ in the first round, and ${\rm L}={\rm
N}_{i}^{t-1}$ when $t>1$. We will present theoretical analysis on PENS and
NSMC in Section 4.5. It is found that the expected probability of true
neighbors (being the same-cluster) is rapidly increasing in NSMC and keeps
constant in PENS. We also show the empirical results that NSMC can boost
personalization even better than Oracle in Section 5. NSMC facilitates clients
to select peers with globally maximal similarities and these most similar
peers may be more helpful than other peers in the same cluster.

###  4.3 Neighbor Augmentation Based on EM-GMM

After NSMC, we enable clients to have few neighbors in the neighbor bag with
high probability of being true neighbors, in other words, the precision is
high. For clustered FL, the recall of clustering is also essential since each
client needs to find out the whole community with the same objective. Thus, in
the second stage of PANM, we facilitate clients to discover more peers with
consistent objectives.

In the second stage of PENS, clients choose peers that are selected more than
“the expected amount of times” in the first stage as neighbors. But if the
setting is difficult, stage-one neighbors of PENS are prone to be noisy,
afterward, in the second stage, the matched neighbors are more likely to
include outliers. Besides, PENS requires the hyperparameter “the expected
amount of times”, and without prior knowledge of cluster information, it is
hard to set the hyperparameter to an appropriate value. To better solve these
problems, we propose a more effective neighbor bag augmentation method, which
is based on Expectation Maximization of Gaussian Mixture Model (EM-GMM).

For a client, given a set of randomly sampled peers, it is obvious that the
true neighbors (i.e. with the same cluster identity) may have high
similarities with it while the false ones (i.e. with different cluster
identities) have low similarities. Therefore, we make the Gaussian Mixture
Model assumption that the similarities of the true neighbors obey a consistent
distribution while the similarities of the false ones obey another
distribution. Formally, the assumption is shown in Assumption 1.

######  Assumption 1.

(Gaussian Mixture Model Assumption) For client $i$ ($\forall i\in[n]$), the
similarities between the true neighbors and client $i$ obey a Gaussian
distribution, parameterized by $\mathcal{N}(\mu_{0},\sigma_{0}^{2})$, and the
similarities between the false neighbors and client $i$ obey another Gaussian
$\mathcal{N}(\mu_{1},\sigma_{1}^{2})$ that

$\begin{split}{\rm s}_{i,p}\sim\mathcal{N}(\mu_{0},\sigma_{0}^{2}),&\ {\rm
s}_{i,q}\sim\mathcal{N}(\mu_{1},\sigma_{1}^{2})\\\ \forall p\in{\rm
N}_{i}^{*},&\ q\in\overline{{\rm N}_{i}^{*}},\end{split}$

where ${\rm N}_{i}^{*}$ refers to the true neighbors of client $i$, and
$\overline{{\rm N}_{i}^{*}}$ refers to the false neighbors of client $i$. We
have $\mu_{0}>\mu_{1}$.

Figure 3: Distributions of similarities. Similarities between client 1 and
other clients are shown. CIFAR10, $n=100$, clusters are formed by rotations
{0°, 180°}.

Assumption 1 is quite natural in clustered FL. In Figure 3, intuitively, the
distributions of similarities satisfy our assumption that there are two
distinct Gaussians.

Under Assumption 1, we can implement neighbor augmentation by solving the GMM
problem and a typical solution to GMM problem is the EM algorithm. But
conventional EM algorithm is not suitable to solve this problem under the
following considerations: (1) Conventional EM method requires calculating
probabilities of all data points in one EM step, but for P2P FL, clients only
can communicate with several neighbors in one round. (2) The focus of
conventional EM solving GMM problems is to accurately estimate the parameters
of Gaussians while our focus is to accurately discriminate cluster identities.
(3) Additionally, EM algorithms are sensitive to initialization, and poor
initialization may lead to bad convergence.

To tackle above mentioned matters, we devise our Neighbor Augmentation Based
on EM-GMM (NAEM) algorithm. In each round, client $i$ randomly samples
neighbor candidate list ${\rm C}_{i}^{t}(|{\rm C}_{i}^{t}|=l)$ from non-
neighbor clients and also samples a selected neighbor list ${\rm
S}_{i}^{t}(|{\rm S}_{i}^{t}|=l$ if $|{\rm B}_{i}^{t}|>l$, else ${\rm
S}_{i}^{t}={\rm B}_{i}^{t})$ from the neighbor bag ${\rm B}_{i}^{t}$. Then,
client $i$ communicates with these clients and compute similarities
$y_{j}={\rm s}_{i,j},\ j\in{\rm M}_{i}^{t}={\rm C}_{i}^{t}\cup{\rm
S}_{i}^{t}$. According to Assumption 1, there are two Gaussian distributions
in these similarities, the one with higher mean center refers to the same-
cluster clients ($\mathcal{N}(\mu_{0},\sigma_{0}^{2})$), another one refers to
the different-cluster ($\mathcal{N}(\mu_{1},\sigma_{1}^{2})$). Assuming the
observed similarity $y_{j},\ j\in{\rm M}_{i}^{t}$ is generated by the Gaussian
Mixture Model:

${\rm Pr}(y|\Theta)=\sum\limits_{r=0}^{1}\beta_{r}\phi(y|\Theta_{r}).$ (8)

Here, $\beta_{r}$ refers to the overall probability that $y$ is generated by
distribution $r$, and $\Theta=(\beta_{0},\beta_{1};\Theta_{0},\Theta_{1})$.
Our target is using EM algorithm to estimate the distribution identities of
$y_{j}$, given by

$\gamma_{j,r}=\left\\{\begin{aligned} 1,\ &\text{if}\ j\ \text{belongs\ to\
distribution}\ \mathcal{N}_{r};\\\ 0,\ &\text{otherwise}.\\\
\end{aligned}\right.$

where $j\in{\rm M}_{i}^{t},\ r\in\\{0,1\\}$. Knowing that EM algorithm is
sensitive to initialization, with the prior knowledge that most of the clients
in ${\rm S}_{i}^{t}$ are true neighbors, so we can initialize a better
parameter as

$\gamma_{j,r}^{(1)}=\left\\{\begin{aligned} 1,\ &j\in{\rm S}_{i}^{t}\
\text{and}\ r=1,\ \text{or}\ j\in{\rm C}_{i}^{t}\ \text{and}\ r=0;\\\ 0,\
&\text{otherwise}.\\\ \end{aligned}\right.$

While the latent variable is the distribution parameters:
$\Theta_{0}=(\mu_{0},\sigma_{0}),\Theta_{1}=(\mu_{1},\sigma_{1})$, so the
complete data is

$(y_{j},\Theta_{0},\Theta_{1}),\ j\in{\rm M}_{i}^{t}.$

Then we formulate the expectation function $Q$, based on the log likelihood
function of complete data,

$\begin{split}&Q(\gamma,\gamma^{(a)})=\mathbb{E}[\log{\rm
Pr}(y,\Theta|\gamma)|y,\gamma^{(a)}]\\\
&=\sum\limits_{r=0}^{1}\bigg{\\{}n_{r}\log\mathbb{E}\beta_{r}+\sum\limits_{j\in{\rm
M}_{i}^{t}}\gamma_{j,r}[\log(\frac{1}{\sqrt{2\pi}})-\log\mathbb{E}\sigma_{r}\\\
&-\frac{1}{2\mathbb{E}\sigma_{r}^{2}}(y_{j}-\mathbb{E}\mu_{r})^{2}]\bigg{\\}},\end{split}$
(9)

where $n_{r}=\sum\limits_{j\in{\rm M}_{i}^{t}}\gamma_{j,r}$, $a$ denotes the
iteration step.

E-step: Now we need to estimate $\mathbb{E}(\mu_{r},\sigma_{r},\beta_{r})$,
notated as $\hat{\mu}_{r},\ \hat{\sigma}_{r},\ \hat{\beta}_{r}$.

$\begin{split}\hat{\mu}_{r}=\frac{\sum\limits_{j\in{\rm
M}_{i}^{t}}\gamma_{j,r}y_{j}}{n_{r}},\hat{\beta}_{r}=\frac{n_{r}}{|{\rm
M}_{i}^{t}|},\hat{\sigma}_{r}^{2}=\frac{\sum\limits_{j\in{\rm
M}_{i}^{t}}\gamma_{j,r}(y_{j}-\hat{\mu}_{r})^{2}}{n_{r}},\end{split}$

where $r\in\\{0,1\\}$.

M-step: Iterative M-step is to find the maximum of the function
$Q(\gamma,\gamma^{(a)})$ with respect to $\gamma^{(a)}$, as to set
$\gamma^{(a+1)}$ in the next iterative epoch

$\gamma^{(a+1)}=\mathop{\arg\max}_{\gamma}Q(\gamma,\gamma^{(a)}).$ (10)

We use the following function to maximize expectation, since $y_{j}$ more
likely belongs to $\mathcal{N}_{0}$ if
$\beta_{0}\phi(y_{j}|\Theta_{0})>\beta_{1}\phi(y_{j}|\Theta_{1})$, vice versa.

$\begin{split}\gamma_{j,r}^{(a+1)}=&\mathbbm{1}\Bigg{\\{}r=\mathop{\arg\max}_{r}\frac{\hat{\beta}_{r}\phi(y_{j}|\hat{\Theta}_{r})}{\sum\limits_{c=0}^{1}\hat{\beta}_{c}\phi(y_{j}|\hat{\Theta}_{c})}\Bigg{\\}},\\\
j\in&{\rm M}_{i}^{t},r\in\\{0,1\\}.\end{split}$ (11)

Repeat the E-step and M-step until $\gamma^{(a+1)}=\gamma^{(a)}$. Then we
obtain the estimated true neighbors in this round notated as ${\rm
H}_{i}^{t}$, where $\gamma_{j,0}=1,\ j\in{\rm H}_{i}^{t},\ {\rm
H}_{i}^{t}\subseteqq{\rm M}_{i}^{t}$, then we update the neighbor bag,

${\rm B}_{i}^{t+1}=({\rm B}_{i}^{t}-{\rm S}_{i}^{t})\cup{\rm H}_{i}^{t}.$ (12)

By the NAEM algorithm, clients can continually update their neighbor bags,
adding new same-cluster peers and removing outliers in the neighbor bag. For
model aggregation, clients can conduct gossip communication with the peers in
the neighbor bag.

###  4.4 PANM: Personalized Adaptive Neighbor Matching

Now we present PANM by combining the algorithms mentioned above. In the first
stage, client $i\ (i\in[n])$ communicates randomly in the network while
conducting NSMC for $T_{1}$ rounds. The neighbor list ${\rm N}_{i}^{t}$ in the
last round of the first stage is set as the initial neighbor bag in the second
stage, ${\rm B}_{i}^{T_{1}+1}={\rm N}_{i}^{T_{1}}$. In the second stage,
client $i$ operates gossip communication with peers ${\rm N}_{i}^{t}$ (${\rm
N}_{i}^{t}\subseteqq{\rm B}_{i}^{t},|{\rm N}_{i}^{t}|=k$) sampled from the
neighbor bag for aggregation and performs NAEM every $\tau$ rounds to update
the neighbor bag ${\rm B}_{i}^{t}$. The process of PANM is shown in Algorithm
1.

TABLE II: Complexity analysis regarding computation and communication. Please refer to Table I for the meaning of notations.  Methods | Similarity Computation | Communication cost | Maximal required bandwidth
---|---|---|---
FedAvg | $\backslash$ | $\mathcal{O}(n(T_{1}+T_{2})$ | $\mathcal{O}(n)$
IFCA | $\mathcal{O}(dcn(T_{1}+T_{2}))$ | $\mathcal{O}(n(c+1)(T_{1}+T_{2}))$ | $\mathcal{O}(cn)$
PENS | $\mathcal{O}(dlnT_{1}+dknT_{2})$ | $\mathcal{O}(nlT_{1}+nkT_{2})$ | $\mathcal{O}(l)$
PANMLoss | $\mathcal{O}(d(k+l)nT_{1}+dn(l\tau+kT_{2}))$ | $\mathcal{O}(n(l+k)T_{1}+n(l\tau+kT_{2}))$ | $\mathcal{O}(l+k)$
PANMGrad | $\mathcal{O}((k+l)nT_{1}+n(l\tau+kT_{2}))$ | $\mathcal{O}(n(l+k)T_{1}+n(l\tau+kT_{2}))$ | $\mathcal{O}(l+k)$

Complexity Analysis of PANM. We conduct complexity analysis regarding
similarity computation333We note that the EM steps in NAEM require much little
computation because: (1) the computation of similarity measurement includes
the operation of high-dimensional vectors, while the EM steps only operate a
small set of scalars (the similarity values); (2) the number of similarity
values is small; (3) due to our better initialization, it is faster to
converge. Thus, we omit the computation of EM steps in the analysis.,
communication cost, and maximal required bandwidth as shown in Table II. In
Table II, FedAvg and IFCA are centralized FL algorithms, and IFCA is the
state-of-the-art clustered FL approach. PENS and our PANMLoss and PANMGrad are
P2P FL methods. For the similarity computation, the complexity of the
centralized IFCA relies on the assumed number of clusters ($c$), while the P2P
methods rely on the number of communicated peers ($l,k$). We notice the
computation is much more efficient in PANMGrad since it does not rely on local
data inference. For communication cost, IFCA has more overhead than FedAvg,
and in a sparse P2P network where $l\approx c$, the P2P methods have a similar
overhead to IFCA. As for maximal required bandwidth, P2P approaches have a
dominant advantage over the centralized since $n\gg(l+k)$ is usually held in
practice. We notice that PANM has more overhead compared with PENS in the
first stage, but PANM realizes a more pure neighbor selection, that we can set
a relatively smaller $T_{1}$ for PANM to reduce the overhead.

Applying PANM under Server-client Protocol. In applications, if only the
server-client protocol is available, PANM can still be applied by simply
taking the server as a relay for transmitting models. Concretely, clients send
local models and requests about which peers it wants to communicate with to
the server, and then the server sends the requested models to corresponding
clients. The similarity measurement and aggregation process are implemented on
the client side. Clients update their neighbor lists and generate the request
in each round. The scheme that the server sends other clients’ models to a
client for updating the client similarity matrix is adopted in personalized FL
[35], showing this scheme is realistic in practice. Nevertheless, our method
is essentially a P2P algorithm where clients have the autonomy to choose the
neighbors, while in [35], the server updates the client similarity matrix and
has the autonomy.

Algorithm 1 PANM: Personalized Adaptive neighbor Matching

Input:
$n,k,l,T_{1},T_{2},\eta,E,\tau,\alpha,\mathbf{w}_{0},\mathbf{W}^{0}=\\{\mathbf{w}_{0}^{1}=\mathbf{w}_{0},i\in[n]\\}$;
Output: $\mathbf{W}^{T_{1}+T_{2}}$, B;

1: Initiate neighbor list: ${\rm N}_{i}^{0}$;

2: for each round $t=1,\dots,T_{1}+T_{2}$ do

3: for each client $i,i\in[n]$ in parallel do

4: Compute $E$ epochs of local training:

5: $\mathbf{w}_{i}^{t-\frac{1}{2}}\leftarrow\mathbf{w}_{i}^{t-1}-\eta\nabla
F_{i}\left(\mathbf{w}_{i}^{t-1}\right)$;

6: if $t\in[T_{1}]$ then

7: ${\rm N}_{i}^{t}\leftarrow$NSMC(${\rm N}_{i}^{t-1}$),

8: $\mathbf{w}_{i}^{t}\leftarrow$ Aggregation(${\rm
N}_{i}^{t}$,$\mathbf{w}_{i}^{t-\frac{1}{2}}$);

9: else

10: ${\rm B}_{i}^{T_{1}+1}={\rm N}_{i}^{T_{1}}$;

11: if $t\%\tau=0$ then

12: ${\rm B}_{i}^{t}\leftarrow$ NAEM(${\rm B}_{i}^{t-1}$),

13: ${\rm N}_{i}^{t}\leftarrow$ RandomSample(${\rm B}_{i}^{t}$),

14: $\mathbf{w}_{i}^{t}\leftarrow$ Aggregation(${\rm
N}_{i}^{t}$,$\mathbf{w}_{i}^{t-\frac{1}{2}}$);

15: else

16: ${\rm B}_{i}^{t}\leftarrow{\rm B}_{i}^{t-1}$,

17: ${\rm N}_{i}^{t}\leftarrow$ RandomSample(${\rm B}_{i}^{t}$),

18: $\mathbf{w}_{i}^{t}\leftarrow$ Aggregation(${\rm
N}_{i}^{t}$,$\mathbf{w}_{i}^{t-\frac{1}{2}}$);

19: end if

20: end if

21: end for

22: end for

###  4.5 Theoretical Analysis

In this section, we provide theoretical analysis. We first give the
probability model about the expected probability that all neighbors are true
in Theorem 1. It shows that the Monte Carlo method will enable PANM to have a
increasingly pure neighbors in the first stage, while PENS has constant
expectation on the purity. Then, we provide a unified framework about the one-
round error bound to the clustered optimum in Theorem 2. In conjunction with
Theorems 1 and 2, we deduce the error bound of PANM in Theorem 3.

Probability Model about the Purity of Neighbors. We first deduce the
probability model by providing the assumption about the effectiveness of
similarity measurement.

######  Assumption 2.

(Effectiveness of Similarity Measurement) The metrics in Equation 3 and 6 are
effective enough, so that for client $i$ ($\forall i\in[n]$), we have:

${\rm s}_{i,p}>{\rm s}_{i,q}\quad\forall p\in{\rm N}_{i}^{*},\
q\in\overline{{\rm N}_{i}^{*}}.$ (13)

Given Assumption 2, we can provide the expected probability that all neighbors
are true in round $t$. Recall that there are $n$ clients in the system
(including client $i$) and $a$ clients in the same cluster as client $i$
(including client $i$), so we can infer the following theorem.

######  Theorem 1.

(Expected Probability of True Neighbors) Under Assumption 2, in the round $t$
when conducting NSMC as Equation 7 where ${\rm L}={\rm N}_{i}^{t-1}$ when
$t>1$; for client $i$, the expected probability that all neighbors are true is
${\rm P}^{t}(k)$, we have

$\begin{split}{\rm P}^{t}(k)&={\rm G}(k)\ast{\rm P}^{t-1}(k)+{\rm R}(k)\\\
&\dots\\\ {\rm P}^{2}(k)&={\rm G}(k)\ast{\rm P}^{1}(k)+{\rm R}(k)\\\ {\rm
P}^{1}(k)&={\rm R}(k).\end{split}$ (14)

where R(x) and G(x) are two functions and the ’$\ast$’ refers to the discrete
convolution computation, defined as

$\begin{split}&{\rm
R}(x)=\small{\frac{l!(n-l-1)!}{(n-1)!}\sum\limits_{s=0}^{l-x}\frac{(a-1)!(n-a)!}{s!(l-s)!(n-a-s)!(a-l+s-1)!}}\\\
&{\rm G}(x)=\frac{l!(a-1)!(n-a)!(n-l-1)!}{x!(n-1)!(l-x)!(a-x-1)!(n-a-l+x)!}\\\
&{\rm G}(x)\ast{\rm P}(x)=\sum\limits^{x-1}_{m=0}{\rm G}(m){\rm
P}(x-m).\end{split}$

If conducting PENS as Equation 7 where ${\rm L}=\emptyset$, the expected
probability is

${\rm P}^{t}(k)\equiv{\rm R}(k).$ (15)

Based on Theorem 1, we provide the following corollary.

######  Corollary 1.

(The Monotonicity of Probability Functions) Given Theorem 1, we denote ${\rm
Q}(t)={\rm P}^{t}(k),t\in[T]$ as the probability function of round $t$. The
function ${\rm Q}(t)$ of NSMC is monotone increasing, so we have

${\rm Q}(t)>{\rm Q}(t-1)>\dots>{\rm Q}(2)>{\rm Q}(1).$ (16)

The function ${\rm Q}(t)$ of PENS is constant which satisfies

${\rm Q}(t)={\rm Q}(t-1)=\dots={\rm Q}(1)={\rm R}(k).$ (17)

The proofs of Theorem 1 and Corollary 1 are shown in the appendix. The
Corollary 1 shows that: by NSMC, the probability increases over round, while
PENS keeps it unchanged at a low value. Intuitively, we calculate the
theoretical probability under different settings in Table III. It is obvious
that the probability of NSMC increases fast, it will reach 100% in round 5;
whereas PENS will have constantly low probability.

TABLE III: Theoretical precision of true neighbors under different settings. The results are shown in percentage (%). | t=3 | t=5 | t=7
---|---|---|---
n, a, l, k | PENS | NSMC | PENS | NSMC | PENS | NSMC
200,50,10,5 | 7.29 | 90.75 | 7.29 | 99.82 | 7.29 | 100.00
200,50,20,10 | 0.98 | 96.24 | 0.98 | 100.00 | 0.98 | 100.00
200,50,20,6 | 38.00 | 99.94 | 38.00 | 100.00 | 38.00 | 100.00
100,50,10,5 | 62.97 | 100.00 | 62.97 | 100.00 | 62.97 | 100.00

However, we note that Assumption2 is strong, and we provide this assumption
just for theoretical analysis. There are gaps between theory and practice,
especially in the first couple of rounds, when the similarity measurement is
not effective enough. If the effectiveness of similarity is not strongly hold
as Assumption2, the probability in Theorem 1 will have a discount, but the
monotone increasing property of NSMC in Corollary 1 still holds.

Error Bound to the Clustered Optimum. Inspired by [11], we propose a general
theoretical framework to analyse the convergence and error bound under
clustered heterogeneity in P2P FL. Then we incorporate Theorem 1 to give the
error bound of PANM. To start with, we first give the following definitions.

######  Definition 1.

(Optimality within a Cluster) Knowing that there are $r$ clusters, for the
data distribution of cluster $j$ ($j\in[r]$), we define the population loss of
cluster $j$ and the optimal model of cluster $j$ as

$\begin{split}F^{j}(\mathbf{w})&\coloneqq\mathbb{E}_{\xi\sim\mathcal{D}^{j}}\left[f(\mathbf{w}_{i},\xi_{i})\right],\\\
\mathbf{w}_{j}^{*}&=\arg\min_{\mathbf{w}}F^{j}(\mathbf{w}).\end{split}$

######  Definition 2.

(Cluster Heterogeneity) We define the cluster heterogeneity as the maximal
distance between the optimal models of each cluster.

$\Delta\coloneqq\max_{i\neq
j;i,j\in[r]}\|\mathbf{w}_{i}^{*}-\mathbf{w}_{j}^{*}\|.$

######  Definition 3.

(The Error Rate of Neighbor Estimation) For a given client $i$, the error rate
in the aggregation neighbor list is the proportion of false neighbors to all
neighbors,

$\epsilon=\frac{|{\rm N}_{i}\cap\overline{{\rm N}_{i}^{*}}|}{|{\rm
N}_{i}|}=\frac{|{\rm N}_{i}\cap\overline{{\rm N}_{i}^{*}}|}{k}.$

Thus, the number of true neighbors is $|{\rm N}_{i}\cap{\rm
N}_{i}^{*}|=k(1-\epsilon)$, and the number of false neighbors is $|{\rm
N}_{i}\cap\overline{{\rm N}_{i}^{*}}|=k\epsilon$.

Then, we give the following assumptions for theoretical analysis.

######  Assumption 3.

($\mu$-strongly Convexity) The loss functions of each client
$F_{i}(\mathbf{w}),\forall i\in[n]$ and each cluster
$F^{j}(\mathbf{w}),\forall j\in[r]$ are all $\mu$-strongly convex that
satisfy: $\forall\mathbf{w},\mathbf{w}^{\prime}$,

$F(\mathbf{w}^{\prime})\geq F(\mathbf{w})+\langle\nabla
F(\mathbf{w}),\mathbf{w}^{\prime}-\mathbf{w}\rangle+\frac{\mu}{2}\|\mathbf{w}^{\prime}-\mathbf{w}\|^{2}.$

######  Assumption 4.

($L$-smoothness) The loss functions of each client $F_{i}(\mathbf{w}),\forall
i\in[n]$ and each cluster $F^{j}(\mathbf{w}),\forall j\in[r]$ are all
$L$-smooth that satisfy: $\forall\mathbf{w},\mathbf{w}^{\prime}$,

$F(\mathbf{w}^{\prime})\leq F(\mathbf{w})+\langle\nabla
F(\mathbf{w}),\mathbf{w}^{\prime}-\mathbf{w}\rangle+\frac{L}{2}\|\mathbf{w}^{\prime}-\mathbf{w}\|^{2}.$

######  Assumption 5.

(Bounded Gradient Variance) We bound the variance of gradients within a
cluster. For every $\mathbf{w}$ and every $j\in[r]$, the variance of $\nabla
f(\mathbf{w},\xi)$ is upper bounded by $v^{2}$, when $\xi$ is sampled from
$\mathcal{D}^{j}$.

$\mathbb{E}_{\xi\sim\mathcal{D}^{j}}[\|\nabla f(\mathbf{w},\xi)-\nabla
F^{j}(\mathbf{w})\|^{2}]\leq v^{2}.$

Given the above definitions and assumptions, we present the theorem about the
error bound within one communication round in arbitrary P2P algorithms.

######  Theorem 2.

(Error Bound within One Communication Round) For a client $i,i\in[n]$, which
belongs to cluster $j,j\in[r]$, in a certain communication round, the error
gap between its model to the clustered optimum is
$\|\mathbf{w}_{i}-\mathbf{w}_{j}^{*}\|$. Let $\mathbf{w}_{i}^{+}$ be the next-
round model after communicating with neighbors. Then, the next-round error gap
is

$\begin{split}\|\mathbf{w}_{i}^{+}-\mathbf{w}_{j}^{*}\|&\leq(1-\frac{\eta\mu
L(1-\epsilon)}{\mu+L}+\eta L\epsilon)\|\mathbf{w}_{i}-\mathbf{w}_{j}^{*}\|\\\
&+\eta L\Delta\epsilon+\frac{v}{\sqrt{dk}}\frac{1}{\sqrt{1-\epsilon}}+\eta
v\sqrt{\frac{r}{kd}}\sqrt{\epsilon}.\end{split}$ (18)

######  Remark 1.

(Error Bound under Different $\epsilon$) Note that Theorem 2 is a unified
bound for any algorithm and the differences between algorithms lie in the
error rate of neighbor estimation $\epsilon$.

If the algorithm is effective enough that have $\epsilon\rightarrow 0$, we
have

$\|\mathbf{w}_{i}^{+}-\mathbf{w}_{j}^{*}\|\leq(1-\frac{\eta\mu
L}{\mu+L})\|\mathbf{w}_{i}-\mathbf{w}_{j}^{*}\|+\frac{v}{\sqrt{dk}}.$ (19)

In this case, it is clear that the $\|\mathbf{w}_{i}-\mathbf{w}_{j}^{*}\|$
term is decreasing, and if $d,k$ are large while $v$ is small, the model will
converge to the clustered optimum.

If the algorithm is dump that $\epsilon\rightarrow\frac{k-1}{k}$, we have

$\|\mathbf{w}_{i}^{+}-\mathbf{w}_{j}^{*}\|\leq(1+\eta
L)\|\mathbf{w}_{i}-\mathbf{w}_{j}^{*}\|+\eta L\Delta+\eta
v\sqrt{\frac{r}{kd}}+\frac{v}{\sqrt{d}}.$ (20)

In this case, $(1+\eta L)$ shows that it is not converging to the clustered
optimum. If the clustered heterogeneity is more dominant with larger $\Delta$,
the model will be further away from the optimum.

From Equation B.2, we can infer that if $1-\frac{\eta\mu
L(1-\epsilon)}{\mu+L}+\eta
L\epsilon>1\Leftrightarrow\epsilon>\frac{\mu}{2\mu+L}$, the convergence to the
clustered optimum is not satisfied. More intuitively, if we assume $\mu=L$,
the condition becomes $\epsilon>\frac{1}{3}$, which means if the proportion of
false neighbors is larger than $\frac{1}{3}$ in each round, it is impossible
to converge to the clustered optimal. Therefore, the neighbor estimation and
selection is quite essential for clients to converge to the clustered optimum.

######  Theorem 3.

(Error Bound of PANM in the First Stage) We assume Assumptions 1-5 hold and
$\mu=L$, and set the learning rate $\eta=\frac{1}{L}$. We analyse the error
bound of client $i,i\in[n]$, which belongs to cluster $j,j\in[r]$, when
applying PANM in the P2P FL system. The initial error gap is defined as
$\delta_{0}=\|\mathbf{w}_{i}^{0}-\mathbf{w}_{j}^{*}\|$. After $T$ rounds, the
error bound is

$\begin{split}\|\mathbf{w}_{i}^{T}-\mathbf{w}_{j}^{*}\|&\leq\frac{1}{2^{T-1}}{\Bigg{[}}\frac{1+3\epsilon_{0}}{2}\delta_{0}+\epsilon_{0}\Delta+\frac{v}{\sqrt{dk(1-\epsilon_{0})}}\\\
&+\frac{v}{L}\sqrt{\frac{r\epsilon_{0}}{kd}}\Bigg{]}+\sum_{t=0}^{T-2}\frac{1}{2^{t}}\frac{v}{\sqrt{dk}},\end{split}$
(21)

where $\epsilon_{0}={\rm
R}(k)=\small{\frac{l!(n-l-1)!}{(n-1)!}\sum\limits_{s=0}^{l-k}\frac{(a-1)!(n-a)!}{s!(l-s)!(n-a-s)!(a-l+s-1)!}}$.

The proofs of Theorems 2 and 3 are shown in the appendix. From Theorems 2 and
3, we prove that PANM can converge to the clustered optimum and it has a
linear convergence rate. It is worthy mentioning that the effect of clustered
heterogeneity $\Delta$. Intuitively, more dominant heterogeneity will result
in more effective similarity measurement, in other words, Assumption 2 is more
likely to be held and the error rate of neighbor estimation $\epsilon$ is
lower. In Remark 1, lower error rate will result in faster convergence to the
optimum. However, on the other hand, larger $\Delta$ will have a more dominant
error term in Theorem 3.

If we can formulate $\epsilon$ into a function of $\Delta$, the effect of
heterogeneity is more tractable. For instance, if
$\epsilon=\mathcal{O}(\frac{1}{\Delta^{2}})$, the error term
$\Delta\epsilon=\mathcal{O}(\frac{1}{\Delta})$, in this case, larger
heterogeneity will benefit; and if
$\epsilon=\mathcal{O}(\frac{1}{\sqrt{\Delta}})$, the error term
$\Delta\epsilon=\mathcal{O}(\sqrt{\Delta})$, thus, larger heterogeneity will
lead to larger error gap; and if $\epsilon=0$ in all rounds, the effect of
$\Delta$ will be removed.

##  5 Experiments and Results

In this section, we evaluate our methods and compare them with baselines. P2P
FL baselines include PENS [33] (state-of-the-art personalized P2P FL
algorithm), Random (gossip with random neighbors), Local (without
communication), FixTopology (neighbors are randomly sampled at the beginning
and fixed during training). We also include Oracle (with prior knowledge of
cluster identities, gossip with true neighbors) for comparison, and it is not
a baseline but the ideal gossip algorithm with ground-truth cluster
information, which is not realistic in practice. Oracle may indicate the upper
bound of accuracy in clustered P2P FL, but the following experiments will show
our methods can sometimes surpass it.

Centralized FL baselines include IFCA [11] (state-of-the-art centralized
clustered FL) and centralized FedAvg [5]. Our methods include PANMLoss (PANM
with metric based on loss), PANMGrad (PANM with metric based on weight updates
and gradients).

###  5.1 Settings of Datasets

Synthetic Clustered Heterogeneity. We use three public benchmark datasets,
MNIST [36], CIFAR10 [37], and FMNIST (Fashion-MNIST) [38]. To synthesize
clustered heterogeneity, we use rotation transformation and label-swapping,
respectively; we note these two settings are commonly used in clustered FL
(rotation [33, 11], label-swapping [13]). All results are evaluated on each
client’s local testset, and we keep the size of the local testset to 100 for
all scenarios and present the averaged results among all clients. We then
describe the details of clustered rotation transformation and label-swapping.

Rotation Transformation: There are two settings for rotation transformation.
First is rotation with two clusters ({0°, 180°}): clients in cluster 0 keep
images without any transformation (0° rotation), while clients in cluster 1
rotate every image in the trainset and testset for 180°. The second is
rotation with four clusters ({0°, 90°, 180°, 270°}): clients in cluster 0 keep
images without any transformation (0° rotation), and clients in cluster 1
rotate every image in trainset and testset for 90°, clients in cluster 2 for
180°, and clients in cluster 3 for 270°. The labels of images remain
unchanged, and each client’s class distributions are balanced.

Swapping Labels: There are two settings for swapping labels. First is forming
two clusters by swapping labels: for clients in cluster 0, images labeled as
“0” are relabeled as “1” and images labeled as “1” are relabeled as “0”; while
for clients in cluster 1, images labeled as “6” are relabeled as “7” and
images labeled as “7” are relabeled as “6”. The second is forming four
clusters by swapping labels: (1) for clients in cluster 0, images labeled as
“0” and “1” are swapped by labels; (2) for clients in cluster 1, images
labeled as “2” and “3” are swapped; (3) for clients in cluster 2, images
labeled as “4” and “5” are swapped; (4) for clients in cluster 3, images
labeled as “6” and “7” are swapped. Note that the class distributions in
clients are balanced.

Real-world Clustered Heterogeneity. We also use Digit-five [39, 40, 41] to
validate the algorithms. Digit-five is a collection of five digital
recognition datasets, namely handwritten digits (MNIST) [42], digits with
colored backgrounds (MNIST-M) [43], street images of digits (SVHN) [44],
synthetic digits (Synthetic Digits) [43], and digits from postal services
(USPS) [45]. These datasets are of different domains and modalities, and
assigning these datasets to clients can inherently realize clustered
heterogeneity. USPS is much smaller than others, so we exclude USPS and select
50000 samples from each of the other four domains as the FL trainset. As a
result, there exist four clusters among clients. To enable the training under
the same model architecture, we transform the images in different domains to
the same size and number of channels.

###  5.2 Details of Implementations

Implementation Environment. All the experiments are implemented in PyTorch
1.7.1. We have several GPUs for training, including Tesla P40 GPU with 24451MB
memory, Quadro RTX 8000 GPU with 48601MB memory, Tesla P100 GPU with 16280MB
memory, and Tesla V100 GPU with 16130MB memory.

Clients’ Models. A three-layer MLP with ReLU activations is adopted as the
model for training on MNIST and FMNIST. For CIFAR10, a five-layer convolution
neural network model (three convolutional layers followed by two fully
connected layers) is used. For Digit-five, we use LeNet-5 [46]. We do not use
data augmentation techniques like flipping and random cropping.

Hyperparameters. We set the batch size for all experiments to 128, and the
number of local epochs in each round is 3. We adopt the learning rate decay
strategy used in IFCA [11]. The decay step size is 0.99, which means for each
round, the learning rate is set to the learning rate in the last round × 0.99.
The initial learning rate is set to 0.08 in the first round. We use the SGD
optimizer and set SGD momentum to 0.9. We set $T_{1}=100,\ T_{2}=200$ in all
experiments. For “the expected amount of times” in PENS, we set this
hyperparameter to an appropriate value ceil($T_{1}\times(l+k)/n$) for fair
comparison. For centralized FL: IFCA and FedAvg, we set full participation of
clients in each round. For PANMGrad, we set $\alpha=0.5$ in all experiments.

Result Presentation. In every setting, we conduct experiments with different
random initialization three times and average the results, and the mean
results and the standard deviations are shown in the tables and figures. All
experimental results are shown in percentage value (%).

###  5.3 Results on Different Datasets

Figure 4: Heatmaps of aggregation records in the first stage. CIFAR-10 with
two rotations {0°: clients 0-49, 180°: clients 50-99}, trainset size is 400,
$l=10,k=5$.

Table IV shows the test accuracies of all methods under different datasets.
Although FixTopology and Random improve accuracy compared with local training,
in contrast to Oracle, the fixed or random topology will impede performance
gains.

Recall Oracle has perfect information about cluster identities which is
impossible in real FL scenarios. Notably, our methods surpass Oracle in FMNIST
and CIFAR10. We show the accuracy and loss curves of results in CIFAR10 in (a)
and (b) of Figure 5. It is demonstrated that PANMLoss achieves high accuracy
and fast convergence in the first stage, which means the NSMC algorithm is
effective. We explain that the Monte Carlo method enables the clients to
collaborate with peers with maximal similarities, so the performance will be
better than randomly sampled from same-cluster peers (Oracle). This
explanation is also validated in the heatmap of aggregation records between
clients in Figure 4. In PANM, the neighbors are pure compared with PENS and
clients are prone to communicate with several peers instead of all true
neighbors.

Additionally, we notice that PANM performs normally in MNIST, and we reckon
this is because the clustered heterogeneity $\Delta$ is not dominant in
rotated MNIST. One example is that if we rotate the images of “0” for 180°,
the images represent the same distribution. PANM will not take full advantage
when $\Delta$ is small. Firstly, as we have discussed in Section 4.5, smaller
$\Delta$ will make the similarity metrics less effective. More importantly, in
this case, the different clustered optimums have close distances, which means
that the negative transfer between clusters is weak, so there is less
necessity for clustering.

TABLE IV: Results on different datasets. The top two are in bold. For all datasets: trainset size is 200, two rotations {0°,180°}, $l=10,k=5$. $n=100$ for CIFAR10 and FMNIST, $n=200$ for MNIST. Methods | MNIST | FMNIST | CIFAR10
---|---|---|---
Local | 82.57 ±0.28 | 76.24 ±0.22 | 25.27 ±1.21
FixTopology | 94.71 ±0.09 | 85.86 ±0.17 | 39.74 ±2.27
Random | 95.12 ±0.04 | 85.94 ±0.27 | 42.96 ±1.42
Oracle | 95.87 ±0.08 | 87.01 ±0.26 | 49.11 ±0.48
PENS | 96.15 ±0.16 | 86.82 ±0.11 | 44.78 ±1.12
PANMLoss | 95.63 ±0.12 | 87.33 ±0.17 | 49.19 ±0.79
PANMGrad | 95.65 ±0.09 | 86.88 ±0.34 | 48.83 ±0.39

(a)

(b)

(c)

Figure 5: Accuracy and loss curves. CIFAR10, $n=100,l=10,k=5$, trainset size
is 200. (a) 4 clusters with swapping labels; (b) 2 clusters with rotations
{0°,180°}; (c) comparing with centralized FL methods, 4 clusters with
rotations {0°,90°,180°,270°}.

###  5.4 Results under Various Clustered Heterogeneity

Table V shows results under various heterogeneity: swapping labels and more
rotations. For test accuracy, it is evident that our methods are robust in
different Non-IID environments. It is notable that in some experiments
(CIFAR10 Label-swap(2) and (4)), PANM even outperforms Oracle with a large
margin. PANMGrad has similar performances to PANMLoss, but performances vary
in different settings. This is due to their different perspectives of client
similarity that the loss-based and gradient-based perspectives will take
advantage in different scenarios.

TABLE V: Results under various heterogeneity. CIFAR10, $n=100,l=10,k=5$,
trainset size is 200. Label-swap(2)/(4): two/four clusters with swapping
labels, Rotation(4): four clusters with rotation {0°,90°,180°,270°}.

| Test Accuracy
---|---
Methods | Label-swap(2) | Label-swap(4) | Rotation(4)
Local | 25.27 ±1.21 | 25.27 ±1.21 | 25.27 ±1.21
FixTopology | 36.56 ±1.58 | 35.08 ±2.70 | 31.86 ±0.47
Random | 37.32 ±0.26 | 37.14 ±1.30 | 33.16 ±0.55
Oracle | 43.34 ±1.29 | 43.32 ±1.06 | 43.32 ±0.85
PENS | 45.72 ±1.34 | 43.49 ±0.28 | 36.64 ±0.58
PANMLoss | 47.12 ±1.30 | 45.78 ±1.85 | 41.43 ±1.83
PANMGrad | 45.84 ±1.92 | 42.14 ±1.34 | 43.99 ±1.26

| Precision of Neighbors
---|---
Methods | Label-swap(2) | Label-swap(4) | Rotation(4)
PENS | 100 | 70.83±4.17 | 59.75±5.08
PANMLoss | 100 | 100 | 68.19±28.12
PANMGrad | 100 | 83.33±28.87 | 100

| Recall of Neighbors
---|---
Methods | Label-swap(2) | Label-swap(4) | Rotation(4)
PENS | 59.18±2.04 | 66.67±4.17 | 52.78±8.67
PANMLoss | 74.15±32.42 | 48.61±13.39 | 62.50±31.46
PANMGrad | 100 | 94.44±6.36 | 98.61±2.41

For precision (the fraction of true neighbors in the neighbor bag) and recall
(the fraction of estimated true neighbors among all true neighbors) of
neighbor estimation in the second stage, our methods outperform PENS. It
indicates our EM-based NAEM method is effective in enabling clients to match
most of the true neighbors. We also demonstrate the neighbor topology in the
second stage in Figure 6. In PANM, clients evolve to form the four-cluster
structure without prior knowledge of cluster identities, whereas PENS and
Random construct disordered topologies.

Figure 6: Neighbor topologies in the second stage. Four clusters with rotations, CIFAR10, $n=100,l=10,n=5$, trainset size is 200. Each color denotes a cluster. Figure 7: Left: Accuracies when changing trainset size; $n=100,l=10,k=5$, two rotations {0°,180°} for all. Right: Accuracies when changing number of clients, $l=10,k=5$, trainset size is 200, two rotations {0°,180°} for all. TABLE VI: Impact of $k$ and $l$. CIFAR10 with two rotations {0°,180°}, $n=100$, trainset size is 100 for all settings. | $l,k$
---|---
Methods | 10,5 | 10,3 | 20,10 | 20,5 | 30,15 | 30,10
Local | 19.93 ±0.36 | 19.93 ±0.36 | 19.93 ±0.36 | 19.93 ±0.36 | 19.93 ±0.36 | 19.93 ±0.36
FixTopology | 36.60 ±2.58 | 31.54 ±0.18 | 38.31 ±1.45 | 34.94 ±0.84 | 38.88 ±0.52 | 38.77 ±3.80
Random | 39.19 ±1.04 | 38.54 ±2.24 | 40.82 ±1.09 | 37.34 ±0.80 | 42.22 ±2.25 | 39.91 ±0.60
Oracle | 43.83 ±0.80 | 42.28 ±1.25 | 43.39 ±2.80 | 43.57 ±0.93 | 44.79 ±2.36 | 44.16 ±1.32
PENS | 42.42 ±1.58 | 40.04 ±0.90 | 42.57 ±1.74 | 41.92 ±1.28 | 44.12 ±0.22 | 42.80 ±0.98
PANMLoss | 41.75 ±0.24 | 39.55 ±1.78 | 44.02 ±0.59 | 43.64 ±1.54 | 46.82 ±0.41 | 46.19 ±0.84
PANMGrad | 42.48 ±0.21 | 39.53 ±2.99 | 38.24 ±4.26 | 41.94 ±3.15 | 41.16 ±3.60 | 42.23 ±1.02

###  5.5 Impact of l and k

$l$ is the size of neighbor candidate list, and $k$ is the size of the
aggregation neighbor list. The choices of $l$ and $k$ depend on communication
budgets in the system, and they determine the network connectivity. Larger $l$
and $k$ will result in denser network connectivity and bring more
communication costs. Besides, the ratio of $l$ and $k$ is also crucial
(especially for PENS), and it decides the purity of neighbors as we have
inferred in Theorem 1 and Corollary 1. We conduct experiments under different
network setups by changing $l,k$ as demonstrated in Table VI.

We notice if $l$ and $\frac{k}{l}$ are small (for example, $l=10,k=3$), PENS
performs well, but in other settings, PENS has poor results. As we have
discussed in Section 4.5, if $l,k$ are not set appropriately, PENS is prone to
be noisy in neighbor matching.

For Oracle, the communication only relies on $k$. As $k$ increases, the
network connection is denser, and the performance of Oracle increases. We
explain that if the neighbor bag is pure and the number of aggregation
neighbors increases, it is better for clients to reach partial consensus
within clusters, and the model weights are more likely to be similar. It is
worth mentioning that PANMLoss is very robust under various network setups,
surpassing Oracle in most settings. PANMLoss benefits a lot when $k$
increases.

TABLE VII: Comparison with centralized FL. $n=100,l=10,k=5$, trainset size is 200. Best performances in the centralized and decentralized are in bold. Clusters are generated by rotations: 2 for {0°,180°}, 4 for {0°,90°,180°,270°}. Methods | CIFAR10(4) | FMNIST(4) | FMNIST(2)
---|---|---|---
Local | 25.27 ±1.21 | 76.24 ±0.22 | 76.24 ±0.22
FedAvg | 37.03 ±0.74 | 83.54 ±0.08 | 86.86 ±0.16
IFCA($c$=2) | 40.64 ±2.18 | 86.19 ±0.04 | 88.06 ±0.20
IFCA($c$=3) | 41.05 ±1.09 | 86.78 ±0.36 | /
IFCA($c$=4) | 43.65 ±0.77 | 86.50 ±0.07 | /
Oracle | 43.32 ±0.85 | 85.45 ±0.38 | 87.01 ±0.26
PENS | 36.64 ±0.58 | 84.68 ±0.27 | 86.82 ±0.11
PANMLoss | 41.43 ±1.83 | 86.09 ±0.31 | 87.33 ±0.17
PANMGrad | 43.99 ±1.26 | 85.64 ±0.25 | 86.88 ±0.34
TABLE VIII: Performances under low communication budgets, where $n=100$, the trainset size is 200 and $\Omega=100\omega$ with $\omega$ being the single model size. We use CIFAR-10 with 4 rotations. For PANM, we set $l=4,~{}\tau=10$. Methods | Comm. costs | Max. req. band. | Test acc.
---|---|---|---
FedAvg | 600$\Omega$ | 1$\Omega$ | 37.03 ±0.74
IFCA ($c$=2) | 900$\Omega$ | 2$\Omega$ | 40.64 ±2.18
IFCA ($c$=3) | 1200$\Omega$ | 3$\Omega$ | 41.05 ±1.09
IFCA ($c$=4) | 1500$\Omega$ | 4$\Omega$ | 43.65 ±0.77
PANMLoss ($k$=2) | 1118$\Omega$ | 0.06$\Omega$ | 41.36±0.64
PANMGrad ($k$=2) | 1118$\Omega$ | 0.06$\Omega$ | 42.78±1.68
PANMLoss ($k$=3) | 1397$\Omega$ | 0.07$\Omega$ | 43.30±1.32
PANMGrad ($k$=3) | 1397$\Omega$ | 0.07$\Omega$ | 43.34±0.85

###  5.6 Impact of Trainset size and Number of Clients

In the left figure of Figure 7, we compare the methods by varying the size of
the local trainsets, and in the right figure of Figure 7, we show the results
of changing the number of clients. We see that PANM consistently outperforms
all baselines (Local, PENS, Random, and FixTopology), and it has comparable
performance with Oracle.

###  5.7 Comparison with Centralized Clustered FL

P2P FL takes advantage of bandwidth and reliability, as we addressed in
Section 1. Besides, as for clustered FL, our P2P solution is more robust and
can exploit the latent cluster structure in a self-evolved manner without
assuming the number of clusters. We compare IFCA [11], the state-of-the-art
centralized clustered FL and centralized FedAvg [5] with decentralized P2P
methods, as shown in Table VII and (c) of Figure 5. In typical centralized FL
algorithms, the central server randomly samples $l$ clients for aggregation,
but we notice this will result in bad convergence for IFCA. In our
implementations, in a scenario where there are 100 clients with 4 clusters,
and the central server samples 10 clients in each round (where $l/n=0.1$),
IFCA has poor convergence of estimations. As a result, we have to set full
aggregation participation of clients in IFCA (where $l/n=1.0$), but we remind
this will cause large communication burdens, and it is unfair to the P2P
setting (where we set $n=100,l=10,l/n=0.1$). Even if, in Table VII, our P2P
method PANM also achieves proportionate performances as a contrast to IFCA.
What’s more, IFCA requires the assumption on the number of clusters ($c$), and
we find that if $c$ is set inappropriately, the performance will be poor.
According to Table VII, in CIFAR10 with 4 rotations setting, if set $c=2$, the
accuracy of IFCA is 40.64% while our PANMLoss and PANMGrad reach 41.43% and
43.99%. Moreover, from the learning curves in Figure (c) of Figure 5, it is
apparent that our PANM keeps a more steady and robust learning process while
there are some disturbances in the curves of centralized counterparts.

Comparison under Sparse Network. Generally, if $l$ and $k$ are large, the
overall communication costs of P2P FL are larger than those of centralized FL
methods. In Table VIII, we conduct experiments where PANM will have comparable
communication costs as the centralized methods. This setting depicts an
extremely sparse network for PANM. The results show that PANM can have
intimate performances to IFCA when the communication costs are similar, but
PANM requires much lower bandwidth. We also find that the consequence of
inappropriately estimating the number of clusters will be severe for IFCA
(43.65% when $c=4$; 41.05% when $c=3$). On the contrary, PANM is flexible
enough to explore the cluster structure under any hyperparameters, and the
influence of communication budgets is subtle. Therefore, we reckon PANM is
more robust and effective than the centralized IFCA.

###  5.8 Results under Real-world Clustered Heterogeneity

We validate the algorithms on Digit-five benchmark to see how they perform
under real-world clustered heterogeneity, and the results are demonstrated in
Table IX.

TABLE IX: Results on Digit-five, $l=10,k=5$, and trainset size is 200. | Number of Clients ($n$)
---|---
Methods | 200 | 400
Local | 16.58±0.14 | 18.38±0.92
FedAvg | 80.94±7.66 | 71.92±15.8
IFCA ($c$=2) | 50.23±1.04 | 66.34±23.59
IFCA ($c$=3) | 91.34±0.44 | 52.56±8.82
IFCA ($c$=4) | 64.94±28.33 | 78.73±13.09
FixTopology | 73.44±25.14 | 39.29±5.13
Random | 65.9±19.46 | 41.82±9.04
Oracle | 91.48±0.44 | 83.05±12.41
PENS | 85.57±1.05 | 86.52±1.03
PANMLoss | 88.6±1.63 | 87.04±0.31
PANMGrad | 89.66±0.51 | 90.24±1.51

It shows PANM is robust and effective that it has high mean and low variance
in accuracy even in the real-world clustered heterogeneity. When the number of
clients is 400, PANM has even superior performance over Oracle.

Interestingly, we observe that even though the Digit-five dataset has four
domains, the best assumed number of clusters is not necessarily four. For
IFCA, when $n=200$, the best $c$ is 3, and when $n=400$, the best $c$ is 4. It
reveals that in real-world data, the clustered structure is not absolute. When
the number of clients changes that clients come in and out, the cluster
relationship among them also varies. Therefore, it is not flexible of IFCA to
assume the cluster number that inappropriate $c$ will cause poor and unstable
performances. However, our method can dynamically form the clustered topology,
which is more robust and effective.

##  6 Discussion on the Applicability of PANM

Choice between PANMLoss and PANMGrad. For PANMLoss and PANMGrad, the metrics
require different computation resources. As we have discussed in Section 4.4,
generally, PANMGrad is more computationally efficient since it only requires
several inner product calculations on sparse vectors (gradients), while
PANMLoss needs inference on local datasets. Hence, under limited computation
resources, PANMGrad is preferable.

In addition, in conjunction with the results in Table VI and Table VIII, we
found PANMGrad has better performance under sparse communication while
PANMLoss benefits more in dense connection. Therefore, under limited
communication resources, PANMGrad is preferable. And when the computation and
communication resources are sufficient, PANMLoss is the better choice with
better performance.

Client Accessibility. We have mentioned in Subsection 5.5 that we can choose
different $l,k$ by the communication budgets, and we have shown PANM is still
effective under low communication budgets. Furthermore, in our
implementations, we assume fully connected communication accessibility, which
means that each client can communicate with any other client in the system.
The fully connected accessibility is not often satisfied in realistic
scenarios, but we state that PANM is also applicable under limited
accessibility. In PANM, we hold loose assumptions about accessibility, that
clients can purify their neighbors within the scope of accessible peers. Thus,
PANM is flexible in practice.

##  7 Conclusion

This paper studies the clustered Non-IID problem in FL under P2P communication
and develops PANM that enables clients to match neighbors with similar
objectives. PANM is more flexible and effective than the centralized clustered
FL methods because it does not require the assumption of the number of
clusters. Specifically, in PANM, we present two novel metrics for measuring
client similarity based on loss and gradient, respectively. Then, we propose a
two-stage algorithm. In the first stage, an effective method based on Monte
Carlo is proposed to enable clients to match neighbors with maximally high
similarities. Then in the second stage, a method based on Expectation
Maximization under the Gaussian Mixture Model assumption of similarities is
used for clients to discover more neighbors with similar objectives. We have
conducted theoretical analyses of PANM on the probability of neighbor
estimation and the error gap to the clustered optimum. We have also
implemented extensive experiments under both synthetic and real-world
clustered heterogeneity. Theoretical analysis and empirical experiments show
that the proposed algorithm is superior to the P2P FL counterparts and
achieves better performance than the centralized cluster FL method. PANM is
effective even under extremely low communication budgets.

## Acknowledgments

This work is supported by the National Key Research and Development Project of
China (No. 2021ZD0110400), National Natural Science Foundation of China (No.
U19B2042), The University Synergy Innovation Program of Anhui Province (No.
GXXT-2021-004), and Key Research Project of Zhejiang Lab (No. 2021KE0AC02).

## References

  * [1] J. Lin, W. Yu, N. Zhang, X. Yang, H. Zhang, and W. Zhao, “A survey on internet of things: Architecture, enabling technologies, security and privacy, and applications,” _IEEE internet of things journal_ , vol. 4, no. 5, pp. 1125–1142, 2017.
  * [2] A. Imteaj, U. Thakker, S. Wang, J. Li, and M. H. Amini, “A survey on federated learning for resource-constrained iot devices,” _IEEE Internet of Things Journal_ , vol. 9, no. 1, pp. 1–24, 2021.
  * [3] D. C. Nguyen, M. Ding, P. N. Pathirana, A. Seneviratne, J. Li, and H. V. Poor, “Federated learning for internet of things: A comprehensive survey,” _IEEE Communications Surveys & Tutorials_, vol. 23, no. 3, pp. 1622–1658, 2021.
  * [4] Q. Yang, Y. Liu, T. Chen, and Y. Tong, “Federated machine learning: Concept and applications,” _ACM Transactions on Intelligent Systems and Technology (TIST)_ , vol. 10, no. 2, pp. 1–19, 2019.
  * [5] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Artificial intelligence and statistics_. PMLR, 2017, pp. 1273–1282.
  * [6] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith, “Federated learning: Challenges, methods, and future directions,” _IEEE Signal Processing Magazine_ , vol. 37, no. 3, pp. 50–60, 2020.
  * [7] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings _et al._ , “Advances and open problems in federated learning,” _Foundations and Trends® in Machine Learning_ , vol. 14, no. 1–2, pp. 1–210, 2021\.
  * [8] H. Zhu, J. Xu, S. Liu, and Y. Jin, “Federated learning on non-iid data: A survey,” _Neurocomputing_ , vol. 465, pp. 371–390, 2021.
  * [9] B. M. Sarwar, G. Karypis, J. Konstan, and J. Riedl, “Recommender systems for large-scale e-commerce: Scalable neighborhood formation using clustering,” in _Proceedings of the fifth international conference on computer and information technology_ , vol. 1. Citeseer, 2002, pp. 291–324.
  * [10] Q. Li and B. M. Kim, “Clustering approach for hybrid recommender system,” in _Proceedings IEEE/WIC International Conference on Web Intelligence (WI 2003)_. IEEE, 2003, pp. 33–38.
  * [11] A. Ghosh, J. Chung, D. Yin, and K. Ramchandran, “An efficient framework for clustered federated learning,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 19 586–19 597, 2020.
  * [12] M. Xie, G. Long, T. Shen, T. Zhou, X. Wang, J. Jiang, and C. Zhang, “Multi-center federated learning,” _arXiv preprint arXiv:2005.01026_ , 2020\.
  * [13] F. Sattler, K.-R. Müller, and W. Samek, “Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints,” _IEEE transactions on neural networks and learning systems_ , vol. 32, no. 8, pp. 3710–3722, 2020.
  * [14] M. Duan, D. Liu, X. Ji, Y. Wu, L. Liang, X. Chen, Y. Tan, and A. Ren, “Flexible clustered federated learning for client-level data distribution shift,” _IEEE Transactions on Parallel and Distributed Systems_ , 2021.
  * [15] X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and J. Liu, “Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent,” _Advances in Neural Information Processing Systems_ , vol. 30, 2017.
  * [16] A. Lalitha, O. C. Kilinc, T. Javidi, and F. Koushanfar, “Peer-to-peer federated learning on graphs,” _arXiv preprint arXiv:1901.11173_ , 2019.
  * [17] A. Lalitha, S. Shekhar, T. Javidi, and F. Koushanfar, “Fully decentralized federated learning,” in _Third workshop on Bayesian Deep Learning (NeurIPS)_ , 2018.
  * [18] T. Lin, S. P. Karimireddy, S. U. Stich, and M. Jaggi, “Quasi-global momentum: Accelerating decentralized deep learning on heterogeneous data,” _arXiv preprint arXiv:2102.04761_ , 2021.
  * [19] L. Kong, T. Lin, A. Koloskova, M. Jaggi, and S. Stich, “Consensus control for decentralized deep learning,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 5686–5696.
  * [20] L. Cui, X. Su, Y. Zhou, and J. Liu, “Optimal rate adaption in federated learning with compressed communications,” in _IEEE INFOCOM 2022-IEEE Conference on Computer Communications_. IEEE, 2022, pp. 1459–1468.
  * [21] L. Cui, X. Su, Y. Zhou, and Y. Pan, “Slashing communication traffic in federated learning by transmitting clustered model updates,” _IEEE Journal on Selected Areas in Communications_ , vol. 39, no. 8, pp. 2572–2589, 2021\.
  * [22] M. N. Nguyen, S. R. Pandey, T. N. Dang, E.-N. Huh, N. H. Tran, W. Saad, and C. S. Hong, “Self-organizing democratized learning: Toward large-scale distributed learning systems,” _IEEE Transactions on Neural Networks and Learning Systems_ , 2022.
  * [23] M. Duan, D. Liu, X. Ji, R. Liu, L. Liang, X. Chen, and Y. Tan, “Fedgroup: Ternary cosine similarity-based clustered federated learning framework toward high accuracy in heterogeneous data,” _arXiv preprint arXiv:2010.06870_ , 2020.
  * [24] C. Briggs, Z. Fan, and P. Andras, “Federated learning with hierarchical clustering of local updates to improve training on non-iid data,” in _2020 International Joint Conference on Neural Networks (IJCNN)_. IEEE, 2020, pp. 1–9.
  * [25] S. Warnat-Herresthal, H. Schultze, K. L. Shastry, S. Manamohan, S. Mukherjee, V. Garg, R. Sarveswara, K. Händler, P. Pickkers, N. A. Aziz _et al._ , “Swarm learning for decentralized and confidential clinical machine learning,” _Nature_ , vol. 594, no. 7862, pp. 265–270, 2021.
  * [26] I. Hegedűs, G. Danner, and M. Jelasity, “Decentralized learning works: An empirical comparison of gossip learning and federated learning,” _Journal of Parallel and Distributed Computing_ , vol. 148, pp. 109–124, 2021\.
  * [27] A. Bellet, R. Guerraoui, M. Taziki, and M. Tommasi, “Personalized and private peer-to-peer machine learning,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2018, pp. 473–481.
  * [28] C. Li, G. Li, and P. K. Varshney, “Decentralized federated learning via mutual knowledge transfer,” _IEEE Internet of Things Journal_ , vol. 9, no. 2, pp. 1136–1147, 2021.
  * [29] A. Bellet, A.-M. Kermarrec, and E. Lavoie, “D-cliques: Compensating noniidness in decentralized federated learning with topology,” _arXiv preprint arXiv:2104.07365_ , 2021.
  * [30] Z. Tang, S. Shi, and X. Chu, “Communication-efficient decentralized learning with sparsification and adaptive peer selection,” in _2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS)_. IEEE, 2020, pp. 1207–1208.
  * [31] J. Jiang and L. Hu, “Decentralised federated learning with adaptive partial gradient aggregation,” _CAAI Transactions on Intelligence Technology_ , vol. 5, no. 3, pp. 230–236, 2020.
  * [32] O. Marfoq, C. Xu, G. Neglia, and R. Vidal, “Throughput-optimal topology design for cross-silo federated learning,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 19 478–19 487, 2020.
  * [33] N. Onoszko, G. Karlsson, O. Mogren, and E. L. Zec, “Decentralized federated learning of deep neural networks on non-iid data,” _arXiv preprint arXiv:2107.08517_ , 2021.
  * [34] E. Tzeng, J. Hoffman, N. Zhang, K. Saenko, and T. Darrell, “Deep domain confusion: Maximizing for domain invariance,” _arXiv preprint arXiv:1412.3474_ , 2014.
  * [35] M. Zhang, K. Sapra, S. Fidler, S. Yeung, and J. M. Alvarez, “Personalized federated learning with first order model optimization,” in _International Conference on Learning Representations_ , 2020.
  * [36] Y. LeCun, C. Cortes, and C. Burges, “Mnist handwritten digit database,” 2010.
  * [37] A. Krizhevsky _et al._ , “Learning multiple layers of features from tiny images,” _Citeseer_ , 2009.
  * [38] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms,” _arXiv preprint arXiv:1708.07747_ , 2017.
  * [39] S. Zhao, G. Wang, S. Zhang, Y. Gu, Y. Li, Z. Song, P. Xu, R. Hu, H. Chai, and K. Keutzer, “Multi-source distilling domain adaptation,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 34, no. 07, 2020, pp. 12 975–12 983.
  * [40] X. Peng, Z. Huang, Y. Zhu, and K. Saenko, “Federated adversarial domain adaptation,” in _International Conference on Learning Representations_ , 2019\.
  * [41] S. Luo, D. Zhu, Z. Li, and C. Wu, “Ensemble federated adversarial training with non-iid data,” _arXiv preprint arXiv:2110.14814_ , 2021.
  * [42] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” _Proceedings of the IEEE_ , vol. 86, no. 11, pp. 2278–2324, 1998.
  * [43] Y. Ganin and V. Lempitsky, “Unsupervised domain adaptation by backpropagation,” in _International conference on machine learning_. PMLR, 2015, pp. 1180–1189.
  * [44] Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Y. Ng, “Reading digits in natural images with unsupervised feature learning,” 2011.
  * [45] J. J. Hull, “A database for handwritten text recognition research,” _IEEE Transactions on pattern analysis and machine intelligence_ , vol. 16, no. 5, pp. 550–554, 1994.
  * [46] Y. LeCun _et al._ , “Lenet-5, convolutional neural networks,” _URL: http://yann. lecun. com/exdb/lenet_ , vol. 20, no. 5, p. 14, 2015.

|  Zexi Li received B.S. degree in Agriculture Engineering from Zhejiang
University, Hangzhou, China, in 2020. Meanwhile, he also obtained an honorary
degree from Chu Kochen Honors College, Zhejiang University. He is currently a
Ph.D. student in Computer Science in Zhejiang University. His main research
interests include federated learning, optimization, and deep learning.
---|---
|  Jiaxun Lu (Member, IEEE) received the B.S. and Ph.D. degrees from the
Department of Electronic Engineering, Tsinghua University, Beijing, China, in
2014 and 2019, respectively. From September 2017 to September 2018, he was a
Visiting Student with Coordinate Science Laboratory, University of Illinois at
Urbana-Champaign, Champaign, IL, USA. Currently, He is a senior researcher
with Noah’s Ark Lab, Huawei Technologies. His research interests include
statistical learning, information theory, and mobile wireless communication.
---|---
|  Shuang Luo received the B.Eng. degree from the School of Data and Computer
Science, Sun Yat-sen University, China, in 2019. She is currently pursuing the
Ph.D. degree in the College of Public Affairs, Zhejiang University. Her
current research interests include deep learning, reinforcement learning and
distributed artificial intelligence.
---|---
|  Didi Zhu received the B.S. degree in Computer Science and Technology from
Beijing University of Chemical Technology, Beijing, China, in 2020. She is
currently a Ph.D. student of Zhejiang University. Her main research interests
include federated learning and domain adaptation.
---|---
|  Yunfeng Shao (Member, IEEE) received the B.S. and Ph.D. degrees in
Electronic Engineering from Shanghai Jiao Tong University and University of
Chinese Academy of Sciences China, in 2009 and 2014, respectively. He is
currently an expert in Huawei Noah’s Ark Lab. His research interests include
machine learning with privacy protection, federated learning, transfer
learning and their applications in Telecommunication network.
---|---
|  Yinchuan Li (Member, IEEE) was born in Bozhou, Anhui, China, in 1994. He
received the B.S. and Ph.D. degrees in electronic engineering from the Beijing
Institute of Technology (BIT), Beijing, China, in 2015 and 2020, respectively.
From November 2017 to November 2019, he was a Visiting Scholar with the
Department of Electrical Engineering, Columbia University, New York, NY, USA.
From February 2020 to August 2020, he was a senior technical consultant in
Santé Ventures, Austin, TX, USA. He now works at Noah’s Ark Lab, Huawei
Technologies, Beijing, China, as an AI researcher. His current research
interests include machine learning, deep learning, reinforcement learning, and
sparse signal processing. Dr. Li received the Excellent Paper Award at the
2019 IEEE International Conference on Signal, Information and Data Processing.
---|---
|  Zhimeng Zhang received Ph.D. degree from the College of Computer Science
and Technology, Zhejiang University in 2004. He completed postdoctoral career
in system control from Zhejiang University in 2011. Since 2004, he has been
teaching software development courses for master students in software
engineering. From 2006, he has instructed more than 200 master students in the
School of Software Technology, Zhejiang University.
---|---
|  Yongheng Wang received his PhD degree in computer science and technology
from National University of Defense Technology, Changsha, China, in 2006.
Currently he is a research specialist at the research center of Big data
intelligence, Zhejiang Lab. His research interest covers Big data analysis,
machine learning, computer simulation and intelligent decision making.
---|---
|  Chao Wu is a tenure-track associate professor at the School of Public
Affairs, Zhejiang University and the director of Computational Social Science
Research Center in Zhejiang University. He is also an honorary Research Fellow
at The Department of Computer Science, Imperial College London. His research
interests include federated learning and distributed machine learning, data
privacy protection and data pricing, and computational social sciences. He has
published more than 60 papers in international conferences and journals, and
presided over many scientific research projects including the key projects of
the National Natural Science Foundation of China.
---|---

##  Appendix A Proof of Theorem 1 and Corollary 1

###  A.1 Proof of Theorem 1

Under Assumption 2, the similarity metrics are effective enough that all the
true neighbors will have higher similarities than the false neighbors.
Therefore if there are at least $k$ true neighbors in the $l$ neighbor
candidates, the top $k$ peers with maximum similarities must be true. As a
result, we can formulate the problem of all the top $k$ neighbors being true
into the “Ball Selection Problem”, as follows.

Ball Selection Problem: There are $n-1$ balls in the box and $a-1$ of them are
white balls. Select $l$ balls at one time without replacement. For the
selected $l$ balls, solve:
(1) the probability that at least $k$ balls are white balls.
Conducting the selection for the first time and note down the number of white
balls as $s_{1}$. Conducting the selection for the second time and note down
the number of white balls as $s_{2}$. …. Conducting the selection for the
$t$-th time and note down the number of white balls as $s_{t}$. Solve:
(2) the probability that $\sum\limits_{c=1}^{t}s_{c}\geq k$.

Question (1) in the “Ball Selection Problem” is equivalent to the problem that
for client $i$, randomly sampling $l$ clients, solve the probability that at
least $k$ peers are true. Question (2) in “Ball Selection Problem” is
equivalent to the problem that for client $i$, conducting NSMC strategy for
$t$ rounds, solve the probability that all the $k$ neighbors in round $t$ are
true.

We further calculate the probabilities in Questions (1) and (2). We define the
probability that select $l$ balls and $x$ of them are white balls as a
function ${\rm G}(x)$ and the probability that select $l$ balls and at least
$x$ of them are white balls as function ${\rm R}(x)$.

First, we give the calculation of ${\rm G}(x)$. All possible cases are: from
all $n-1$ balls to select $l$ balls, as $C_{n-1}^{l}$. The cases satisfying
our condition are: from $a-1$ white balls to select $x$ balls while from other
$n-a$ balls to select $l-x$ balls, as $C_{a-1}^{x}\cdot C_{n-a}^{l-x}$. The
equation is as follows.

$\small\begin{split}{\rm G}(x)=&\frac{C_{a-1}^{x}\cdot
C_{n-a}^{l-x}}{C_{n-1}^{l}}\\\
=&\bigg{[}\frac{(a-1)!}{x!(a-x-1)!}\cdot\frac{(n-a)!}{(l-x)!(n-a-
l-x)!}\bigg{]}\bigg{/}\\\ &\bigg{[}\frac{(n-1)!}{l!(n-l-1)!}\bigg{]}\\\
=&\frac{l!(a-1)!(n-a)!(n-l-1)!}{x!(n-1)!(l-x)!(a-x-1)!(n-a-l+x)!}.\end{split}$
(22)

Then, we give the calculation of ${\rm R}(x)$. All possible cases are: from
all $n-1$ balls to select $l$ balls, as $C_{n-1}^{l}$. The number of white
balls satisfying our condition ranges from $x$ to $l$, so the cases satisfying
our condition are: $x$ white balls and $l-x$ other balls, $x+1$ white balls
and $l-x-1$ other balls, …, $l-1$ white balls and $1$ other balls, $l$ white
balls and $0$ other ball. Thus the equation is as follows.

$\small\begin{split}{\rm R}(x)=&\big{(}C_{a-1}^{x}\cdot
C_{n-a}^{l-x}+C_{a-1}^{x+1}\cdot C_{n-a}^{l-x-1}+\dots+C_{a-1}^{l-1}\cdot
C_{n-a}^{1}+\\\ &C_{a-1}^{l}\cdot C_{n-a}^{0}\big{)}\big{/}C_{n-1}^{l}\\\
=&\Bigg{[}\sum\limits_{s=0}^{l-x}\frac{(a-1)!}{(l-s)!(a-l+s-1)!}\cdot\frac{(n-a)!}{s!(n-a-s)!}\Bigg{]}\bigg{/}\\\
&\bigg{[}\frac{(n-1)!}{l!(n-l-1)!}\bigg{]}\\\
=&{\frac{l!(n-l-1)!}{(n-1)!}\sum\limits_{s=0}^{l-x}\frac{(a-1)!(n-a)!}{s!(l-s)!(n-a-s)!(a-l+s-1)!}}\\\
.\end{split}$ (23)

Obviously, for Question (1), the probability is ${\rm P}^{1}(k)={\rm R}(k)$.
Then, we consider the scenario where $t=2$ in Question (2). All the satisfying
cases are: none of the white balls is selected in the first time and at least
$k$ white balls are selected in the second time, 1 white ball is selected in
the first time and at least $k-1$ white balls are selected in the second
time,…, $k-1$ white balls are selected in the first time and at least $1$
white balls are selected in the second time, at least $k$ white balls are
selected in the first time and it does not matter how many white balls are
selected in the second time. Therefore, the equation is as follows.

$\small\begin{split}{\rm P}^{2}(k)=&{\rm G}(0)\cdot{\rm R}(k)+{\rm
G}(1)\cdot{\rm R}(k-1)+\dots+{\rm G}(k-1)\cdot\\\ &{\rm R}(1)+{\rm
R}(k).\end{split}$ (24)

Similar to Equation (24), we can infer the satisfying cases when $t=t$: none
of the white balls is selected in the first time and at least $k$ white balls
are selected in the remaining $t-1$ times, 1 white ball is selected in the
first time and at least $k-1$ white balls are selected in the remaining $t-1$
times,…, $k-1$ white balls are selected in the first time and at least $1$
white balls are selected in the remaining $t-1$ times, at least $k$ white
balls are selected in the first time and it does not matter how many white
balls are selected in the remaining $t-1$ times. The equation is as follows.

$\small\begin{split}{\rm P}^{t}(k)=&{\rm G}(0)\cdot{\rm P}^{t-1}(k)+{\rm
G}(1)\cdot{\rm P}^{t-1}(k-1)+\dots+{\rm G}(k-1)\cdot\\\ &{\rm P}^{t-1}(1)+{\rm
R}(k)\\\ =&\sum\limits^{k-1}_{m=0}{\rm G}(m){\rm P}^{t-1}(k-m)+{\rm R}(k)\\\
=&{\rm G}(k)\ast{\rm P}^{t-1}(k)+{\rm R}(k),\end{split}$ (25)

where ${\rm G}(k)\ast{\rm P}^{t-1}(k)=\sum\limits^{k-1}_{m=0}{\rm G}(m){\rm
P}^{t-1}(k-m)$.

For the first stage of PENS, neighbor selection in each round is independent,
so the probability remains unchanged in all rounds, we have

${\rm P}^{t}(k)\equiv{\rm R}(k).$ (26)

###  A.2 Proof of Corollary 1

Function ${\rm Q}(t)$ is defined as ${\rm Q}(t)={\rm
P}^{t}(k),t\in\\{1,\dots,T\\}$. To prove Corollary 1, we need to prove ${\rm
Q}(t)-{\rm Q}(t-1)>0,t\in\\{2,\dots,T\\}$. We use Mathematical Induction
method to prove the corollary.

Step 1: ${\rm Q}(t)-{\rm Q}(t-1)>0$ is satisfied when $t=2$, because

$\begin{split}{\rm Q}(2)-{\rm Q}(1)=&{\rm P}^{2}(k)-{\rm P}^{1}(k)\\\ =&{\rm
G}(k)\ast{\rm P}^{1}(k)+{\rm R}(k)-{\rm R}(k)\\\ =&{\rm G}(k)\ast{\rm
P}^{1}(k)>0.\end{split}$ (27)

Step 2: Assume ${\rm Q}(t)-{\rm Q}(t-1)>0$ when $t=t$, we now prove ${\rm
Q}(t+1)-{\rm Q}(t)>0$ when $t=t+1$.

$\begin{split}&{\rm Q}(t+1)-{\rm Q}(t)\\\ =&{\rm P}^{t+1}(k)-{\rm P}^{t}(k)\\\
=&{\rm G}(k)\ast{\rm P}^{t}(k)+{\rm R}(k)-({\rm G}(k)\ast{\rm P}^{t-1}(k)+{\rm
R}(k))\\\ =&{\rm G}(k)\ast{\rm P}^{t}(k)-{\rm G}(k)\ast{\rm P}^{t-1}(k)\\\
=&\sum\limits^{k-1}_{m=0}{\rm G}(m){\rm
P}^{t}(k-m)-\sum\limits^{k-1}_{m=0}{\rm G}(m){\rm P}^{t-1}(k-m)\\\
=&\sum\limits^{k-1}_{m=0}{\rm G}(m)[{\rm P}^{t}(k-m)-{\rm
P}^{t-1}(k-m)].\end{split}$ (28)

We have ${\rm Q}(t)-{\rm Q}(t-1)>0$, further

${\rm Q}(t)-{\rm Q}(t-1)={\rm P}^{t}(k)-{\rm P}^{t-1}(k)>0.$ (29)

Therefore,

${\rm P}^{t}(k-m)-{\rm P}^{t-1}(k-m)>0,\ k>m.$ (30)

Together with Equation (28) and (30), we can infer

${\rm Q}(t)-{\rm Q}(t-1)>0.$ (31)

Step 3: Based on Step 1 and 2, we can draw the conclusion that

${\rm Q}(t)-{\rm Q}(t-1)>0,\ \forall t\in\\{2,\dots,T\\}$ (32)

Then, the proof is completed.

##  Appendix B Proof of Theorem 2 and Theorem 3

###  B.1 Proof of Theorem 2

In a P2P FL system, each client communicates with his neighbors and averages
the models received from the neighbors. For algorithms like PANM and PENS, the
communicated neighbors change in each round. This system is complex because
your model’s performance is not only affected by your neighbors (first-order
neighbors) but also your neighbors’ neighbors (second-order neighbors),
$\cdots$. The changing neighbor relationships and the complexity of
information flow make the convergence of each client intractable.

Thus, to make this problem tractable, we only consider the first-order
neighbors’ impacts and analyze from client perspective. For client
$i,i\in[n]$, we view it as the central server and only consider the neighbor
communication and model averaging process (without the local training
process). And for other clients, we only consider the local training process
and assume their local models are downloaded from client $i$ in each round,
ignoring their gossip communications. This simplification means that for a
given client, we only consider the impact of its first-order neighbors, and
the convergence and performance rely on selecting these neighbors. It is
reasonable in the theoretical analysis since the first-order neighbors have
the most dominant impacts, and when the orders of neighbors are higher, the
impacts are much weaker.

Without loss of generality, we analyze client 1, which belongs to cluster 1,
and the analysis is general to all clients. Recall that the optimal model of
cluster 1 is denoted as $\mathbf{w}_{1}^{*}$, for a certain round, client 1’s
model is $\mathbf{w}_{1}$, and its next-round model is $\mathbf{w}_{1}^{+}$.
For simplicity, in the analysis, we omit the superscript $t$, which indicates
the communication round. We consider the error gap between the optimum
$\mathbf{w}_{1}^{*}$ and the next-round model $\mathbf{w}_{1}^{+}$.

$\|\mathbf{w}_{1}^{+}-\mathbf{w}_{1}^{*}\|=\|\underbrace{\mathbf{w}_{1}-\mathbf{w}_{1}^{*}-\frac{\eta}{k}\sum_{i\in{\rm
N}_{1}\cap{\rm N}_{1}^{*}}\nabla
F_{i}(\mathbf{w}_{1})}_{T_{1}}-\underbrace{\frac{\eta}{k}\sum_{i\in{\rm
N}_{1}\cap\overline{{\rm N}_{1}^{*}}}\nabla F_{i}(\mathbf{w}_{1})}_{T_{2}}\|,$

where $\eta$ is the learning rate and $k~{}(k=|{\rm N}_{1}|)$ is the number of
aggregation neighbors. We use the triangle inequality and obtain

$\|\mathbf{w}_{1}^{+}-\mathbf{w}_{1}^{*}\|\leq\|T_{1}\|+\|T_{2}\|.$ (33)

In Equation 33, $\|T_{1}\|$ is the term including the gradients of true
neighbors and $\|T_{2}\|$ is the term about the gradients of false neighbors.
We bound $\|T_{1}\|$ and $\|T_{2}\|$ respectively.

Bound $\|T_{1}\|$ Recall that $\epsilon=\frac{|{\rm N}_{1}\cap\overline{{\rm
N}_{1}^{*}}|}{|{\rm N}_{1}|}$.

$\begin{split}T_{1}=&\underbrace{\mathbf{w}_{1}-\mathbf{w}_{1}^{*}-\eta(1-\epsilon)\nabla
F^{1}(\mathbf{w}_{1})}_{T_{11}}\\\ &+\underbrace{\eta(1-\epsilon)\Big{(}\nabla
F^{1}(\mathbf{w}_{1})-\frac{1}{k(1-\epsilon)}\sum_{i\in{\rm N}_{1}\cap{\rm
N}_{1}^{*}}\nabla F_{i}(\mathbf{w}_{1})\Big{)}}_{T_{12}}\end{split}$

We assume $\eta\leq\frac{1}{L}$, thus $\eta(1-\epsilon)\leq\frac{1}{L}$.
According to standard analysis techniques for gradient descent on strongly
convex functions, we know that

$\begin{split}\|T_{11}\|&=\|\mathbf{w}_{1}-\mathbf{w}_{1}^{*}-\eta(1-\epsilon)\nabla
F^{1}(\mathbf{w}_{1})\|\\\ &\leq\left(1-\frac{\mu
L\eta(1-\epsilon)}{\mu+L}\right)\|\mathbf{w}_{1}-\mathbf{w}_{1}^{*}\|.\end{split}$

Further, we have
$\mathbb{E}\left[\|T_{12}\|^{2}\right]=\frac{v^{2}}{dk(1-\epsilon)}$, which
implies that
$\mathbb{E}\left[\|T_{12}\|\right]=\frac{v}{\sqrt{dk(1-\epsilon)}}$.

Therefore, the bound of $\|T_{1}\|$ is

$\|T_{1}\|\leq\left(1-\frac{\mu
L\eta(1-\epsilon)}{\mu+L}\right)\|\mathbf{w}_{1}-\mathbf{w}_{1}^{*}\|+\frac{v}{\sqrt{dk(1-\epsilon)}}.$
(34)

Bound $\|T_{2}\|$ We define $T_{2j}\coloneqq\sum_{i\in{\rm N}_{1}\cap{\rm
N}_{j}^{*}}\nabla F_{i}(\mathbf{w_{1}}),j\geq 2,j\in[r]$, which refers to the
sum gradients of the neighbors which belong to cluster $j$. Thus, we have
$T_{2}=\frac{\eta}{k}\sum_{j=2}^{r}T_{2j}$. For $T_{2j}$, we have

$T_{2j}=|{\rm N}_{1}\cap{\rm N}_{j}^{*}|\nabla
F^{j}(\mathbf{w}_{1})+\sum_{i\in{\rm N}_{1}\cap{\rm N}_{j}^{*}}\left(\nabla
F_{i}(\mathbf{w}_{1})-\nabla F^{j}(\mathbf{w}_{1})\right).$

Due to the smoothness of $F^{j}(\mathbf{w})$, we know that

$\begin{split}\|\nabla F^{j}(\mathbf{w}_{1})\|&\leq
L\|\mathbf{w}_{1}-\mathbf{w}_{j}^{*}\|=L\|\mathbf{w}_{1}-\mathbf{w}_{1}^{*}+\mathbf{w}_{1}^{*}-\mathbf{w}_{j}^{*}\|\\\
&\leq
L(\|\mathbf{w}_{1}-\mathbf{w}_{1}^{*}\|+\|\mathbf{w}_{1}^{*}-\mathbf{w}_{j}^{*}\|)\\\
&\leq L(\|\mathbf{w}_{1}-\mathbf{w}_{1}^{*}\|+\Delta).\end{split}$

Additionally, according to the bounded variance of gradients, we have

$\begin{split}&\mathbb{E}\left[\|\sum_{{\rm N}_{1}\cap{\rm
N}_{j}^{*}}\left(\nabla F_{i}(\mathbf{w}_{1})-\nabla
F^{j}(\mathbf{w}_{1})\right)\|^{2}\right]=|{\rm N}_{1}\cap{\rm
N}_{j}^{*}|\frac{v^{2}}{d},\\\ &\mathbb{E}\left[\|\sum_{{\rm N}_{1}\cap{\rm
N}_{j}^{*}}\left(\nabla F_{i}(\mathbf{w}_{1})-\nabla
F^{j}(\mathbf{w}_{1})\right)\|\right]=\sqrt{|{\rm N}_{1}\cap{\rm
N}_{j}^{*}|}\frac{v}{\sqrt{d}}.\end{split}$

Summing up, the bound for $\|T_{2}\|$ is

$\|T_{2}\|=\frac{\eta}{k}\|\sum_{j=2}^{r}T_{2j}\|\leq\eta
L\epsilon\|\mathbf{w}_{1}-\mathbf{w}_{j}^{*}\|+\eta
L\Delta\epsilon+\frac{v\eta\sqrt{r}}{\sqrt{dk}}\sqrt{\epsilon}.$ (35)

Combining Equations 33, 34 and 35, we can have a bound for
$\|T_{1}\|+\|T_{2}\|$

$\begin{split}\|\mathbf{w}_{1}^{+}-\mathbf{w}_{1}^{*}\|\leq&\left(1-\frac{\mu
L\eta(1-\epsilon)}{\mu+L}+\eta
L\epsilon\right)\|\mathbf{w}_{1}-\mathbf{w}_{j}^{*}\|\\\ &+\eta
L\Delta\epsilon+\frac{v}{\sqrt{dk}}\frac{1}{\sqrt{1-\epsilon}}+\frac{v\eta\sqrt{r}}{\sqrt{dk}}\sqrt{\epsilon}.\end{split}$
(36)

The proof is completed.

###  B.2 Proof of Theorem 3

We set the learning rate $\eta=\frac{1}{L}$, assume $\mu=L$ and define the
initial error gap is defined as $\delta_{0}=\|\mathbf{w}\|$. According to
Theorem 2, we can have

$\|\mathbf{w}_{1}^{+}-\mathbf{w}_{1}^{*}\|\leq(\frac{1+3\epsilon}{2})\|\mathbf{w}_{1}-\mathbf{w}_{1}^{*}\|+\Delta\epsilon+\frac{v}{\sqrt{dk}}\frac{1}{\sqrt{1-\epsilon}}+\frac{v}{L}\sqrt{\frac{r}{kd}}\sqrt{\epsilon}.$

For PANM, the initial $\epsilon_{0}={\rm R}(k)$, thus, for the first round, we
have

$\begin{split}\|\mathbf{w}_{1}^{1}-\mathbf{w}_{1}^{*}\|&\leq(\frac{1+3\epsilon_{0}}{2})\|\mathbf{w}_{1}^{0}-\mathbf{w}_{1}^{*}\|+\Delta\epsilon_{0}+\frac{v}{\sqrt{dk}}\frac{1}{\sqrt{1-\epsilon_{0}}}+\frac{v}{L}\sqrt{\frac{r\epsilon_{0}}{kd}}\\\
&=(\frac{1+3\epsilon_{0}}{2})\delta_{0}+\Delta\epsilon_{0}+\frac{v}{\sqrt{dk}}\frac{1}{\sqrt{1-\epsilon_{0}}}+\frac{v}{L}\sqrt{\frac{r}{kd}}\sqrt{\epsilon_{0}}\end{split}$
(37)

According to Theorem 1, in the first stage of PANM, it will have a decreasing
$\epsilon$, and the decreasing speed is very fast. As a result, we only
consider $\epsilon_{0}$ and for $T\geq 1$, we assume $\epsilon\rightarrow 0$.
When $\epsilon\rightarrow 0$, we have

$\|\mathbf{w}_{1}^{+}-\mathbf{w}_{1}^{*}\|\leq\frac{1}{2}\|\mathbf{w}_{1}-\mathbf{w}_{1}^{*}\|+\frac{v}{dk}.$

Summing the error gaps over rounds, we can have the error bound for the first
stage of PANM, as

$\begin{split}\|\mathbf{w}_{1}^{T}-\mathbf{w}_{1}^{*}\|&\leq\frac{1}{2^{T-1}}{\Bigg{[}}\frac{1+3\epsilon_{0}}{2}\delta_{0}+\epsilon_{0}\Delta+\frac{v}{\sqrt{dk(1-\epsilon_{0})}}\\\
&+\frac{v}{L}\sqrt{\frac{r\epsilon_{0}}{kd}}\Bigg{]}+\sum_{t=0}^{T-2}\frac{1}{2^{t}}\frac{v}{\sqrt{dk}},\end{split}$
(38)

where $\epsilon_{0}={\rm
R}(k)=\small{\frac{l!(n-l-1)!}{(n-1)!}\sum\limits_{s=0}^{l-k}\frac{(a-1)!(n-a)!}{s!(l-s)!(n-a-s)!(a-l+s-1)!}}$.