# Graph Federated Learning for CIoT Devices in Smart Home Applications

Arash Rasti-Meymandi
Department of Electrical and Computer Engineering
University of Toronto
Toronto, Canada
<EMAIL_ADDRESS>
& Seyed Mohammad Sheikholeslami
Department of Electrical and Computer Engineering
University of Toronto
Toronto, Canada
<EMAIL_ADDRESS>
& Jamshid Abouei
Department of Electrical Engineering
Yazd University
Yazd, Iran
<EMAIL_ADDRESS>
& Konstantinos N. Plataniotis
Department of Electrical and Computer Engineering
University of Toronto
Toronto, Canada
<EMAIL_ADDRESS>

###### Abstract

This paper deals with the problem of statistical and system heterogeneity in a
cross-silo Federated Learning (FL) framework where there exist a limited
number of Consumer Internet of Things (CIoT) devices in a smart building. We
propose a novel Graph Signal Processing (GSP)-inspired aggregation rule based
on graph filtering dubbed “G-Fedfilt”111The implementation is available at
https://github.com/FL-HAR/Graph-Federated-Learning-for-CIoT-Devices.git. The
proposed aggregator enables a structured flow of information based on the
graph’s topology. This behavior allows capturing the interconnection of CIoT
devices and training domain-specific models. The embedded graph filter is
equipped with a tunable parameter which enables a continuous trade-off between
domain-agnostic and domain-specific FL. In the case of domain-agnostic, it
forces G-Fedfilt to act similar to the conventional Federated Averaging
(FedAvg) aggregation rule. The proposed G-Fedfilt also enables an intrinsic
smooth clustering based on the graph connectivity without explicitly specified
which further boosts the personalization of the models in the framework. In
addition, the proposed scheme enjoys a communication-efficient time-scheduling
to alleviate the system heterogeneity. This is accomplished by adaptively
adjusting the amount of training data samples and sparsity of the models’
gradients to reduce communication desynchronization and latency. Simulation
results show that the proposed G-Fedfilt achieves up to $3.99\%$ better
classification accuracy than the conventional FedAvg when concerning model
personalization on the statistically heterogeneous local datasets, while it is
capable of yielding up to $2.41\%$ higher accuracy than FedAvg in the case of
testing the generalization of the models. Furthermore, the proposed
communication optimization scheme can boost the framework’s efficiency by
reducing the computation, communication desynchronization, and latency up to
$70.21\%$, $99.65\%$, and $44.61\%$, respectively, at the cost of $0.36\%$
accuracy and under the system heterogeneity222This article has been accepted
for publication in IEEE Internet of Things Journal. This is the author’s
version which has not been fully edited and content may change prior to final
publication. Citation information: DOI: 10.1109/JIOT.2022.3228727.

_Keywords_ Federate learning (FL) $\cdot$ Graph signal processing (GSP)
$\cdot$ Communication-efficient $\cdot$ Graph filtering $\cdot$ Consumer
Internet of Things (CIoT)

##  1 Introduction

Within the past few years, there has been tremendous growth in Consumer
Internet of Things (CIoT) and personal smart devices with powerful
communication and computation capabilities (Poushter et al., 2016). These
devices often share a common goal when it comes to applications such as Human
Activity Recognition (HAR), object detection and object recognition. In this
regard, they have Machine Learning (ML) models embedded inside to make
decisions based on the training data and without being explicitly programmed
to act. For the ML model to perform well in real-world scenarios, training
data should be supplied by the clients themselves. However, these data are
often restricted by end-users due to privacy concerns. In addition, as the
number of edge devices increases, so does the uplink communication of the data
which in return, causes a large latency and a communication overhead due to
the bandwidth limitations (Chiang and Zhang, 2016). Recently, Federated
Learning (FL), an advanced distributed ML algorithm, has been recognized as a
promising solution for the above challenges (McMahan et al., 2017; Gafni et
al., 2021). FL has gained an exponential attraction in both wireless
communication and signal processing communities. The key idea behind FL is to
distribute the training computation of an ML model at the edge and hence,
preserve the privacy of end users’ data while conveying less information to
the server in each round of communication (Li et al., 2020). In conventional
FL, there are several iterations for model convergence. At each iteration, end
users produce local models on their available local datasets. The models are
then transmitted to a server for aggregation. Finally, the aggregated model is
shared among all devices. This process is repeated until model convergence.
Although FL can perform the joint training in a distributed manner, there are
still some actively researched challenges that are needed to be addressed
before their employment in smart home applications. Some of these challenges
include:

Statistical Heterogeneity: The ubiquity of CIoT devices has brought about a
plethora of high-performance machines in smart homes, including smartphones,
smartwatches, and smart speakers. Such devices accumulate various information
from the clients; however, the collected data is often statistically biased to
whom the device belongs. For instance, one client performs a specific gesture
by moving his/her hand in a particular manner; while another client makes the
same gesture, however, differently and less frequently. As a result, the data
samples collected at each smart home differ from each other in two aspects;
$i)$ they are acquired from different clients and edge devices resulting in a
feature distribution skew, and $ii)$ the labels of data samples are varied
from one client or device to another, thus creating a label distribution skew
(Kairouz et al., 2019). These biased characteristics among the local datasets
are regarded as “statistical heterogeneity”. The effect is a decrease in the
convergence time and the accuracy of the FL model. On the other hand, global
aggregations in most conventional FL cannot take statistical heterogeneity
into account. Therefore, they are not suitable for FL in smart home
applications. Note that conventional aggregation rules in FL such as Federated
Averaging (FedAvg) or some of its variants (Reddi et al., 2020) are considered
global aggregations. They primarily capture the general features rather than
personal structures in data; in other words, they are agnostic to domain
specifics.

System Heterogeneity: Edge devices over the CIoT network have diverse
computational powers and network connectivity. For example, most smartphone
brands nowadays are equipped with high-speed CPU chipsets much more
computationally potent than smartwatches. Consequently, the training time of
local models on these two devices will significantly vary. Besides, even
devices with similar capabilities and brands may show performance fluctuation
over time. Such diversity in computation and communication performance among
devices is known as “system heterogeneity”. This problem intensifies the
asynchronicity of the training during the aggregation which in turn, imposes a
large latency and desynchronization in each round of communication. In
practice, more valuable power resources and time are consumed.

There is a surge in describing the intrinsic connections of interactive
systems by traditional mathematical representations such as graphs. However,
the data supported by such graphs require a new processing mechanism beyond
the classical Signal Processing (SP) algorithms. In other words, a unified
approach is needed to analyze and extract useful information from the
irregularities yet meaningful connections on graphs. In this regard, Graph
Signal Processing (GSP), a generalization of classical SP, aims to handle the
graph-structured data and open a new path to better data processing (Dong et
al., 2020). In addition, it is rather intuitive to presume an underlying
relationship between smart devices in an FL framework. This interconnection
stems from both the data and the physical hardware of devices and it can be
represented by a graph. Thus, GSP can be employed to further benefit from the
inherited relationship among smart CIoT devices and better train ML models in
a distributed learning paradigm such as FL. As a motivating example, consider
the application of HAR or gesture recognition in a smart building with
multiple smart homes illustrated in Fig. 1. Some large-scale activities, such
as walking, might be recognizable via a smartphone. However, there are many
other large or small-scale activities and gestures demanding an ensembled
decision collected from multiple smart devices. Let each device be equipped
with an ML model. The inference they make is highly dependent on how they are
trained. It is not a far-fetched idea to assume an intrinsic relationship
among these devices as they collect data from a specific client (the intra-
connections in Fig. 1). Furthermore, this client might also have some
relationship with another client in the building, thus creating inter-
connections between devices. To account for such connectivity, one can use a
graph. The connectivity could be based on data correlation, hardware
specification similarities, or geometrical distances. In such a scenario,
training the ML models will be dependent based on the graph. Therefore, the
exchange of gradients of the models in the aggregation phase will be handled
not in an agnostic but in a more structured fashion. The result is, ML models
learn more relatively in the training process and consequently, make a
decision more accurately in the inference stage.

Figure 1: An overview of smart homes with multiple smart devices: Each device
has an ML model for a common application. There are intra/inter-cluster
relationships among devices (blue and red dashed lines) which are captured by
a graph. The models will then be trained collaboratively based on the graph.

###  1.1 Literature Review

Since its inception in (McMahan et al., 2017), there has been lots of research
on addressing the statistical heterogeneity in FL due to the Non-identically
independent distributed (Non-i.i.d.) and unbalanced datasets among devices
(Khaled et al., 2020; Abad et al., 2020; Li et al., 2019a). However, the
distribution skewness among edge devices might prevent the global model to
converge to an optimum point (Li et al., 2019b). To tackle this problem,
several works have been proposed to find a more personalized model for each
device, including $i)$ fine-tuning, where the idea is to fine-tune the model
based on the local dataset (Deng et al., 2020; Mansour et al., 2020; Liang et
al., 2020), $ii)$ federated transfer learning, where they freeze the globally
trained models and personalize deeper layers of the deep models by retraining
them on the local dataset (Chen et al., 2020a; Feng et al., 2020; Arivazhagan
et al., 2019), $iii)$ federated meta-learning, where a model trained to handle
many tasks (e.g., edge devices) is to be trained on a small local dataset with
few gradient iterations to get an essence of personalization (Jiang et al.,
2019; Fallah et al., 2020; Khodak et al., 2019), and $iv)$ federated multi-
task learning, where each edge device is trained collaboratively based on
others’ information and its own update (Corinzia et al., 2019; Smith et al.,
2017).

Although all the above researches have conducted a level of personalization
for edge devices, they merely considered them as independent devices. In other
words, edge device relationship has been underrated within their algorithms.
Since its introduction, multiple GSP-inspired algorithms have been developed
to handle graph-structured data in different areas such as spectral clustering
(Tremblay and Loukas, 2020) and action recognition (Hao et al., 2021). There
have also been some recent studies on graphs in FL known as “Federated Graph
Learning” (He et al., 2021). Most of the current relevant research including
(Sajadmanesh and Gatica-Perez, 2021; Jiang et al., 2020; Wu et al., 2021; Meng
et al., 2021) aims to train a Graph Neural Network (GNN), an advanced GSP-
inspired ML model, using FL. Authors in (Mei et al., 2019; Zheng et al., 2021)
used the graph as an auxiliary representation for improving node
classification. In (Wang et al., 2020), authors used FL to train a semi-
supervised graph-based node classification in a real-world application. To the
best of our knowledge, the only work in the community that utilizes graphs as
a way of mitigating statistical heterogeneity is the work in (Caldarola et
al., 2021). They split the model’s weights into two parts of global and local
layers where the latter one is trained on shared information provided by a
Graph Convolutional Network (GCN).

In the case of system heterogeneity, there has been some attempt to increase
the communication efficiency under the existence of slow or straggler devices.
Some works including (Damaskinos et al., 2020) attempted to devise an
asynchronous scheme. However, the staleness effect of slow devices might
reduce the convergence time or even prevent it from reaching a stable point.
Some other researches such as (Chen et al., 2021) provided a device selection
scheme where only devices with the most contribution are chosen to reduce the
number of communication round, while another group focused on the network
resource management (Yang et al., 2020; Chen et al., 2020b). While the salient
point of these researches is on the premise that there exist millions of
devices (cross-device FL), there only exist a few studies on how to have a
communication-efficient FL in a cross-silo setting where there is often a full
participation in the aggregation (Zhang et al., 2020). In this case, due to
the disparate resources and performance capabilities of devices, there will be
a desynchronization in each round of communication, i.e., the more the
heterogeneity, the more the desynchronization. This also poses a large latency
resulting in a slow training procedure. Thus, an optimization scheme is
required to reduce such delay in each communication round.

###  1.2 Contributions

Motivated by the edge devices’ underlying relationship and their heterogeneous
behavior, we introduce a novel framework, called Graph Federated Internet of
Things Learning (GFIoTL). The key contributions of the proposed framework are
summarized as follows:

$\bullet$ The proposed GFIoTL approach incorporates a graph filtering
aggregation rule based on the GSP concept dubbed “G-Fedfilt” where it opens
the door to a whole new level of aggregation using graph filter design while
incorporating FedAvg in a special case. To the best of our knowledge, this is
the first work where graph filter design is used as an aggregation rule in FL
which could potentially increase the devices’ collaboration in training the
models specific to each device.

$\bullet$ G-Fedfilt brings personalization into FL algorithms while keeping a
flow of information and unlike other personalized FL, involves edge device
relationship on the graph. The proposed aggregation rule can also cluster edge
devices inherently based on the graph’s connectivity.

$\bullet$ We propose a solution to system heterogeneity among CIoT devices in
a cross-silo setting. The idea is to adaptively adjust the number of data
samples and sparsity of models’ gradients to dynamically synchronize the
aggregation update. Additionally, the procedure is executed on the edge server
based on the computational capabilities and the network connectivity of edge
devices.

The rest of this paper is organized as follows. In Section 2, the model
description is presented. Section 3 introduces the main contributions of this
work including the GFIoTL framework along with the parameter optimization
scheme at the end. The experimental results are presented in Section 4 and
finally, the conclusion with some remarks are stated in Section 5.

##  2 Problem Description

In this section, we describe the backbone of the proposed framework in detail.
Our description mainly focuses on a building with multiple smart homes where
there exist various heterogeneous CIoT devices inside each one as depicted in
Fig. 1. Although designed for a smart building, the model can be readily
interpreted as a general-purpose framework for other fields of intelligent
environment and devices such as smart factories, smart cities, and smart
indoor environments (Sheikholeslami et al., 2021). Tables 1 and 2 provide the
summary of the notations used hereafter.

