# IoT Localization and Optimized Topology Extraction Using Eigenvector
Synchronization ††thanks: This material is based upon work supported by
Science Foundation Ireland (SFI) and is co-funded under the European Regional
Development Fund under Grant Numbers 13/RC/2077 and 13/RC/2077-P2.
©2023 IEEE. Personal use of this material is permitted. Permission from IEEE
must be obtained for all other uses, in any current or future media, including
reprinting/republishing this material for advertising or promotional purposes,
creating new collective works, for resale or redistribution to servers or
lists, or reuse of any copyrighted component of this work in other works.

_Indrakshi Dey and Nicola Marchetti_

###### Abstract

Internet-of-Things (IoT) devices are low size, weight and power (SWaP), low
complexity and include sensors, meters, wearables and trackers. Transmitting
information with high signal power is exacting on device battery life,
therefore an efficient link and network configuration is absolutely crucial to
avoid signal power enhancement in interference-rich environment and resorting
to battery-life extending strategies. Efficient network configuration can also
ensure fulfilment of network performance metrics like throughput, coding rate
and spectral efficiency. We formulate a novel approach of first localizing the
IoT nodes and then extracting the network topology for information exchange
between the nodes (devices, gateway and sinks), such that overall network
throughput is maximized. The nodes are localized using noisy measurements of a
subset of Euclidean distances between two nodes. Realizable subsets of
neighboring devices agree with their own position within the entire network
graph through eigenvector synchronization. Using communication global graph-
model-based technique, network topology is constructed in terms of transmit
power allocation with the aim of maximizing spatial usage and overall network
throughput. This topology extraction problem is solved using the concept of
linear programming.

##  1 Introduction

Internet-of-Things (IoT) is proliferating through every possible corners of
our lives with applications and services that improves and uplifts the quality
of lives across different aspects [1]. Localization is an essential process in
the IoT environment for tracking and monitoring the targets with the help of
sensor nodes. Localization is also of paramount importance for optimizing the
spatial usage and network coverage with minimum number of devices [2].

IoT networks are a collection of low size, weight and power (SWaP) devices
distributed over a geographical area and under different radio conditions that
cooperate to monitor and manage various physical or environmental condition.
Such devices are capable of limited computing power, memory, communication
capabilities. Therefore, many IoT nodes cannot afford Global Navigation
Satellite Systems (GNSS) [3, 4] receivers, which is the most common method of
wireless device localization, due to their high power and cost requirements.
Localization in IoT networks is also challenging owing a) complexity of the
surrounding radio conditions, b) large amount of sensor errors resulting from
low-cost sensors and c) dynamic nature of IoT nodes for certain applications
[5, 6, 7, 8, 9, 10, 11, 12].

Different database-matching (DB-M)-based techniques have been also introduced
for localization [13, 14, 15]. Machine Learning (ML)-based DB-M techniques
like Artificial Neural Networks (ANN) [16, 17], random forests [18, 19], Deep
Reinforcement Learning (DRL) [20, 21], have also been introduced for IoT node
localization. However, any DB-M technique will need a strong database which
may be difficult to get hold off when deploying a new network. Moreover ML-
based techniques are always computationally heavy and are not feasible for IoT
nodes with limited battery life.

In this paper, we formally argue that IoT node localization and network
topology extraction can be optimally achieved by investigating the
relationship between the spatio-temporal structure of a network and flow of
information over the network links. We embed graph over the network structure,
break the large network graph into many small overlapping sub-graphs or
patches and stitch them together consistently in a global coordinate system. A
communication graph-model-based topology of the IoT network is constructed in
this way with the aim of maximizing the spatial usage. In this respect, we
investigate the question whether there exists certain power assignment that
enables topology control for maximizing the spatial usage.

To enable effective topology extraction, we formulate a signal-to-noise ratio
(SNR)-based optimization problem that can be solved to obtain the minimal
possible power that each IoT node can fire with, to reach its farthest
neighbor (as defined in the communication graph). By iteratively invoking our
formulated topology extraction, the power assignment converges within 7
iterations, on average, to an operational point that maximizes network
throughput. Our proposed ‘ _Topology Extraction for Maximizing Network
Throughput ( MaxNTtop)_’ improves achievable network throughput by around 45%
over the traditional Brute-force search-based algorithm.

The remainder of the paper is organized as follows. We first introduce in
Section II the graph embedding algorithm for mapping the spatio-temporal
relationship and flow of information within an IoT network. Following that, we
investigate in Section III the issue of whether or not a feasible power
assignment exists that enables the communication graph capable of satisfying
overall network lower SNR threshold. Towards this end, we devise a new
topology extraction algorithm, called MaxNTtop that iteratively invokes
topology formulation until the power assignment converges to an operational
point. We present in Section IV a simulation study and show the superiority of
the topology induced by MaxNTtop in terms of maximizing the network throughput
and spatial usage. Finally, we conclude the paper in Section V.

##  2 Graph Embedding

An IoT network is modelled as an oriented graph $G=(V,E)$ where $|V|=n$ and
$V$ is the set of IoT nodes, while $|E|=m$ and $E$ is the set of links (edges)
which is associated with a distance measurement matching the Euclidean
distance between two neighboring IoT nodes. In other words, the distance
between nodes $i$ and $j$, $d_{ij}=d_{ji}$ and the link (edge) between
$(i,j)\in E$. For any such graph realization problem, the main goal is to find
graph embeddings $p_{1},p_{2},\dotso,p_{n}\in\mathbb{R}^{\mathsf{d}}$, in
$\mathsf{d}$-dimensional space and for any distance $d_{ij}$ and link between
$(i,j)\in E$, where the embeddings will satisfy, $||p_{i}-p_{j}||=d_{ij}$. For
realistic embeddings, we define a noisy representation of the distance,
$d_{ij}=||p_{i}-p_{j}||+\varepsilon_{ij}$ where $\varepsilon_{ij}$ is the
added noise, and we have to find the optimal graph embedding considering
$\varepsilon_{ij}$. The key idea behind our contribution is to divide $G$ into
smaller sub-graphs which can be sewed together back in the global graph
representing the entire IoT network, in a way that the number of fold-overs is
minimized and both local sub-graphs and global graph are globally rigid111A
globally rigid graph refers to a graph in planar Euclidean space which is
structurally stable, i.e. the edges can be replaced by solid rods. Evaluating
rigidity of a graph is a separate detailed mathematical study, which is beyond
the scope of this paper. The verifiability and rigidity of the graph embedding
outlined in this paper will be studied elaborately in our future work.. When
we are sewing the sub-graphs or patches, we need to find the reflection,
rotation and translation for maximally aligning two sub-graphs in a consistent
manner. This process is referred to as _synchronization_ [22] in traditional
graph theory. A conceptual overview of our graph embedding is presented in
Fig. 1.

Figure 1: A Conceptual representation of our graph embedding algorithm for
aligning patches or sub-graphs within an IoT network with the over-arching
goal of maximizing network coverage.

###  2.1 Graph Embedding Algorithm

For every node $j$, $V(i)=\\{j:(i,j)\in E\\}\cup\\{i\\}$ represent the set of
neighbors and $G(i)=(V(i),E(i))$ represents the sub-graph consisting of 1-hop
neighbors of $i$ (i.e. the set of IoT nodes which can be reached from node $i$
in just one hop; we refer to those nodes as the 1-hop neighbors). We will
embed $G(i)$ in $\mathbb{R}^{2}$ if $G(i)$ is globally rigid and we will break
$G(i)$ into more sub-graphs if $G(i)$ is not globally rigid. Therefore, to
summarize our algorithm, we divide the network graph $G$ into $N$ globally
rigid sub-graphs or patches denoted by $P_{1},\dotso,P_{N}$ and then embed
each of those patches $P_{i}$ separately using a graph embedding method of our
choice.

####  2.1.1 Patch Reflection

