# Pinning control of social fairness in the Ultimatum game

Guozhong Zheng  School of Physics and Information Technology, Shaanxi Normal
University, Xi’an 710061, P. R. China  Jiqiang Zhang  School of Physics and
Electronic-Electrical Engineering, Ningxia University, Yinchuan 750021, P. R.
China  Zhenwei Ding  School of Physics and Electronic-Electrical Engineering,
Ningxia University, Yinchuan 750021, P. R. China  Lin Ma  School of Physics
and Information Technology, Shaanxi Normal University, Xi’an 710061, P. R.
China  Li Chen<EMAIL_ADDRESS>School of Physics and Information
Technology, Shaanxi Normal University, Xi’an 710061, P. R. China

###### Abstract

Decent social fairness is highly desired for both socio-economic activities
and individuals, as it is one of the cornerstones of the social welfare and
sustainability. How to effectively promote the level of fairness thus becomes
a significant issue to be addressed. Here, by adopting a pinning control
procedure, we find that when a very small fraction of individuals ($\sim 3\%$)
are pinned to be fair players in the Ultimatum Game, the whole population
unexpectedly evolves into the full fairness level. This leverage effect is
robust to the underlying structures of the population, the process is
generally in the form of first-order phase transition for homogeneous networks
($1d$ lattice and Erdős-Rényi random networks) and the well-mixed population
as the number of pinning individuals increases. For heterogeneous networks
(e.g. scale-free networks), however, one hub node is sufficient for the aim,
and even the on-off control procedure can be applied to further reduce the
control cost. Intermittent failures are seen in the latter case, our
statistical analysis indicates the evolution shows some sort of criticality.
Our work suggests that the pinning control procedure could potentially be a
good strategy to promote the social fairness for some real scenarios when
necessary.

##  I 1\. Introduction

In his bestseller, _Capital in the Twenty-first Century_ Piketty (2014),
Thomas Piketty reported that half of the wealth is owned by the top one
percent of the population globally, and the bottom 70% only owns 3% of the
wealth. The concern of inequality or social unfairness has been so far
attracting many attentions from economists, political scientists, to
psychologists, and even physicists. The key questions to be addressed are:
what are the mechanisms for the fairness emergence, and how to improve the
level of fairness for those unsatisfactory scenarios.

Most previous studies of fairness are based upon the Ultimatum game (UG) model
Güth  _et al._ (1982). Two persons are to divide a sum of money, and they act
as the role of proposer and responder respectively. The proposer first
proposes an allocation plan, and the responder chooses either to agree or
reject. If the agreement is reached, the money will be divided according to
the plan; otherwise both get nothing.

Within the paradigm of _Homo economicus_ Solow and Simon (1957); Samuelson and
Nordhaus (2005), people are interest maximizers, a low fairness outcome is
expected in the UG. Since “something is better than nothing”, the responder
will accept any small amount of money; with this knowledge, the proposer
should propose the smallest possible offer to the responder to keep the
largest amount to her/his own interest. Fortunately, a lot of behavior
experiments have revealed that we humans have a remarkable preference for
fairness. When playing the UG, most offers are between 40% and 50% of the
total amount, and very few offers are below 20% that will be rejected by
responders with more than half a chance Güth  _et al._ (1982); Thaler (1988);
Bolton and Zwick (1995); Kagel and Roth (1995); Güth and Kocher (2014).
Evidences in non-human species also support this observation Brosnan and de
Waal (2003); Proctor  _et al._ (2013).

Different mechanisms are later proposed to understand the emergence of
fairness. One theoretical finding is that once the population is structured,
the fairness level is better than the well-mixed case that was extensively
studied before Page and Sigmund (2000); Kuperman and Risau-Gusman (2008);
Sinatra  _et al._ (2009). Besides, the factors of fame and reputation Nowak
_et al._ (2000); Andre and Baumard (2011), empathy Sanchez and Cuesta (2005);
Page and Nowak (2002), and noise Binmore and Samuelson (1994); Gale  _et al._
(1995) are also found to have potentially important impacts on the evolution
of fairness. While quite a few studies aim to decipher the mechanism behind
fairness emergence, much less effort has been seen to improve it when the
level of fairness is unsatisfactory. Undoubtedly, there are a lot of examples
of unfair divisions where the promotion of fairness is highly desired.

Figure 1: (Color online) The evolution of fairness on the $1d$ lattice. (a)
Phase transition of the average offer $\langle p\rangle$ versus the number of
pinned individuals $N_{p}$, a first-order phase transition can be observed.
There are $100$ realizations for each $N_{p}$, $t=10^{6}$ where the steady
states are expected. (b) The probability density distribution (PDF) of
$\langle p\rangle$ within the bistable region, the curves present clear
bimodal distributions. (c) A hysteresis structure by changing $N_{p}$ in
different directions with a ramp rate of $1/2\times 10^{-5}$ per step. Time
average has been computed over $2\times 10^{6}$ time steps. The red and the
black lines respectively correspond to the scenarios of increasing and
decreasing $N_{p}$. Parameters: $N=1000$, $K=40$.

In our work, we try to promote the level of fairness from the control point of
view, specifically, we will adopt the pinning control procedure. Originally,
it is derived from the pinning effect in condensed matter physics Di Vece  _et
al._ (2005), but later it is widely applied to a variety of contexts,
including the turbulence Tang and Hu (2006), plasma instability, reaction-
diffusion systems Wang  _et al._ (2016), synchronization on complex networks
Sorrentino  _et al._ (2007); Yu  _et al._ (2013, 2009); Jin  _et al._ (2008),
as well as the problem of resource allocation optimization Zhang  _et al._
(2013, 2016), etc. The general idea behind this is that by pinning only a
small number of individuals, the impact will disproportionately drive the
whole system to the target states.

Specifically, we apply the method of pinning control to the UG model, starting
from the one-dimensional lattice network, by pinning a small number of
individuals to be fair players, we succeed in achieving a high level of
fairness for the population as a whole. We find that with the increasing
number of pinned individuals, the fairness level shows a first-order phase
transition, which is confirmed by the corresponding bimodal curve distribution
and the hysteresis loop. In addition, we verify the results on two different
networks. The key issue for pinning control is: How many nodes need to be
pinned? Furthermore, for those heterogeneous networks, which nodes should be
selected for the optimal control effect? These are the specific questions that
need to be addressed.

The paper is organized as follows: we introduce our model in Sec. 2II. In Sec.
3III we show results for the population with 1d lattice, Erdős-Rényi random
networks and well-mixed structures. In Sec. 4IV, Barabási-Albert scale-free
networks are also examined to study the impact of the structural
heterogeneity. Finally, we conclude and discuss our work in Sec. 5V.

##  II 2\. Model

We consider a population of $N$ individuals playing the Ultimatum Game, they
could either be well-stirred or structured in some certain manners that will
be specified later on. As a rule of thumb Güth  _et al._ (1982); Debove  _et
al._ (2016), the sum of the amounts of money to be divided is set to be the
unity. The strategy for player $i$ is given by $S_{i}\\!=\\!(p_{i},q_{i})$,
where $p_{i}$ is the _offer_ when acting as a proposer and $q_{i}$ is the
_acceptance threshold_ when acting as a responder. Obviously,
$p_{i},q_{i}\in[0,1]$, usually their initial values are chosen randomly in
that range.

Now, when two players $i,j$ encounter each other and assume they are in the
role of proposer and responder with equal chance, the expected payoff for
player $i$ versus $j$ is as follows