Table 1: List of general notations used in this paper. Parameter | Description
---|---
$A_{i}\times B_{i}\times C_{i}$ | Size of each room $c_{j}\in\mathcal{N}$
$\mathcal{N}$ | Set of smart rooms
$N$ | Number of rooms
$\mathcal{K}_{c_{j}}$ | Set of devices in $c_{j}\in\mathcal{N}$
$K_{c_{j}}$ | Number of devices in each room
$s_{i,c_{j}}$ | Device $i$ in room $c_{j}$
$K$ | Total number of devices
$\mathcal{G}$ | Network graph between devices
$\mathcal{V}$ | Set of vertices of graph $\mathcal{G}$
$\mathcal{A}_{s_{i,c_{j}}}$ | Neighbors’ set of device $i$ in room $c_{j}$
$\mathcal{E}$ | Set of edges of graph $\mathcal{G}$
$\boldsymbol{A}$ | Adjacency matrix of graph $\mathcal{G}$
$\boldsymbol{D}$ | Diagonal degree matrix of $\mathcal{G}$
$\boldsymbol{L}$ | Combinatorial graph Laplacian of $\mathcal{G}$
$\mathcal{D}_{s_{i,c_{j}}}$ | Dataset of device $i$ in room $c_{j}$
$\mathcal{X}$ | Training data set
$\mathcal{Y}$ | Label set
$F_{s_{i,c_{j}}}(\cdot)$ | ML model for device $i$ in room $c_{j}$
$\kappa_{s_{i,c_{j}}}$ | Associated weight of device $i$ in room $c_{j}$
$L(\cdot)$ | Data sample loss function
$\tilde{L}(\cdot)$ | Local loss function
$L^{\textrm{g}}(\cdot)$ | Collaborative loss function
$\boldsymbol{g}_{s_{i,c_{j}}}$ | Gradient update of device $i$ in room $c_{j}$
$R$ | Total number of comm. rounds
$\alpha_{s_{i,c_{j}}}$ | Number of local training at each comm. round
$\boldsymbol{G}$ | Matrix of gradient updates of all devices
$\boldsymbol{V}$ | Matrix of eigenvectors of $\boldsymbol{L}$
$(v_{i},\lambda_{i})$ |  $i^{th}$ eigenvector and eigenvalue of $\boldsymbol{L}$
$\boldsymbol{\Lambda}$ | Diagonal matrix of eigenvalues of $\boldsymbol{L}$

Environment Specifications: In this work, we consider a smart building
consisting of $N$ smart homes each equipped with a Femto Access Point (FAP).
Each smart home includes $K_{c_{j}}$ smart devices, indexed by
$\mathcal{K}_{c_{j}}=\\{s_{1,c_{j}},...,s_{K_{c_{j}},c_{j}}\\}$, and with the
total number of $K=\sum_{j=1}^{N}K_{c_{j}}$ devices. For simplicity and
without loss of generality, we assume all devices belonging to a smart home
are inside a single room. Each room, also called a cluster, is indexed by
$c_{j}\in\mathcal{N}=[c_{1},...,c_{N}]$ and has the size $A_{i}\times
B_{i}\times C_{i}$ , $i\in 1,...,N$. We opt to select devices that are
prevalent in real-world scenarios and mostly present in every common living
room. To illustrate a more realistic scenario, consider each room having a set
of common CIoT devices such as laptops, smartphones, smartwatches, tablets,
and a smart TV creating a heterogeneous setup. In this case, each device
$s_{i,c_{j}}\in\mathcal{K}_{c_{j}}$ is capable of performing a complex
computation while having different specifications.

Graph Network: Each device $s_{i,c_{j}}\in\mathcal{K}_{c_{j}}$ is connected to
its neighbors in the subset $\mathcal{A}_{s_{i,c_{j}}}$. It is assumed that
devices in the building constitute a bidirectional graph, denoted by
$\mathcal{G}(\mathcal{V},\mathcal{E})$, where
$\mathcal{V}=\cup_{j=1}^{N}\mathcal{K}_{c_{j}}$ consists of all devices as the
vertices of the graph and
$\mathcal{E}=\cup_{j=1}^{N}\cup_{i=1}^{K_{c_{j}}}\mathcal{A}_{s_{i,c_{j}}}$
indicates all the edges connecting the devices. Moreover, the weight of the
edges is indicated in the adjacency matrix $\boldsymbol{A}$, where
$(\boldsymbol{A})_{ij}$ is the connection weight of devices $i$ and $j$. The
entry $(\boldsymbol{A})_{ij}$ is chosen as either “one” or “zero” indicating
the connectivity of devices $i$ and $j$ which is specified by

$(\boldsymbol{A})_{ij}=\left\\{\begin{matrix}1&\textrm{if}~{}d_{ij}<d_{max}\\\
0&\textrm{otherwise}\end{matrix}\right.,$ (1)

where $d_{ij}$ represents the distance between devices $i$ and $j$, $d_{max}$
denotes the maximum distance considered for paired devices. In addition, all
devices have access to a nearby edge server to where they can share
information and exchange data. The edge server can be any high processing
machine located in the building, such as a central computer. It should be
noted that the point of considering the graph connectivity between devices is
to exploit such relationship and flow of information among devices which will
be elaborated on further in the paper.

Federated Learning Task: Each device $s_{i,c_{j}}\in\mathcal{K}_{c_{j}}$ in
cluster $c_{j}$, has a local dataset, denoted by $\mathcal{D}_{s_{i,c_{j}}}$,
where $\mathcal{D}_{s_{i,c_{j}}}$ and $\mathcal{D}_{s_{i^{\prime},c_{j}}}$,
$i\neq i^{\prime}$, might or not have shared data samples. In this scheme, a
supervised training procedure is considered where
$(\mathcal{X},\mathcal{Y})\in\mathcal{D}_{s_{i,c_{j}}}$ denotes the training
data set $\mathcal{X}=\\{\boldsymbol{x}_{n}\\}_{n=1}^{M}$,
$\boldsymbol{x}_{n}\in\mathbb{R}^{\mathtt{d}}$ and its corresponding label set
$\mathcal{Y}=\\{\boldsymbol{y}_{n}\\}_{n=1}^{M}$,
$\boldsymbol{y}_{n}\in(0,1)$. Here, $M$ represents the total number of data
samples in $\mathcal{D}_{s_{i,c_{j}}}$ and $\mathbb{R}^{\mathtt{d}}$ specifies
the feature space of the input data $\boldsymbol{x}_{i}$. In addition, a
personalized model $F_{s_{i,c_{j}}}(x_{n};\boldsymbol{\omega}_{s_{i,c_{j}}})$
with the loss function
$L(F_{s_{i,c_{j}}}(x_{n},\boldsymbol{\omega}_{s_{i,c_{j}}}),y_{n})$,
distributed among devices in the set $\mathcal{K}_{c_{j}}$ where
$\boldsymbol{\omega}_{s_{i,c_{j}}}\in\mathbb{R}^{B}$, represents the
parameters to be trained. Hence, the loss function of device $s_{i,c_{j}}$ is

$\tilde{L}(\boldsymbol{\omega}_{s_{i,c_{j}}})=\dfrac{1}{D_{s_{i,c_{j}}}}\sum_{(x_{n},y_{n})\in\mathcal{D}_{s_{i,c_{j}}}}L(F_{s_{i,c_{j}}}(x_{n},\boldsymbol{\omega}_{s_{i,c_{j}}}),y_{n}),$
(2)

where $D_{s_{i,c_{j}}}=|\mathcal{D}_{s_{i,c_{j}}}|$ denotes the cardinality of
the set $\mathcal{D}_{s_{i,c_{j}}}$. The collaborative loss function of the
framework is calculated as

$L^{\textrm{g}}(\boldsymbol{\omega})=\sum_{j=1}^{N}\sum_{i=1}^{K_{c_{j}}}\kappa_{s_{i,c_{j}}}\tilde{L}(\boldsymbol{\omega}_{s_{i,c_{j}}}),$
(3)

where $\kappa_{s_{i,c_{j}}}$ is the associated weight of each device
$s_{i,c_{j}}\in\mathcal{K}_{c_{j}}$. The main goal of the FL is to solve the
following minimization problem:

$\boldsymbol{\omega}_{s_{i,c_{j}}}^{\textrm{opt}}=\arg~{}\min
L^{\textrm{g}}(\boldsymbol{\omega}),$ (4)

where $\boldsymbol{\omega}_{s_{i,c_{j}}}^{\textrm{opt}}$ is the optimum
parameter weights for the model
$F_{s_{i,c_{j}}}(x_{n},\boldsymbol{\omega}_{s_{i,c_{j}}})$. Note that in case
of searching a global parameter, we have
$\boldsymbol{\omega}_{i,c_{j}}^{\textrm{opt}}=\boldsymbol{\omega}^{\textrm{opt}}_{0}$,
$\forall s_{i,c_{j}}$, where $\boldsymbol{\omega}^{\textrm{opt}}_{0}$ is the
global parameter.

Remark 1: In case the input dimensions of ML models are different, one can
equalize the dimensions using Encoder-Decoder (En-De) architectures. To do so,
a preprocessing En-De unit can be used before the ML model of each device
$s_{i,c_{j}}\in\mathcal{K}_{c_{j}}$. Although En-De units are fed with
different input dimensions, they can produce fixed-size latent spaces.
Finally, the ML models are fed by the acquired latent space features that have
the same dimensions.

##  3 Graph Federated Internet of Things Learning

In this section, we introduce a novel paradigm in constructing an aggregation
rule based on the graph connectivity of devices by exploiting Graph Signal
Processing (GSP). We show that our new paradigm can incorporate FedAvg based
on GSP under a certain condition which ultimately indicates the generality of
the proposed approach. More specifically, we design a graph filter to not only
aggregate the devices’ gradients but also keep a level of personalization
among devices. As another intrinsic capability of graph representation, we
show that our approach can inherently group devices into different clusters
based on their connections while allowing the flow of information. Note that
by personalization, we refer to training specialized models tailored for each
device rather than a single globally-shared model (Tan et al., 2021).

###  3.1 GFIoTL Overview

We consider a cross-silo situation where all devices participate in each round
of training. In addition, each device has its own specific ID where the edge
server can identify. We also define a discrete-time set
$\mathcal{T}=\\{1,...,R\\}$ and $t\in\mathcal{T}$ as the index time of the
whole training procedure. Based upon the time notations, a fixed number of
device-based updates occur before each aggregation time. After locally
training each device $s_{i,c_{j}}\in\mathcal{K}_{c_{j}}$ for
$\alpha_{s_{i,c_{j}}}$ epochs, the updated local weights
$\boldsymbol{\omega}_{s_{i,c_{j}}}$ are sent to the edge server for the
aggregation. Once the edge server collects enough model weights from edge
devices, it performs model aggregation and sends the updated weights to
specific devices. Although FedAvg is one of the most successful aggregation
rules in FL, it does not consider any personalization due to its inherited
averaging characteristic. In other words, with considering each device to have
a specific domain due to data and label heterogeneity, FedAvg primarily acts
as a domain-agnostic approach and ignores the domain specifics.

To better handle the domain specificity in GFIoTL, we exploit
$\mathcal{G}(\mathcal{V},\mathcal{E})$ and its representative adjacency matrix
$\boldsymbol{A}$ further in the proposed paradigm. Moreover, it is more
convenient to express the gradients update in a matrix form, denoted by
$\boldsymbol{G}^{(t)}\in\mathbb{R}^{K\times B}$, where $i^{th}$ row of
$\boldsymbol{G}^{(t)}$ corresponds to device $s_{i,c_{j}}$’s gradient update
$\boldsymbol{g}^{(t)}_{s_{i,c_{j}}}=\boldsymbol{\omega}^{(t)}_{s_{i,c_{j}}}-\boldsymbol{\omega}^{(t-1)}_{s_{i,c_{j}}}$.
In what follows, we will discuss some preliminaries regarding graphs in the
Fourier domain as our aggregation rule is heavily dependent upon spatial
frequencies and eigenfunctions.

###  3.2 GSP Background

One of the important properties of a bidirectional graph is the so called
combinatorial graph Laplacian, defined as
$\boldsymbol{L}=\boldsymbol{D}-\boldsymbol{A}$, where $\boldsymbol{D}$ denotes
the diagonal degree matrix of $\mathcal{G}$ with
$(\boldsymbol{D})_{ii}=\sum_{j=1}^{K}(\boldsymbol{A})_{ij}$. It can be shown
that for a bidirectional graph such as $\mathcal{G}$, $\boldsymbol{L}$ is a
positive semidefinite and all eigenvalues are non-negative real valued (Ortega
et al., 2018). Hence, it is common to choose the eigenvectors of the graph
Laplacian $\boldsymbol{L}$ as the eigenfunctions, i.e, the basis of the
Fourier transform. Consequently, the Fourier bases are extracted by the
eigenvalue decomposition of the graph Laplacian as

$\boldsymbol{L}=\boldsymbol{V}\boldsymbol{\Lambda}\boldsymbol{V}^{T},$ (5)

where $\boldsymbol{V}=[\boldsymbol{v}_{0},...,\boldsymbol{v}_{K-1}]$
represents the matrix of the $K$ eigenvectors of $\boldsymbol{L}$ and
$\boldsymbol{\Lambda}=\textrm{diag}[\lambda_{0},...,\lambda_{K-1}]$ is the
corresponding eigenvalues. Thus, assuming eigenvalues are ordered based on the
Total Variation (TV) of their eigenvectors used in (Ortega et al., 2018), the
corresponding eigenvector of $\lambda_{0}$ represents the DC basis and other
eigenvectors of higher $\lambda_{i}$, $i=1,...,K-1,$ indicate the higher
frequency bases of that particular graph. Consequently, the Graph Fourier
Transform (GFT) and the Inverse GF Transform (IGFT) of the gradient matrix,
denoted by $f(\boldsymbol{G}^{(t)})$ and $f^{-1}(f(\boldsymbol{G}^{(t)}))$,
are calculated respectively as

$\boldsymbol{G}^{(t)}_{f}=f(\boldsymbol{G}^{(t)})=\boldsymbol{V}^{T}\boldsymbol{G}^{(t)},$
(6)
$\boldsymbol{G}^{(t)}=f^{-1}(f(\boldsymbol{G}^{(t)}))=\boldsymbol{V}\boldsymbol{G}^{(t)}_{f}.$
(7)

Having the gradient update frequency coefficients $\boldsymbol{G}^{(t)}_{f}$
allows filtering the specific graph frequency by means of multiplication with
the filter frequency response. Thus, there are three steps in graph filtering
enumerated as $i)$ GFT, $ii)$ multiplication of the coefficient with the
filter frequency response, and $iii)$ IGFT of the resultant. To achieve such
filtering, a graph filter is defined in a matrix form, $\boldsymbol{H}$, such
that
$\boldsymbol{H}=\boldsymbol{V}h_{s}(\boldsymbol{\Lambda})\boldsymbol{V}^{T}$,
where $h_{s}(\boldsymbol{\Lambda})$ is the filter operator, i.e.,
$h_{s}(\boldsymbol{\Lambda})=\textrm{diag}[h_{s}(\lambda_{0}),...,h_{s}(\lambda_{k-1})]$.
Hence, the filtered gradient updates is calculated in a compact form of
multiplication as