Our aim is to estimate the set of rigid motions,
$\sigma_{1},\dotso,\sigma_{N}$, where the $i$th motion $\sigma_{i}$ moves the
patch $P_{i}$ to its correct position with respect to the global coordinate
system and $\sigma_{i}\in\text{Euc}(2)$ where $\text{Euc}(2)$ is the Euclidean
group of rigid motions on $\mathbb{R}^{2}$. Let us consider that we want to
align the patches $P_{i}$ and $P_{j}$ where $P_{i}$ and $P_{j}$ have more than
two IoT nodes in common. Let us also consider that the relative reflection can
be estimated as, $z_{ij}\in\\{-1,+1\\}$, of the patches $P_{i}$ and $P_{j}$.
Using $z_{ij}$ , we build a $N\times N$ sparse symmetric matrix $Z$ such that,

$\displaystyle Z=(z_{ij})=\begin{cases}1&\quad\text{align}\leavevmode\nobreak\
P_{i}\leavevmode\nobreak\ \text{\&}\leavevmode\nobreak\
P_{j}\leavevmode\nobreak\ \text{without any reflection}\\\
-1&\quad\text{align}\leavevmode\nobreak\ P_{i}\leavevmode\nobreak\
\text{\&}\leavevmode\nobreak\ P_{j}\leavevmode\nobreak\ \text{with one
reflection}\\\ 0&\quad P_{i}\leavevmode\nobreak\ \text{\&}\leavevmode\nobreak\
P_{j}\leavevmode\nobreak\ \text{cannot be aligned}\end{cases}$ (1)

The next step then is to compute the top eigenvector222The top eigenvector is
defined as the direction onto which a projection of the principal components
has the largest variance. $v^{\zeta}_{1}$ of $\zeta=\Delta^{-1}Z$ where
$\Delta$ is a diagonal matrix with $\Delta_{ii}=\text{deg}(i)$ satisfying
$\zeta v^{\zeta}_{1}=\lambda^{\zeta}_{1}v^{\zeta}_{1}$. Now using the
eigenvector quantification and the reflections $z_{ij}$, we can estimate the
global reflection of patch $P_{i}$,

$\displaystyle\hat{z}_{i}=\text{sign}(v^{\zeta}_{1}(i))=v^{\zeta}_{1}(i)/|v^{\zeta}_{1}(i)|$
(2)

and for the cases where $\hat{z}_{i}=-1$, $P_{i}$ will be replaced by its
mirrored image.

####  2.1.2 Patch Rotation

Similar to the reflections, we will estimate the relative rotations,
$\theta_{ij}$, of the patches $P_{i}$ and $P_{j}$, such that
$\theta_{ij}\in[0,2\pi)$ and $r_{ij}=e^{\imath\theta_{ij}}$. Using $r_{ij}$,
we construct another $N\times N$ Hermitian matrix, $R=(r_{ij})$, such that,

$\displaystyle r_{ij}=\begin{cases}e^{\imath\theta_{ij}}&\quad
P_{i}\leavevmode\nobreak\ \text{\&}\leavevmode\nobreak\
P_{j}\leavevmode\nobreak\ \text{can be aligned}\\\ 0&\quad
P_{i}\leavevmode\nobreak\ \text{\&}\leavevmode\nobreak\
P_{j}\leavevmode\nobreak\ \text{cannot be aligned}\end{cases}$ (3)

where since $R$ is a Hermitian matrix, $\theta_{ij}=-\theta_{ji}\mod 2\pi$ and
it follows that $R_{ij}=\bar{R}_{ji}$ for any complex number $\omega=a+\imath
b$ and its complex conjugate, $\bar{\omega}=a-\imath b$. We also compute the
top eigenvector $v^{\mathcal{R}}_{1}$ of $\mathcal{R}=\Delta^{-1}R$ such that
$v^{\mathcal{R}}_{1}$ satisfies
$\mathcal{R}v^{\mathcal{R}}_{1}=\lambda^{\mathcal{R}}_{1}v^{\mathcal{R}}_{1}$.
This can be used to estimate the global rotation angle $\hat{\theta}_{i}$ of
patch $P_{i}$ using,

$\displaystyle
e^{\imath\hat{\theta}_{i}}=v^{\mathcal{R}}_{1}(i)/|v^{\mathcal{R}}_{1}(i)|$
(4)

and with the estimated angle $e^{\imath\hat{\theta}_{i}}$ we can rotate the
patch $P_{i}$ for embedding.

####  2.1.3 Patch Translation

The final step is to compute coordinates (2-dimensional) of each patch when
sewed back into the global graph. Let us consider the $k$th patch $P_{k}$ with
associated graph $G_{k}=(V_{k},E_{k})$ where $G_{k}$ needs to be embedded into
$G=(V,E)$. For the $i$th node in patch $P_{k}$, we should have,

$\displaystyle p_{i}=p_{i}^{(k)}+t^{(k)};i\in V_{k};k=1,\dotso,N$ (5)

where $t^{(k)}$ is the associated translation. Using the over-determined
system of (5), we can estimated the global coordinates, $p_{1},\dotso,p_{n}$
using least square solution to (5). The set of translations
$t^{(1)},\dotso,t^{(N)}$ is disregarded. So for each edge $(i,k)\in E_{k}$,
$p_{i}-p_{j}=p_{i}^{(k)}-p_{j}^{(k)}$. If we replace the patches with the
$(x,y)$ coordinates,
$x_{i}-x_{j}=x_{i}^{(k)}-x_{j}^{(k)};y_{i}-y_{j}=y_{i}^{(k)}-y_{j}^{(k)}$,
which can be solved separately. Now we can write, $\tau x=\gamma^{x}$, where
$\tau$ is the least square matrix, $x$ is the $n\times 1$ vector of
$x$-coordinates of all IoT nodes localized in a patch or sub-graph, and
$\gamma^{x}$ is the vector with entries from the right-hand side of the last
equation. Similarly, we can write $\tau y=\gamma^{y}$. Now by adding all the
equations corresponding to the same edge $(i,j)$ from different patches,

$\displaystyle\sum_{k\in\\{1,\dotso,N\\};(i,j)\in E_{k}}x_{i}-x_{j}$
$\displaystyle=\sum_{k\in\\{1,\dotso,N\\};(i,j)\in
E_{k}}x_{i}^{(k)}-x_{j}^{(k)},\leavevmode\nobreak\ (i,j)\in E$ (6)

and similarly for the $y$-coordinates we can formulate the least-square
transition matrix $\tau$, i.e. $m\times n$ over-determined system of linear
equations. If the estimated transition matrix is denoted by $\hat{\tau}$, the
least square solutions to $\hat{\tau}x=\gamma^{x}$ and
$\hat{\tau}y=\gamma^{y}$ will be given by, $\hat{p}_{1},\dotso,\hat{p}_{n}$.
The error in any estimated patch coordinates can be calculated as
$||p_{i}-\hat{p}_{i}||$.

###  2.2 Patch Embedding for globally non-rigid sub-graph

For patch embedding in our globally non-rigid IoT network sub-graphs, we
resort to the three-step method outlined in [23]. The first step is to
estimate the missing distance, $d^{\prime}_{ij}$ with $(i,j)\notin
E_{k}$,333We are considering an annular graph, with a network where the IoT
devices are distributed randomly on an annulus surrounding the IoT gateway at
the center.

$\displaystyle d^{\prime}_{ij}=(\underline{d_{ij}}+\overline{d_{ij}})/2$ (7)

for,

$\displaystyle\overline{d_{ij}}$ $\displaystyle=\min_{k:(i,k),(j,k)\in
E_{k}}d_{ik}+d_{jk}$ (8) $\displaystyle\underline{d_{ij}}$
$\displaystyle=\max\bigg{[}\max_{k:(i,k)\in E_{k}}d_{ik},\max_{k:(j,k)\in
E_{k}}d_{jk}\bigg{]}$ (9)

The second step is to compute local coordinates of all nodes in a patch using
multi-dimensional scaling [24] on the complete set of pairwise distances. We
can express, $\mathbf{D}=-1/2\mathbf{J}\mathbf{L}\mathbf{J}$ where
$\mathbf{J}=\mathbf{I}_{n}-1/n\mathbf{1}\mathbf{1}^{t}$, $\mathbf{1}$ is a
matrix of ones, $\mathbf{I}$ is the identity matrix, $\mathbf{L}$ is the
matrix of squared pairwise distances, $\mathbf{L}\in\mathbb{R}^{n\times n}$,
$t$ denotes the transpose and $n\geq 1$ is an integer and the matrix of the
local coordinates of all nodes in a patch can be calculated as,