$\pi_{ij}=\left\\{\begin{array}[]{lr}1-p_{i}+p_{j},\quad\quad\mbox{if}\
p_{i}\geqslant q_{j}\ \mbox{and}\ p_{j}\geqslant q_{i},\\\
1-p_{i},\quad\quad\quad\quad\,\mbox{if}\ p_{i}\geqslant q_{j}\ \mbox{and}\
p_{j}<q_{i},\\\ p_{j},\quad\quad\quad\quad\quad\;\;\>\mbox{if}\
p_{i}<q_{j}\>\mbox{and}\ p_{j}\geqslant q_{i},\\\
0,\quad\quad\quad\quad\quad\;\;\>\>\,\mbox{if}\ p_{i}<q_{j}\ \mbox{and}\
p_{j}<q_{i}.\\\ \end{array}\right.$ (1)

At the very beginning, $N_{p}$ individuals are randomly selected as the
pinning sites, they will stick to the fair strategy
$S_{h}\\!\equiv\\!(p_{h},q_{h})$ with $p_{h}\\!=\\!q_{h}\\!=\\!C_{h}=0.5$
throughout the evolution. This “irrational” behavior may happen when they are
supported financially by external parties like the government or for other
incentives Colin F. Camerer and Rabin (2003); Loewenstein and Lerner (2003);
Sanfey  _et al._ (2003); Rilling and Sanfey (2011). The rest $N-N_{p}$ players
evolve according to the following synchronous updating rules.

These players are initially assigned with a random strategy $p_{i},q_{i}$
uniformly and independently in the range between 0 and 1. Next, each player
interacts with all their nearest-neighbors, obtains their payoffs according to
the Eq.(1), and sums them up $\pi_{i}=\sum_{j\in\Omega_{i}}\pi_{ij}$, where
$\Omega_{i}$ denotes the neighborhood of player $i$. Finally, the reproduction
of strategy is linearly proportional to the payoffs in the neighborhood, each
player updates its strategy according to the Moran update rule Roca  _et al._
(2009)

$w(S_{j}\rightarrow
S_{i})=\frac{\pi_{j}}{\sum_{j\in\Omega^{\prime}_{i}}\pi_{j}},$ (2)

where $w(S_{j}\rightarrow S_{i})$ is the probability that player $i$ imitates
the strategies in its neighborhood, including itself
($\Omega^{\prime}_{i}=\Omega_{i}\cup\\{i\\}$). To this end, all imitations are
subject to a small noise $p_{i}=p_{j}+\delta p$ and $q_{i}=q_{j}+\delta q$,
where $(\delta p,\delta q)\in[-\varepsilon,\varepsilon]$, and we set
$\varepsilon=0.001$.

To measure population fairness level, we calculate the average offer $\langle
p\rangle$ and the average acceptance level $\langle q\rangle$ of the
population as order parameters. When $(\langle p\rangle,\langle q\rangle)$
approaches $(0.5,0.5)$, i.e. $S_{h}$, the population reaches the ideal half-
half split, which is always desired. It’s worth mentioning that the value of
$q_{i}$ is almost always slightly smaller than $p_{i}$ in the long run, we
thus only focus on the evolution of the offer $\langle p\rangle$ to avoid
redundancy.

Obviously, when $N_{p}=0$, our model is then reduced to the classic model
Kuperman and Risau-Gusman (2008) that has been extensively studied previously;
but when $N_{p}\rightarrow N$, the high fairness level $S_{h}$ can be
trivially expected. We are primarily interested in the following questions: Is
it possible to promote overall fairness by pinning very few individuals? and
if yes, what fraction is needed?

Figure 2: The probability density distribution of payoff on 1d lattice within
the bistable region for two different realizations. (a) and (b) are for
scenarios where the high fairness state is unsuccessfully and successfully
reached, respectively. The solid/open points correspond to the pinned/unpinned
individuals. Parameters: $N_{p}\\!=\\!30$, $N=1000$, and the degree $k=40$.

##  III 3\. Results

###  III.1 3.1. Lattices

We first report the numerical results of the 1-dimensional lattice population
with $N=1000$, each is connected to $K/2$ neighbors on either side, where the
degree $K=40$ in our study. Fig. 1(a) shows the average offer $\langle
p\rangle$ in different realizations for a different number of pinning
individuals. In the absence of pinning control $N_{p}=0$, individuals are only
willing to offer $10\%\sim 20\%$ share to their partners on average, denoted
as the typical low fairness strategy $S_{l}$, which is consistent with
previous studies Kuperman and Risau-Gusman (2008). A gradual increase of
$N_{p}(<15)$ only slightly improves the value of $\langle p\rangle$.
Interestingly, a further increase in $N_{p}$ potentially leads to a sudden
jump into the half-half split state — the fully fair state $S_{h}$. But in
some other realizations, the population could still stay in the low fairness
state $S_{l}$. The fairness of the population is in a bistable state when
$15\lesssim N\lesssim 50$. When $N_{p}\gtrsim 50$, the evolution in all
implementations goes to the full fairness state $S_{h}$ irrespective of the
initial conditions. That means, the level of fairness presents a first-order
phase transition as the number of pinning sites increases.

To understand the bistability, the probability density distribution of the
order parameter $\langle p\rangle$ within the bistable interval is calculated,
shown in Fig. 1(b). The typical bimodal structure can be seen, and with the
increase of $N_{p}$, the low fairness peak shrinks, and the other peak around
$\langle p\rangle=0.5$ rises as expected. Furthermore, a hysteresis loop is
also shown in Fig. 1(c), where the evolution of the fairness state depends on
the history. These observations strengthen the first-order nature of phase
transition.

From the practice point of view, the pinning control might need financial
support externally, it’s natural to ask what’s the difference between pinned
and unpinned individuals in terms of payoffs, since this is directly related
to how much cost is needed. Thus, we provide the PDF of their payoffs
respectively for both unsuccessfully and successfully pinned to the high
fairness state, in Fig. 2(a) and (b). When failed to approach the target
state, Fig. 2(a) shows that the payoffs of pinned players are significantly
lower than unpinned on average, additional cost might be needed to compensate
for their loss. But once the fairness state is reached, the two payoffs are
very close, no more cost is required afterwards.

As to why the pinning control works, the mechanism is largely the same as our
previous work Zheng  _et al._ (2022). Physically, the dynamical process
similar to a nucleation phenomenon in the phase transition of matter states
Stanley (1987), where the pinned sites act as nucleation cores. Once some fair
clusters are formed and grow successfully at the initial stage, they merge
with each other till the whole population is in a single group. But, if the
initial growth does not happen, the clusters around these pinned sites cannot
reach each other, no coalition is expected and the majority of the population
is in a low fairness state. A mean-field theory based on the replicator
equation Taylor and Jonker (1978); Roca  _et al._ (2009) is developed in ref.
Zheng  _et al._ (2022) that captures the physical picture and is also
applicable here.

Figure 3:  (Color online) The average offer level $\langle$p$\rangle$ versus
the number of randomly selected pinned individuals $N_{p}$ on ER networks at
$t=10^{6}$. The inset is a hysteresis loop, conducted in the same way as in
Fig. 1(c). Parameters: $N=1000$, the average degree $\langle k\rangle=4$.

###  III.2 3.2. Erdős-Rényi random networks

To verify whether the above observations of fairness promotion are dependent
on the underlying structures of the population, we also examine two complex
topologies: Erdős-Rényi (ER) random networks Bollobás (2001) and Barabási-
Albert (BA) scale-free networks Barabási and Albert (1999), which represents
the typical homogeneous and heterogeneous networks, respectively.

Figure 4: (Color online) The evolution of fairness on BA scale-free networks.
Typical time series of $\langle$p$\rangle$ and $\langle$q$\rangle$ by either
randomly pinning $N_{p}$=30 nodes (a), or the largest hub (c); we see both
reach the high fairness state, but strong fluctuations are present in (a). (b)
Continuous transition of $\langle$p$\rangle$ and $\langle$q$\rangle$ are shown
versus the number of randomly pinning nodes $N_{p}$. The error bars are
standard deviations of the time series after the transient. (d) The minimal
number $m$ of pinned nodes required to achieve the fair state versus the
nodes’ degree $k$, a power law is approximated as $m\sim k^{-1}$. Parameters:
$N=1000$, $\langle$k$\rangle=4$.

Fig. 3 provides the results on ER networks, with the same network size as
above and the average degree $\langle k\rangle=4$. We see that the dependence
of $\langle p\rangle$ on the number of randomly selected pinning sites $N_{p}$
also exhibits a first-order phase transition, where the bistable region is
$15\lesssim N\lesssim 80$, a bit wider than the lattice case as in Fig. 1(a).
A hysteresis loop in the inset of Fig. 3 indicates that the bistable interval
is even wider ($15\lesssim N\lesssim 100$) than the main plot. This is because
the initial condition in the inset are starting from either all low fair
players or all high fair players, whereas the random initial conditions are
used in the main plot. Therefore, more pinning players are needed to jump into
the fair state when the majority are in $S_{l}$, and less are required to
sustain this state once $S_{h}$ is reached.

Together with the findings in the lattice case, our study shows that the
first-order phase transition for the pinning control is robust in the
homogeneously structured population, the remarkable leverage effect is
revealed by pinning only a small fraction of individuals. In fact, we also
find that even in the well-mixed population, qualitatively the same results
are seen (see AppendixB A).

##  IV 4\. Scale-free networks

The population structures studied in the previous two sections are essentially
homogeneous. In the real world, however, the underlying topologies are often
heterogeneous, where the connectivities for different individuals could be
very different. Therefore, apart from the question of how many individuals are
needed to be pinned, the selection of pinning nodes for the optimal control is
another issue to be addressed.

Fig. 4(a) provides an example that when $3\%$ nodes are pinned in a random
manner, the population evolves into a high fairness state on average, though
intermittent failures are also seen. Fig. 4(b) shows that when the pinning
sites are chosen randomly, the fairness transition now becomes smooth, not in
the first-order phase transition anymore as in the homogeneous networks. It
shows that when less than 30 individuals ($3\%$ of the population) are pinned,
the average level of fairness approaches 0.5. A larger pinning percentage
further stabilizes the fairness level.

Quite unexpectedly, when only one hub with the largest degree is pinned, the
fairness is rapidly pinned to $S_{h}$ and is very stable, see Fig. 4(c). In
numerical experiments, we find that even if the population size is increased
up to $10^{4}$, pinning the largest hub is still sufficient to drive the whole
population to the high fairness state. To reduce the control cost, we don’t
even need to pin the largest hub continuously; e.g. a periodic on-off control
procedure can sustain the fair state $S_{h}$ for the whole population, with
only about 1/50 control time-windows (see Appendix B).

To systematically investigate the impact of degree heterogeneity, we give the
minimal number of nodes required $m$ versus the degree of the pinning nodes
$k$. Fig. 4(d) shows that quite some hub nodes alone rather than the largest
hub can pin the level of fairness to approach $(0.5,0.5)$. Interesting, there
is a power-law for those small or intermediately large degrees, with an
exponent -1.4. This means that to promote the fairness of heterogeneously
structured populations, we can pin either very few hubs or relatively more
periphery nodes according to the power-law revealed.

To understand the impact of the degree heterogeneity, it’s helpful to derive
the condition under which the fair strategy can spread for a given number of
randomly pinning individual $N_{p}$. Let’s consider a pair of interacting
players $i$ and $j$, respectively with the strategy $S_{h}$ and $S_{l}$. Their
expected payoffs are
$\Pi_{i}=(1-C_{h})+\frac{N_{p}}{N}(k_{i}-1)+(1-C_{h})(1-\frac{N_{p}}{N})(k_{i}-1)$
and
$\Pi_{j}=C_{h}+C_{h}\frac{N_{p}}{N}(k_{j}-1)+(1-\frac{N_{p}}{N})(k_{j}-1)$,
respectively. The spread of $S_{h}$ is statistically conditioned by
$\Pi_{i}>\Pi_{j}$, which leads to

$\frac{k_{i}-2k_{j}+1}{2}+(\frac{k_{i}}{2}+\frac{k_{j}}{2}-1)\frac{N_{p}}{N}\geq
0,$ (3)

where $C_{h}=\frac{1}{2}$, the same as in the above. The larger of the left
side of this inequality, the more likely for the fair strategy $S_{h}$ to
spread. While the sign of the first term could be either positive or negative,
depending on the $k_{i,j}$. Nevertheless, by plotting its value versus degree
$k_{i}$, it can be found that the probability of the first term being positive
increases with the increase of $k_{i}$. The second term is always positive and
is larger if node $i$ is a hub. This explains why pinning hub node is more
efficient than the periphery node as shown in Fig. 4(d).

Figure 5: (Color online) Intermittent behaviors in BA scale-free networks. (a)
Typical time series of intermittent failures when $45$ nodes with degree-$2$
are pinned. (b) The cumulative distribution curve (CDF) of the interval time
$\tau$ of intermittent events for two different pinning scenarios. The black
dashed line is a fitting line with an exponent of -0.35. Parameters: $N=1000$,
$\langle$k$\rangle=4$.

Finally, we study the intermittent behaviors as we have already seen in Fig.
4(a). A more clear example is shown in Fig. 5(a), where $45$ nodes of
degree-$2$ are pinned. After transient, the fairness level drops from time to
time when the population reached the fair state $S_{h}$, and these
intermittent failures are an intrinsic property for even longer time
evolution. We define each $\tau$ as the time interval during which
$\langle$p$\rangle\geq 0.5$ and do a statistics of $\tau$ for these
intermittent events. The CDF indicates that there is a power-law with an
exponent $-0.35$ for about two orders in $\tau$, with a heavy tail at the
other end. This power-law distribution implies that the system is near some
sort of critical state Satz (1989); Bénichou  _et al._ (2005); Hammer  _et
al._ (1994); Wei  _et al._ (2021); Lohse and Grossmann (1993); Huepe and
Aldana (2004). This observation disappears when fewer or more nodes are
pinned, or the hub nodes are pinned, as shown in Fig. 5(b), as well as Fig.
4(c).

##  V 5\. Conclusion and Discussion

In summary, we apply the idea of pinning control to the UG model and show that
this is an efficient approach to improving the level of social fairness. For
homogeneously structured populations, a first-order phase transition is
revealed that a sudden jump of the social fairness is seen when the number of
pinning individuals increases. By contrast, this transition is continuous for
heterogeneous populations, and we find a single hub is sufficient to drive the
whole system into the high fairness state. We also provide some analysis of
why pinning hub works better. But, if the pinning control is not strong
enough, intermittent failures can be seen.

Our analysis shows that once the goal is achieved, the payoff difference
between the pinned individuals and the unpinned disappears, meaning no more
control cost is needed afterwards. But if the fairness of the population fails
to the target level, the payoffs for the pinned are indeed lower than the
rest, which might need to be compensated. For the heterogeneously structured
population, one convenient option is to pin only one hub; and to reduce the
control cost, the control can even be imposed discontinuously, like the on-off
control scheme.

Within the paradigm of _Homo economicus_ , the behaviors sticky to the high
fairness are irrational, which can only be explained by supported by some
external support for compensation. In our daily lives, however, there are
indeed some “good Samaritans” that their decision-makings are not only
economic-driven but also morality- or emotion- driven. In these scenarios, the
fair behaviors are spontaneous that need no compensation. Anyway, in those
societies where the fairness level are unsatisfactory, our study indicates
that the pinning control might be a feasible option to improve.

##  VI Acknowledgments

We are supported by the Natural Science Foundation of China under Grants Nos.
61703257 and 11747309, and by the Fundamental Research Funds for the Central
Universities GK201903012. ZJQ is supported by the Natural Science Foundation
of China under Grants No. 12165014.

##  Appendix A Appendix A: Pinning control in the well-mixed population

Figure 6:  (Color online) PT of the average offer level $\langle$p$\rangle$
versus the number of pinned individuals $N_{p}$ in the well-mixed population.
The inset is a hysteresis loop, conducted in the same way as in Fig.1(c).
Parameters: $N=1000$, the transient time $t=10^{6}$.

In Fig. 6, we show the evolution of fairness in the well-mixed population. By
changing the number of randomly chosen pinning nodes $N_{p}$, the phase
transition of $\langle$p$\rangle$ presents a first-order phase transition,
where a bistable region appears between $20\lesssim N\lesssim 50$. A
hysteresis loop in the inset shows a wider bistable interval $5\lesssim
N\lesssim 110$. This means that the structured population is not a necessary
condition for the discontinuous phase transition observed here.

Figure 7: (Color online) On-off pinning control of the largest hub in BA
networks. (a) The time evolution of $\langle$p$\rangle$ and
$\langle$q$\rangle$ by pinning control till $10^{3}$ steps, afterwards the
fairness evolves without pinning. (b) The average offer $\langle$p$\rangle$
and acceptance $\langle$q$\rangle$ versus the parameter $\theta$, the error
bar represents their standard deviations. (c) On-off pinning control with
three different control periods $t_{c}$, where the characteristic time we used
works best. Parameters: $N=1000$, $\langle$k$\rangle=4$.

##  Appendix B Appendix B: On-off pinning control in BA networks

To reduce the control cost, a periodic on-off pinning control Chen  _et al._
(2009) for the largest hub is found to be sufficient to sustain the fair state
$S_{h}$ for the whole population.

First of all, we compute the characteristic time $t_{c}$ of the system as the
control period. Specifically, we adopt the idea of the Lyapunov exponent in
the nonlinear dynamics Strogatz (2015) by analogy as follows

$\lambda=\frac{1}{\Delta t}\ln(\frac{|\Delta p^{\prime}|}{|\Delta p|}),$ (4)

$\Delta p$ denotes the distance to the high fair state $S_{h}$ at some moment
$t$ when the system with pinning control reaches the steady-state, $\Delta
p=0.5-\langle$p(t)$\rangle$. When the pinning control is withdrawn, the
fairness is expected to decrease. $\Delta p^{\prime}$ is the new distance to
$S_{h}$ after $\Delta t$, $\Delta p^{\prime}=0.5-\langle p(t+\Delta
t)\rangle$, see Fig. 7(a). In our computation, $t=1000$, $\Delta t=10000$, the
Lyapunov exponent $\lambda$ is averaged over 100 realizations. Here, the
pinning control acts like a perturbation, the value of $\lambda$ reflects the
evolution rate back to the low fairness state, capturing the time-scale of the
dynamics. Once the Lyapunov exponent $\lambda$ is obtained, the characteristic
time $t_{c}=\frac{1}{\lambda}$.

Denote $\theta$ as the proportion of the period within which the pinning
control is turned on. In Fig. 7(b), we can see that the population has
steadily risen to the high fairness when $\theta=0.02$. It means that the high
fairness of the whole population can be achieved largely with only about 1/50
control time windows. The standard deviation, however, shows that a larger
$\theta$ is required if smaller fluctuations are desired. This indicates that
due to the structural heterogeneity, discontinuous pinning may be a good
option to reduce the control cost. Finally, we also compare the results with
three different on-off periods, showing that the characteristic time we
adopted is a reasonable choice, see Fig. 7(c).

## References

  * Piketty (2014) T. Piketty,  _Capital in the Twenty-First Century_ (Belknap Press: An Imprint of Harvard University Press, 2014).
  * Güth  _et al._ (1982) W. Güth, R. W. Schmittberger, and B. Schwarze, Journal of Economic Behavior and Organization 3, 367 (1982).
  * Solow and Simon (1957) R. M. Solow and H. A. Simon,  _Models of Man: Social and Rational_ (Willey, 1957).
  * Samuelson and Nordhaus (2005) P. Samuelson and W. Nordhaus,  _Economics (18th edition)_ (McGraw-Hil Education, 2005).
  * Thaler (1988) R. H. Thaler, Journal of Economic Perspectives 2, 195 (1988).
  * Bolton and Zwick (1995) G. E. Bolton and R. Zwick, Games and Economic Behavior 10, 95 (1995).
  * Kagel and Roth (1995) J. H. Kagel and A. E. Roth,  _The Handbook of Experimental Economics_ (Princeton University Press, Princeton, NJ, 1995).
  * Güth and Kocher (2014) W. Güth and M. G. Kocher, Journal of Economic Behavior and Organization 108, 396 (2014).
  * Brosnan and de Waal (2003) S. F. Brosnan and F. B. M. de Waal, Nature 425, 297 (2003).
  * Proctor  _et al._ (2013) D. Proctor, R. Williamson, F. B. M. de Waal, and S. F. Brosnan, Proc. Nat. Acad. Sci. USA 110, 2070 (2013).
  * Page and Sigmund (2000) K. M. Page and N. K. Sigmund, Proceedings Biological Sciences 267, 2177 (2000).
  * Kuperman and Risau-Gusman (2008) M. N. Kuperman and S. Risau-Gusman, European Physical Journal B 62, 233 (2008).
  * Sinatra  _et al._ (2009) R. Sinatra, J. Iranzo, J. Gómez-Gardenes, L. M. Floría, V. Latora, and Y. Moreno, Journal of Statistical Mechanics: Theory and Experiment 58, 09012 (2009).
  * Nowak  _et al._ (2000) M. A. Nowak, K. M. Page, and K. Sigmund, Science 289, 1773 (2000).
  * Andre and Baumard (2011) J. B. Andre and N. Baumard, Journal of Theoretical Biology 289, 128 (2011).
  * Sanchez and Cuesta (2005) A. Sanchez and J. A. Cuesta, Journal of Theoretical Biology 235, 233 (2005).
  * Page and Nowak (2002) K. M. Page and M. A. Nowak, Bulletin of Mathematical Biology 64, 1101 (2002).
  * Binmore and Samuelson (1994) K. Binmore and L. Samuelson, Journal of Institutional and Theoretical Economics 150, 45 (1994).
  * Gale  _et al._ (1995) J. Gale, K. G. Binmore, and L. Samuelson, Games and Economic Behavior 8, 56 (1995).
  * Di Vece  _et al._ (2005) M. Di Vece, S. Palomba, and R. E. Palmer, Phys. Rev. B 72, 073407 (2005).
  * Tang and Hu (2006) G. Tang and G. Hu, Chinese Physics Letters 23, 1523 (2006).
  * Wang  _et al._ (2016) J. Wang, H. Wu, T. Huang, S. Ren, and J. Wu, IEEE Transactions on Systems, Man, and Cybernetics: Systems 46, 1109 (2016).
  * Sorrentino  _et al._ (2007) F. Sorrentino, M. di Bernardo, F. Garofalo, and G. Chen, Phys. Rev. E 75, 046103 (2007).
  * Yu  _et al._ (2013) W. Yu, G. Chen, J. Lü, and J. Kurths, SIAM Journal on Control and Optimization 51, 1395 (2013).
  * Yu  _et al._ (2009) W. Yu, G. Chen, and J. Lü, Automatica 45, 429 (2009).
  * Jin  _et al._ (2008) Z. Jin, J. Lu, and J. Lü, Automatica 44, 996 (2008).
  * Zhang  _et al._ (2013) J. Zhang, Z. Huang, J. Dong, L. Huang, and Y. Lai, Physical review. E, Statistical, nonlinear, and soft matter physics 87, 052808 (2013).
  * Zhang  _et al._ (2016) J. Zhang, Z. Huang, Z. Wu, R. Su, and Y. Lai, Scientific reports 6, 20925 (2016).
  * Debove  _et al._ (2016) S. Debove, N. Baumard, and J.-B. André, Evolution and Human Behavior 37, 245 (2016).
  * Colin F. Camerer and Rabin (2003) G. L. Colin F. Camerer and M. Rabin,  _Advances in Behavioral Economics_ (Princeton University Press, Princeton, NJ, 2003).
  * Loewenstein and Lerner (2003) G. Loewenstein and J. S. Lerner,  _The Role of Affect in Decision Making_ (Oxford University Press, Oxford, 2003).
  * Sanfey  _et al._ (2003) A. G. Sanfey, J. K. Rilling, J. A. Aronson, L. Nystrom, and J. D. Cohen, Science 300, 1755 (2003).
  * Rilling and Sanfey (2011) J. K. Rilling and A. G. Sanfey, Annual Review of Psychology 62, 23 (2011).
  * Roca  _et al._ (2009) C. P. Roca, J. A. Cuesta, and A. Sánchez, Physics of Life Reviews 6, 208 (2009).
  * Zheng  _et al._ (2022) G. Zheng, J. Zhang, R. Liang, L. Ma, and L. Chen, (2022), arXiv:2202.06002 [q-bio.PE] .
  * Stanley (1987) H. E. Stanley,  _Introduction to Phase Transitions and Critical Phenomena_ (Oxford University Press, 1987).
  * Taylor and Jonker (1978) P. D. Taylor and L. B. Jonker, Mathematical Biosciences 40, 145 (1978).
  * Bollobás (2001) B. Bollobás,  _Random Graphs_ (Cambridge University Press, 2001).
  * Barabási and Albert (1999) A. L. Barabási and R. Albert, Science 286, 509 (1999).
  * Satz (1989) H. Satz, Nuclear Physics B 326, 613 (1989).
  * Bénichou  _et al._ (2005) O. Bénichou, M. Coppey, M. Moreau, P. Suet, and R. Voituriez, Physica A: Statistical Mechanics and its Applications 356, 151 (2005).
  * Hammer  _et al._ (1994) P. W. Hammer, N. Platt, S. M. Hammel, J. F. Heagy, and B. D. Lee, Phys. Rev. Lett. 73, 1095 (1994).
  * Wei  _et al._ (2021) Z. Wei, L. Zhang, Y. Ren, W. Wei, H. Zhang, X. Cai, Y. Song, and L. Kang, Atmospheric Research 249, 105312 (2021).
  * Lohse and Grossmann (1993) D. Lohse and S. Grossmann, Physica A: Statistical Mechanics and its Applications 194, 519 (1993).
  * Huepe and Aldana (2004) C. Huepe and M. Aldana, Phys. Rev. Lett. 92, 168701 (2004).
  * Chen  _et al._ (2009) L. Chen, C. Qiu, and H. Huang, Physical review. E, Statistical, nonlinear, and soft matter physics 79 (2009), 10.1103/PhysRevE.79.045101.
  * Strogatz (2015) S. H. Strogatz, Physics Today 68 (2015), 10.1063/PT.3.2751.


# Empowering HWNs with Efficient Data Labeling: A Clustered Federated Semi-
Supervised Learning Approach

Moqbel Hamood, Abdullatif Albaseer, Mohamed Abdallah, Ala Al-Fuqaha  Division
of Information and Computing Technology, College of Science and Engineering,
Hamad Bin Khalifa University, Doha, Qatar
{moha19838, aalbaseer, moabdallah<EMAIL_ADDRESS>
###### Abstract

Clustered Federated Multi-task Learning (CFL) has gained considerable
attention as an effective strategy for overcoming statistical challenges,
particularly when dealing with non-independent and identically distributed
(non-IID) data across multiple users. However, much of the existing research
on CFL operates under the unrealistic premise that devices have access to
accurate ground-truth labels. This assumption becomes especially problematic
in, especially hierarchical wireless networks (HWNs), where edge networks
contain a large amount of unlabeled data, resulting in slower convergence
rates and increased processing times—particularly when dealing with two layers
of model aggregation. To address these issues, we introduce a novel
framework—Clustered Federated Semi-Supervised Learning (CFSL), designed for
more realistic HWN scenarios. Our approach leverages a best-performing
specialized model algorithm, wherein each device is assigned a specialized
model that is highly adept at generating accurate pseudo-labels for unlabeled
data, even when the data stems from diverse environments. We validate the
efficacy of CFSL through extensive experiments, comparing it with existing
methods highlighted in recent literature. Our numerical results demonstrate
that CFSL significantly improves upon key metrics such as testing accuracy,
labeling accuracy, and labeling latency under varying proportions of labeled
and unlabeled data while also accommodating the non-IID nature of the data and
the unique characteristics of wireless edge networks.

###### Index Terms:

Clustered federated learning (CFL), Semi-supervised learning (SSL),
Hierarchical wireless networks, Specialized models.

##  I Introduction

The proliferation of mobile devices and the Internet of Things (IoT) has not
only exponentially increased data generation but also ignited a technological
revolution that transforms everyday life [1, 2]. This surge in data has
enriched various applications and enabled cross-domain knowledge sharing,
especially within Hierarchical Wireless Networks (HWNs) in which different
edge networks, including mobile and IoT devices, are connected through a cloud
[3, 4]. Particularly, HWNs enable seamless collaboration among diverse IoT
ecosystems, optimizing the data’s utility for multiple applications by
employing Machine Learning (ML) and Deep Learning (DL) techniques. However,
traditional ML/DL approaches face considerable challenges when operating in
HWNs, including handling vast volumes of data, which mostly is unlabeled,
limited network resources, latency due to two levels of connections, and
privacy concerns due to data leakage [5, 6, 7].

In response, hierarchical federated learning (HFL) [8] was introduced as a
proposed solution to address some of the aforementioned challenges. In the HFL
approach, IoT-enabled devices conduct local model training and send only model
parameters (i.e., weights and biases) to their corresponding edge servers and
then to the cloud to update a global model. This strategy minimizes
communication overhead and protects sensitive data. Despite its advantages,
HFL approaches face several challenges during training. These include the
diversity of device capabilities and the massive amount of non-independent and
identically distributed (non-IID) data, which hinder efficient model
development and communication.

Cluster federated learning (CFL) paradigm [9] has emerged as a promising
solution that copes with these problems, especially the non-IID problem where
the data residing on each device does not follow the same distribution, nor
are the data points independent of each other. CFL is considered a post-
processing technique that improves the FL algorithm without altering its
fundamental communication protocol and at least achieves the same performance
as FL. This is done by splitting devices into clusters based on similarity in
their data distributions when the HFL objective at each edge network reaches a
stationary point (i.e., where the FL model cannot improve further on its
current data). Each cluster then develops a tailored model that accurately
captures specific data patterns. Several existing research [9, 10, 11, 12]
have delved into CFL’s effectiveness within the edge network, focusing on
fully labeled datasets to cluster the devices into different clusters. These
works have also addressed bandwidth and energy consumption for the CFL in
wireless edge networks. For example, the work in [13] proposed solutions to
prioritize participant devices according to their training latency by
leveraging the dynamic characteristics of edge networks, scheduling devices
based on their round latency, satisfying fairness, and exploiting bandwidth
reuse. In addition, the work in [14] proposed a solution to address the
service heterogeneity where local models have different structures in HWNs
using CFL with knowledge distillation. However, none of these works [9, 10,
11, 12, 13, 14] addressed the problem of unlabeled data under HWNs and CFL
settings.

In the literature, applying Semi-supervised learning (SSL) in conjunction with
FL has received considerable effort [15, 16]. For instance, the authors of
[16] proposed a framework that integrates SSL and FL, allowing devices with
only unlabeled data to train models across several local epochs, with the
server maintaining a small subset of labeled data. Another study in [15]
introduced the federated semi-supervised learning (FedSemL) method,
considering wireless communication challenges such as bandwidth, latency, and
energy consumption. Nevertheless, none of these works also considered the CFL
and HWNs setting when dealing with the unlabeled data, as these methods
generally focus on a single global model, which is insufficient for
confidently labeling a vast array of non-IID data.

In practice, the predominant data type collected by edge devices in HWNs is
both unlabeled and non-IID, necessitating more robust solutions that account
for limited edge network resources. Particularly, there is a need for an
efficient approach to leverage the unlabeled data under CFL and HWN settings,
in which CFL creates multiple specialized models only based on the fully
labeled data. Each specialized model for each group of users or devices may
fail to label the unlabeled data that belong to a different data distribution
than the model belongs to. Another aspect is to consider the complexity of SSL
when applied within HWNs due to dual-level model aggregation and computation.
Therefore, exploring a framework that enables efficient use of unlabeled data
in different edge networks while considering the unbalanced and non-IID data
distribution is imperative.

Motivated by these gaps, we propose a novel framework incorporating CFL with
SSL in HWNs to bridge existing gaps in the research field. This framework,
dubbed Clustered Federated Semi-Supervised Learning (CFSL), is designed to use
the best-specialized models resulting from the clustering process in the CFL
to label unlabeled non-IID data using the SSL. Rigorously, the aim is to
accurately label the data samples using a specialized model, even if it has
resulted from a different distribution, while optimizing the resources and
adhering to deadline constraints at both edge and cloud servers. We formulate
an optimization problem and introduce the proposed methods for a tractable
solution. To assess the efficacy of the proposed approach, we conduct
extensive simulations utilizing the FEMNIST dataset, evaluating testing
accuracy, labeling accuracy, and latency compared to baselines.

The structure of this paper is as follows: Section II details the system
model, learning process, and computational and communication models. Section
III delves into the problem formulation. The proposed approach is explained in
Section IV. Section V presents our experimental findings and results. Finally,
Section VI concludes the paper and hints at potential future directions.

Figure 1: The system model

##  II System Model

The system model illustrated in Fig. 1 comprises a cloud server connected to a
set of edge servers $\mathcal{N}=\\{1,\dots,N\\}$, where $N=|\mathcal{N}|$,
linked to a set of devices $\mathcal{K}=\\{1,\dots,K\\}$, where
$K=|\mathcal{K}|$. Each $k$-th device owns a local dataset $\mathcal{D}_{k}$,
where a small set of this data is labeled,
$\mathcal{D}^{l}_{k}=\\{{x}^{(k)}_{i,d}\in\mathbb{R}^{d},~{}y^{(k)}_{i}\\}_{i=1}^{D^{l}_{k}}$,
and much larger is unlabeled,
$\mathcal{D}^{u}_{k}=\\{{x}^{(k)}_{i,d}\in\mathbb{R}^{d}\\}_{i=1}^{D^{u}_{k}}$.
Here, ${x}^{(k)}_{i,d}$ is the $d$ dimension feature vector of the $i$-th
sample at $k$-th device, and $y^{(k)}_{i}$ is the corresponding label; thus,
the entire dataset
$\mathcal{D}_{k}=\mathcal{D}^{l}_{k}\cup\mathcal{D}^{u}_{k}$. The total number
of labeled and unlabeled data for the $k$-th device is defined as
${D}^{l}_{k}=|\mathcal{D}^{l}_{k}|$ and ${D}^{u}_{k}=|\mathcal{D}^{u}_{k}|$,
respectively. It is worth noting that devices are associated with edge servers
based on physical proximity.

###  II-A HFL Model

In HFL, we assume the cloud server connects different edge networks, each with
an edge server and a set of connected devices. To start the HFL process, the
cloud initiates the global model, $W_{\circ}$, and sends it to the edge
servers-connected devices. Each edge server selects a subset of active devices
($S^{n}_{r}$) to participate in the training. Each device trains its local
model using the labeled data and uploads it to the associated edge server.
Afterward, the edge servers aggregate and average local models from their
devices before sending them to the cloud. The cloud receives the models,
updates the global model, and then forwards it back to the edge servers and
the corresponding devices for further training. This process iteratively
continues until the global model converges. It is worth mentioning that the
cloud and edge servers enforce a deadline constraint to synchronize model
updates to attenuate the risk of latency-induced delays resulting from the
time-varying channels in wireless networks. Let us assume that stochastic
gradient descent (SGD) is used for training with mini-batches as a local
solver to update the local models using their labeled data. The batch in mini-
batch SGD performs several updates within one epoch defined as
$\sigma=\frac{{D}^{l}_{k}}{b}$, where $b$ is the batch size.

To evaluate the performance of local models, each $k$-th device runs the min-
batch SGD algorithm $\sigma$ times to minimize the error of the local model
between the actual and predicted labels in every $r$-th round. Thus, the local
loss function for the $k$-th devices to catch the error over each $i$-th
sample of labeled data $\mathcal{D}^{l}_{k}$ is defined as:

$F_{k}(W_{r}):=\frac{1}{D^{l}_{k}}\sum_{i\in\mathcal{D}^{l}_{k}}f_{i}(W_{r}).$
(1)

The SGD iterates through each sample point to reduce its loss function (i.e.,
$f_{i}(W_{r})=\mathcal{F}_{i}(x^{(k)}_{i},y^{(k)}_{i};W_{r})$), and achieve an
optimal local model that fits well with its labeled data distribution.
Ultimately, HFL aims to minimize the total loss function over all devices’
labeled datasets $\mathcal{D}^{l}=\bigcup_{k}\mathcal{D}^{l}_{k}$.

###  II-B Clustered Federated Learning (CFL)

The CFL process in HWNs can be represented as parameterized trees, where the
roots of these trees represent the HFL processes that reach stationary
solutions (i.e., $W^{*}_{n}$). After that, the CFL partitions the devices in
each $n$-th edge network into two clusters. This occurs by requesting the
devices’ gradients and then computing their similarity to split them into
clusters, each with a specialized model. In practice, the cosine similarity
($\alpha$) is used by the edge server to compute the similarity between any
two devices’ gradients within the same $n$-th edge network or by the cloud
server to compute the similarity between different edge networks in HWNs.
Formally, the cosine similarity in this context is obtained as follows:

$\displaystyle\alpha^{n}_{k,k^{\prime}}$ $\displaystyle:=\alpha(\nabla
F_{k}(W^{*}_{n}),\nabla F_{k^{\prime}}(W^{*}_{n})):=\frac{\langle\nabla
F_{k}(W^{*}_{n}),\nabla F_{k^{\prime}}(W^{*}_{n})\rangle}{\parallel\nabla
F_{k}(W^{*}_{n})\parallel\parallel\nabla F_{k^{\prime}}(W^{*}_{n})\parallel}$
$\displaystyle=\begin{cases}1,&\text{if $J(k)=J(k^{\prime})$}\\\ -1,&\text{ if
$J(k)\neq J(k^{\prime})$},\end{cases}$ (2)

Here, $J(k)$ and $J(k^{\prime})$ are the distributions of local labeled data
for $k$ and $k^{\prime}$ devices, respectively. Consequently, the accurate bi-
partitioning for clusters can be formulated as
$c_{n_{1}}=\\{k|\alpha^{k}_{k,0}=1\\},\quad
c_{n_{2}}=\\{k|\alpha^{n}_{k,0}=-1\\}$. To perform accurate splitting between
two clusters, two critical conditions must be satisfied. First, the solution
of the HFL objective must approach the stationary points, mathematically
expressed as follows: $\tiny
0\leq\Biggl{\|}\sum_{k\in\mathcal{K}_{n}}\frac{D^{l}_{k}}{|D|}\nabla_{W}F_{k}(W^{*}_{n})\Biggr{\|}<\varepsilon_{1},$
and second, devices must be far from the stationary point of their respective
local loss functions:
$\tiny\max_{k\in\mathcal{K}_{n}}\left\|\nabla_{W}F_{k}(W^{*}_{n})\right\|>\varepsilon_{2}>0,$
where $\varepsilon_{1}$ and $\varepsilon_{2}$ are pre-determined
hyperparameters designated explicitly for controlling the clustering task
using the labeled datasets. It is worth highlighting that training the models
using labeled data continues in each cluster until either it approaches a new
stationary point (i.e., splitting is required) or reaches the stopping point
(i.e., no further splitting for this model). This process recursively
continues until all clusters reach the stopping point.

###  II-C Communication and Computation Models

Computation model: Let us define $f_{k}$ as the computation frequency (CPU
speed) and $\Theta$ as the needed CPU cycles to process one data sample.
Therefore, the local computation time for $k$-th device running the local
solver for $P$ epochs in a given round $r$ is obtained as follows:
$T^{cmp}_{k}=P\frac{{D}^{l}_{k}\Theta}{f_{k}}$. In the edge servers layer, we
have to set a deadline $T^{n}_{S_{r}}$ in every $r$-th round to avoid longer
waiting times for devices that take a longer time than others to complete
their assigned tasks during the training process due to large data sizes,
limited resources, or intermittent connectivity.
Communication model: First, the uploading time of models to the edge server is
defined as $T^{com}_{k}=\frac{\delta}{R^{com}_{k}}$, where $\delta$ is the
model size and ${R^{com}_{k}}$ is the transmission data rate achieved by the
$k$-th device, defined as
${R^{com}_{k}=\beta_{k,n}~{}B_{n}~{}\text{log}_{2}\left(1+\frac{|\mathbf{h}_{k}|^{2}P_{k}}{N\circ}\right)}$.
Here, $\beta^{r}_{k,n}$ indicates the bandwidth allocation ratio,
$\beta^{r}_{k,n}B_{n}$ is the allocated bandwidth for the $k$-th device,
$h_{n,k}$ is the channel gain between the $k$-th device and the $n$-th edge
server, $N_{\circ}$ refers to the complex additive white Gaussian noise (AWGN)
power, and $P_{k}$ is the transmission power. In addition, we use orthogonal
frequency-division multiple access (OFDMA) techniques to partition the channel
into sub-channels. Each edge server has limited sub-channels to upload local
models in every $r$-th round. Accordingly, the total time required for each
$k$-th device for training and uploading to the $n$-th edge server is defined
as:

$T_{S_{r}}^{n}=\mathrm{max}\left(T^{cmp}_{k}+T^{com}_{k}\right).$ (3)

It is important to note that, given the edge servers’ robust processing and
transmission capacities, we neglected the time and energy associated with
broadcasting edge and specialized models to devices.

For the cloud layer, the duration taken by the $n$-th edge server to upload
its models can be defined as
$T^{\mathrm{cloud}}_{n}=\frac{\delta}{R^{com}_{n}}$, where $R^{com}_{n}$
signifies the transmission rate achievable by the $n$-th edge server.
Accordingly, the latency in a given round $r$-th global round is expressed as
follows:

$T_{r}=\underset{n\in\mathcal{N}}{\max}(T^{\mathrm{cloud}}_{n}+T_{S_{r}}^{n}).$
(4)

##  III Problem Formulation

As previously mentioned, each device holds a substantial pool of unlabeled
data. Importantly, each device is allocated a specialized model based on its
fully labeled data. However, this specialized model may not necessarily be
suitable for labeling the device’s unlabeled data samples, which could belong
to a different data distribution requiring another specialized model or
refining the whole training process. This adds another layer of complexity to
the challenge, particularly when dealing with non-IID data distributions. Our
objective is to harness these unlabeled samples effectively to enhance overall
system performance. Specifically, selecting the best-performing specialized
model for each device, potentially spanning different edge networks, is
critical. This task becomes even more daunting when considering the limited-
resource aspects of network configurations, such as computational power and
communication bandwidth. When incorporating unlabeled data predicted with a
probability exceeding a given threshold, $\phi$, meticulous design is
imperative for the CFSL approach. Mathematically speaking, we can express the
pseudo-labeled data $D^{l}_{semi}$ that satisfy the confidence threshold
$\phi$ as follows:

$D^{l,new}_{k}=D^{l}_{k}+D^{l}_{semi}.$ (5)

From (5), it is crucial for the $k$-th device that adds new samples to its
training data to adjust $T^{cmp}_{k}$ to meet the deadline constraint as
$T^{cmp,new}_{k}=P\frac{{D}^{l,new}_{k}\Theta}{f_{k}}.$

To better refine our objective, we aim to minimize the loss function
$F(W_{k},\mathcal{D}^{l}_{k})$ for each device’s labeled data while maximizing
the utility function $\mathcal{U}(W_{m},\mathcal{D}^{u}_{k})$ of using model
$m$ to label the unlabeled data. This occurs by firstly deriving an optimal
aggregation methodology to attain $M$ specialized models
$\mathcal{M}=$$\\{W_{m}:m=1,\dots,M\\}$ within a total time budget, $T_{tot}$,
and secondly selecting a specialized model that provides optimal pseudo
labeling for this device. In this regard, the selected sets of available and
active devices for all rounds ($R$) are denoted as
$S_{[R]}=[S_{1},\dots,S_{R}]$, and the deadline for every round is
$T_{[R]}=[T_{1},\dots,T_{R}]$. Therefore, the aim is to minimize the loss of
all specialized models while maximizing the utility of using the unlabeled
data, which can be defined as:

$\small
f(W,z,\mathcal{D}^{l},\mathcal{D}^{u})=\sum^{R}_{r=1}\sum^{K}_{k}\left[F(W_{k},\mathcal{D}^{l}_{k})-\lambda\sum_{m\in\mathcal{M}}z_{km}\mathcal{U}(W_{m},\mathcal{D}^{u}_{k})\right]$
(6)

Consequently, the whole problem formulation for all clusters can be written as
follows:

$\displaystyle\textbf{P1:}\quad\underset{\mathbf{W},R,\mathbf{z}}{\text{minimize}}$
$\displaystyle~{}f(W,z,\mathcal{D}^{l},\mathcal{D}^{u})$ (7a) s.t.
$\displaystyle F(W_{m})-F(W^{*}_{m})\leq\epsilon,\quad\forall
m\in\mathcal{M},$ (7b) $\displaystyle\sum_{r=1}^{R}T_{r}(S_{r})\leq
T_{tot},\quad r\in\forall[R],$ (7c)
$\displaystyle(T^{cmp,new}_{k}+T^{com}_{k})\leq T_{S^{n}_{r}}^{n},~{}\forall
k\in\mathcal{K},~{}\forall n\in\mathcal{N}$ (7d)
$\displaystyle\sum_{k\in\mathcal{K}}\text{B}(W_{k})\leq B,$ (7e)
$\displaystyle\sum_{m\in\mathcal{M}}z_{km}=1,\quad\forall k,\in\mathcal{K},$
(7f) $\displaystyle z_{km}\in\\{0,1\\},\quad\forall k\in\mathcal{K},\quad
m\in\mathcal{M}$ (7g) $\displaystyle A_{k}\in\\{0,1\\},\quad\forall
k\in\mathcal{K},$ (7h)

where $\lambda$ refers to a trade-off parameter. Constraint (7b) ensures that
each cluster’s specialized models converge over the labeled and pseudo-labeled
data. Constraint (7c) ensures that the total time taken by all selected
devices in all edge networks during the CFL process remains within the
predefined time allocation, $T_{tot}$ across all rounds. Constraint (7d)
ensures that the combined computation and communication time in a given round
does not surpass the time limit set by each edge server. Constraint (7e)
guarantees that the total bandwidth used to transmit the models across all
devices should not exceed the system bandwidth ($B$). To ensure that each
$k$-th  device uses only one specialized model $W_{m}$ (it could belong to the
device’s cluster or from other clusters) for the pseudo-labeling process.
Constraint (7f) is a binary variable indicating whether the model $m$ is used
to label the unlabeled data of device $k$ the model ( $z_{km}=1$) if yes,
($z_{km}=0$ otherwise). The final constraint (7h) is a binary association
constraint for $k$-th device (i.e., $1$ if the device is allowed to connect to
a given edge server, $0$ otherwise).

##  IV Proposed Solution

As seen from Section III, Problem P1 is an NP-hard and MIP problem, primarily
because the product of the binary variable $z_{km}$ with the utility function
results in a non-linear relation. Also, the problem contains the continuous
variable $W_{m}$ and the integer variable such as $z_{km}$. In addition, it
requires determining the impact of $W$, $R$, and $z$ on each cluster model’s
weight vector, $F(W_{m})$. Further complicating the problem are the
unpredictable variations in wireless channels and inconsistent computation
times across devices during training. All these complexities complicate
selecting the best-performing specialized model for pseudo-labeling,
preventing a direct solution. Thus, this section introduces a tractable
proposed solution to ensure proper labeling under HWNs and CFL settings while
considering the network limitations. However, the critical aspect of this
approach is how to select the best-performing specialized model and how to
determine the appropriate time to deploy such a model for predicting and
injecting the unlabeled data. In CFL, a device is allocated only a specialized
model when the clustering starts. This process is imperative since the global
model under the non-IID data distribution setting will never converge and
accurately label the unlabeled data. For clarity, suppose a specialized model
$m$ is assigned to a cluster and its devices. Evaluating whether this
specialized model aligns with the unlabeled data distribution within the same
cluster is crucial. If differences arise, we select the most suitable
specialized model from other clusters within the same edge network or from
different edge networks, which aligns with the current unlabeled data
distribution and meets a predefined confidence threshold
$\max(P(y^{u}_{i}))\geq\phi$, where $\phi$ is the output probability, and
$y^{u}_{i}$ is pseudo labels for the $i$-th sample.

Based on this, our proposed approach determines when and how to select the
best-performing specialized model for the $k$-th device to label the unlabeled
data, which is outlined as follows. Initially, the cloud initiates $W_{\circ}$
and sends it to the edge servers, which then forwards it to the edge devices
for training. Each device uses its labeled data to train the local model and
upload it to the associated edge server. Afterward, the edge servers aggregate
these local models, fuse them, and then send them to the cloud. The cloud also
aggregates edge models, averages them, and sends them back to the edge servers
and devices for further training. This process is repeated until the splitting
conditions are satisfied. Specifically, each edge server splits the assigned
devices into clusters, each with a specialized model that fits the data
distribution well. Once we have the specialized models, each $k$-th device
starts predicting and injecting unlabeled data using the best-performing
specialized model. It is worth noting that the best-performing specialized
model for the $k$-th device does not necessarily mean the specialized model
where the device belongs during the first training phase; it could come from a
different cluster in the same or a different edge network. This is because
this specialized model may fail to accurately label the unlabeled data since
the unlabeled data samples might have different data distributions. Therefore,
the $k$-th device will notify the cloud to send all the specialized models
from different clusters. After that, it will evaluate the utility of using
every specialized model to label its unlabeled data. Accordingly, the $k$-th
device selects only the best-performing specialized model with the highest
labeling accuracy and less latency to label its unlabeled data perfectly.
Algorithm 1 details the procedure steps of our proposed approach.

Input: Device count ($K$), initial parameters ($W_{\circ}$), controlling
parameters $\varepsilon_{1}$ and $\varepsilon_{2}$, epoch count ($P$), batch
size $b$, confidence level $\phi$, and device’s labeled data (${D}^{l}_{k}$)
and unlabeled data (${D}^{u}_{k}$)

Output: $M$ specialized models and a FL global model

1

2Initialization: Define device cluster $\mathcal{K}$, set $W_{k}\leftarrow
0~{}\forall k$, and $r=1$

3for  _$r=1$ to $R$_ do

4

5 Aggregation at Edge

6 for  _$n=1$ to $N$_ do

7 Edge server $n$ pre-process: Identify responsive devices and distribute
$W_{r-1}$

8 Device tasks: for  _$k=1$ to $|\mathcal{S}^{n}_{r}|$_ do

9 Get $W_{r-1}$.

10 // Device’s Pseudo Labeling

11 Perform training: $W_{k}=W_{r-1}-\eta\sum_{t=1}^{\tau}\nabla
F_{k}(W_{k}{(t)})$

12 // Starting clustering, developing specialized models

13 Label ${D}^{u}_{k}$ using the best-performing specialized model $m$

14 Satisfying confidence threshold: $\max(P(y^{u}_{i}))\geq\phi$

15 Injecting pseudo-labeled data into the training data

16 Aggregate device models, compute $F_{n}(W_{r})$, and adjust $W_{n,r}$

17 for  _$c\in\mathcal{M}$_ do

18 Determine $\triangle W_{m}$ and update the specialized model set if
splitting conditions are met

19 Update $\mathcal{M}$

20

21 Cloud Aggregation:

22 Aggregate edge and specialized models, and update global model $W_{r}$

23 if  _$\textbf{M} >2$_ then

24 perform similarity checks among specialized models

25 Increment $r$

Return global model and $M$ specialized models

Algorithm 1 CFSL Framework

##  V Performance Evaluation

###  V-A Experimental Setup

This section evaluates the CFSL performance via simulation and elaborates on
the experimental setup. It showcases the numerical results of the proposed
approach in contrast to baseline techniques, focusing on testing accuracy,
labeling accuracy, and latency.
Experimental Parameters: The total bandwidth of the system is 10 MHz. Each
device’s channel gain ($\mathbf{h}_{k}$) is determined based on a path loss
(($\alpha=g\circ(\frac{d_{\circ}}{d})^{4}$)), where the reference gain
$g_{\circ}$ is -$35$ dB and the reference distance $d_{\circ}$ is set at $2$
m. The AWGN power is maintained at $N_{\circ}=10^{-6}$ watts. The computation
frequency $f_{k}$ ranges from $1$ GHz to $9$ GHz. Every device requires a
$\Theta=20$ cycle/sample. The transmission power, $P_{k}$, confined within a
range of $P^{\min}_{k}=-10$ dBm and $P^{\max}_{k}=20$ dBm. The simulation
parameters are set for $200$ communication rounds (R) involving $200$ devices
(K), while the learning rate is $0.01$ and we use $5$ epochs for local
training in each global round.
Dataset Preprocessing: We use the FEMNIST dataset [17], which has 62 classes
(10 digits, 26 lowercase letters, and 26 uppercase letters). It is used under
non-IID settings where each device is assigned a maximum of $2$ classes. This
ensures that each edge network receives a distinct data subset, preventing any
single device from having a complete view of the entire dataset. We employed
convolutional neural networks (CNN) for the classification task. We use only a
small portion of labeled data samples and numerous unlabeled samples to
prepare the data for our experiments.
Performance Metrics and Benchmarks: We evaluated the performance of our
proposed approach against two different techniques. The first baseline is the
CFL technique, which utilizes the fully labeled dataset for training. The
second is the traditional HFL in conjunction with the SSL technique, which
uses the global model for pseudo-labeling tasks.

###  V-B Results and Discussion

Figure 2: Testing accuracy for the proposed and baseline ( fully labeled CFL)
when $\phi=0.8$.

(a) $\phi=0.40$

(b) $\phi=0.80$

Figure 3: Labeling accuracy for the proposed and baseline approaches with
different percentages of labeled data.

####  V-B1 The Significance of Applying CFSL

As shown in Fig. 2, the testing accuracy is simulated using all participating
devices’ minimum, mean, and maximum accuracy to show how the proposed CFSL
improves the performance. One can note that our proposed approach surpasses
baselines and significantly improves the testing accuracy at different
percentages of labeled data (i.e., $2$$\%$, $5$$\%$, and $10$$\%$). This stems
from injecting unlabeled data into the training data during the training phase
using the most fitting model for the local unlabeled data, enhancing the
overall system performance.

####  V-B2 Labeling Accuracy and Latency

Figs. 3(a) and 3(b) illustrate the labeling accuracy of the proposed and
baseline algorithms when the confidence level is $\phi=0.40$ and $0.80$,
respectively. Notably, injecting the unlabeled samples using varying
proportions of labeled data and confidence levels through the specialized
models significantly enhances labeling accuracy, outperforming baselines. One
can notice that the increment of labeling accuracy in CFSL is much larger than
the baseline using different percentages of labeled data (i.e., 0.02, 0.05,
and 0.10). This stems from the fact that specialized models adapt more
precisely to the unique features of the data with a faster convergence rate
and perform better prediction of labels in non-IID data, even if unlabeled
data samples belong to different distributions. In contrast, the global model
fails to capture all data patterns due to the non-IIDness of the data, leading
to potential inaccuracies and slowing down convergence rates during incorrect
labeling or the delay of injecting the unlabeled samples.

(a) $\phi=0.40$

(b) $\phi=0.80$

Figure 4: Labeling latency for the proposed and baseline approaches with
different percentages of labeled data

Regarding the labeling latency, Figs. 4(a) and 4(b) showcase the averaged
labeling latencies of both the proposed approach and baselines at confidence
levels of $\phi=0.4$ and $\phi=0.8$. CFSL consistently exhibits a much lower
latency than the baselines across different labeled sample proportions, even
when only $2\%$ of labeled data is used. This efficiency is attributed to
selecting the most fitting specialized models, which are fine-tuned for
distinct tasks, allowing for faster processing and minimizing computational
demands compared to using only a single global model as in baselines.
Furthermore, elevating the confidence level from $\phi=0.4$ to $\phi=0.8$
results in a substantial rise in latency, highlighting the trade-off between
computational demands and confidence-level accuracy.

##  VI Conclusion

In this paper, we addressed the significant challenge of enabling efficient
CFL and SSL in HWNs under the constraints of non-IID data distribution and
limited network resources. We formulated an optimization problem to achieve
our goal. Due to the NP-hard and MIP nature of the problem, finding an optimal
solution is computationally intensive and not practical; thus, we proposed a
tractable solution to determine how and when to use the best-performing
specialized model for labeling, balancing trade-offs between accuracy,
latency, and system constraints. Our approach started by initializing a global
model that is iteratively refined based on edge devices’ local models. CFL
recursively grouped devices into clusters, and each attained a specialized
model that evaluated its utility in labeling the unlabeled data of devices
within its cluster and potentially across clusters. The specialized model
offering the highest accuracy and lowest latency in labeling a device’s
unlabeled data is selected for that task. Our approach also effectively
balanced the trade-off between labeling accuracy and system constraints,
offering a scalable and efficient solution for harnessing unlabeled data in
HWN and CFL settings.

## Acknowledgement

This publication was made possible by NPRP-Standard (NPRP-S) Thirteen (13th)
Cycle grant # NPRP13S-0201-200219 from the Qatar National Research Fund (a
member of Qatar Foundation). The findings herein reflect the work and are
solely the authors’ responsibility.

## References

  * [1] H. Cao, J. Du, H. Zhao, D. X. Luo, N. Kumar, L. Yang, and F. R. Yu, “Resource-ability assisted service function chain embedding and scheduling for 6g networks with virtualization,” _IEEE Transactions on Vehicular Technology_ , vol. 70, no. 4, pp. 3846–3859, 2021.
  * [2] W. Y. B. Lim, N. C. Luong, D. T. Hoang, Y. Jiao, Y.-C. Liang, Q. Yang, D. Niyato, and C. Miao, “Federated learning in mobile edge networks: A comprehensive survey,” _IEEE Communications Surveys & Tutorials_, vol. 22, no. 3, pp. 2031–2063, 2020.
  * [3] Y. Sun, M. Peng, Y. Zhou, Y. Huang, and S. Mao, “Application of machine learning in wireless networks: Key techniques and open issues,” _IEEE Communications Surveys & Tutorials_, vol. 21, no. 4, pp. 3072–3108, 2019.
  * [4] S. Hosseinalipour, C. G. Brinton, V. Aggarwal, H. Dai, and M. Chiang, “From federated to fog learning: Distributed machine learning over heterogeneous wireless networks,” _IEEE Communications Magazine_ , vol. 58, no. 12, pp. 41–47, 2020.
  * [5] C. Feng, H. H. Yang, D. Hu, Z. Zhao, T. Q. Quek, and G. Min, “Mobility-aware cluster federated learning in hierarchical wireless networks,” _IEEE Transactions on Wireless Communications_ , vol. 21, no. 10, pp. 8441–8458, 2022.
  * [6] S. Vahidian, M. Morafah, M. Shah, and B. Lin, “Rethinking data heterogeneity in federated learning: Introducing a new notion and standard benchmarks,” _IEEE Transactions on Artificial Intelligence_ , 2023.
  * [7] E. Bertino and S. Banerjee, “Artificial intelligence at the edge,” _arXiv preprint arXiv:2012.05410_ , 2020.
  * [8] S. Luo, X. Chen, Q. Wu, Z. Zhou, and S. Yu, “Hfel: Joint edge association and resource allocation for cost-efficient hierarchical federated edge learning,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 10, pp. 6535–6548, 2020.
  * [9] 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.
  * [10] 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.
  * [11] Y. Luo, X. Liu, and J. Xiu, “Energy-efficient clustering to address data heterogeneity in federated learning,” in _ICC 2021-IEEE International Conference on Communications_. IEEE, 2021, pp. 1–6.
  * [12] B. Gong, T. Xing, Z. Liu, W. Xi, and X. Chen, “Adaptive client clustering for efficient federated learning over non-iid and imbalanced data,” _IEEE Transactions on Big Data_ , 2022.
  * [13] A. Albaseer, M. Abdallah, A. Al-Fuqaha, A. Mohammed, A. Erbad, and O. A. Dobre, “Fair selection of edge nodes to participate in clustered federated multitask learning,” _IEEE Transactions on Network and Service Management_ , 2023.
  * [14] M. Hamood, A. Albaseer, M. Abdallah, and A. Al-Fuqaha, “Clustered and multi-tasked federated distillation for heterogeneous and resource constrained industrial iot applications,” _IEEE Internet of Things Magazine_ , vol. 6, no. 2, pp. 64–69, 2023.
  * [15] A. Albaseer, M. Abdallah, A. Al-Fuqaha, A. Erbad, and O. A. Dobre, “Semi-supervised federated learning over heterogeneous wireless iot edge networks: Framework and algorithms,” _IEEE Internet of Things Journal_ , vol. 9, no. 24, pp. 25 626–25 642, 2022.
  * [16] E. Diao, J. Ding, and V. Tarokh, “Semifl: Semi-supervised federated learning for unlabeled clients with alternate training,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 17 871–17 884, 2022.
  * [17] S. Caldas, S. M. K. Duddu, P. Wu, T. Li, J. Konečnỳ, H. B. McMahan, V. Smith, and A. Talwalkar, “Leaf: A benchmark for federated settings,” _arXiv preprint arXiv:1812.01097_ , 2018.