$\displaystyle\widehat{\boldsymbol{G}}^{(t)}=\boldsymbol{H}\boldsymbol{G}^{(t)}$
$\displaystyle=\boldsymbol{\boldsymbol{V}}h_{s}(\boldsymbol{\Lambda})\underbrace{\boldsymbol{V}^{T}\boldsymbol{G}^{(t)}}_{\text{GFT}}$
(8)
$\displaystyle=\boldsymbol{\boldsymbol{V}}\underbrace{h_{s}(\boldsymbol{\Lambda})\boldsymbol{G}^{(t)}_{f}}_{\text{
freq. response mul.}}$ (9)
$\displaystyle=\underbrace{\boldsymbol{\boldsymbol{V}}\widehat{\boldsymbol{G}}^{(t)}_{f}}_{\text{IGFT}}.$

###  3.3 GFIoTL Updates

In this subsection, the two primary gradient updates required to achieve
$\boldsymbol{\omega}^{\textrm{opt}}_{s_{i,c_{j}}}$ are discussed in detail.

Local Model Update: Each device $s_{i,c_{j}}\in\mathcal{K}_{c_{j}}$ performs a
number of local updates independently on their dataset
$\mathcal{D}_{s_{i,c_{j}}}$ to update their model parameters
$\boldsymbol{\omega}_{s_{i,c_{j}}}$. Considering
$\beta_{s_{i,c_{j}}}\subset\mathcal{D}_{s_{i,c_{j}}}$ as the mini-batch on
which device $s_{i,c_{j}}$ is to be trained, the gradient estimate of the
local update at time slot $t-1$ is calculated as

$\boldsymbol{\Delta}_{s_{i,c_{j}}}^{(t-1)}=\dfrac{1}{|\beta^{(t-1)}_{s_{i,c_{j}}}|}\sum_{(x_{n},y_{n})\in\beta^{(t-1)}_{s_{i,c_{j}}}}\bigtriangledown
L(F_{s_{i,c_{j}}}(x_{n},\boldsymbol{\omega}_{s_{i,c_{j}}}^{(t-1)}),y_{n}).$
(10)

Therefore, the updated model parameter at time slot $t$ can be defined as

$\boldsymbol{\omega}_{s_{i,c_{j}}}^{(t)}=\boldsymbol{\omega}_{s_{i,c_{j}}}^{(t-1)}-\eta^{(t-1)}_{s_{i,c_{j}}}\boldsymbol{\Delta}_{s_{i,c_{j}}}^{(t-1)},~{}~{}\forall
s_{i,c_{j}}\in\mathcal{K}_{c_{j}}$ (11)

where $\eta^{(t-1)}_{s_{i,c_{j}}}$ indicates the local learning rate at time
slot $t-1$.

Global Aggregation Via Graph Filtering: After all model gradient updates of
edge devices were collected by the edge server, it performs the aggregation
process using the Graph Federated filtering (G-Fedfilt) as

$\boldsymbol{\widehat{G}}^{(t)}=\boldsymbol{H}\textrm{diag}[\kappa_{1},...,\kappa_{K}]\boldsymbol{G}^{(t)},$
(12)

where $\textrm{diag}[\kappa_{1},...,\kappa_{K}]$ represents the diagonal
matrix of the weights associated to all edge devices and $\boldsymbol{H}$ is
the graph filter to be designed based on the eigenvectors of $\boldsymbol{L}$
and the graph filter operator $h_{s}(\cdot)$.

An interesting point in representing the connectivity of devices in graphs is
that the FedAvg aggregation rule can be realized by applying a low-pass
filter, denoted by $\boldsymbol{H}_{DC}$, with the cut-off frequency
$f_{high}$ where $\lambda_{1}>f_{high}>\lambda_{0}$. In this case, the mean
value is primarily obtained and broadcasted to all devices and therefore,
there is no personalization for individual devices. On the other hand,
consider an all-pass filter $\boldsymbol{H}_{all}$ with
$f_{high}>\lambda_{K-1}$. Obviously, the resultant filtering of
$\boldsymbol{G}^{(t)}$ is the matrix itself without any change, i.e.,
$\boldsymbol{G}^{(t)}=\boldsymbol{H}_{all}\boldsymbol{G}^{(t)}$. This outcome
can be interpreted as a situation where only the data for each domain is
considered and there is no flow of information among devices. In other words,
we have a full personalization when aggregating the gradients using an all-
pass filter. We can now make a rather concrete statement; as the cut-off
frequency of the low-pass filter increases, so does the domain-specific
behavior of the aggregation rule. Conversely, as the cut-off frequency
decreases, so does the domain-agnostic of the aggregation rule.

Further elaboration on the mechanics of G-Fedfilt is presented in Appendix
6.1.

###  3.4 Graph Filter Design

The underlying concept of using graph filters in G-Fedfilt is to consider both
the domain-specific and the domain-agnostic gradient updates; to have a
tunable personalization in FL. In this regard, we propose a graph filter
operator in the graph frequency domain, behaving as a low-pass filter, that
could achieve such a goal which is expressed as follows:

$h_{s}(\lambda;\mu_{s})=\dfrac{1}{(1+\mu_{s}\lambda)},$ (13)

where $\mu_{s}$ is the tunable parameter of the filter. Therefore, given the
eigenvalue $\lambda_{i},~{}i=0,...,K-1$, the role of $h_{s}(\lambda_{i})$ is
to attenuate the coefficients in $\boldsymbol{G}_{f}^{(t)}$ associated with
higher frequencies while retaining the coefficients related to lower
frequencies. This can be accomplished by the multiplication
$h_{s}(\boldsymbol{\Lambda})\boldsymbol{G}^{(t)}_{f}$. An illustration of such
a filter is shown in Fig. 2. As seen, $h_{s}$ has a smooth transient low-pass
filter which eventually goes to zero. It is worthwhile to remind that graph
frequencies are represented by the eigenvalues of the graph Laplacian and
therefore, vary with respect to $\boldsymbol{A}$. Here in Fig. 2, we
considered $\boldsymbol{A}$ to be a $20\times 20$ symmetric matrix and the
silver-colored horizontal lines show the eigenvalues of such matrix, i.e.,
graph frequencies ordered from zero to the highest eigenvalue corresponding to
the highest graph frequency. Note that, the filter $h_{s}$ is not ideal and in
fact, there are many ways to design a more suitable filter to be used in
G-Fedfilt which opens up lots of rooms to design graph filters for the purpose
of better aggregation in the GFIoTL.

Figure 2: The graph frequency response of the proposed filter in G-Fedfilt for
$\mu_{s}=5$. Horizontal lines indicate eigenvalues/graph frequencies.

Figure 3: An illustration of different graph filtering on a single shared
gradient update $\boldsymbol{g}_{s_{i,c_{j}}}[1]$. Each node represents a
device $s_{i,c_{j}}$ connected by $\mathcal{G}$.

To have a better understanding of a low-pass graph filtering application, a
graph signal along with its corresponding filtered versions is illustrated in
Fig. 3. We used the publicly available PyGSP toolbox for this simulation
(Defferrard et al., 2017). Here, there exist $100$ nodes corresponding to
$100$ devices interconnected via a graph as a simulation environment of a
building with multiple smart rooms. Each device $s_{i,c_{j}}$ is expressed
with a color representing the first gradient element
$\boldsymbol{g}_{s_{i,c_{j}}}[1]$ shared with all devices. From this figure,
it is seen that when the graph is filtered with $\boldsymbol{H}_{0}$,
corresponding to $h_{s}(\lambda,10^{4})$, the average of the gradients will be
calculated whereas, when filtered with $\boldsymbol{H}_{1}$, they have
different aggregated values, though, they are still very close to the average.
This behavior indicates that there is a flow of information among devices, and
there also exists a level of personalization that can be smoothly controlled
by adjusting the tunable parameter, i.e., $\mu_{s}$. Another salient point
worth discussing is that when the graph is filtered by $\boldsymbol{H}_{1}$,
each section of the graph appears to have a certain aggregated gradient value;
as if each section turned into a cluster where the gradient value assigned to
the nodes is the average value of that particular cluster. This behavior
suggests that graph filtering can indeed cluster devices dynamically and
intrinsically solely based on the graph’s connectivity. In the end, a filter
such as $\boldsymbol{H}_{2}$ behaves as an all-pass filter where the local
updates will be assigned as the next gradient updated without considering the
neighboring gradients. The proposed G-Fedfilt algorithm is shown in Algorithm
1.

Table 2: List of notations used in the proposed algorithms. Parameter | Description
---|---
$d_{ij}$ | Distance between devices $i$ and $j$
$d_{max}$ | Maximum distance between paired devices
$h_{s}(\cdot,\mu_{s})$ | Graph filter operator
$\mu_{s}$ | Tunable parameter of $h_{s}$
$\boldsymbol{\widehat{G}}$ | Updated gradient matrix
$\boldsymbol{H}$ | Graph filter in matrix form
$\mathcal{B}_{s_{i,c_{j}}}$ | Mini-batch set for device $i$ in room $c_{j}$
$\beta_{s_{i,c_{j}}}$ | Mini-batch in the set $\mathcal{B}_{s_{i,c_{j}}}$
$\boldsymbol{\Delta}_{s_{i,c_{j}}}$ | Local gradient after each local update
$\boldsymbol{\omega}_{s_{i,c_{j}}}$ | Model weights for device $i$ in room $c_{j}$
$\eta_{s_{i,c_{j}}}$ | Local learning rate
$z_{s_{i,c_{j}}}$ | Sparsification controlling parameter
$q_{s_{i,c_{j}}}$ | Local data number controlling parameter
$Th_{s_{i,c_{j}}}$ | Sparsification threshold
$T$ | Deadline for each Comm. round
$\rho_{s_{i,c_{j}}}$ | Computing intensity
$f_{s_{i,c_{j}}}$ | Number of CPU cycles per sec.
$\varsigma$ | Effective switch capacitance
$b_{s_{i,c_{j}}}$ | Allocated bandwidth
$p^{\textrm{tran}}_{s_{i,c_{j}}}$ | Average transmission power
$n_{0}$ | Power spectral density of the Gaussian noise
$r_{s_{i,c_{j}}}$ | Transmission rate
$(E^{\textrm{comp}}_{s_{i,c_{j}}},E^{\textrm{tran}}_{s_{i,c_{j}}})$ | Comp. and comm. energy consumption
$(\mu_{1},\mu_{2},\mu_{3})$ | Problem $\mathcal{P}^{\prime\prime}$ optimization coefficients
$\alpha_{s_{i,c_{j}}}$ | Number of local training at each comm. round
$\chi(\varphi(\cdot;z_{s_{i,c_{j}}}))$ | Data size of the sparsification function
$\psi(\cdot;q_{s_{i,c_{j}}})$ | Number of data samples used for training
$\chi(\varphi(\cdot;z_{s_{i,c_{j}}}))$ | Data size of the sparsification function
$\psi(\cdot;q_{s_{i,c_{j}}})$ | Number of data samples used for training
$(\tau^{\textrm{comp}}_{s_{i,c_{j}}},\tau^{\textrm{tran}}_{s_{i,c_{j}}})$ | Computation and Comm. time
Algorithm 1 The proposed G-Fedfilt Algorithm

Input: model weights $\boldsymbol{\omega}^{(0)}_{s_{i,c_{j}}}$,$N$,
$K_{c_{j}}$, $K$, number of comm. rounds $R$, number of local training updates
$\alpha_{s_{i,c_{j}}}$, device distances $d_{ij}$, $d_{max}$, filter parameter
$\mu_{s}$.

1:procedure G-Fedfilt

2:  _Edge Server Initialization:_