$\displaystyle P_{k}=\mathbf{U}_{k}\sqrt{\Lambda_{k}}$
$\displaystyle\quad=\bigg{[}\sqrt{\lambda_{1}}\mathbf{u}_{1},\dotso,\underbrace{\sqrt{\lambda_{r+1}}\mathbf{u}_{r+1}}_{=0},\dotso,\underbrace{\sqrt{\lambda_{k}}\mathbf{u}_{k}}_{=0}\bigg{]}\in\mathbb{R}^{n\times
k}$ (10)

where $({\lambda_{n}},\mathbf{u}_{n})$ are the eigen-pairs of the $\mathbf{D}$
matrix.

The final step is to refine the embedding using iterative majorization
technique. The coordinates of each IoT node are updated according to,

$\displaystyle p_{i}\leftarrow 1/\leavevmode\nobreak\ \text{deg}_{i}(P_{k})$
$\displaystyle\quad\sum_{j\in V_{k},(i,j)\in
E_{k}}[p_{j}+d_{ij}(p_{i}-p_{j})\leavevmode\nobreak\
\text{inv}\leavevmode\nobreak\ (||p_{i}-p_{j}||)]$ (11)

where $\text{deg}_{i}(P_{k})$ denotes the degree of node $i$ in patch $P_{k}$
and,

$\text{inv}\leavevmode\nobreak\ (x)=\begin{cases}1/x&\quad\text{if }x\neq 0\\\
0&\quad\text{if }x=0\end{cases}$

###  2.3 Aligning Patches and Sewing them together

Following the embedding of the patch $P_{k}$, now let us look into how we can
align $P_{k}$ with another patch $P_{l}$ where $P_{k}$ and $P_{l}$ have more
than 2 IoT nodes in common. Let us denote the set of intersecting nodes
between $P_{k}$ and $P_{l}$ as $V_{k,l}=\\{v_{1},\dotso,v_{s}\\}=V_{k}\cap
V_{l}$, the coordinates of $V_{k,l}$ in $P_{k}$ as
$p_{1}^{(k)},\dotso,p_{s}^{(k)}$, and the coordinates of $V_{k,l}$ in $P_{l}$
as $p_{1}^{(l)},\dotso,p_{s}^{(l)}$. For the $i$th node in $P_{k}$,
$p_{i}^{(k)}=(x_{i}^{(k)},y_{i}^{(k)})=x_{i}^{(k)}+\imath y_{i}^{(k)}$ is
mirrored across to the $x$-axis to the rotation
$\bar{p}_{i}^{(k)}=(x_{i}^{(k)},-y_{i}^{(k)})=x_{i}^{(k)}-\imath y_{i}^{(k)}$.
The aim is to find $r_{\theta}=e^{\imath\theta}$ and translation vector,
$\tau=x+\imath y$, that minimize the following objective function,

$\displaystyle
f(\theta,\tau)=\sum_{i=1}^{s}|p_{i}^{(k)}-(r_{\theta}p_{i}^{(l)}+\tau)|^{2}$
(12)

Now $P_{l}$ may be aligned with $P_{k}$ in its original form or we may need to
consider the mirror image of $\bar{P}_{l}$ for aligning. The objective
function that needs minimization for mirrored $P_{l}$ is,

$\displaystyle\tilde{f}(\theta,\tau)=\sum_{i=1}^{s}|p_{i}^{(k)}-(r_{\theta}\bar{p}_{i}^{(l)}+\tau)|^{2}$
(13)

Consequently, we can define the required relative reflection, $z_{ij}$,
required for final aligning as,

$\displaystyle z_{kl}=\begin{cases}1&\quad\text{if}\leavevmode\nobreak\
\min_{\theta,i}f(\theta,\tau)\leq\min_{\theta,i}\tilde{f}(\theta,\tau)\\\
-1&\quad\text{if}\leavevmode\nobreak\
\min_{\theta,i}f(\theta,\tau)>\min_{\theta,i}\tilde{f}(\theta,\tau)\\\ 0&\quad
P_{k}\leavevmode\nobreak\ \text{\&}\leavevmode\nobreak\
P_{l}\leavevmode\nobreak\ \text{cannot be aligned}\end{cases}$ (14)

We can then rewrite (12) and (13) as $||A\xi-B||^{2}$ where,

$\displaystyle
A^{t}=\begin{pmatrix}p_{1}^{(l)}&\dotso&p_{i}^{(l)}&\dotso&p_{s}^{(l)}\\\
1&\dotso&1&\dotso&1\end{pmatrix}$ $\displaystyle B^{t}=(p_{1}^{(k)}\dotso
p_{i}^{(k)}\dotso p_{s}^{(k)});\leavevmode\nobreak\ \xi=[r_{\theta},\tau]$
(15)

in order to solve the minimization problem in (13) for the rotation and
translation vector for the patches. The optimal solution is obtained by
solving the problem in (12) using complex least squares following the method
outlined in Subsection II-C.

##  3 Topology Extraction

Let us now consider two IoT nodes $V_{i}$ and $V_{j}$ with Euclidean distance
$d_{ij}=d(v_{i},v_{j})$ and Euclidean coordinates $v(x,y),x\in X,y\in Y$. Let
every node $v_{i}$ fire with a transmit power $\rho_{T}(i)$ and all the
transmit power assignments are collated in,
$\\{\rho_{T}(1),\dotso,\rho_{T}(n)\\}$. On the receiver side, we can define
the signal-to-noise ratio (SNR) of a reliably detectable signal as,

$\displaystyle\text{SNR}_{ij}=h_{ij}\leavevmode\nobreak\
\rho_{T}(i)\leavevmode\nobreak\ d_{ij}^{-\nu}/\mathcal{N}\geq\beta$ (16)

where $h_{ij}$ is the channel gain (link gain) between the $i$th and $j$th IoT
nodes, $\nu$ is the pathloss exponent, $\mathcal{N}$ is the noise power and
$\beta$ is the lower SNR threshold or the minimum detectable SNR on the
receive side.

With the constraint (16) in place, we can now formulate the problem of power
assignment for maximizing spatial usage or network coverage such that the
network throughput is maximized. Specifically, we model the problem as a
system of linear programming with respect to transmit power
$\rho_{T}(i),i=1,\dotso,n$:

$\displaystyle\text{minimize}\leavevmode\nobreak\ \leavevmode\nobreak\
\sum_{i=1}^{n}$ $\displaystyle\rho_{T}(i)$ subject to,
$\displaystyle\rho_{T}(i)\leq\rho_{T_{\text{max}}};\leavevmode\nobreak\
\text{SNR}_{ij}\geq\beta$ $\displaystyle\rho_{T}(i)\geq
d_{ij}^{\nu}\leavevmode\nobreak\ \rho_{R_{\text{min}}}\leavevmode\nobreak\
\leavevmode\nobreak\ \forall e_{ij}\in G$ (17)

where $\rho_{T_{\text{max}}}$ is the maximum power with which any IoT device
can fire a signal (depending on the particular device battery life) and
$\rho_{R_{\text{min}}}$ is the minimum received power which is detectable and
decodable by the receiver (gateway or any other IoT network device).

Next we will be using the solution to the power allocation problem formulated
in (3) and improve network throughput. First we compute power assignment to
maximize spatial usage and then extract the corresponding network topology.
The algorithm continues until it converges to a point where network throughput
is maximized. We summarize the algorithm as below.

Topology Extraction for Maximizing Network Throughput (MaxNTtop)

Input : A set of IoT nodes $V$ and their coordinates $\\{X,Y\\}$
Let us consider an iteration step $\varepsilon$ of a small value
Step 1 : Power assignment
$\mathsf{P}_{T}\to\\{\rho_{T}(1),\dotso,\rho_{T}(n)\\}$
For all node pairs $i,j$ such that $d_{ij}\leq$ transmission range, compute
SNR by (16)
Step 2 : Sort edges in the decreasing order of SNR
Let $\hat{e}_{1},\hat{e}_{2},\dotso$ be the resulting sequence of edges,
initialize $m$ patches
If patch ($i$) $\neq$ patch ($j$) then sew them using graph embedding
algorithm outlined in Section II, $E=E\cup\\{\hat{e}_{i,j}\\}$, where
$\hat{e}_{i,j}$ is the newly formed edge after patch alignment
Extract Topology $\Gamma(V,E)$
Step 3 : Calculate SNR$(\Gamma,\mathsf{P}_{T})$ and initialize $\Delta=1$
For all; $\Delta>\varepsilon$; SNR${}_{\text{max}}$ =
SNR$(\Gamma,\rho_{T_{\text{max}}})$;
$\Delta=||\text{SNR}_{\text{max}}-\text{SNR}(\Gamma,\mathsf{P}_{T})||$
Output : Finalize power assignment $\mathsf{P}_{T}$ It is worth-mentioning
here that the number of iterations required for MaxNTtop to converge is
independent of the network size and converges on average within 6 to 7
iterations.

##  4 Numerical Results and Discussion

We compare the results of our proposed MaxNTtop algorithm with those of Brute-
force search by choosing the minimum transmit power allocation to any IoT node
for firing its signal to it farthest neighboring node in the graph. The Brute-
force algorithm will systematically enumerate all the possible solutions to
the transmit power allocation problem in (3) until all optimal solutions have
been exhausted. Our proposed algorithm is also compared with the local minimal
spanning tree (LMST) [25] which is a topology control algorithm for
communication graphs. We focus on a non-link-sharing scenario where each link
is used only between a pair of nodes in a particular iteration.

Figure 2: Average comparative node degree achievable with different
algorithms. A total of 5 random IoT networks are generated, each of which has
50 nodes distributed uniformly on an annulus surrounding a network gateway at
the center with radius of 1 km. Figure 3: Average comparative node degree
achievable with different algorithms. A total of 5 random IoT networks are
generated, each of which has 80 nodes randomly distributed over a $4\times 4$
km2 rectangular area.

The first set of results are generated for comparing the spatial usage
capability offered by our algorithm in comparison to the LMST and Brute-force
search. Spatial usage is defined as the network throughput of accommodating
concurrent transmissions and is often measured in terms of node degree, i.e.,
the number of edges that can be connected to a node at the same time. So we
are comparing average node degrees in Fig. 2 for a total of 5 different IoT
networks, each with 50 nodes that are distributed uniformly on an annulus
surrounding a network gateway at the center with radius of 1 km. We considered
average pathloss exponent of $\nu=4$, $\rho_{R_{\text{min}}}=-63$ dBm,
$\rho_{T_{\text{max}}}=27$ dBm, $\beta=2.5$ dB and a typical value of
$\mathcal{N}=-50$ dBm is considered for all simulation results. In Fig. 3, we
increased the number of nodes per network to 80 nodes that are distributed
randomly within a $4\times 4$ km2 rectangular area without any central
gateway. All the other simulation parameters are kept same as in Fig. 2.

Figure 4: Comparative achievable average throughput over different values of
lower SNR threshold for an IoT network consisting of 50 nodes distributed
uniformly on an annulus surrounding a network gateway at the center with
radius of 1 km. Figure 5: Comparative achievable average throughput over
different values of lower SNR threshold for an IoT network consisting of 80
nodes randomly distributed over a $4\times 4$ km2 rectangular area.

Both in Fig. 2 and Fig. 3, LMST reports minimum average node degrees while
Brute-force enables use of smaller number of nodes than the Brute-force
search-based algorithm to cover a larger area in terms of higher possibility
of connecting with more number of nodes. MaxNTtop offers best node degree both
in the circular and rectangular spatial distribution. Higher spatial usage is
observed when the number of nodes is increased in Fig. 3. This is due to the
possibility of aligning patches within the entire network; MaxNTtop offers
rotation and reflection of the patch to suitably align them in a way that
patches sharing more than two common nodes can be sewed together. As a result
a larger spatial area can be covered with a smaller number of IoT nodes.

The second set of results in Fig. 4 and Fig. 5 are generated by comparing the
average network throughput achievable by MaxNTtop with respect to LMST and
Brute-force search. We use the same set of parameters used in Fig. 2 and Fig.
3 for Fig. 4 and Fig. 5 respectively. In this result set, we stitch patches
with common nodes, one-by-one until all existing nodes within an IoT network
are connected. Each new patch is sewed on the condition that it does not
result in end-to-end violation of the minimum SNR constraint ($\beta$). From,
Fig. 4 and Fig. 5, we can see that MaxNTtop definitely improves network
throughput. Now here we compare the network throughput against the SNR
threshold and as the threshold increases, network throughput improves as all
the links are experiencing higher average SNR. However, this improvement is
capped and saturates when $\beta$ is increased over 25 dB. This limitation is
observed as throughput is dependent on the link bandwidth. Also, intuitively,
it gets more difficult to obtain connectivity with a higher SNR threshold to
abide to. Therefore, even though the SNR constraint is allowed to increase,
the average throughput cannot increase further as the link bandwidth is
constant.

##  5 Conclusions

In this paper, we formulate optimized topology extraction and control for IoT
networks, with the objective of maximizing network throughput. We model an IoT
network as a global graph where a cluster of IoT nodes within a one-hop
communication link is considered a patch or a sub-graph. The patches are
aligned with each other when two patches share more than two common IoT nodes.
The patches are aligned through eigenvector synchronization combining
rotation, reflection and translation. After the patches are aligned, they are
sewed together so that the topology created by sewing is capable of maximizing
the coverage or spatial usage. Finally, the topology extracted in this way is
optimized to offer maximum average network throughput under the physical
signal-to-noise ratio (SNR) constraint. We demonstrated that our proposed
algorithm MaxNTtop combining graph embedding and topology extraction offers
improved network throughput and spatial usage, in comparison to Brute-force
search and state-of-the-art LMST algorithms. Currently, MaxNTtop is a
centralized approach. In future, it will be realistic to investigate how the
topology extraction approach can be led in a distributed way such that each
IoT node is intelligent enough to make their own decision on the neighbor to
connect to, how much power to fire with or which direction to consider for
information communications without relying on the central control gateway or
any other node in the network.