3:
$(\boldsymbol{A})_{ij}\leftarrow\left\\{\begin{matrix}1&\textrm{if}~{}d_{ij}<d_{max}\\\
0&\textrm{otherwise}\end{matrix}\right.,$

4:
$\kappa_{s_{i,c_{j}}}\leftarrow\dfrac{|D_{s_{i,c_{j}}}|}{\sum^{N}_{j=1}\sum^{K_{c_{j}}}_{i=1}|D_{s_{i,c_{j}}}|}$

5: Get $\boldsymbol{\Lambda}$ and $\boldsymbol{V}$ by eigenvalue decomp. of
$\boldsymbol{L}=\boldsymbol{D}-\boldsymbol{A}$

6: $h_{s}(\boldsymbol{\Lambda};\mu_{s})\leftarrow h_{s}(\lambda;\mu_{s})$
$\triangleright$ Matrix format

7:
$\boldsymbol{H}\leftarrow\boldsymbol{\boldsymbol{V}}h_{s}(\boldsymbol{\Lambda})\boldsymbol{V}^{T}$

8: for each round $t=1,...,R$ do

9:  _Edge user Side_

10: for each device $s_{i,c_{j}}\in\mathcal{K}_{c_{j}}$ in parallel do

11: $\boldsymbol{\omega}^{(t+1)}_{s_{i,c_{j}}}\leftarrow$
ClientUpdate($\boldsymbol{\omega}^{(t)}_{s_{i,c_{j}}}$,$\alpha_{s_{i,c_{j}}}$)

12:
$\boldsymbol{g}^{(t+1)}_{s_{i,c_{j}}}\leftarrow\boldsymbol{\omega}^{(t+1)}_{s_{i,c_{j}}}-\boldsymbol{\omega}^{(t)}_{s_{i,c_{j}}}$

13: Transmit $\boldsymbol{g}^{(t+1)}_{s_{i,c_{j}}}$ to the edge server End for

14:  _Edge Server Side_ :

15: Stack $\boldsymbol{g}^{(t+1)}_{s_{i,c_{j}}}$ to create
$\boldsymbol{G}^{(t+1)}$

16:
$\boldsymbol{\widehat{G}}^{(t+1)}\leftarrow\boldsymbol{H}\textrm{diag}[\kappa_{1},...,\kappa_{K}]\boldsymbol{G}^{(t+1)},$

17: Broadcast $\boldsymbol{\widehat{G}}^{(t+1)}$ End for End procedure

1:function
ClientUpdate($\boldsymbol{\omega}^{(t)}_{s_{i,c_{j}}}$,$\alpha_{s_{i,c_{j}}}$)

2: for each local update $l=1,...,\alpha_{s_{i,c_{j}}}$ do

3: $\mathcal{B}_{s_{i,c_{j}}}\leftarrow$ create a set of mini-batches from
$\mathcal{D}_{s_{i,c_{j}}}$

4: for each mini-batch $\beta_{s_{i,c_{j}}}\in\mathcal{B}_{s_{i,c_{j}}}$ do

5:
$\boldsymbol{\Delta}_{s_{i,c_{j}}}^{(t-1)}\leftarrow\dfrac{1}{|\beta^{(t)}_{s_{i,c_{j}}}|}\sum_{(x_{n},y_{n})\in\beta^{(t)}_{s_{i,c_{j}}}}\bigtriangledown
L(F_{s_{i,c_{j}}},y_{n})$

6:
$\boldsymbol{\omega}_{s_{i,c_{j}}}^{(t+1)}\leftarrow\boldsymbol{\omega}_{s_{i,c_{j}}}^{(t)}-\eta^{(t)}_{s_{i,c_{j}}}\boldsymbol{\Delta}_{s_{i,c_{j}}}^{(t)}$
End for End for

7: return $\boldsymbol{\omega}_{s_{i,c_{j}}}^{(t+1)}$ End function

###  3.5 Parameter Optimization For Communication Efficiency

The primary goal of this section is to reduce the latency and the
desynchronization caused by the system heterogeneity of devices in each
$c_{j}\in\mathcal{N}$. In the following, we elaborate on the details and
formulations of this problem and our solution embedded in the proposed GFIoTL.

We define a deadline $T$ in second for each round of communication within
which all gradient updates must have already been received by the edge server.
This means that each device $s_{i,c_{j}}\in\mathcal{K}_{c_{j}}$ in room
$c_{j}$ must perform its local update computation and communication before
$T$. This parameter depends on the index $t$ meaning that its value is subject
to change at the onset of every first device-based update. This is due to the
high-performance variability and heterogeneity, even for the same device
(Nishio and Yonetani, 2019). Here, for simplicity of notation presentation, we
drop the time index $t$ and make the point that each following calculation is
performed at the beginning of the first device-based update back in the edge
server.

There exist two sources of energy consumption in each device
$s_{i,c_{j}}\in\mathcal{K}_{c_{j}}$. The first source is the computation
energy caused by the local training and the second one is the communication
energy wasted during the data transmission. For each, we calculate the time of
which they perform the task (i.e., computation and communication) as
demonstrated in (Cui et al., 2017).

Local Computation: Let $\rho_{s_{i,c_{j}}}$ denote the computing intensity (in
the unit of CPU cycle per sample) of the device $s_{i,c_{j}}$ and
$f_{s_{i,c_{j}}}$ the computation capacity measured by the number of CPU
cycles per second. Therefore, the computation time for $\alpha_{s_{i,c_{j}}}$
rounds of local update for device $s_{i,c_{j}}$ is calculated as

$\tau^{\textrm{comp}}_{s_{i,c_{j}}}=\dfrac{\alpha_{s_{i,c_{j}}}\psi(\mathcal{D}_{s_{i,c_{j}}};q_{s_{i,c_{j}}})\rho_{s_{i,c_{j}}}}{f_{s_{i,c_{j}}}},~{}\forall
s_{i,c_{j}}\in\mathcal{K}_{c_{j}},$ (14)

where
$\psi(\mathcal{D}_{s_{i,c_{j}}};q_{s_{i,c_{j}}})=[q_{s_{i,c_{j}}}|\mathcal{D}_{s_{i,c_{j}}}|]$
represents a function characterized by $q_{s_{i,c_{j}}}\in(0,1)$ for how much
percentage of the number of local dataset is to be used in the training
process at each communication round. Moreover, the total energy consumption
due to the computation at each device-based update is derived as

$E_{s_{i,c_{j}}}^{\textrm{comp}}=\varsigma\alpha_{s_{i,c_{j}}}\psi(\mathcal{D}_{s_{i,c_{j}}};q_{s_{i,c_{j}}})\rho_{s_{i,c_{j}}}f^{2}_{s_{i,c_{j}}},$
(15)

where $\varsigma$ represents the effective switched capacitance that depends
on the chip architecture.

Wireless Communication: With regard to the communication between smart devices
and the edge server, we consider an Orthogonal Frequency-Division Multiple
Access (OFDMA) technique where a subset of subcarriers are assigned to the
smart devices. Accordingly, denoting $b_{s_{i,c_{j}}}$ as the allocated
bandwidth to device $s_{i,c_{j}}$, the achievable transmission rate of device
$s_{i,c_{j}}$ is obtained as

$r_{s_{i,c_{j}}}=b_{s_{i,c_{j}}}\log_{2}\left(1+\dfrac{\xi_{s_{i,c_{j}}}p^{\textrm{tran}}_{s_{i,c_{j}}}}{n_{0}b_{s_{i,c_{j}}}}\right),~{}~{}\forall
s_{i,c_{j}}\in\mathcal{K}_{c_{j}},$ (16)

where $\xi_{s_{i,c_{j}}}$ denotes the channel gain between device
$s_{i,c_{j}}$ and the edge server, $p^{\textrm{tran}}_{s_{i,c_{j}}}$
represents the average transmit power of device $s_{i,c_{j}}$, and $n_{0}$ is
the power spectral density of the Gaussian noise. Since a limited bandwidth is
available, we also have the constraint
$\sum_{i=1}^{k_{c_{j}}}\sum_{j=1}^{N}b_{s_{i,c_{j}}}\leq\beta$ where $\beta$
is the total bandwidth. Moreover, we define
$\chi(\varphi(\boldsymbol{g}_{s_{i,c_{j}}};z_{s_{i,c_{j}}})):\mathbb{R}^{B}\rightarrow\mathbb{R}$
to determine the data size of the $\varphi$’s output. Note that
$\chi(\varphi(\boldsymbol{g}_{s_{i,c_{j}}};z_{s_{i,c_{j}}}))$ is increasing
with respect to $z_{s_{i,c_{j}}}$. As an example, decreasing $z_{s_{i,c_{j}}}$
creates a sparser gradient output derived from
$\varphi(\boldsymbol{g}_{s_{i,c_{j}}};z_{s_{i,c_{j}}})$ and consequently, the
data size indicated by
$\chi(\varphi(\boldsymbol{g}_{s_{i,c_{j}}};z_{s_{i,c_{j}}}))$ becomes smaller.
Thus, the transmission time between each device $s_{i,c_{j}}$ and the edge
server is derived as follows:

$\tau^{\textrm{tran}}_{s_{i,c_{j}}}=\dfrac{\chi(\varphi(\boldsymbol{g}_{s_{i,c_{j}}};z_{s_{i,c_{j}}}))}{r_{s_{i,c_{j}}}}.$
(17)

Accordingly, the energy consumption caused by the transmission is given by

$E_{s_{i,c_{j}}}^{\textrm{tran}}=p^{\textrm{tran}}_{s_{i,c_{j}}}\tau^{\textrm{tran}}_{s_{i,c_{j}}}.$
(18)

Furthermore, the latency of device $s_{i,c_{j}}$ at each communication round
is defined as

$\tau_{s_{i,c_{j}}}=\tau^{\textrm{comp}}_{s_{i,c_{j}}}+\tau^{\textrm{tran}}_{s_{i,c_{j}}}\leq
T.$ (19)

To reduce the total amount of communication and computation time for each
device $s_{i,c_{j}}$, four parameters need to be tuned: $i)$ the number of
rounds in each local update, $\alpha_{s_{i,c_{j}}}$, $ii)$ the portion of
local data set used for training in each round, $q_{s_{i,c_{j}}}$, $iii)$ the
sparsification parameter $z_{s_{i,c_{j}}}$, and $iv)$ the deadline in each
communication round, $T$. In this regard, we aim to minimize the latency in
each communication round, $T$, while maximizing $\alpha_{s_{i,c_{j}}}$,
$q_{s_{i,c_{j}}}$, and $z_{s_{i,c_{j}}}$. To achieve this goal, we formulate
the following optimization problem ($\mathcal{P}$) which is solved by the edge
server at the beginning of each round:

$\displaystyle\mathcal{P}:$
$\displaystyle\max_{\boldsymbol{\alpha},\boldsymbol{q},\boldsymbol{z},T}~{}~{}~{}~{}~{}\boldsymbol{F}=\\{\alpha_{s_{i,c_{j}}},q_{s_{i,c_{j}}},z_{s_{i,c_{j}}},\frac{1}{T}\\}$
(20) s.t.
$\displaystyle(C_{1})~{}\tau^{\textrm{comp}}_{s_{i,c_{j}}}+\tau^{\textrm{tran}}_{s_{i,c_{j}}}\leq
T~{},~{}\forall s_{i,c_{j}}\in\mathcal{K}_{c_{j}},$ (21)
$\displaystyle(C_{2})~{}E_{s_{i,c_{j}}}^{\textrm{comp}}+E_{s_{i,c_{j}}}^{\textrm{tran}}\leq
E_{s_{i,c_{j}}}^{\textrm{max}}~{},~{}\forall
s_{i,c_{j}}\in\mathcal{K}_{c_{j}},$ (22)
$\displaystyle(C_{3})~{}\alpha_{s_{i,c_{j}}}^{\textrm{min}}\leq\alpha_{s_{i,c_{j}}}\leq\alpha_{s_{i,c_{j}}}^{\textrm{max}},\alpha_{s_{i,c_{j}}}\in\mathbb{N},~{}\forall
s_{i,c_{j}}\in\mathcal{K}_{c_{j}},$ (23)
$\displaystyle(C_{4})~{}q_{s_{i,c_{j}}}^{\textrm{min}}\leq q_{s_{i,c_{j}}}\leq
1~{},~{}\forall s_{i,c_{j}}\in\mathcal{K}_{c_{j}},$ (24)
$\displaystyle(C_{5})~{}z_{s_{i,c_{j}}}^{\textrm{min}}\leq z_{s_{i,c_{j}}}\leq
1~{},~{}\forall s_{i,c_{j}}\in\mathcal{K}_{c_{j}},$ (25)

where
$\boldsymbol{\alpha}=[\alpha_{s_{1,c_{1}}},...,\alpha_{s_{K_{c_{N}},c_{N}}}]$,
$\boldsymbol{q}=[q_{s_{1,c_{1}}},...,q_{s_{K_{c_{N}},c_{N}}}]$, and
$\boldsymbol{z}=[z_{s_{1,c_{1}}},...,z_{s_{K_{c_{N}},c_{N}}}]$ are the vectors
containing the variables of the optimization problem. As it can be seen from
(20), problem $\mathcal{P}$ is a multi-objective problem. Note that
constraints (24) and (25) are linear and do not violate the convexity of the
problem. However, functions $\psi(\mathcal{D}_{s_{i,c_{j}}};q_{s_{i,c_{j}}})$
and $\chi(\varphi(\boldsymbol{g}_{s_{i,c_{j}}};z_{s_{i,c_{j}}}))$ are non-
convex with respect to $q_{s_{i,c_{j}}}$ and $z_{s_{i,c_{j}}}$, thus,
according to (14) and (17), constraint $(C_{1})$ is non-convex for
$q_{s_{i,c_{j}}}$ and $z_{s_{i,c_{j}}}$. Similarly, it can be understood from
(15) and (18) that the left side of constraint $(C_{2})$ provides non-
convexity for variables $q_{s_{i,c_{j}}}$ and $z_{s_{i,c_{j}}}$. Moreover, the
integer parameter $\alpha_{s_{i,c_{j}}}$ used in constraints
$(C_{1})$-$(C_{3})$ is non-convex.

Additionally, the objective function and the constraints in optimization
problem $\mathcal{P}$ are convex with respect to $T$. Hence, to solve
optimization problem $\mathcal{P}$, we first derive the optimum value for $T$,
denoted by $T^{\textrm{opt}}$. Then, given the optimal value of $T$, we
substitute it in problem $\mathcal{P}$ and optimize the other optimization
variables, i.e., $\boldsymbol{\alpha}$, $\boldsymbol{q}$ and $\boldsymbol{z}$.
As it can be seen from Fig. 4, the minimum value of $T$ is equal to the
latency of the device with the biggest delay. In other words,

$T=\text{max}~{}~{}~{}\tau^{\textrm{comp}}_{s_{i,c_{j}}}+\tau^{\textrm{tran}}_{s_{i,c_{j}}},~{}\forall
s_{i,c_{j}}\in\mathcal{K}_{c_{j}}.$ (26)

Figure 4: An illustration of the system heterogeneity in the training phase
and the effect of the proposed parameter optimization scheme on reducing the
latency in each communication round.