## References

  * [1] A. Zanella, N. Bui, A. Castellani, L. Vangelista and M. Zorzi, “Internet of Things for Smart Cities," _IEEE Internet Things J._ , vol. 1, no. 1, pp. 22-32, Feb. 2014.
  * [2] F. Zafari, A. Gkelias and K. K. Leung, “A Survey of Indoor Localization Systems and Technologies," _IEEE Commun Surv Tut_ , doi: 10.1109/COMST.2019.2911558, Apr. 2019.
  * [3] Z. Gao, Y. Li, Y. Zhuang, H. Yang, Y. Pan, H. Zhang, “Robust Kalman Filter Aided GEO/IGSO/GPS Raw-PPP/INS Tight Integration". _Sensors_ , vol. 2019, no. 19, pp. 1-17, Jan. 2019.
  * [4] R. Shit, S. Sharma, D. Puthal and A. Zomaya, “Location of Things (LoT): A Review and Taxonomy of Sensors Localization in IoT Infrastructure," _IEEE Commun. Surv. Tut._ , vol. 20, no. 3, pp. 2028-2061, third-quarter 2018.
  * [5] M. Ramadan, V. Sark, J. Gutierrez and E. Grass, “NLoS Identification for Indoor Localization using Random Forest Algorithm," in _Int ITG Worksh Smart Antenna_ , Bochum, Germany, 14-16 Mar. 2018.
  * [6] P. Meissner, “Multipath-assisted Indoor Positioning", _Ph.D. Thesis_ , Graz University of Technology, Austria, Oct. 2014.
  * [7] V. Erceg, L. Greenstein, S. Tjandra, R. Bianchi, et. al., “An empirically based path loss model for wireless channels in suburban environments," _IEEE J. Sel. Areas Commun._ , vol. 17, no. 7, pp. 1205-1211, Jul. 1999.
  * [8] Y. Li, Z. Gao, Z. He, P. Zhang, R. Chen and N. El-Sheimy, “Multi-Sensor Multi-Floor 3D Localization With Robust Floor Detection," _IEEE Access_ , vol. 6, pp. 76689-76699, Nov. 2018.
  * [9] J. Trogh, D. Plets, A. Thielens, L. Martens and W. Joseph, “Enhanced Indoor Location Tracking Through Body Shadowing Compensation," _IEEE Sens. J._ , vol. 16, no. 7, pp. 2105-2114, Apr. 2016.
  * [10] X. Niu, Y. Li, H. Zhang, Q. Wang, and Y. Ban, “Fast Thermal Calibration of Low-Grade Inertial Sensors and Inertial Measurement Units", _Sensors_ , vol. 13, no. 9, pp. 12192-12217, Sept. 2013.
  * [11] Y. Li, Y. Zhuang, P. Zhang, H. Lan, X. Niu, and N. El-Sheimy, “An improved inertial/wifi/magnetic fusion structure for indoor navigation," _Inform Fusion_ , vol. 2017, no. 34, pp. 101-119, Mar. 2017.
  * [12] S. Saeedi, “Context-Aware Personal Navigation Services Using Multilevel Sensor Fusion Algorithms", _Ph.D. Thesis_ , University of Calgary, Canada, Oct. 2013.
  * [13] J. Niu, B. Wang, L. Shu, T. Q. Duong and Y. Chen, “ZIL: An EnergyEfficient Indoor Localization System Using ZigBee Radio to Detect WiFi Fingerprints," _IEEE J. Sel. Areas Commun._ , vol. 33, no. 7, pp. 1431- 1442, Jul. 2015.
  * [14] J. Torres-Sospedra, R. Montoliu, S. Trilles, . Belmonte, and J. Huerta, “Comprehensive analysis of distance and similarity measures for Wi-Fi fingerprinting indoor positioning systems," _Expert Sys. Appl._ , vol. 42, no. 23, pp. 9263-9278, Dec. 2015.
  * [15] Y. Xie, Y. Wang, A. Nallanathan and L. Wang, “An Improved K-Nearest Neighbor Indoor Localization Method Based on Spearman Distance," _IEEE Signal Processing Letters_ , vol. 23, no. 3, pp. 351-355, Mar. 2016.
  * [16] J. Choi, W. Lee, J. Lee, J. Lee and S. Kim, “Deep Learning Based NLoS Identification With Commodity WLAN Devices," _IEEE Trans. Veh. Technol._ , vol. 67, no. 4, pp. 3295-3303, Apr. 2018.
  * [17] D. Konings, B. Parr, F. Alam and E. Lai, “Falcon: Fused Application of Light Based Positioning Coupled With Onboard Network Localization," _IEEE Access_ , vol. 6, pp. 36155-36167, 2018.
  * [18] J. Rodriguez, L. Kuncheva and C. Alonso, “Rotation Forest: A New Classifier Ensemble Method," _IEEE T. Pattern Anal. Mach. Intell._ , vol. 28, no. 10, pp. 1619-1630, Oct. 2006.
  * [19] B. Menze, M. Kelm, R. Masuch, U. Himmelreich, P. Bachert, W. Petrich and F. Hamprecht, “A comparison of random forest and its Gini importance with standard chemometric methods for the feature selection and classification of spectral data", _BMC Bioinform_ , vol. 10, no. 213, pp. 1-16, Jul. 2009.
  * [20] M. Hessel, J. Modayil, H. Hasselt, T. Schaul, G. Ostrovski, W. Dabney, D. Horgan, B. Piot, M. Azar, D. Silver, “Rainbow: Combining Improvements in Deep Reinforcement Learning", in _AAAI Conf. Artif. Intell._ , New Orleans, USA, 2-7 Feb. 2018.
  * [21] V. Mnih, K. Kavukcuoglu, D. Silver, A. Rusu, D. Hassabis, et. al, “Human-level control through deep reinforcement learning", _Nature_ , vol. 518, no. 1, pp. 529-533, Feb. 2015.
  * [22] R. Karp, J. Elson, D. Estrin, and S. Shenker, _Optimal and global time synchronization in sensor-nets._ Tech. rep., Center for Embedded Networked Sensing, University of California, Los Angeles, 2003.
  * [23] Y. Koren, C. Gotsman, and M. Ben-Chen, _PATCHWORK: Efficient localization for sensor networks by distributed global optimization_. Tech. rep., 2005.
  * [24] Y. Shang, and W. Ruml, “Improved MDS-based localization." in _Proceedings of IEEE Infocom._ vol. 23. Hong Kong, China, pp. 2640–2651, 2004.
  * [25] N. Li, J. C.Hou, and L. Sha, “Design and analysis of a mst-based distributed topology control algorithm for wireless ad-hoc networks," _IEEE Trans. on Wireless Communications_ , vol. 4, no. 3, pp. 1195–1207, May 2005.


11institutetext: Northeast Electric Power University, China

# Attention-based Graph ResNet for Motor Intent Detection from Raw EEG signals

Shuyue Jia  Yimin Hou  Yan Shi  Yang Li

###### Abstract

In previous studies, decoding electroencephalography (EEG) signals has not
considered the topological relationship of EEG electrodes. However, the latest
neuroscience has suggested brain network connectivity. Thus, the exhibited
interaction between EEG channels might not be appropriately measured via
Euclidean distance. To fill the gap, an attention-based graph residual
network, a novel structure of Graph Convolutional Neural Network (GCN), was
presented to detect human motor intents from raw EEG signals, where the
topological structure of EEG electrodes was built as a graph. Meanwhile, deep
residual learning with a full-attention architecture was introduced to address
the degradation problem concerning deeper networks in raw EEG motor imagery
(MI) data. Individual variability, the critical and longstanding challenge
underlying EEG signals, has been successfully handled with the state-of-the-
art performance, 98.08% accuracy at the subject level, 94.28% for 20 subjects.
Numerical results were promising that the implementation of the graph-
structured topology was superior to decode raw EEG data. The innovative deep
learning approach was expected to entail a universal method towards both
neuroscience research and real-world EEG-based practical applications, e.g.,
seizure prediction.

###### Keywords:

EEG Motor Imagery Graph Convolutional Neural Network Deep Residual Learning
Attention Mechanism

##  1 Introduction

The recent decade has witnessed a flourishing market in the brain-computer
interface (BCI) to assist and rehabilitate patients from strokes, Parkinson’s
disease, and brain injuries[1, 13]. Electroencephalography (EEG) obtains
growth in popularity because of its non-invasiveness, high temporal
resolution, and portability[13]. In particular, the EEG-based motor imagery
(MI) technique has been extensively employed to manipulate the peripherals via
neural activities[12]. De facto, individual variability poses a critical and
longstanding challenge for current EEG signal processing. Hence, it is eagerly
expected for researchers to handle such a concern to better understand the
mechanism of cognitive functions and build robust EEG-based BCI systems.

Traditional works analyzed EEG data without taking consideration of the
topological relationship of EEG electrodes[12, 7, 4]. The latest neuroscience,
however, has suggested brain dynamic functional connectivity[9, 10, 17]. Thus,
the exhibited interaction of EEG channels might not be well reflected via
Euclidean distance. The Graph Convolutional Neural Network (GCN) has generated
widespread research interest, which has proven superior to process and analyze
graph-structured data. Spectral GCN was primarily studied since it well
defined a localized operator for convolutions on graphs, and managed to
process graph signals[14]. Reference[2] proposed an effective and efficient
GCN approach by constructing fast localized graph filters. A few works have
applied such a base model to classify EEG tasks, primarily for emotion
recognition[21, 15, 18]. However, there remains a vacancy to employ the GCN
approach in the area of EEG MI. Therefore, this paper presented a novel
structure of the GCN, an Attention-based graph ResNet, to achieve precise
detection of human motor intentions. The main contributions were precisely
summarized: (1) To date, this was the first work to detect human motor intents
from raw EEG signals via the GCN approach. (2) The intrinsic topological
relationship of EEG electrodes was built as a graph, which has proven superior
to classify and analyze EEG signals. (3) This paper entailed a novel approach
intending to address the universal EEG-based problems in neuroscience, and
pave the road to build practical clinical applications.

##  2 Methods

###  2.1 Graph Convolutional Neural Network

####  2.1.1 Graph Convolution

An undirected graph is represented by the Laplacian matrix $L$, which contains
the graph weights and degrees. The normalized graph Laplacian is defined as
$L=I_{N}-D^{-1/2}AD^{-1/2}$, where $A$ is an adjacency matrix describing graph
weights, $D$ is a degree matrix to represent node degrees. We used Absolute
Pearson’s Matrix $P$, which is the absolute of Pearson’s Matrix as the
adjacency matrix to measure the correlations between nodes. The degree matrix
is measured as $D_{ii}=\sum_{j=1}^{N}A_{ij}$. Since the graph Laplacian is a
real symmetric and positive semidefinite matrix, it can be factored via the
graph Fourier transform as $L=U\Lambda U^{T}$, in which
$U=\left[u_{0},\ldots,u_{N-1}\right]$, and
$\Lambda=\operatorname{diag}\left(\left[\lambda_{0},\ldots,\lambda_{N-1}\right]\right)$
are the eigenvectors and eigenvalues, respectively. Graph convolution is
defined:

$y=Ug_{\theta}(\Lambda)U^{T}x$ (1)

Where the Chebyshev polynomial filter
$g_{\theta}(\Lambda)=\sum_{k=0}^{K-1}\theta_{k}T_{k}(\Lambda)$ is the most
frequently-used filter $g_{\theta}$. $\theta\in\mathbb{R}^{K}$ is the model
parameters, and $T_{k}(\Lambda)$ is the $K^{th}$ order Chebyshev polynomial
approximation. The convolutional operation on the graph is then defined as:

$y=\sum_{k=0}^{K-1}\theta_{k}T_{k}(L)x$ (2)

####  2.1.2 Graph Pooling

Defferrard _et al._ proposed a fast graph pooling approach, including graph
coarsening and balanced binary tree one-dimensional pooling, which has proven
efficient[2]. A balanced binary tree is put forward to store the unarranged
graph nodes. Based on the Graclus multilevel clustering algorithm, the
normalized cut is minimized via the greedy method to coarsen the nodes[3], and
then it max-pooled the nodes in the binary tree. In this way, the number of
nodes will be divided into two, and the graph pooling operation is
accomplished[2].

###  2.2 Residual Learning and Attention Mechanism

The performance of DL models almost reached a plateau with a growing depth of
networks. The phenomenon is well-known as the network degradation. Such a
concern can be tackled via the residual learning framework, by which the
networks can still converge and achieve higher accuracy when the number of
layers increased[6, 8]. In this work, residual learning was introduced to
explore the performance of deeper networks for raw EEG signals. Previously, a
stack of layers approximates the underlying mapping, which is from input $x$
to output $H(x)$. In contrast, with regard to residual learning, the layers
fit the residual function $F(x)=H(x)-x$, where $x$ is the input, and
$H(x)=F(x)+x$ is the originally desired mapping[6]. As a result, the output of
a stack of layers is $F(x)+x$, and it can be implemented via the shortcut
connection.

Discovered from the human vision, researchers have attracted considerable
interest in the attention mechanism[16]. Previous works have either recognized
equal contribution regarding the decoding tasks for all the EEG electrodes or
selected the most influential electrodes (e.g., from the brain motor cortex).
The principle of the attention mechanism is demonstrated as follows.

$u=\tanh\left(wy+b\right)$ (3)
$\alpha=\frac{\exp\left(u^{\top}u_{w}\right)}{\sum\exp\left(u^{\top}u_{w}\right)}$
(4) $s=\alpha y$ (5)

In which $y$ is the original output of each layer, $u$ is a FC layer (In the
experiment, we used tanh activation function), $\alpha$ is a Softmax layer,
and $s$ is the attention-based final output. $w$, $u_{w}$, and $b$ are
trainable weights and biases. The weighted method selects the most contributed
features with regard to the classification task[19]. A full-attention
architecture was presented to preserve the details from raw EEG signals, and
select the most crucial info. Each layer of the graph ResNet is followed and
connected with an attention layer. And all the attention layers are jointly
trained with the network.

###  2.3 Attention-based Graph ResNet

The introduced approach was a novel structure of the GCN. It designed with the
deep residual learning, and each layer (i.e., graph convolution, graph
pooling, and fully-connected layer) was followed by an individual attention
mechanism, which has formulated a full attention architecture. The residual
learning framework makes it possible for deeper models to converge. The
attention mechanism assigns weights to EEG electrodes, and selects and sticks
out the most significant features to enhance the capability of the presented
model. With regard to the EEG Motor Movement/Imagery Dataset, it is an
international 10-10 system with 64 EEG electrodes. Thus, the dimension of the
input, i.e., graph Laplacian, was 64$\times$64, followed by 12 layers of graph
convolutions, and each two of them connected with a graph max-pooling layer,
which reduced the dimension by two. The order of Chebyshev polynomial
approximation for graph convolutional filters we used in our experiment was
three. The activation function of graph convolution was Leaky ReLu, which was
used after the batch normalization. The cross-entropy with L2 norm (0.001
regularization parameter) was applied as the loss function. We utilized the
Adam Optimizer with 0.001 and 0.0001 learning rate for the graph-level and
subject-level training, respectively. The framework was implemented via
TensorFlow 1.14.0 under NVIDIA GTX1060 6G GPU and CUDA toolkit 10.0.

##  3 Numerical Experiments

###  3.1 Description of Dataset

In the experiment, the EEG Motor Movement/Imagery Dataset (Physionet database)
was used to validate the model. It performed four MI tasks, including imaging
opening and closing left fist (denoting L), right fist (denoting R), both
fists (denoting B), and both feet (denoting F)[5]. The sample rate was 160 Hz,
and we used a four-second experimental duration, i.e., 640 time points per
trial, to analyze the data[7]. 109 participants ($S_{1}-S_{109}$) took part in
the experiment with 84 trials (4 tasks$\times$7 trials$\times$3 runs) for
every participant. The detailed description of the dataset can be found in our
previous work[7]. In this paper, the number of samples was 53,760 per subject.
During all the experiments, the total dataset was randomly divided into ten
pieces. Nine of them were selected as the training set, and the last one was
regarded as the test set.

###  3.2 Model Comparison

We compared the performance of various models, including the GCN, graph
ResNet, Attention-based graph ResNet with two-layer (Proposed Model 1), and
three-layer (Proposed Model 2) graph conv in the residual block. The dataset
collected from 20 subjects ($S_{1}-S_{20}$) was utilized. Thus, the number of
samples were 1,075,200 (20 subjects$\times$53,760 samples). The accuracy and
loss over iterations curves were demonstrated inFigure 1.

(a) Accuracy of different models over iterations

(b) Loss value of different models over iterations

Figure 1: Different models’ performance comparison (accuracy and loss value)
over iterations.

Figure 1 has shown the classification accuracy of different models. It was
evident that all the GCN-based approach has achieved competitive results
($>$85% accuracy). The reason for this phenomenon was that this work has taken
consideration of the topological relationship of EEG electrodes. Compared with
the GCN approach (86.03% accuracy), the graph ResNet model increased the
classification accuracy by 4.63% via the deep residual learning. It, however,
should also be admitted that as illustrated in Figure 1, the overfitting had
occured as the model got complicated. Fortunately, after applying the
attention mechanism, the problem has been effectively suppressed. Furthermore,
the Attention-based graph ResNet has achieved dominant results at the group-
level (20 subjects), which was supreme to decode EEG MI tasks. The proposed
method 2 achieved 94.28% accuracy, which was a little higher than the proposed
method 1 (92.77%). This was because there were more graph convolutions, thus
the features can be extractd comprehensively, and the inter-subject
variability can be filtered in a superior way. In other words, the residual
learning approach promoted the classification performance compared with the
original GCN model since it can tackle the problem of network degradation.
Plus, the attention mechanism enhanced the performance again by assigning
weights to the graph ResNet layer, which selected and highlighted the
essential features in the layer.

###  3.3 Subject-level Evaluation

To explore the effectiveness on the inter-trial variability, the introduced
approach has been validated on 10 subjects from $S_{1}$ to $S_{10}$. For each
evaluation, the total dataset was 53,760 samples. The results were given in
Table 1.

Table 1: Subject-level adaptation results for 10 individual subjects.