Hence, it is aimed to minimize the latency of the slowest device participating
in the current communication round. To reach the minimum value for $T$, we
first derive a lower bound for the latency of each smart device. According to
(14) and (17), and considering that $\psi(.)$ and $\varphi(.)$ are increasing
functions with respect to $\alpha_{s_{i,c_{j}}}$, $q_{s_{i,c_{j}}}$ and
$z_{s_{i,c_{j}}}$, respectively, it is concluded that both terms of delays
(i.e., transmission and computation terms) have an increasing relationship
with the optimization variables, $\alpha_{s_{i,c_{j}}}$, $q_{s_{i,c_{j}}}$,
and $z_{s_{i,c_{j}}}$. Therefore, the minimum latency for each device
$s_{i,c_{j}}$ is achieved when the optimization variables are equal to their
lowest values (i.e.,
$\widetilde{\alpha}_{s_{i,c_{j}}}=\alpha_{s_{i,c_{j}}}^{\text{min}}$,
$\widetilde{q}_{s_{i,c_{j}}}=q_{s_{i,c_{j}}}^{\text{min}}$, and
$\widetilde{z}_{s_{i,c_{j}}}=z_{s_{i,c_{j}}}^{\text{min}}$). Thus, the lower
bound for the latency of each smart device $s_{i,c_{j}}$, denoted by
$\widetilde{\tau}_{s_{i,c_{j}}}$, is obtained by applying
$\widetilde{\alpha}_{s_{i,c_{j}}}$, $\widetilde{q}_{s_{i,c_{j}}}$, and
$\widetilde{z}_{s_{i,c_{j}}}$ in (19). Finally, according to (26), the optimum
value for $T$ is the latency of the slowest device given as

$T^{\textrm{opt}}=\text{max}~{}\widetilde{\tau}_{s_{i,c_{j}}}.$ (27)

To proceed with solving problem $\mathcal{P}$, we substitute
$T=T^{\text{opt}}$ and relax constraints $(C_{1})$ and $(C_{2})$ which are
non-convex for the optimization variables $\alpha_{s_{i,c_{j}}}$,
$q_{s_{i,c_{j}}}$ and $z_{s_{i,c_{j}}}$. To cope with the non-convexity caused
by $\psi(\mathcal{D}_{s_{i,c_{j}}};q_{i,c_{j}})$ in (14) and (15), we use the
following estimation in constraints $(C_{1})$ and $(C_{2})$ as
$q_{s_{i,c_{j}}}|\mathcal{D}_{s_{i,c_{j}}}|>>1$ is a relatively large number.

$\psi(\mathcal{D}_{s_{i,c_{j}}};q_{s_{i,c_{j}}})=[q_{s_{i,c_{j}}}|\mathcal{D}_{s_{i,c_{j}}}|]\approx
q_{s_{i,c_{j}}}|\mathcal{D}_{s_{i,c_{j}}}|.$ (28)

To remove the non-convexity imposed by function $\varphi(.)$, it can be shown
that $\chi(\varphi(\boldsymbol{g}_{s_{i,c_{j}}};z_{s_{i,c_{j}}}))$ is
increasing with respect to $z_{s_{i,c_{j}}}$. In other words, maximizing
$\chi(\varphi(\boldsymbol{g}_{s_{i,c_{j}}};z_{s_{i,c_{j}}}))$ leads to
maximizing $z_{s_{i,c_{j}}}$. Thus, we replace $z_{s_{i,c_{j}}}$ in the
objective function with
$\chi(\varphi(\boldsymbol{g}_{s_{i,c_{j}}};z_{s_{i,c_{j}}}))$ which makes the
both constraints $(C_{1})$ and $(C_{2})$ convex. In addition, we relax the
integer variable $\alpha_{s_{i,c_{j}}}$ to remove the non-convexity in
constraints $(C_{1})$-$(C_{3})$. Finally, by applying the optimal value of $T$
in (27), problem $\mathcal{P}$ is converted to the following optimization
problem:

$\displaystyle\mathcal{P^{\prime}}:$
$\displaystyle\max_{\boldsymbol{\alpha},\boldsymbol{q},\boldsymbol{\varphi}}~{}~{}~{}\widetilde{\boldsymbol{F}}=\\{\alpha_{s_{i,c_{j}}},q_{s_{i,c_{j}}},\chi(\varphi(\boldsymbol{g}_{s_{i,c_{j}}};z_{s_{i,c_{j}}}))\\}$
(29) s.t.
$\displaystyle(C_{1})~{}\tau^{\textrm{comp}}_{s_{i,c_{j}}}+\tau^{\textrm{tran}}_{s_{i,c_{j}}}=T^{\text{opt}}~{},~{}\forall
s_{i,c_{j}}\in\mathcal{K}_{c_{j}},$ (30)
$\displaystyle(C_{3})~{}\alpha_{s_{i,c_{j}}}^{\textrm{min}}\leq\alpha_{s_{i,c_{j}}}\leq\alpha_{s_{i,c_{j}}}^{\textrm{max}}~{},~{}\forall
s_{i,c_{j}}\in\mathcal{K}_{c_{j}},$ (31)
$\displaystyle(\ref{e_bound}),(\ref{q_bound}),(\ref{z_bound}).$

The next step in solving the optimization problem $\mathcal{P}$ is to maximize
$\alpha_{s_{i,c_{j}}}$, $q_{s_{i,c_{j}}}$, and
$\chi(\varphi(\boldsymbol{g}_{s_{i,c_{j}}};z_{s_{i,c_{j}}}))$ according to the
optimum value of $T=T^{\textrm{opt}}$ such that smart devices deliver their
local models to the edge server at the same time. In order to solve
$\mathcal{P}^{\prime}$, we first make a single dimensionless objective
function by dividing the objectives to their nominal values,
$\alpha_{s_{i,c_{j}}}^{\textrm{max}}$, $q_{s_{i,c_{j}}}^{\textrm{max}}$, and
$\chi_{s_{i,c_{j}}}^{\textrm{max}}$, respectively, for $\alpha_{s_{i,c_{j}}}$,
$q_{s_{i,c_{j}}}$, and
$\chi(\varphi(\boldsymbol{g}_{s_{i,c_{j}}};z_{s_{i,c_{j}}}))$. Additionally,
we assign weight coefficients $\mu_{1}$, $\mu_{2}$, and $\mu_{3}$, where
$\mu_{1}+\mu_{2}+\mu_{3}=1$, to model the relative importance among variables
for each device. Thus, the optimization problem $\mathcal{P}^{\prime}$ is
converted to the following problem:

$\displaystyle\mathcal{P}^{\prime\prime}:$
$\displaystyle\max_{\boldsymbol{\alpha},\boldsymbol{q},\boldsymbol{z}}~{}~{}~{}\frac{\mu_{1}}{\alpha_{s_{i,c_{j}}}^{\textrm{max}}}\alpha_{s_{i,c_{j}}}+\frac{\mu_{2}}{q_{s_{i,c_{j}}}^{\textrm{max}}}q_{s_{i,c_{j}}}$
(32)
$\displaystyle+\frac{\mu_{3}}{\chi_{s_{i,c_{j}}}^{\textrm{max}}}\chi(\varphi(\boldsymbol{g}_{s_{i,c_{j}}};z_{s_{i,c_{j}}}))$
$\displaystyle\textbf{s.t.}~{}~{}~{}~{}(\ref{e_bound}),(\ref{q_bound}),(\ref{z_bound}),(\ref{T_bound_new}),(\ref{a_bound_new}).$

Problem $\mathcal{P}^{\prime\prime}$ is convex and can be solved with the
standard optimization techniques, such as convex optimization and barrier
methods (Boyd and Vandenberghe, 2004) that are employed in MATLAB CVX
optimization toolbox (Grant and Boyd, 2014). Note that the optimal value for
$z_{s_{i,c_{j}}}$ can be obtained with the optimum
$\chi(\varphi(\boldsymbol{g}_{s_{i,c_{j}}};z_{s_{i,c_{j}}}))$ as it is
increasing with respect to $z_{s_{i,c_{j}}}$.

##  4 Simulation Results

In this section, we evaluate the proposed G-Fedfilt algorithm in the
introduced GFIoTL framework and the proposed parameter optimization for
communication efficiency in FL. The cornerstone of the proposed GFIoTL
framework is task-independent meaning that, given the ML models deployed on
various devices, the proposed approach trains the models in a federated manner
and based on their connections on the graph. In summary, there are four
components required for the GFIoTL framework to perform on smart home
applications such as HAR; $1)$ device hardware specifications for parameter
optimization, $2)$ the ML models, $3)$ the data with which models are being
trained, and $4)$ a criterion for the representative graph’s connectivity.
Based on such requirements, we test the applicability and performance of the
proposed scheme in a typical simulation environment similar to smart home/room
application scenarios. We also aim to find the answer to the following
questions:

$\bullet$ Does G-Fedfilt incorporate FedAvg?

$\bullet$ What is the impact of graph filtering in model personalization under
label and data heterogeneity?

$\bullet$ Can we personalize the models over their local datasets while
keeping a level of generalization when it comes to data from other
distributions?

$\bullet$ Does exploiting devices’ relationship in the form of a graph
contribute to the models’ accuracy?

$\bullet$ Is it possible to decrease the communication round delay while
involving devices with the system heterogeneity and performance variability.

To seek the answer to above questions and evaluate GFIoTL performance on the
simulation environment, we conduct various numerical experiments with
different scenarios. The specification of the simulation is as follows.

###  4.1 Experimental Setup

Throughout the simulations, we consider $K=20$ heterogeneous edge devices
spread out in $N=4$ smart rooms with the square area of $A_{j}\times
B_{j}\times C_{j}=10^{3}$ m3 such that $K_{c_{j}}\sim Du(4,7)$, $\forall
c_{j}$, where $Du(\cdot)$ indicates the discrete uniform distribution. It is
assumed that the edge server is close by, and the link between devices and the
edge server is error-less. It is worthwhile to note that although the purpose
of the setup is for the training phase, one can exploit such an arrangement
for the inference phase in the case of HAR applications. In this scenario,
smart devices in each room collect data on the client and make an inference
about their activity. Eventually, the edge server gathers the decisions and
makes the final vote.

Furthermore, we presume a deterministic graph structure $\mathcal{G}$ in the
experiments illustrated in Fig. 5. Note that the graph frequencies of
$\mathcal{G}$ are the horizontal lines shown in Fig. 2. In particular, there
are $20$ eigenvalues each corresponding to the graph frequencies where the
first one with the value $0$ indicates the DC and the last one with the value
$8.06$ corresponds to the highest graph frequency in $\mathcal{G}$. Moreover,
the power spectral density of the white noise is set to $n_{0}=-174$ dBm/Hz
and the effective switched capacitance is fixed to $\varsigma=10^{-28}$ as
suggested in (Mao et al., 2016). To have a more realistic scenario, we sample
heterogeneous values for the computing intensity, computation capacity, and
the average transmit power from the uniform distribution $U$ as
$\rho_{s_{i,c_{j}}}\sim U(1,3.5)$ cycles/sample, $f_{s_{i,c_{j}}}\sim
U(1,3.5)$ GHz, and $P_{s_{i,c_{j}}}\sim U(0.5,1)$ W, respectively.
Furthermore, we assume full participation where all devices share their models
at each communication round. We also set $\alpha_{s_{i,c_{j}}}=3$ for the
device-based number of iterations in all our experiments, except in the
parameter optimization simulation. The whole parameter specifications are
gathered in Table 3 for convenience.

Figure 5: The graph structure used in the simulation. Each node represents a device with different performance capability and data/label heterogeneity. The distance between nodes in this figure does not indicate the actual distance between devices. Table 3: Simulation parameters.  Parameter | Value
---|---
$A_{j}\times B_{j}\times C_{j}$ |  $10^{3}$ m3 , $\forall c_{j}$
$N$ | $4$
$K_{c_{j}}$ | $\\{K_{c_{j}}\sim Du(4,7)|K=20\\}$
$n_{0}$ |  $-174$ dbm/Hz
$\rho_{s_{i,c_{j}}}$ |  $U(1,5)\times 10^{4}$ cycles/sample
$\varsigma$ | $10^{-28}$
$f_{s_{i,c_{j}}}$ |  $U(1,3.5)$ GHz
$p^{\textrm{tran}}_{s_{i,c_{j}}}$ |  $U(0.5,1)$ W
$\xi_{s_{i,c_{j}}}$ |  $U(1,2)$ dB
$\beta$ | 20 MHz

Heterogeneity indicator: To have a quantitative representation of the system
heterogeneity, we define

$H=1-\dfrac{1}{K}\sum_{j=1}^{N}\sum_{i=1}^{K_{c_{j}}}\dfrac{Min\\{\widehat{\tau}_{s_{i,c_{j}}}\\}}{\widehat{\tau}_{s_{i,c_{j}}}},$
(33)

where $\widehat{\tau}_{s_{i,c_{j}}}$ indicates the total computation and
communication time given $\psi(\mathcal{D}_{s_{i,c_{j}}};q_{s_{i,c_{j}}})=1$
and $\chi(\varphi(\boldsymbol{g}_{s_{i,c_{j}}};z_{s_{i,c_{j}}}))=1$. The
indicator in (33) suggests a high performance variability if $H\rightarrow 1$
and vice versa.

In addition, we opt to assess the proposed framework for the image
classification as an example of the computer vision application. In this
regard, a deep model implemented in Tensorflow is used consisting of $32$ and
$64$ Conv2D filters, respectively, each with the kernel size of $3$ and stride
$2$ followed by a ReLu activation function and a maxpooling layer with $(2,2)$
pooling size. The last layer of this convolutional layer is then connected to
the fully connected layers with the $128$ and $10$ neurons in each successive
layer. It should be noted that the main goal in this work is not to achieve a
state-of-the-art image classification accuracy. Here, we aim to compare the
proposed approach in model personalization and the impact of graph filtering
with different settings in our GFIoTL framework using the G-Fedfilt
aggregation rule. Indeed, a more complex deep model can achieve higher
accuracy, however, the relative results provided in this paper can still apply
using a different deep model.

###  4.2 Datasets

We consider MNIST333http://yann.lecun.com/exdb/mnist/ and its extension,
EMNIST datasets, that are commonly used for the evaluation of image
classification tasks. We leverage such generic datasets because they are
standard and recognizable datasets for ML model evaluation. MNIST gives a
moderate and typical complexity of IoT applications (Zhao et al., 2020).
Furthermore, it is straightforward to create different levels of label
heterogeneity, as a form of statistical heterogeneity to evaluate the
framework. It is also noteworthy to mention that the MNIST dataset has been
used extensively for testing FL frameworks and IoT systems (Xu et al., 2020;
Mills et al., 2019). MNIST consists of $60,000$ training and $10,000$ testing
examples of $28\times 28$ digit images with $0$ to $9$ as the labels. For the
MNIST dataset, we take the same step as (McMahan et al., 2017) to create
different label-heterogeneous Non-i.i.d./i.i.d. datasets. In particular, three
datasets are created and indicated respectively as MNIST2, MNIST4, and
MNIST10, where for MNIST2 there only exist two classes per device, MNIST4 four
classes per device, and for MNIST10 all classes exists at each device
$s_{i,c_{j}}\in\mathcal{K}_{c_{j}}$. Such label heterogeneity is quite common
in smart home application scenarios. For instance, in the case of HAR, one
client might avoid activities such as exercising and running. Consequently,
the datasets collected by devices will only contain partial labels. We choose
$D_{s_{i,c_{j}}}=450$, $\forall s_{i,c_{j}}$, for the training dataset. To
evaluate the personalization of the models over their local dataset as well as
their generalization, we create two types of test sets. The first set
indicated as “local test set” is created with the same label distribution as
the training set with $100$ data samples; and the second one, “global test
set”, is created with all the labels to create $100$ data samples. Such a test
set is important since, in personalized FL, it is often straightforward to
notice a decrease in accuracy when data from other distributions is tested on
a personalized model. Thus, a global test set could potentially indicate how
much the generalization of the model is lost because of personalization.

The EMNIST dataset is by default, a heterogeneous set with data heterogeneity.
The dataset is similar to the situation in HAR applications where each client
has its own way of performing an activity distinctive to others. Here, we only
considered the digit images for the training where each device has
$D_{s_{i,c_{j}}}=450$ training samples. This dataset has a data heterogeneity
(as oppose to label heterogeneity) since the authors have a different
handwriting. In the case of the test set, we follow the same step as for the
MNIST dataset where there are two local and global test sets. Throughout the
simulations, we also average the model accuracy of edge devices to calculate a
single accuracy. Furthermore, the following experiments and their results are
the averages of $5$ times of simulation run.

###  4.3 Performance Indices

To assess the credibility of the proposed GFIoTL framework, we define various
performance indices in terms of computation, communication, and models’
classification capabilities. For better presentation, the time step $t$ is
dropped in the formulations meaning that the parameters are prone to change at
each communication round $t$. Hence, the metrics are expressed as follows:

Classification metrics: We use four classification performance metrics to
evaluate the behavior of the trained models. To do so, we first define an
$n_{c}\times n_{c}$ confusion matrix $CM_{s_{i,c_{j}}}$ for each model in
device $s_{i,c_{j}}$ where $n_{c}$ is the total number of classes. The
elements of the confusion matrix are filled according to the true and
predicted labels. Overall, $K$ confusion matrices are created due to having
$K$ devices. We then apply a summation to construct a confusion matrix
$CM^{\textrm{total}}=\sum_{j=1}^{N}\sum_{i=1}^{K_{c_{j}}}CM_{s_{i,c_{j}}}$ in
which, all the test samples in the framework are encompassed. Additionally,
$CM^{\textrm{total}}$ can be interpreted through metrics such as accuracy,
precision, recall, and F1-score. We define each metric, respectively, as

$I_{1}=\dfrac{1}{n^{\textrm{total}}}\sum_{i=1}^{n_{c}}TP_{i},$ (34)
$I_{2}=\dfrac{1}{n_{c}}\sum_{i=1}^{n_{c}}\dfrac{TP_{i}}{TP_{i}+FP_{i}},$ (35)
$I_{3}=\dfrac{1}{n_{c}}\sum_{i=1}^{n_{c}}\dfrac{TP_{i}}{TP_{i}+FN_{i}},$ (36)
$I_{4}=\dfrac{2I_{2}\times I_{3}}{I_{2}+I_{3}},$ (37)

where $TP_{i}$, $FP_{i}$, and $FN_{i}$ represent true positives, false
positives, and false negatives in $CM^{\textrm{total}}$ associated with
$i^{th}$ class. Moreover, $n^{\textrm{total}}$ is the total number of samples
in the test set used to evaluate the models.

Computation Cost: This metric determines how much computation is spent on the
local CIoT devices as a whole. The computation cost can be evaluated as the
total sum of Floating-Point Operations (FLOPs) executed on the edge side
expressed as

$I_{5}=\sum_{t=1}^{R}\sum_{j=1}^{N}\sum_{i=1}^{K_{c_{j}}}\alpha_{s_{i,c_{j}}}\phi_{s_{i,c_{j}}}\psi(\mathcal{D}_{s_{i,c_{j}}};q_{s_{i,c_{j}}}),$
(38)

where $\phi_{s_{i,c_{j}}}$ denotes the FLOPs per one input data sample for
device $s_{i,c_{j}}\in\mathcal{K}_{c_{j}}$.

Communication Latency: In FL, the slowest device in the framework always drags
the whole training procedure causing the deadline $T$ to become a large value.
In this regard, the total latency of an FL framework is given by

$I_{6}=\sum_{t=1}^{R}T.$ (39)

Communication Desynchronization: Since CIoT devices have different
computational capabilities and might experience different fading channels, the
gradient updates will not reach the server at the same time. In addition,
different distances between edge devices and the server along with poor
connections exacerbate this phenomenon and prevent a synchronized aggregation.
This causes the edge server to be active for a longer period of time in order
to collect all the gradients. Therefore, it is desirable to minimize the total
desynchronization time at the server side for $R$ rounds defined as:

$I_{7}=\sum_{t=1}^{R}\left(T-\min\\{\tau_{s_{i,c_{j}}}\\}\right).$ (40)

###  4.4 Results and Discussions

In this subsection, the performance of the proposed GFIoTL framework under
various conditions is investigated. We first assess the embedded G-Fedfilt
aggregation rule as the main backbone of the proposed structure. G-Fedfilt is
compared with FedAvg and evaluated with different $h_{s}$ using statistically
heterogeneous datasets. Afterward, we evaluate the impact of parameter
optimization and the subsequent solutions acquired from problem $\mathcal{P}$
in terms of the aforementioned performance indices.

G-Fedfilt as FedAvg: Here, we investigate the relationship between G-Fedfilt
and FedAvg and how it incorporates FedAvg aggregation rule. In this case, we
choose $h_{s}(\lambda;\mu_{s}=10^{4})$ in order to have a complete domain-
agnostic aggregation. Fig. 6 shows the results of FedAvg and G-Fedfilt on the
EMNIST global test set. As observed, both G-Fedfilt and FedAvg achieve almost
the same classification accuracy during each round of communication. Of
course, the learning curves are not exactly overlapping and this is primarily
due to the Tensorflow implementation and the usage of built-in functions for
the training rather than the theoretical aspect of the proposed method.

Figure 6: Classification accuracy of the proposed G-Fedfilt and FedAvg
algorithms trained on EMNIST dataset where the graph filter is designed to
pass only the DC components of the gradient update matrix.

Convergence Behavior: To understand the impact of different graph filtering on
the convergence curves, we run the simulation on MNIST2 and MNIST4 datasets by
adjusting various values for $\mu_{s}$. Fig. 7 shows the convergence curve of
different settings tested on both the local and the global test sets for $200$
communication rounds. In Fig. 7a, it is inferred that decreasing the value of
$\mu_{s}$ results in more personalization of the models on the local test set
at the edge. This is mainly because by adjusting a low value for $\mu_{s}$,
higher graph frequencies remain involved. On the other hand, from Fig. 7b, it
can be seen that the generalization of the models on the global test set often
reduces with lower $\mu_{s}$; however, for some parameters such as $\mu_{s}=1$
or $\mu_{s}=10$, the generalization keeps improving close to FedAvg over the
communication rounds. In other words, G-fedfilt is capable of retaining the
personalization over edge devices while keeping a decent level of
generalization in the models. The same argument applies for the results tested
on MNIST4 shown in Fig. 7c,d; however, since there is less statistical
heterogeneity involved, we do not see large differences between convergence
curves evaluated on the global and local test sets as much as Fig. 7a,b.

(a)  (b)  (c)  (d)

Figure 7: Comparing the performance of the proposed G-Fedfilt aggregation rule with FedAvg using different values of $\mu_{s}$. The models are trained on statistically heterogeneous MNIST2 (a,b) and MNIST4 (c,d) datasets and are evaluated on both the global (right column) and the local (left column) test sets. Table 4: The quantitative results of FedAvg and G-Fedfilt using different parameter settings evaluated on the local test sets and after $200$ communication rounds. The values are indicated as the mean $\pm$ std of the accuracy of $K=20$ devices. Algorithms | Parameters | Datasets
---|---|---
MNIST10 | MNIST4 | MNIST2 | EMNIST
FedAvg | —- | $86.12\pm 4.84$ | $88.37\pm 4.95$ | $79.50\pm 10.32$ | $95.99\pm 6.79$
G-Fedfilt | $\mu_{s}=0.1$ | $79.74\pm 7.91$ | $92.74\pm 4.34$ | $95.62\pm 9.52$ | $96.58\pm 6.44$
$\mu_{s}=1$ | $84.37\pm 5.55$ | $91.12\pm 4.20$ | $92.37\pm 8.14$ | $97.41\pm 6.48$
$\mu_{s}=10$ | $85.50\pm 6.25$ | $89.87\pm 4.43$ | $83.49\pm 9.54$ | $96.16\pm 6.84$
$\mu_{s}=100$ | $85.75\pm 5.37$ | $89.35\pm 4.82$ | $80.49\pm 10.64$ | $95.59\pm 6.84$
Table 5: The quantitative results of FedAvg and G-Fedfilt using different parameter settings evaluated on the global test set and after $200$ communication rounds. The values are indicated as the mean $\pm$ std of the accuracy of $K=20$ devices. Algorithms | Parameters | Datasets
---|---|---
MNIST10 | MNIST4 | MNIST2 | EMNIST
FedAvg | —- | $85.05\pm 0.00$ | $77.27\pm 0.00$ | $76.04\pm 0.00$ | $87.21\pm 0.00$
G-Fedfilt | $\mu_{s}=0.1$ | $80.55\pm 6.56$ | $72.33\pm 4.78$ | $49.03\pm 7.45$ | $80.59\pm 2.02$
$\mu_{s}=1$ | $84.49\pm 1.25$ | $77.27\pm 1.73$ | $73.07\pm 5.38$ | $87.38\pm 0.52$
$\mu_{s}=10$ | $86.02\pm 0.18$ | $77.75\pm 0.34$ | $78.45\pm 0.24$ | $88.09\pm 0.15$
$\mu_{s}=100$ | $85.57\pm.15$ | $78.04\pm 0.07$ | $74.95\pm 0.08$ | $88.14\pm 0.01$

Effect of $\mu_{s}$ Under Statistical Heterogeneity: To have a full
investigation on the tunable parameter $\mu_{s}$ and its behavior under
data/label heterogeneity, we assess the performance of the proposed G-Fedfilt
on i.i.d. dataset such as MNIST10, and Non-i.i.d. datasets including MNIST2,
MNIST4, and EMNIST. Table 4 shows the classification accuracy (mean $\pm$
standard deviation) of the proposed G-Fedfilt algorithm and FedAvg for $K=20$
devices and after $200$ communication rounds evaluated on the local test set.
We observe that when the label and data heterogeneity is involved, G-Fedfilt
achieves better accuracy than Fedavg, from $1.42\%$ for the EMNIST up to
$6.12\%$ for the MNIST2 datasets; while for the MNIST10 where there is no
heterogeneity, it does not perform superior to FedAvg on the local test set.
It is also seen that increasing $\mu_{s}$ would reduce the accuracy since by
doing so, higher frequencies are filtered. On the other hand, when looking at
Table 5, which shows the resultant accuracy on the global test set, we see
that imposing less personalization (by increasing $\mu_{s}$) often eventuates
in a better classification accuracy. This argument fairly applies to all the
datasets. In addition, Table 6 shows the classification performance based on
precision, recall, and F1-score. Here, the models are trained on the
heterogeneous MNIST2 training dataset and tested on its local and global test
sets. As seen, assigning a lower value to $\mu_{s}$ shows better performance
on the local test set. On the other hand, the reduction in $\mu_{s}$ decreases
the performance on the global test set in all three metrics. Based on the
results in Tables 4, 5, and 6, it is rather concrete to say that there is a
trade-off between model personalization and generalization in the G-Fedfilt
aggregation rule that can be adjusted by the parameter $\mu_{s}$.