No. of Subjects | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | Average
---|---|---|---|---|---|---|---|---|---|---|---
Accuracy(%) | 97.49 | 87.69 | 96.73 | 97.01 | 92.89 | 90.70 | 88.08 | 96.84 | 96.32 | 98.08 | 94.18
F1 Score (%) | 97.50 | 87.55 | 96.78 | 97.05 | 92.86 | 90.62 | 87.97 | 96.89 | 96.39 | 98.09 | 94.17

Evaluated on the individual participant, the high of the accuracy was 98.08%
and the average was 94.18% via the subject level analysis. Macro-averaged F1
score was also used to measure the performance of the presented model. The
average of F1 score was 94.17%, and the high was 98.09%. The subject-level
performance has indicated that the introduced approach was able to be applied
to a single subject by precious prediction of MI tasks. It paved the road to
build real-world EEG MI-based applications at the subject level, e.g.,
clinical translation of the technology. Meanwhile, it was suggested that the
graph-based EEG analysis may become one of the research focus in the field of
neuroscience.

###  3.4 Group-wise Cross-validation

(a) Box Plot for 10-fold Cross-validation

(b) Confusion Matrix from One Individual Test

Figure 2: Box plot for 10-fold cross-validation, and the confusion matrix from
one individual test.

Next, we 10-fold cross-validated the proposed model 2. The dataset we used was
from 20 subjects, which was the same as that in Section 3.2. The box plot was
demonstrated in Figure 2. The median accuracy was 93.76%, and the high was
94.16%. Besides, the average was 93.78%, which was the state-of-the-art for
group-wise EEG analysis among current studies. From the repetitive
experiments, the stability and reliability of our presented model have been
verified, in which the results can be stably reproduced. The reason under the
outcome was that the proposed approach took consideration of the topological
relationship of EEG electrodes, and made full advantage of network
connectivity of brain dynamics.

Further, as shown in Figure 1, the Proposed Model 2 has achieved 94.28%
accuracy. It has been evaluated to obtain separate accuracy on each task.
Displayed in Figure 2, the separate accuracy on task L, R, B, F were 92.09%,
90.98%, 94.26%, and 99.88%. The data indicated that the introduced approach
was superior for the prediction of imaging both feet. It was suggested that
the method managed to tackle the concern of inter-subject variability due to
its robustness and effectiveness. Plus, the group-specific model can be shared
with a group of subjects with highly accurate prediction. Thus, it may pave
the road towards building an universal EEG MI model for both neuroscience
research and practical clinical translation.

###  3.5 Comparison with State of the Art

The proposed approach has been carried out to compare the performance with
current competitive models on the EEG Motor Movement/Imagery Dataset in Table
2.

Table 2: Performance comparison with state-of-the-art Approach | Max Accuracy | Num of Subjects
---|---|---
CNNs (2018)[4] | 68.51% | 1
RNNs (2018)[11] | 68.20% | 12
Attention-based CNNs (2019)[20] | 76.36% | 1
ESI+CNNs (2020)[7] | 96.00% | 1
92.50% | 14
Attention-based graph ResNet | 98.08% | 1
94.28% | 20

Hou _et al._ put forward a Convolutional Neural Network (CNN) based approach
to classify four-class EEG MI, which was only been implemented to 14
subjects[7]. Our method accomplished better performance ($+$1.78%) using the
data from more subjects. Zhang _et al._ introduced an Attention-based CNNs,
and achieved an average of 76.36% accuracy for subject-independent
prediction[20]. However, there was still space to improve the performance for
practical implementation in the real world. Although the work from Dose _et
al._ work has not obtained convincing results, but the transfer learning they
presented was worth to exploit in our future work for the clinical translation
of EEG-based BCI technologies[4]. According to Table 2, the evidence suggested
that our model achieved predominant and promising results from the perspective
of both subject and group levels. This may be reasonable to suppose that the
Attention-based graph ResNet was superior to decode graph-structured EEG
signals by considering the topological relationship of EEG electrodes.

##  4 Conclusion

In this paper, we proposed a novel structure of the GCN to predict four-class
MI tasks from raw EEG data, which took consideration of the topological
relationship of EEG electrodes. The presented Attention-based graph ResNet was
superior to decode EEG signals that entailed a novel deep learning approach
intending to address the universal EEG-based challenges in neuroscience, and
pave the road towards clinical translation of the technology. Dominant results
have shown that the approach managed to handle the inter-subject and inter-
trial variations in raw EEG data. In the future, we will exploit the model by
representing the topological structure of EEG electrodes from 2D to 3D, and
implementing the Attention-based graph ResNet from the 3D perspective.

## References

  * [1] Biasiucci, A., Leeb, R., Iturrate, I., Perdikis, S., Al-Khodairy, A., Corbet, T., Schnider, A., Schmidlin, T., Zhang, H., Bassolino, M., et al.: Brain-actuated functional electrical stimulation elicits lasting arm motor recovery after stroke. Nature communications 9(1), 1–13 (2018)
  * [2] Defferrard, M., Bresson, X., Vandergheynst, P.: Convolutional neural networks on graphs with fast localized spectral filtering. In: Advances in neural information processing systems. pp. 3844–3852 (2016)
  * [3] Dhillon, I.S., Guan, Y., Kulis, B.: Weighted graph cuts without eigenvectors a multilevel approach. IEEE transactions on pattern analysis and machine intelligence 29(11), 1944–1957 (2007)
  * [4] Dose, H., Møller, J.S., Iversen, H.K., Puthusserypady, S.: An end-to-end deep learning approach to mi-eeg signal classification for bcis. Expert Systems with Applications 114, 532–542 (2018)
  * [5] Goldberger, A.L., Amaral, L.A., Glass, L., Hausdorff, J.M., Ivanov, P.C., Mark, R.G., et al.: Physiobank, physiotoolkit, and physionet: components of a new research resource for complex physiologic signals. Circulation 101(23), e215–e220 (2000)
  * [6] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 770–778 (2016)
  * [7] Hou, Y., Zhou, L., Jia, S., Lun, X.: A novel approach of decoding eeg four-class motor imagery tasks via scout esi and cnn. Journal of neural engineering 17(1), 016048 (2020)
  * [8] Li, G., Muller, M., Thabet, A., Ghanem, B.: Deepgcns: Can gcns go as deep as cnns? In: Proceedings of the IEEE International Conference on Computer Vision. pp. 9267–9276 (2019)
  * [9] Lv, J., Jiang, X., Li, X., Zhu, D., Zhang, S., Zhao, S., Chen, H., Zhang, T., Hu, X., Han, J., et al.: Holistic atlases of functional networks and interactions reveal reciprocal organizational architecture of cortical function. IEEE Transactions on Biomedical Engineering 62(4), 1120–1131 (2014)
  * [10] Lv, J., Nguyen, V.T., van der Meer, J., Breakspear, M., Guo, C.C.: N-way decomposition: Towards linking concurrent eeg and fmri analysis during natural stimulus. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 382–389. Springer (2017)
  * [11] Ma, X., Qiu, S., Du, C., Xing, J., He, H.: Improving eeg-based motor imagery classification via spatial and temporal recurrent neural networks. In: 2018 40th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC). pp. 1903–1906. IEEE (2018)
  * [12] Mahmood, M., Mzurikwao, D., Kim, Y.S., Lee, Y., Mishra, S., Herbert, R., Duarte, A., Ang, C.S., Yeo, W.H.: Fully portable and wireless universal brain–machine interfaces enabled by flexible scalp electronics and deep learning algorithm. Nature Machine Intelligence 1(9), 412–422 (2019)
  * [13] Shanechi, M.M.: Brain–machine interfaces from motor to mood. Nature neuroscience 22(10), 1554–1564 (2019)
  * [14] Shuman, D.I., Narang, S.K., Frossard, P., Ortega, A., Vandergheynst, P.: The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine 30(3), 83–98 (2013)
  * [15] Song, T., Zheng, W., Song, P., Cui, Z.: Eeg emotion recognition using dynamical graph convolutional neural networks. IEEE Transactions on Affective Computing (2018)
  * [16] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, Ł., Polosukhin, I.: Attention is all you need. In: Advances in neural information processing systems. pp. 5998–6008 (2017)
  * [17] Vidaurre, D., Smith, S.M., Woolrich, M.W.: Brain network dynamics are hierarchically organized in time. Proceedings of the National Academy of Sciences 114(48), 12827–12832 (2017)
  * [18] Wang, X.h., Zhang, T., Xu, X.m., Chen, L., Xing, X.f., Chen, C.P.: Eeg emotion recognition using dynamical graph convolutional neural networks and broad learning system. In: 2018 IEEE International Conference on Bioinformatics and Biomedicine (BIBM). pp. 1240–1244. IEEE (2018)
  * [19] Yang, Z., Yang, D., Dyer, C., He, X., Smola, A., Hovy, E.: Hierarchical attention networks for document classification. In: Proceedings of the 2016 conference of the North American chapter of the association for computational linguistics: human language technologies. pp. 1480–1489 (2016)
  * [20] Zhang, D., Yao, L., Chen, K., Wang, S., Haghighi, P.D., Sullivan, C.: A graph-based hierarchical attention model for movement intention detection from eeg signals. IEEE Transactions on Neural Systems and Rehabilitation Engineering 27(11), 2247–2253 (2019)
  * [21] Zhang, T., Wang, X., Xu, X., Chen, C.P.: Gcb-net: Graph convolutional broad network and its application in emotion recognition. IEEE Transactions on Affective Computing (2019)