Effect of Graph Connectivity: Here, we explore the role of devices’
connectivity on the model personalization via a graph. We distribute the MNIST
dataset such that each device $s_{i,c_{j}}$ in cluster $c_{j}\in\mathcal{N}$
has similar label distribution as other devices in $c_{j}$ while, exhibits a
different distribution with devices of other clusters. More specifically, the
device $s_{i_{1},c_{j}}$ has a dataset consisting of $4$ labels, $3$ of which
are labeled the same as the device $s_{i_{2},c_{j}}$. Therefore, the devices
connected in a particular cluster tend to have the same data distribution. We
call this “Setup 1” to further recall that in the simulation. Note that this
behavior of the same distribution in a cluster is not far from a real-world
scenario. This is because the devices in a certain cluster (or a smart
room/home) are often owned by a particular client which makes the data
gathered by edge devices have a similar distribution. To compare this scenario
with a situation where devices in a cluster do not have a similar
distribution, we created “Setup 2” where we randomly selected $4$ labels out
of $10$ for each device without the consideration of their positions in the
graph. These setups are then used for training. We choose FedAvg and G-Fedfilt
with $h_{s}(\lambda;\mu_{s}=10)$ for the aggregation in order to have a fair
comparison irrespective to the graph filter. Fig. 8 illustrates the
convergence curve of such simulation evaluated on the local test set. For
better inspection, the y-axis of this figure starts from $0.6$. As seen,
G-Fedfilt in Setup 1 is consistently better compared to its performance in
Setup 2. Furthermore, when using G-Fedfilt, both setups can achieve better
accuracy than FedAvg. Note that FedAvg performs the same in both setups since
it does not involve the connections of devices. Hence, it is concluded that
the graph connectivity in the proposed GFIoTL framework plays an important
role in the model personalization.

Figure 8: Comparison of the proposed G-Fedfilt and FedAvg convergence curve in two setups on MNIST4 dataset. In Setup 1, edge devices in a certain cluster have similar data distribution while, in Setup 2, their data distributions are randomly chosen.  Table 6: Performance evaluation of the proposed G-Fedfilt and FedAvg algorithms in terms of precision, recall, and F1-score. The algorithms are evaluated on the MNIST2 dataset after $R=200$ communication rounds. The metrics are indicated in %. Algorithm | Parameter |  | Local test set
---
| Global test set
---
Precision | Recall | F1-score | Presicion | Recall | F1-score
FedAvg | ___ | 71.99 | 77.70 | 74.74 | 72.07 | 75.03 | 73.52
G-Fedfilt | $\mu_{s}=0.1$ | 92.85 | 93.72 | 93.29 | 34.93 | 43.17 | 38.61
$\mu_{s}=1$ | 87.14 | 89.68 | 88.39 | 66.53 | 73.20 | 69.70
$\mu_{s}=10$ | 74.58 | 81.78 | 78.01 | 71.73 | 74.41 | 73.04
$\mu_{s}=100$ | 73.91 | 79.36 | 76.54 | 72.51 | 75.49 | 73.96
Table 7: Performance evaluation of the proposed G-Fedfilt in terms of
classification accuracy, communication desybchronization time, and latency
before and after the parameter optimization is tested on MNIST10 global test
set under various system heterogeneity settings.

Heterogeneity | Algorithm | After 200 comm. rounds | After 400 Comm. Rounds | $\Delta$ Acc.(%)
---|---|---|---|---
Acc. (%) | Comm. Desync. (s) | Latency (s) | Acc. (%) | Comm. Desync. (s) | Latency (s)
$H=0.31$ | G-Fedfilt | 86.66 | 167.30 | 349.18 | 88.01 | 319.8 | 680.34 | $+1.35$
G-FedfiltOpt | 84.52 | 0.62 | 181.87 | 87.65 | 1.11 | 356.46 | $+3.13$
$H=0.54$ | G-Fedfilt | 86.66 | 453.00 | 661.78 | 88.01 | 921.51 | 1332.92 | $+1.35$
G-FedfiltOpt | 82.24 | 12.68 | 220.04 | 86.25 | 25.82 | 443.17 | $+4.01$
$H=0.65$ | G-Fedfilt | 86.66 | 861.59 | 1009.50 | 88.01 | 1706.69 | 2004.61 | $+1.35$
G-FedfiltOpt | 74.41 | 55.09 | 201.90 | 83.05 | 108.23 | 399.04 | $+8.64$

Communication Desynchronization Alleviation: In this simulation, we
investigate the effect of dynamic values for
$\psi(\mathcal{D}_{s_{i,c_{j}}};q_{s_{i,c_{j}}})$ and
$\chi(\varphi(\boldsymbol{g}_{s_{i,c_{j}}};z_{s_{i,c_{j}}}))$ on the
communication desynchronization and latency when the control parameters
$z_{s_{i,c_{j}}}$, $q_{s_{i,c_{j}}}$, and $\alpha_{s_{i,c_{j}}}$ are optimized
based on solving problem $\mathcal{P}$. We set $\mu_{1}=\mu_{2}=0.4$ and
$\mu_{3}=0.2$ for solving the optimization problem in the simulation where
$\mu_{1}+\mu_{2}+\mu_{3}=1$. Note that the reason for selecting a smaller
$\mu_{3}$ lies behind the fact that it is experimentally shown in (Aji and
Heafield, 2017), that almost $90\%$ of the gradients to be sent to the server
can be ignored with nearly no loss of classification accuracy. In addition,
maximizing $\psi(\mathcal{D}_{s_{i,c_{j}}};q_{s_{i,c_{j}}})$ and
$\alpha_{s_{i,c_{j}}}$ participate more to higher classification accuracy
compared to that of $z_{s_{i,c_{j}}}$ which corresponds to decreasing the
sparsification. We further opt to select $b_{s_{i,c_{j}}}=\frac{\beta}{K}$,
$q_{s_{i,c_{j}}}^{\textrm{min}}=0.3$, $\alpha_{s_{i,c_{j}}}^{\textrm{min}}=1$,
$\alpha_{s_{i,c_{j}}}^{\textrm{max}}=5$, and
$z_{s_{i,c_{j}}}^{\textrm{min}}=0.1$, $\forall
s_{i,c_{j}}\in\mathcal{K}_{c_{j}}$, for simplicity and to have a minimum
convergence requirement for the training process. Thus, after the
optimization, the number of data samples for training and the sparsified
gradients required to be sent to the server is obtained for each device. We
determine different heterogeneous settings, indicated by $H$, by producing
random values for simulation parameters specified in Table 3. The performance
of the proposed G-Fedfilt algorithm with $\mu_{s}=10$ is evaluated in Table 7
before and after the framework is optimized for different $H$. Moreover, the
models are trained on MNIST10 dataset and evaluated on its global test set.
After $200$ communication rounds, we can observe that there is a $99.63\%$ and
$47.91\%$ reduction in the total communication desynchronization and latency
when comparing G-FedfiltOpt with G-Fedfilt for $H=0.31$; although, it costs
$2.14\%$ accuracy reduction. It is also seen that when $H$ increases, the
desynchronization time and the latency are affected less for G-FedfiltOpt than
that of G-Fedfilt; however, the accuracy decreases largely. One more important
result that can be deduced in Table 7 is that when executing the algorithm for
$400$ communication rounds, the accuracy of G-FedfiltOpt increases at a faster
pace than that of G-Fedfilt. This phenomenon is due to the fact that at each
round of communication some devices with less computational capabilities train
their models with the subset of the true dataset, i.e.,
$\widehat{\mathcal{D}}_{s_{i,c_{j}}}\subseteq\mathcal{D}_{s_{i,c_{j}}}$. Thus,
G-FedfiltOpt eventually achieves comparable accuracy to G-Fedfilt in the long
run. It is worthwhile to note that a larger number of communication rounds
does not mean a longer latency. For instance, we can see in Table 7 that
G-FedfiltOpt achieves $+1\%$ better accuracy than G-Fedfilt with the fairly
similar latency, however, $200$ more communication rounds. In addition, the
bar graph in Fig. 9 shows the computation cost of this simulation under
different heterogeneous settings and after $400$ communication rounds. As
observed, the cost of G-Fedfiltopt is significantly lower than that of
G-Fedfilt which suggests that the optimized G-Fedfilt is also computationally
efficient.

Figure 9: The computation cost of CIoT devices under different system
heterogeneity in terms of Billion FLOPs (BFLOBs) after $400$ communication
rounds.

While it appears that the parameter optimization in the proposed GFIoT scheme
reduces the classification accuracy, from a practical perspective, the cost of
computation and communication might impose more than that of the accuracy
after it surpasses a certain value. This is also intensified when CIoT devices
are involved since they tend to relocate or pull out of the framework by the
owners in the smart building. Another point to highlight here is the fact that
due to the same relocation, device pull-out situation, or communication
failure the graph representation of the network becomes more dynamic than
deterministic as time elapses. Hence, the training procedure must be carried
out as quickly as possible in order to approximate the dynamic graph as fixed
in a limited time interval. Although lessening the latency with the proposed
optimization problem might be one avenue, another fundamental approach is to
design a graph-based FL for CIoT devices that is robust to such dynamics which
we will leave to be addressed in our upcoming works.

##  5 Conclusion

In this paper, we introduced the Graph Federated Internet of Things Learning
(GFIoTL) framework for collaborative training of CIoT devices in a smart
building. To alleviate the effect of statistical heterogeneity, we developed a
GSP-inspired aggregation rule based on graph filtering (G-Fedfilt) that
incorporates the underlying connectivity of smart CIoT devices. This concept
could potentially open up a wide range of filter designs for better model
optimization and tunable personalization. Furthermore, the proposed GFIoTL
framework is equipped with a communication-efficient parameter optimization
scheme in order to lessen the impact of system heterogeneity in the framework.
According to the simulation results, when tuned appropriately, G-Fedfilt was
capable of achieving model personalization while attaining a decent amount of
generalization in contrast to the conventional Federated Averaging (FedAvg).
In addition, when parameter optimization was applied, the computation cost,
communication desynchronization, and latency were reduced dramatically at the
cost of a small reduction in classification accuracy.

## Acknowledgment

This work was partially supported by the Natural Sciences and Engineering
Research Council (NSERC) of Canada.

##  6 Appendix

###  6.1 The Mechanics Behind G-Fedfilt Algorithm

To better understand the proposed G-Fedfilt algorithm, a simplified example is
presented as follows. Consider an undirected light graph with $N=3$ and an
adjacency matrix $\boldsymbol{A}_{3\times 3}$. Each node/device $i$ has a
model with a vector of two variables $\boldsymbol{g_{i}}=[g_{i1},g_{i2}]$. The
Laplacian matrix of $\boldsymbol{A}$ is derived as

$\boldsymbol{L}=\boldsymbol{D}-\boldsymbol{A}=\begin{bmatrix}d_{1}-a_{11}&-a_{12}&-a_{13}\\\
-a_{21}&d_{2}-a_{22}&-a_{23}\\\ -a_{31}&-a_{32}&d_{3}-a_{33}\\\
\end{bmatrix},$ (41)

where $d_{i}=\sum_{j=1}^{3}a_{ij}$ is the degree of each node. We then
decompose $\boldsymbol{L}_{3\times 3}$ as
$\boldsymbol{L}=\boldsymbol{V}\boldsymbol{\Lambda}\boldsymbol{V}^{T}$ and
assume that it has ordered eigenvalues as
$\lambda_{0}<\lambda_{1}<\lambda_{2}$. Thus, the eigenvalues and eigenvectors
can be presented by

$\boldsymbol{V}=\begin{bmatrix}1&v_{12}&v_{13}\\\ 1&v_{22}&v_{23}\\\
1&v_{32}&v_{33}\\\ \end{bmatrix},\boldsymbol{\Lambda}=\
\begin{bmatrix}\lambda_{0}&0&0\\\ 0&\lambda_{1}&0\\\ 0&0&\lambda_{2}\\\
\end{bmatrix},$ (42)

with $\lambda_{0}=0$. Note that the corresponding eigenvector of
$\lambda_{0}=0$ is always a vector of identical values, here normalized as
$1$s. To construct the gradient matrix of the models, we stack
$\boldsymbol{g}_{i}$ horizontally as

$\boldsymbol{G}=\begin{bmatrix}g_{11}&g_{12}\\\ g_{21}&g_{22}\\\
g_{31}&g_{32}\\\ \end{bmatrix}.$ (43)

The reason for stacking the gradients in the row, and not column-wise, is due
to the graph’s specification. For example, since $\boldsymbol{V}^{T}$ is a
$3\times 3$ matrix, the multiplication of
$\boldsymbol{G_{f}}=\boldsymbol{V}^{T}\boldsymbol{G}$ demands the row of
$\boldsymbol{G}$ to be $3$. We will further see that stacking row-wise will
result in aggregating each column of $\boldsymbol{G}$. That is exactly what is
required; aggregating each gradient of the model with respect to the same
gradient element of another. Moreover, we set
$\textrm{diag}[\kappa_{1},...,\kappa_{K}]=\textrm{diag}[\frac{1}{N},...,\frac{1}{N}]$
to further simplify the outcome. Note that $\kappa_{i}$, $i=1,...,K$,
privileges each device individually without any consideration of its
connectivity on the graph.

Defining the filter operator as $h_{s}(\lambda)=\frac{1}{1+\mu_{s}\lambda}$,
we can then derive the matrix frequency coefficients of $\boldsymbol{G}$ as

$\displaystyle\boldsymbol{G_{f}}$
$\displaystyle=\textrm{diag}[\kappa_{1},...,\kappa_{K}]h_{s}(\boldsymbol{\Lambda})\boldsymbol{V}^{T}\boldsymbol{G}=$
(44)
$\displaystyle\begin{bmatrix}h_{s}(\lambda_{0})\frac{1}{N}\sum_{j=1}^{3}g_{j1}&h_{s}(\lambda_{0})\frac{1}{N}\sum_{j=1}^{3}g_{j2}\\\
h_{s}(\lambda_{1})\frac{1}{N}\sum_{j=1}^{3}v_{j2}g_{j1}&h_{s}(\lambda_{1})\frac{1}{N}\sum_{j=1}^{3}v_{j2}g_{j2}\\\
h_{s}(\lambda_{2})\frac{1}{N}\sum_{j=1}^{3}v_{j3}g_{j1}&h_{s}(\lambda_{2})\frac{1}{N}\sum_{j=1}^{3}v_{j3}g_{j2}\\\
\end{bmatrix}.$