# A note on the article On Exploiting Spectral Properties for Solving MDP with
Large State Space

D. Maran

###### Abstract

We improve a theoretical result of the article On Exploiting Spectral
Properties for Solving MDP with Large State Space showing that their
algorithm, which was proved to converge under some unrealistic assumptions, is
actually guaranteed to converge always.

##  1 Introduction

The article [1] introduces a method to generalize the value iteration
algorithm, which becomes computationally unfeasible for MDPs with large state-
space. This algorithm requires run the value iteration algorithm on a subspace
of the state space that is chosen according to the spectral properties of the
probability transition matrix of the process.

The only theoretical guarantee of the article, Proposition 1, assert that the
algorithm converges if the discount factor $\alpha$ is in the range

$\bigg{[}0,\frac{1}{\sqrt{N}}\bigg{)}\qquad N:=|S|.$

Unfortunately, this guarantee is useless, since with a huge state space, say
$N=10^{8}$, $\alpha$ should be smaller than $\frac{1}{\sqrt{N}}=10^{-4}$,
while it is well-known that in most applications the discount factor $\alpha$
should vary in the range $[0.95,1]$. In this short letter, we are showing
that, fortunately, the algorithm they propose works also for every
$\alpha\in[0,1)$.

##  2 Spectral radius

Let us recall some definitions of linear algebra.

######  Definition 2.1.

Given a matrix $A\in\mathbb{R}^{n\times n}$ we define its spectral radius as

$\rho(A):=\text{max}\\{|\lambda_{1}(A)|,|\lambda_{2}(A)|,|\lambda_{3}(A)|,...\\}$

(where $\lambda_{i}(A)$ stands for the eigenvalues of $A$)

Since orthogonal transformation do not modify the non-zero elements of the
spectrum, it is straightforward to prove the following

######  Proposition 2.2.

Given a matrix $A\in\mathbb{R}^{n\times n}$ and an orthogonal matrix
$U\in\mathbb{R}^{n\times k}$, we have

$\rho(A)=\rho(U^{T}AU)$

In order to complete the following proof, we will need another property that
can be found in [2] as theorem 1.5 of pag. 26.

######  Proposition 2.3.

Given a matrix $A\in\mathbb{R}^{n\times n}$ we have

$\rho(A)<1\iff\lim_{k}A^{k}=0$

##  3 Result on the spectral value iteration algorithm

Using the notation of [1], we are calling

  * •

$P_{\mu}$ is the state transition matrix under policy $\mu$, such that
$\|P_{\mu}\|_{\infty}=1$.

  * •

$U_{K}$ is the projection matrix over the basis $u_{1},...u_{K}$, where we
want to project the state-value function, so it is orthogonal.

  * •

$\underline{c}_{\mu}:=c(s,\mu(s))$ is the vector of the expected costs
corresponding to each state using policy $\mu$.

  * •

$\tilde{V}_{\mu}^{(k)}$, which is the $k-$th iteration of the algorithm, is
given by

$\begin{cases}\tilde{V}_{\mu}^{(0)}=0\\\
\tilde{V}_{\mu}^{(k+1)}=U_{K}^{T}\underline{c}_{\mu}+\alpha
U_{K}^{T}P_{\mu}U_{K}\tilde{V}_{\mu}^{(k)}.\end{cases}$

This iteration is referred as algorithm (2) in the article [1].

For the definitions of $\tilde{V}_{\mu},U_{K},P_{\mu}$ see the main article
[1].

######  Proposition 3.1.

The iterative method in algorithm (2) transform domain converges for every
$\alpha<1$

###### Proof.

Define the matrix $A:=U_{K}^{T}P_{\mu}U_{K}$. We have $\rho(A)\leq 1$, indeed,
since $U_{K}$ is orthogonal, we have from 2.2

$\rho(A)=\rho(P_{\mu}).$

Moreover, we have that

$\rho(P_{\mu})\leq\|P_{\mu}\|_{\infty}=1$

since, being $\lambda_{0}$ any eigenvalue, and $v$ its corresponding infinity
norm normalized eigenvector, we have

$|\lambda_{0}|=\|\lambda_{0}v\|_{\infty}=\|P_{\mu}v\|_{\infty}\leq\|v\|_{\infty}=1.$

Therefore, $\rho(\sqrt{\alpha}A)\leq\sqrt{\alpha}<1$, and so, by 2.3, we have
also

$\big{(}\sqrt{\alpha}A\big{)}^{k}\to 0.$

Moreover, since a convergent sequence is always bounded, we can take $M>0$
such that

$\forall k,\ \|\big{(}\sqrt{\alpha}A\big{)}^{k}\|_{2}\leq M.$

At this point, by definition of the algorithm,

$\tilde{V}_{\mu}^{(k+1)}=U_{K}^{T}\underline{c}_{\mu}+\alpha
A\tilde{V}_{\mu}^{(k)}=\sum_{i=0}^{k}\alpha^{i}A^{i}U_{K}^{T}\underline{c}_{\mu}$

in order to prove that this series is convergent with $k\to+\infty$, we can
show that it is absolutely convergent:

$\sup_{k}\sum_{i=0}^{k}\|\alpha^{i}A^{i}U_{K}^{T}\underline{c}_{\mu}\|_{2}\leq\sup_{k}\sum_{i=0}^{k}\|\alpha^{i}A^{i}\|_{2}\|\underline{c}_{\mu}\|_{2}\leq\sup_{k}\sum_{i=0}^{k}\alpha^{\frac{i}{2}}\|\big{(}\sqrt{\alpha}A\big{)}^{i}\|_{2}\|\underline{c}_{\mu}\|_{2}\leq$

$\leq\sup_{k}\sum_{i=0}^{k}\alpha^{\frac{i}{2}}M\|\underline{c}_{\mu}\|_{2}\leq\frac{M}{1-\sqrt{\alpha}}\|\underline{c}_{\mu}\|_{2}<\infty$

this implies that the sequence $\tilde{V}_{\mu}^{(k)}$ converges. ∎

This shows that algorithm (2) always converges. Furthermore, note that, from
Gelfand’s Formula, we have

######  Theorem 3.2.

Given a matrix $A\in\mathbb{R}^{n\times n}$, we have

$\lim_{k}\|A^{k}\|_{2}^{1/k}=\lim_{k}\|A^{k}\|_{\infty}^{1/k}=\rho(A)$

Thus, since, as stated before, $\rho(U_{K}^{T}P_{\mu}U_{K})=\rho(P_{\mu})$,
there is no difference between the asymptotic speed of convergence with
respect to $k$ between the regular value iteration method and the one of
algorithm (2).

## References

  * [1] L. Liu, A. Chattopadhyay, U. Mitra _On Exploiting Spectral Properties for Solving MDP with Large State Space_ , Fifty-Fifth Annual Allerton Conference Allerton House, UIUC, Illinois, USA October 3-6, 2017.
  * [2] A. Quarteroni, R. Sacco, F. Salieri, P. Gervasio _Matematica Numerica_ , Springer, ISBN 978-88-470-5644-2, (2013).