Each element of the columns in $\boldsymbol{G_{f}}$ represents a frequency
coefficient. Now, let us assume we aim to construct the FedAvg algorithm using
G-Fedfilt. To do so, we set $\mu_{s}$ to a large value. The result is
$h_{s}(\lambda_{0}=0)=1$ and $h_{s}(\lambda_{1})\approx
h_{s}(\lambda_{2})\approx 0$. In this case, only the first row of
$\boldsymbol{G}_{f}$ in (44) becomes non-zero, i.e., only DC coefficients
remain. Performing the IGFT on $\boldsymbol{G}_{f}$ gives the aggregated
gradient matrix as

$\boldsymbol{\widehat{G}}=\boldsymbol{V}\boldsymbol{G}_{f}=\begin{bmatrix}\frac{1}{N}\sum_{j=1}^{3}g_{j1}&\frac{1}{N}\sum_{j=1}^{3}g_{j2}\\\
\frac{1}{N}\sum_{j=1}^{3}g_{j1}&\frac{1}{N}\sum_{j=1}^{3}g_{j2}\\\
\frac{1}{N}\sum_{j=1}^{3}g_{j1}&\frac{1}{N}\sum_{j=1}^{3}g_{j2}\end{bmatrix}.$
(45)

It is seen that each row of $\boldsymbol{\widehat{G}}$ is an averaged version
of the original gradients, similar to the behavior of the FedAvg algorithm.
Note that the $i^{th}$ row belongs to the gradient update vector of the
$i^{th}$ node.

## References

  * Poushter et al. [2016] Jacob Poushter et al.  Smartphone ownership and internet usage continues to climb in emerging economies.  _Pew research center_ , 22(1):1–44, Feb. 2016\.
  * Chiang and Zhang [2016] Mung Chiang and Tao Zhang.  Fog and IoT: An overview of research opportunities.  _IEEE Internet of things journal_ , 3(6):854–864, June 2016.
  * McMahan et al. [2017] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial intelligence and statistics_ , pages 1273–1282. PMLR, Apr. 2017.
  * Gafni et al. [2021] Tomer Gafni, Nir Shlezinger, Kobi Cohen, Yonina C Eldar, and H Vincent Poor.  Federated learning: A signal processing perspective.  _arXiv preprint arXiv:2103.17150_ , Aug. 2021.
  * Li et al. [2020] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith.  Federated learning: Challenges, methods, and future directions.  _IEEE Signal Processing Magazine_ , 37(3):50–60, May 2020.
  * Kairouz et al. [2019] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al.  Advances and open problems in federated learning.  _arXiv preprint arXiv:1912.04977_ , Dec. 2019.
  * Reddi et al. [2020] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečnỳ, Sanjiv Kumar, and H Brendan McMahan.  Adaptive federated optimization.  _arXiv preprint arXiv:2003.00295_ , Sep. 2020.
  * Dong et al. [2020] Xiaowen Dong, Dorina Thanou, Laura Toni, Michael Bronstein, and Pascal Frossard.  Graph signal processing for machine learning: A review and new perspectives.  _IEEE Signal processing magazine_ , 37(6):117–127, Oct. 2020.
  * Khaled et al. [2020] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik.  Tighter theory for local sgd on identical and heterogeneous data.  In _International Conference on Artificial Intelligence and Statistics_ , pages 4519–4529. PMLR, Aug. 2020.
  * Abad et al. [2020] Mehdi Salehi Heydar Abad, Emre Ozfatura, Deniz Gunduz, and Ozgur Ercetin.  Hierarchical federated learning across heterogeneous cellular networks.  In _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 8866–8870. IEEE, May. 2020.
  * Li et al. [2019a] Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith.  Fair resource allocation in federated learning.  _arXiv preprint arXiv:1905.10497_ , Feb. 2019a.
  * Li et al. [2019b] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang.  On the convergence of fedavg on non-iid data.  _arXiv preprint arXiv:1907.02189_ , June 2019b.
  * Deng et al. [2020] Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi.  Adaptive personalized federated learning.  _arXiv preprint arXiv:2003.13461_ , Nov. 2020.
  * Mansour et al. [2020] Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh.  Three approaches for personalization with applications to federated learning.  _arXiv preprint arXiv:2002.10619_ , Jul. 2020.
  * Liang et al. [2020] Paul Pu Liang, Terrance Liu, Liu Ziyin, Nicholas B Allen, Randy P Auerbach, David Brent, Ruslan Salakhutdinov, and Louis-Philippe Morency.  Think locally, act globally: Federated learning with local and global representations.  _arXiv preprint arXiv:2001.01523_ , Jul. 2020.
  * Chen et al. [2020a] Yiqiang Chen, Xin Qin, Jindong Wang, Chaohui Yu, and Wen Gao.  Fedhealth: A federated transfer learning framework for wearable healthcare.  _IEEE Intelligent Systems_ , 35(4):83–93, Apr. 2020a.
  * Feng et al. [2020] Jie Feng, Can Rong, Funing Sun, Diansheng Guo, and Yong Li.  Pmf: A privacy-preserving human mobility prediction framework via federated learning.  _Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies_ , 4(1):1–21, Mar. 2020.
  * Arivazhagan et al. [2019] Manoj Ghuhan Arivazhagan, Vinay Aggarwal, Aaditya Kumar Singh, and Sunav Choudhary.  Federated learning with personalization layers.  _arXiv preprint arXiv:1912.00818_ , Dec. 2019.
  * Jiang et al. [2019] Yihan Jiang, Jakub Konečnỳ, Keith Rush, and Sreeram Kannan.  Improving federated learning personalization via model agnostic meta learning.  _arXiv preprint arXiv:1909.12488_ , Sep. 2019.
  * Fallah et al. [2020] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar.  Personalized federated learning: A meta-learning approach.  _arXiv preprint arXiv:2002.07948_ , Oct. 2020.
  * Khodak et al. [2019] Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar.  Adaptive gradient-based meta-learning methods.  _arXiv preprint arXiv:1906.02717_ , 2019.
  * Corinzia et al. [2019] Luca Corinzia, Ami Beuret, and Joachim M Buhmann.  Variational federated multi-task learning.  _arXiv preprint arXiv:1906.06268_ , Feb. 2019.
  * Smith et al. [2017] Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet Talwalkar.  Federated multi-task learning.  _arXiv preprint arXiv:1705.10467_ , 2017.
  * Tremblay and Loukas [2020] Nicolas Tremblay and Andreas Loukas.  Approximating spectral clustering via sampling: a review.  _Sampling Techniques for Supervised or Unsupervised Tasks_ , pages 129–183, Oct. 2020.
  * Hao et al. [2021] Xiaoke Hao, Jie Li, Yingchun Guo, Tao Jiang, and Ming Yu.  Hypergraph neural network for skeleton-based action recognition.  _IEEE Transactions on Image Processing_ , 30:2263–2275, Jan. 2021.
  * He et al. [2021] Chaoyang He, Keshav Balasubramanian, Emir Ceyani, Carl Yang, Han Xie, Lichao Sun, Lifang He, Liangwei Yang, Philip S Yu, Yu Rong, et al.  Fedgraphnn: A federated learning system and benchmark for graph neural networks.  _arXiv preprint arXiv:2104.07145_ , Sep. 2021.
  * Sajadmanesh and Gatica-Perez [2021] Sina Sajadmanesh and Daniel Gatica-Perez.  Locally private graph neural networks.  In _Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security_ , pages 2130–2145, Nov. 2021.
  * Jiang et al. [2020] Meng Jiang, Taeho Jung, Ryan Karl, and Tong Zhao.  Federated dynamic gnn with secure aggregation.  _arXiv preprint arXiv:2009.07351_ , Sep. 2020.
  * Wu et al. [2021] Chuhan Wu, Fangzhao Wu, Yang Cao, Yongfeng Huang, and Xing Xie.  Fedgnn: Federated graph neural network for privacy-preserving recommendation.  _arXiv preprint arXiv:2102.04925_ , Mar. 2021.
  * Meng et al. [2021] Chuizheng Meng, Sirisha Rambhatla, and Yan Liu.  Cross-node federated graph neural network for spatio-temporal data modeling.  _arXiv preprint arXiv:2106.05223_ , Aug. 2021.
  * Mei et al. [2019] Guangxu Mei, Ziyu Guo, Shijun Liu, and Li Pan.  Sgnn: A graph neural network based federated learning approach by hiding structure.  In _2019 IEEE International Conference on Big Data (Big Data)_ , pages 2560–2568. IEEE, Dec. 2019.
  * Zheng et al. [2021] Longfei Zheng, Jun Zhou, Chaochao Chen, Bingzhe Wu, Li Wang, and Benyu Zhang.  Asfgnn: Automated separated-federated graph neural network.  _Peer-to-Peer Networking and Applications_ , 14(3):1692–1704, Feb. 2021.
  * Wang et al. [2020] Binghui Wang, Ang Li, Hai Li, and Yiran Chen.  Graphfl: A federated learning framework for semi-supervised node classification on graphs.  _arXiv preprint arXiv:2012.04187_ , Dec. 2020.
  * Caldarola et al. [2021] Debora Caldarola, Massimiliano Mancini, Fabio Galasso, Marco Ciccone, Emanuele Rodolà, and Barbara Caputo.  Cluster-driven graph federated learning over multiple domains.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 2749–2758, 2021.
  * Damaskinos et al. [2020] Georgios Damaskinos, Rachid Guerraoui, Anne-Marie Kermarrec, Vlad Nitu, Rhicheek Patra, and François Taïani.  Fleet: Online federated learning via staleness awareness and performance prediction.  In _Proceedings of the 21st International Middleware Conference_ , pages 163–177, Dec. 2020.
  * Chen et al. [2021] Mingzhe Chen, Nir Shlezinger, H Vincent Poor, Yonina C Eldar, and Shuguang Cui.  Communication-efficient federated learning.  _Proceedings of the National Academy of Sciences_ , 118(17), 2021.
  * Yang et al. [2020] Zhaohui Yang, Mingzhe Chen, Walid Saad, Choong Seon Hong, and Mohammad Shikh-Bahaei.  Energy efficient federated learning over wireless communication networks.  _IEEE Transactions on Wireless Communications_ , 20(3):1935–1949, Nov. 2020.
  * Chen et al. [2020b] Mingzhe Chen, H Vincent Poor, Walid Saad, and Shuguang Cui.  Convergence time optimization for federated learning over wireless networks.  _IEEE Transactions on Wireless Communications_ , 20(4):2457–2471, Dec. 2020b.
  * Zhang et al. [2020] Chengliang Zhang, Suyi Li, Junzhe Xia, Wei Wang, Feng Yan, and Yang Liu.  $\\{$BatchCrypt$\\}$: Efficient homomorphic encryption for $\\{$Cross-Silo$\\}$ federated learning.  In _2020 USENIX Annual Technical Conference (USENIX ATC 20)_ , pages 493–506, Jul. 2020.
  * Sheikholeslami et al. [2021] Seyed Mohammad Sheikholeslami, Fahimeh Fazel, Jamshid Abouei, and Konstantinos N Plataniotis.  Sub-decimeter VLC 3D indoor localization with handover probability analysis.  _IEEE Access_ , 9:122236–122253, 2021.
  * Tan et al. [2021] Alysa Ziying Tan, Han Yu, Lizhen Cui, and Qiang Yang.  Towards personalized federated learning.  _arXiv preprint arXiv:2103.00710_ , 2021.
  * Ortega et al. [2018] Antonio Ortega, Pascal Frossard, Jelena Kovačević, José MF Moura, and Pierre Vandergheynst.  Graph signal processing: Overview, challenges, and applications.  _Proceedings of the IEEE_ , 106(5):808–828, Apr. 2018.
  * Defferrard et al. [2017] Michaël Defferrard, Lionel Martin, Rodrigo Pena, and Nathanaël Perraudin.  Pygsp: Graph signal processing in python.  _URL https://github. com/epfl-lts2/pygsp_ , 2017.
  * Nishio and Yonetani [2019] Takayuki Nishio and Ryo Yonetani.  Client selection for federated learning with heterogeneous resources in mobile edge.  In _ICC 2019-2019 IEEE International Conference on Communications (ICC)_ , pages 1–7. IEEE, May 2019.
  * Cui et al. [2017] Yong Cui, Jian Song, Kui Ren, Minming Li, Zongpeng Li, Qingmei Ren, and Yangjun Zhang.  Software defined cooperative offloading for mobile cloudlets.  _IEEE/ACM Transactions on Networking_ , 25(3):1746–1760, Feb. 2017.
  * Boyd and Vandenberghe [2004] Stephen Boyd and Lieven Vandenberghe.  _Convex Optimization_.  Cambridge University Press, Cambridge, U.K., 2004.
  * Grant and Boyd [2014] Michael Grant and Stephen Boyd.  Cvx: Matlab software for disciplined convex programming, version 2.1, Mar. 2014.
  * Mao et al. [2016] Yuyi Mao, Jun Zhang, and Khaled B Letaief.  Dynamic computation offloading for mobile-edge computing with energy harvesting devices.  _IEEE Journal on Selected Areas in Communications_ , 34(12):3590–3605, Sep. 2016.
  * Zhao et al. [2020] Yang Zhao, Jun Zhao, Linshan Jiang, Rui Tan, Dusit Niyato, Zengxiang Li, Lingjuan Lyu, and Yingbo Liu.  Privacy-preserving blockchain-based federated learning for iot devices.  _IEEE Internet of Things Journal_ , 8(3):1817–1829, 2020.
  * Xu et al. [2020] Dixing Xu, Mengyao Zheng, Linshan Jiang, Chaojie Gu, Rui Tan, and Peng Cheng.  Lightweight and unobtrusive data obfuscation at iot edge for remote inference.  _IEEE Internet of Things Journal_ , 7(10):9540–9551, 2020.
  * Mills et al. [2019] Jed Mills, Jia Hu, and Geyong Min.  Communication-efficient federated learning for wireless edge intelligence in iot.  _IEEE Internet of Things Journal_ , 7(7):5986–5994, 2019.
  * Aji and Heafield [2017] Alham Fikri Aji and Kenneth Heafield.  Sparse communication for distributed gradient descent.  _arXiv preprint arXiv:1704.05021_ , Jul. 2017.