# Impact Sensitivity Analysis of Cooperative Adaptive Cruise Control Against
Resource-Limited Adversaries

Mischa Huisman, Carlos Murguia, Erjen Lefeber, and Nathan van de Wouw The
research leading to these results has received funding from the European
Union’s Horizon Europe programme under grant agreement No 101069748 – SELFY
project.M. Huisman, C. Murguia, E. Lefeber, and N. van de Wouw are with the
Department of Mechanical Engineering, Eindhoven University of Technology, The
Netherlands. [m.r.huisman, C.G.Murguia, A.A.J.Lefeber<EMAIL_ADDRESS>
###### Abstract

Cooperative Adaptive Cruise Control (CACC) is a technology that allows groups
of vehicles to form in automated, tightly-coupled platoons. CACC schemes
exploit Vehicle-to-Vehicle (V2V) wireless communications to exchange
information between vehicles. However, the use of communication networks
brings security concerns as it exposes network access points that the
adversary can exploit to disrupt the vehicles’ operation and even cause
crashes. In this manuscript, we present a sensitivity analysis of CACC schemes
against a class of resource-limited attacks. We present a modelling framework
that allows us to systematically compute outer ellipsoidal approximations of
reachable sets induced by attacks. We use the size of these sets as a security
metric to quantify the potential damage of attacks affecting different signals
in a CACC-controlled vehicle and study how two key system parameters change
this metric. We carry out a sensitivity analysis for two different controller
implementations (as given the available sensors there is an infinite number of
realizations of the same controller) and show how different controller
realizations can significantly affect the impact of attacks. We present
extensive simulation experiments to illustrate the results.

##  I INTRODUCTION

Connected and Automated Vehicles (CAVs) have become a promising technology in
the automotive industry, offering potential improvements in safety, mobility,
and environmental sustainability. Cooperative Adaptive Cruise Control (CACC)
is a well-explored technology within CAVs that allows groups of vehicles to
form tightly-coupled platoons by exchanging inter-vehicle data through
Vehicle-to-Vehicle (V2V) wireless communication networks [2]. However, the use
of communication networks brings security concerns as it exposes network
access points that the adversary can exploit via cyberattacks, resulting in
new safety and security challenges that were not encountered in traditional
vehicle systems [3]-[6]. Therefore, a pressing need arises for technologies
that can quantify the potential impact of cyberattacks on platooning behavior.
Moreover, quantify the impact sensitivity against the potentially compromised
elements, e.g., sensors, actuators, networks, and software, and provide
guidelines to allocate security resources to minimize the impact of attacks.

New technologies in this field focus on the prevention and detection of
cyberattacks, which are well-explored research fields, where different sorts
of attacks and methods are applied to increase the security of the system
[6]-[9]. However, prevention and detection methods are bounded by unknown
process and measurement disturbances, leaving space for the adversary to
perform resource-limited stealth attacks [10].

There is limited research regarding the potential impact such a resource-
limited attack has on platooning behavior. In [3] and [11], the authors
present simulation studies where they compare the impact of particular types
of attacks on cooperative driving systems. Although interesting, it lacks
generality in terms of the variety of attacks that can be considered. To
overcome these limitations, reachable sets induced by general resource-limited
attacks (referred hereto as adversarial reachable sets) can be used to analyze
attackers’ capabilities to drive the platoon to unsafe states. In [12],
adversarial reachable sets are approximated in a simulation environment for a
class of bounded attacks. In [13] and [14], for a general class of linear-time
invariant dynamical systems driven by peak-bounded disturbances, ellipsoidal
outer approximations of the reachable sets are obtained using first-principles
models and convex optimization techniques.

In this manuscript, we develop a framework to analyze the impact of
cyberattacks by a general class of resource-limited adversaries on standard
CACC schemes, using the outer ellipsoidal approximation of the adversarial
reachable set. Using the size of these sets as a security metric, we quantify
the potential damage of attacks affecting different signals in a CACC-
controlled vehicle. In this scope, we investigate how the use of different
sensors and key system parameters affects the reachable set, where a
difference in size can indicate a more resilient implementation. The notion of
critical states is introduced, which characterize states that, if reached,
compromise the safety and integrity of the vehicle. To support our claims, we
have conducted an extensive simulation study on two different realized CACC
controllers. Our findings reveal that the impact of attacks can significantly
vary depending on the type of controller implementation used.

The structure of the paper is as follows: Section II introduces some
preliminary results necessary for the subsequent sections. Section III
describes the platooning model, the CACC scheme, and the available
measurements. Section IV presents the adversarial LTI systems derived from the
system description. In Section V, an extensive simulation study is conducted
to demonstrate how different implementations and system parameters can
significantly affect the impact of attacks. Finally, Section VI provides the
concluding remarks.

##  II Mathematical Preliminaries

###  II-A Notation

The symbol $\mathbb{R}$ stands for the real numbers,
$\mathbb{R}_{>0}$($\mathbb{R}_{\geq 0}$) denotes the set of positive (non-
negative) real numbers. The symbol $\mathbb{N}$ stands for the set of natural
numbers, including zero. The $n\times m$ matrix composed of only zeros is
denoted by $\mathbf{0}_{n\times m}$, or simply $\mathbf{0}$ when its dimension
is clear. Consider a finite index set
$\mathcal{L}:=\\{l_{1},\ldots,l_{\rho}\\}\subset\mathbb{N}$ with cardinality
$\text{card}[\mathcal{L}]=\rho$, e.g., $\mathcal{L}=\\{1,3,7,15\\}$ with
$\text{card}[\mathcal{L}]=4$, the notation diag[$B_{j}$] and $(B_{j})$,
$j\in\mathcal{L}$, stand for the diagonal block matrix
$\text{diag}[B_{l_{1}},\ldots,B_{l_{\rho}}]$ and stacked block matrix
$(B_{l_{1}},\ldots,B_{l_{\rho}})$, respectively. The notation $A\geq 0$
(resp., $A\leq 0$) indicates that the matrix $A$ is positive (resp., negative)
semidefinite, i.e., all the eigenvalues of the symmetric matrix $A$ are
positive (resp. negative) or equal to zero, whereas the notation $A>0$ (resp.,
$A<0$) indicates the positive (resp., negative) definiteness, i.e., all the
eigenvalues are strictly positive (resp. negative). We often omit implicit
time dependencies of signals for simplicity of notation.

###  II-B Definitions and Preliminary Results

######  Definition 1 (Reachable Set).

_[13]_ Consider the perturbed Linear Time-Invariant (LTI) system:

$\zeta(k+1)=\mathcal{A}\zeta(k)+\sum_{i=1}^{N}\mathcal{B}_{i}\omega_{i}(k),$
(1)

with $k\in\mathbb{N}$, state $\zeta(k)\in\mathbb{R}^{n_{\zeta}}$, perturbation
$\omega_{i}\in\mathbb{R}^{p_{i}}$ satisfying
$\omega_{i}^{\top}W_{i}\omega_{i}\leq 1$ for some positive definite matrix
$W_{i}\in\mathbb{R}^{p_{i}\times p_{i}},i=\\{1,...,N\\},N\in\mathbb{N}$, and
matrices $\mathcal{A}\in\mathbb{R}^{n_{\zeta}\times n_{\zeta}}$ and
$\mathcal{B}_{i}\in\mathbb{R}^{n_{\zeta}\times p_{i}}$. The reachable set
$\mathcal{R}^{\zeta}$(k) at time $k\geq 0$ from the initial condition
$\zeta_{0}\in\mathbb{R}^{n_{\zeta}}$ is the set of states reachable in $k$
steps by system (1) through all possible disturbances satisfying
$\omega_{i}^{\top}W_{i}\omega_{i}\leq 1$, i.e.,

$\mathcal{R}^{\zeta}(k)\\!\coloneqq\\!\\!\left\\{\zeta\in\mathbb{R}^{n_{\zeta}}\left|\begin{array}[]{l}\zeta=\zeta(k),\zeta(k)\text{
{solution to \eqref{eq:LTI_set},}}\\\ \text{ {and}
}\omega_{i}(k)^{\top}W_{i}\omega_{i}(k)\leq
1,\end{array}\\!\\!\\!\\!\\!\right\\}\right..$ (2)

######  Lemma 1 (Ellipsoidal Approximation).

_[13]_ Consider the perturbed LTI system (1) and the reachable set
$\mathcal{R}^{\zeta}(k)$ in Definition 1. For a given $a\in(0,1)$, if there
exist constants $a_{1}$, $\ldots$, $a_{N}$ and matrix $P$ that is the solution
of the convex program:

$\left\\{\\!\begin{aligned} &\min_{P,a_{1},\ldots,a_{N}}-\log\det[P],\\\
&\text{\emph{s.t.}}\hskip 2.84526pta_{1},\ldots,a_{N}\in(0,1),\hskip
1.42262pta_{1}+\ldots+a_{N}\geq a,\\\
&P>0,\begin{bmatrix}aP&\mathcal{A}^{\top}P&\mathbf{0}\\\
P\mathcal{A}&P&P\mathcal{B}\\\
\mathbf{0}&\mathcal{B}^{\top}P&W_{a}\end{bmatrix}\geq 0,\end{aligned}\right.$
(3)

with matrices
$W_{a}:=\operatorname*{diag}\begin{bmatrix}(1-a_{1})W_{1},\ldots,(1-a_{N})W_{N}\end{bmatrix}\in\mathbb{R}^{\bar{p}\times\bar{p}}$
and
$\mathcal{B}:=(\mathcal{B}_{1},\ldots,\mathcal{B}_{N})\in\mathbb{R}^{n_{\zeta}\times\bar{p}}$,
and $\bar{p}=\sum_{i=1}^{N}p_{i}$; then, for all $k\in\mathbb{N}$,
$\mathcal{R}^{\zeta}(k)\subseteq\mathcal{E}^{\zeta}(k)$ with
$\mathcal{E}^{\zeta}(k):=\\{\zeta^{\top}(k)P^{\zeta}\zeta(k)\leq\alpha^{\zeta}(k)\\}$,
with convergent scalar sequence
$\alpha^{\zeta}(k):=a^{k-1}\zeta(k)^{\top}P\zeta(k)+((N-a)(1-a^{k-1}))/(1-a)$.
Ellipsoid $\mathcal{E}^{\zeta}(k)$ has the minimum asymptotic volume among all
outer ellipsoidal approximations of $\mathcal{R}^{\zeta}(k)$.

######  Lemma 2 (Projection).

_[13]_ Consider the ellipsoid:

$\begin{split}\mathcal{E}:=\left\\{x\in\mathbb{R}^{n},y\in\mathbb{R}^{m}\bigg{|}\begin{bmatrix}x\\\
y\end{bmatrix}^{\top}\begin{bmatrix}Q_{1}&Q_{2}\\\
Q_{2}^{\top}&Q_{3}\end{bmatrix}\begin{bmatrix}x\\\
y\end{bmatrix}=\alpha\right\\},\end{split}$ (4)

for some positive definite matrix $Q\in\mathbb{R}^{(n+m)\times(n+m)}$ and
constant $\alpha\in\mathbb{R}_{>0}$. The projection $\mathcal{E}^{\prime}$ of
$\mathcal{E}$ onto the $x$-hyperplane is given by the ellipsoid:

$\mathcal{E}^{\prime}:=\left\\{x\in\mathbb{R}^{n}\left|\hskip
2.84526ptx^{\top}\begin{bmatrix}Q_{1}-Q_{2}Q_{3}^{-1}Q_{2}^{\top}\end{bmatrix}x=\alpha\right\\}.\right.$
(5)

##  III System Description

Consider a platoon of $m$ vehicles, schematically depicted in Fig. 1, with
$d_{i}(t)=q_{i-1}-q_{i}-L_{i}$ ($q_{i}$ reflects the position of the rear
bumper of vehicle $i$ and $L_{i}$ its length) being the distance between
vehicle $i$ and its preceding vehicle $i-1$, $v_{i}$ the velocity of vehicle
$i$. The objective of each vehicle is to keep a desired distance $d_{r,i}$
(the so-called spacing policy) with its preceding vehicle:

$\displaystyle d_{r,i}(t)=r_{i}+hv_{i}(t),\,i\in S_{m},$ (6)

with the headway $h>0$, standstill distance $r_{i}>0$, and
$S_{m}\coloneqq\\{i\in\mathbb{N}\mid 1\leq i\leq m\\}$ (i.e., the set of all
vehicles in a platoon of length $m\in\mathbb{N}$). A set of homogeneous
vehicles is assumed; therefore, also $h$ is chosen the same for all $i$. The
spacing error is then defined as

$\displaystyle\begin{split}e_{i}(t)&\coloneqq d_{i}(t)-d_{r,i}(t).\end{split}$
(7)

Figure 1: CACC-equipped vehicle platoon. Each vehicle is equipped with onboard
sensors (e.g., radars/LiDARs, cameras, and velocity/acceleration sensors).
Vehicles may be subject to FDI attacks.

We adopt the CACC scheme introduced in [2], which considers a longitudinal
vehicle model where the dynamics are described as

$\displaystyle\begin{bmatrix}\dot{q}_{i}\\\ \dot{v}_{i}\\\
\dot{a}_{i}\end{bmatrix}=\begin{bmatrix}v_{i}(t)\\\ a_{i}(t)\\\
-\frac{1}{\tau}a_{i}(t)+\frac{1}{\tau}u_{i}(t)\end{bmatrix},\,i\in S_{m},$ (8)

where $\tau$ is a time constant modelling driveline dynamics, $a_{i}(t)$
denotes the acceleration of vehicle $i$, and $u_{i}(t)$ is its desired
acceleration (the control input). The controller in [2] is a dynamic
controller of the following form:

$\mathcal{C}\coloneqq\dot{u}_{i}=-\tfrac{1}{h}u_{i}+\tfrac{k_{p}}{h}e_{i}+\tfrac{k_{d}}{h}\dot{e}_{i}+\tfrac{k_{dd}}{h}\ddot{e}_{i}+\tfrac{1}{h}u_{i-1},$
(9)

where $k_{p},k_{d}$, and $k_{dd}$ are the controller gains. We refer to
$\mathcal{C}$ as the base controller.

The real-time realization of any control scheme depends on the available
sensors $y_{i,j}$ (sensor number $j$ of vehicle $i$). We use a combination of
sensor data coming from onboard sensors (e.g., radar, LiDAR, cameras, and
velocity/acceleration sensors) and received data transmitted wirelessly
between adjacent vehicles. We assume that the sensors available to implement
control actions are:

$\displaystyle y_{i,1}$ $\displaystyle\coloneqq
q_{i-1}(t)-q_{i}(t)-L_{i}+\delta_{i,1}(t),$ (10a) $\displaystyle y_{i,2}$
$\displaystyle\coloneqq v_{i}(t)+\delta_{i,2}(t),$ (10b) $\displaystyle
y_{i,3}$ $\displaystyle\coloneqq a_{i}(t)+\delta_{i,3}(t),$ (10c)
$\displaystyle y_{i,4}$ $\displaystyle\coloneqq
v_{i-1}(t)-v_{i}(t)+\delta_{i,4}(t),$ (10d) $\displaystyle y_{i,5}$
$\displaystyle\coloneqq a_{i-1}(t)+\delta_{i,5}(t),$ (10e) $\displaystyle
y_{i,6}$ $\displaystyle\coloneqq u_{i-1}(t)+\delta_{i,6}(t).$ (10f)

Herein, $\delta_{i,j}(t)$ models potential false data injection attacks and
$j\in\\{1,...,6\\}$. It is important to note that sensors $y_{i,1}$ and
$y_{i,4}$ provide relative tracking and relative velocity information,
$y_{i,2}$ and $y_{i,3}$ are the onboard measured velocity and acceleration,
and sensors $y_{i,5}$ and $y_{i,6}$ model data received wirelessly from the
preceding vehicle via V2V communication. Using the measured values in (10),
base controller (9) can be implemented as follows:

$\displaystyle\mathcal{C}_{1}\coloneqq\left\\{\begin{aligned}
\dot{\xi}_{i,1}&=-(\tfrac{1}{h}+\tfrac{k_{dd}}{\tau})\xi_{i,1}+\tfrac{k_{p}}{h}y_{i,1}-k_{p}y_{i,2}\\\
&\,\,\,\,\,\,\,-(k_{d}+\tfrac{k_{dd}}{h}-\tfrac{k_{dd}}{\tau})y_{i,3}+\tfrac{k_{d}}{h}y_{i,4}\\\
&\,\,\,\,\,\,\,+\tfrac{k_{dd}}{\tau}y_{i,5}+\tfrac{1}{h}y_{i,6}-\tfrac{k_{p}}{h}r_{i}\\\
{u}_{i}&={\xi}_{i,1},\end{aligned}\right.$ (11)

with controller state $\xi_{i,1}\in\mathbb{R}$.

We remark that the controller implementation in (11) is not unique, and refer
to such a controller as a realized controller. An infinite number of
equivalent realizations of the base controller $\mathcal{C}$ exist that result
in the same control signal $u_{i}(t)$ at the vehicle for $\delta_{i,j}=0$. For
instance, consider the CACC controller in [16], with a change of coordinates
$\tfrac{\tau}{h}\xi_{i,2}=\tfrac{\tau}{h}a_{i-1}+(1-\tfrac{\tau}{h})a_{i}-\xi_{i,1}$
and new controller state $\xi_{i,2}\in\mathbb{R}$. Applying this coordinate
transformation to (9), and using the available sensors in (10), a second
realized controller, $\mathcal{C}_{2}$, can be obtained as

$\displaystyle\mathcal{C}_{2}\coloneqq\left\\{\begin{aligned}
\dot{\xi}_{i,2}&=-\tfrac{1+k_{dd}}{\tau}\xi_{i,2}-\tfrac{k_{p}}{\tau}y_{i,1}+\tfrac{k_{p}h}{\tau}y_{i,2}\\\
&\,\,\,\,\,\,\,+\tfrac{k_{d}h}{\tau}y_{i,3}-\tfrac{k_{d}}{\tau}y_{i,4}+\tfrac{k_{p}}{\tau}r_{i},\\\
{u}_{i}&=\tfrac{\tau}{h}y_{i,5}+(1-\tfrac{\tau}{h})y_{i,3}-\tfrac{\tau}{h}\xi_{i,2}.\end{aligned}\right.$
(12)

That is, we have two different realizations, $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$, of the CACC controller in (9) — each result in the same
control signal $u_{i}(t)$ applied to the vehicle for $\delta_{i,j}(t)=0$. Note
that $\mathcal{C}_{2}$ requires the actual acceleration of the preceding
vehicle, whereas $\mathcal{C}_{1}$ requires the control input of the preceding
vehicle. However, when $\delta_{i,j}(t)\neq 0$, for some $t\geq 0$, they will,
in general, lead to different control signals $u_{i}(t)$.

To quantify the impact of the attack on the two different controller
realizations, we are interested in the reachable sets induced by the attack
signals $\delta_{i,j}(t)$ and use the size of these sets as a security metric.
Here, we are interested in assessing whether $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$ lead to different sensitivity to attacks for the same class
of resource-limited adversaries for varying system and control parameters.

##  IV Adversarial LTI System

###  IV-A Closed-Loop Platooning Dynamics

Using the above expressions for the vehicle dynamics (8), sensors (10), and
realized controllers $\mathcal{C}_{1}$ or $\mathcal{C}_{2}$, we can write the
closed-loop tracking dynamics in terms of the attack signals $\delta_{i,j}(t)$
introduced in (10). To make a fair comparison between the realized controllers
$\mathcal{C}_{1}$ and $\mathcal{C}_{2}$, we write them in the same
coordinates. First, consider (11) and the change of coordinates
$\xi_{i,1}=\tfrac{\tau}{h}a_{i-1}+(1-\tfrac{\tau}{h})a_{i}-\tfrac{\tau}{h}\zeta_{i,1}$
(this is the same transformation, though inverse, that relates
$\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ above), with new controller state
$\zeta_{i,1}\in\mathbb{R}$. Then, after some computations, (11) can be written
in terms of $\zeta_{i,1}$ and $\delta_{i,j}$ as follows:

$\displaystyle\mathcal{C}_{1}\coloneqq\left\\{\begin{aligned}
\dot{\zeta}_{i,1}&=-\tfrac{1+k_{dd}}{\tau}\zeta_{i,1}-\tfrac{k_{p}}{\tau}e_{i}-\tfrac{k_{d}}{\tau}\dot{e}_{i}-\tfrac{k_{p}}{\tau}\delta_{i,1}\\\
&\,\,\,\,\,\,\,+\tfrac{k_{p}h}{\tau}\delta_{i,2}+(\tfrac{k_{d}h+k_{dd}}{\tau}-\tfrac{k_{dd}h}{\tau^{2}})\delta_{i,3}\\\
&\,\,\,\,\,\,\,-\tfrac{k_{d}}{\tau}\delta_{i,4}-\tfrac{k_{dd}}{\tau}\delta_{i,5}-\tfrac{1}{\tau}\delta_{i,6},\\\
{u}_{i}&=-\tfrac{\tau}{h}{\zeta}_{i,1}+\tfrac{\tau}{h}a_{i-1}+(1-\tfrac{\tau}{h})a_{i}.\end{aligned}\right.$
(13)

Define the stacked state vector
$\hat{x}_{i}\coloneqq\text{col}[e_{i},\dot{e}_{i},\zeta_{i,1},z_{i}]$, where
$z_{i}(t)\coloneqq q_{i-1}-q_{i}-L_{i}-r_{i}$. Then, the resulting closed-loop
dynamics (8), (10), (12) can be written as follows:

$\dot{\hat{x}}_{i}\coloneqq
A^{c}\hat{x}_{i}+B_{v}^{c}v_{i-1}+\sum_{j\in\mathcal{L}}\hat{\Gamma}_{j}^{c}\delta_{i,j}$
(14)

with system matrices

$\begin{split}A^{c}&:=\begin{bmatrix}[r]0&1&0&0\\\ 0&0&1&0\\\
-\frac{k_{p}}{\tau}&-\frac{k_{d}}{\tau}&-\frac{1+k_{dd}}{\tau}&0\\\
\frac{1}{h}&0&0&-\frac{1}{h}\end{bmatrix},B_{v}^{c}:=\begin{bmatrix}0\\\ 0\\\
0\\\ 1\end{bmatrix},\end{split}$ (15)

and attack matrices $\hat{\Gamma}^{c}_{j}$

$\left\\{\\!\\!\begin{aligned}
\hat{\Gamma}_{1}^{c}&\\!:=\\!\\!\begin{bmatrix}0\\\ 0\\\
-\frac{k_{p}}{\tau}\\\
0\end{bmatrix}\\!\\!\\!,\hat{\Gamma}_{2}^{c}\\!:=\\!\\!\begin{bmatrix}0\\\
0\\\ \frac{k_{p}h}{\tau}\\\
0\end{bmatrix}\\!\\!\\!,\hat{\Gamma}_{3}^{c}\\!:=\\!\\!\begin{bmatrix}0\\\
0\\\ \frac{k_{d}h+k_{dd}}{\tau}-\frac{k_{dd}h}{\tau^{2}}\\\
0\end{bmatrix}\\!\\!\\!,\\\
\hat{\Gamma}_{4}^{c}\\!&:=\\!\\!\begin{bmatrix}0\\\ 0\\\
-\frac{k_{d}}{\tau}\\\
0\end{bmatrix}\\!\\!\\!,\hat{\Gamma}_{5}^{c}\\!:=\\!\\!\begin{bmatrix}0\\\
0\\\ -\frac{k_{dd}}{\tau}\\\
0\end{bmatrix}\\!\\!\\!,\hat{\Gamma}_{6}^{c}\\!:=\\!\\!\begin{bmatrix}0\\\
0\\\ -\frac{1}{\tau}\\\ 0\end{bmatrix}\\!\\!\\!.\end{aligned}\right.$ (16)

Here, we have introduced the index set $\mathcal{L}\subseteq\\{1,...,6\\}$,
which denotes the set of compromised sensors in (10) (i.e.
$\delta_{i,j}(t)\neq 0$ for $j\in\mathcal{L}$ and some $t\geq 0$). Similarly,
$\mathcal{C}_{2}$ can be written as follows:

$\displaystyle\mathcal{C}_{2}\coloneqq\left\\{\begin{aligned}
\dot{\xi}_{i,2}&=-\tfrac{1+k_{dd}}{\tau}\xi_{i,2}-\tfrac{k_{p}}{\tau}e_{i}-\tfrac{k_{d}}{\tau}\dot{e}_{i}-\tfrac{k_{p}}{\tau}\delta_{i,1}\\\
&\,\,\,\,\,\,\,+\tfrac{k_{p}h}{\tau}\delta_{i,2}+\tfrac{k_{d}h}{\tau}\delta_{i,3}-\tfrac{k_{d}}{\tau}\delta_{i,4},\\\
{u}_{i}&=-\tfrac{\tau}{h}\xi_{i,2}+(1-\tfrac{\tau}{h})a_{i}+\tfrac{\tau}{h}a_{i-1}\\\
&\,\,\,\,\,\,\,+(1-\tfrac{\tau}{h})\delta_{i,3}+\tfrac{\tau}{h}\delta_{i,5}.\end{aligned}\right.$
(17)

Then, the closed-loop dynamics (8), (10), (17) is given by

$\dot{\bar{x}}_{i}\coloneqq
A^{c}\bar{x}_{i}+B_{v}^{c}v_{i-1}+\sum_{j\in\mathcal{L}}\bar{\Gamma}_{j}^{c}\delta_{i,j},$
(18)

where $\bar{x}_{i}\coloneqq\text{col}[e_{i},\dot{e}_{i},\xi_{i,2},z_{i}]$,
$\bar{\Gamma}_{1}^{c}=\hat{\Gamma}_{1}^{c}$,
$\bar{\Gamma}_{2}^{c}=\hat{\Gamma}_{2}^{c}$,
$\bar{\Gamma}_{4}^{c}=\hat{\Gamma}_{4}^{c}$, $A^{c}$ and $B_{v}^{c}$ as
defined in (15), and

$\\!\begin{aligned} \bar{\Gamma}_{3}^{c}:=\begin{bmatrix}0\\\
1-\frac{h}{\tau}\\\ \frac{k_{d}h}{\tau}\\\
0\end{bmatrix},\bar{\Gamma}_{5}^{c}:=\begin{bmatrix}0\\\ -1\\\ 0\\\
0\end{bmatrix},\bar{\Gamma}_{6}^{c}:=\begin{bmatrix}0\\\ 0\\\ 0\\\
0\end{bmatrix}.\end{aligned}$ (19)

Because platooning controllers run in discrete time, and attacks operate on
sampled signals, discrete-time equivalent models of (14) and (18) are obtained
via exact discretization at the sampling time instant,
$t=T_{s}k,\,k\in\mathbb{N}$, with sampling interval $T_{s}>0$, assuming zero-
order hold on the control input $u_{i}(t)$. The equivalent discrete-time
models for (14) and (18) can be written compactly as:

$\displaystyle\hat{x}_{i}(k+1)$
$\displaystyle=A\hat{x}_{i}(k)+B_{v}v_{i-1}(k)+\sum_{j\in\mathcal{L}}\hat{\Gamma}_{j}\delta_{i,j}(k),$
(20a) $\displaystyle\bar{x}_{i}(k+1)$
$\displaystyle=A\bar{x}_{i}(k)+B_{v}v_{i-1}(k)+\sum_{j\in\mathcal{L}}\bar{\Gamma}_{j}\delta_{i,j}(k)$
(20b)

with

$\left\\{\begin{aligned}
&A=e^{A^{c}T_{s}},B_{v}=\left(\int_{0}^{T_{s}}e^{A^{c}\left(T_{s}-s\right)}ds\right)B_{v}^{c},\\\
&\hat{\Gamma}_{j}=\left(\int_{0}^{T_{s}}e^{A^{c}\left(T_{s}-s\right)}ds\right)\hat{\Gamma}_{j}^{c},\,\forall
j\in\mathcal{L},\\\
&\bar{\Gamma}_{j}=\left(\int_{0}^{T_{s}}e^{A^{c}\left(T_{s}-s\right)}ds\right)\bar{\Gamma}_{j}^{c},\,\forall
j\in\mathcal{L}.\end{aligned}\right.$ (21)

###  IV-B Adversarial Reachable Sets

We are primarily interested in resource-limited attacks — attacks that tamper
with sensing, actuation, and networked data while being constrained by factors
such as physical limitations, computing power, and attack strategy [10]. We
model these constraints as hard bounds on attack signals $\delta_{i,j}(k)$. We
also impose a hard bound on the velocity of the preceding vehicle, $v_{i-1}$,
as it enters the closed-loop dynamics (see (20)) as an external disturbance
that will affect the system trajectories. Having bounded velocity is
reasonable as $v_{i-1}$ is constrained by the physical limitations of the
vehicle and highway speed limits. The constraints we impose have the following
structure:

$\displaystyle\delta_{i,j}(k)\in\\{\delta_{i,j}(k)\mid\hskip
2.84526pt\delta^{2}_{i,j}\leq W^{2}_{i,j}\\},\,\forall
k\in\mathbb{N},j\in\mathcal{L},$ (22a) $\displaystyle
v_{i-1}(k)\in\\{v_{i-1}(k)\mid\hskip
2.84526ptv^{2}_{i-1}\leq\bar{v}^{2}\\},\,\forall k\in\mathbb{N},$ (22b)

for some known constants $W_{i,j}\in\mathbb{R}_{>0}$ and
$\bar{v}\in\mathbb{R}_{>0}$. Associated with these constraints, we introduce
the notion of adversarial reachable sets for (20a):

$\mathcal{R}^{\hat{x}_{i}}(k):=\left\\{\hat{x}_{i}\in\mathbb{R}^{4}\left|\begin{aligned}
&\hat{x}_{i}=\hat{x}_{i}(k),\\\ &\hat{x}_{i}(k)\text{ solution to
}\eqref{eq:LTI_Dis_1},\\\ &\delta_{i,j}(k)\text{ satisfies
}\eqref{eq:DeltaBound},\\\\[2.84526pt] &v_{i-1}(k)\text{ satisfies
}\eqref{eq:vBound},\end{aligned}\right.\right\\},$ (23)

and for (20b):

$\mathcal{R}^{\bar{x}_{i}}(k):=\left\\{\bar{x}_{i}\in\mathbb{R}^{4}\left|\begin{aligned}
&\bar{x}_{i}=\bar{x}_{i}(k),\\\ &\bar{x}_{i}(k)\text{ solution to
}\eqref{eq:LTI_Dis_2},\\\ &\delta_{i,j}(k)\text{ satisfies
}\eqref{eq:DeltaBound},\\\\[2.84526pt] &v_{i-1}(k)\text{ satisfies
}\eqref{eq:vBound},\end{aligned}\right.\right\\}.$ (24)

To quantify the adversarial capabilities of attacks, the volume of these
adversarial reachable sets can serve as a security metric [13]. This metric
provides insight into the size of the state space portion that can be induced
by a series of attacks. However, computing the exact value of
$\mathcal{R}^{\hat{x}_{i}}(k)$ is generally not tractable and $k$-dependent.
Instead, we seek to obtain the outer ellipsoidal approximation
$\mathcal{E}^{\hat{x}_{i}}(k)$ via Lemma 1, where due to $a\in(0,1)$ in Lemma
1, the sequence $\alpha_{i}^{\hat{x}_{i}}(k)$ shaping the ellipsoid
$\mathcal{E}^{\hat{x}_{i}}(k)$ converges to
$\alpha_{i}^{\hat{x}_{i}}(\infty)\coloneqq(N-a)/(1-a)$ exponentially fast.
Therefore, in a few steps,
$\mathcal{E}^{\hat{x}_{i}}(k)\approx\mathcal{E}^{\hat{x}_{i}}(\infty)\coloneqq\\{\hat{x}_{i}\mid\hat{x}^{\top}_{i}\mathcal{P}^{\hat{x}_{i}}\hat{x}_{i}\leq(N-a)/(1-a)\\}$,
for some positive definite matrix
$\mathcal{P}^{\hat{x}_{i}}\in\mathbb{R}^{4\times 4}$, and where $N$ is the
number of disturbances (according (22)) acting on the system, hence
$N=1+\text{card}[\mathcal{L}]$, where card$[\cdot]$ denotes cardinality. The
volume of the ellipsoidal approximation $\mathcal{E}^{\hat{x}_{i}}(\infty)$
(similarly for $\mathcal{E}^{\bar{x}_{i}}(\infty)$) is used as an over-
approximation of the proposed security metric. Note that, as we consider the
reachable set at infinity, the security analysis is independent of the initial
condition.

##  V Security Assessment

In this section, we use Lemma 1 to find the smallest ellipsoidal approximation
of the adversarial reachable sets (23) and (24) for different subsets of
sensors (10) being attacked. We introduce the notion of critical states,
denoted as $\mathcal{D}^{x_{i}}$, which characterizes states that, if reached,
compromise the safety and integrity of the vehicle. These critical states may
include situations such as collisions between vehicles or a vehicle exceeding
the speed limit on the highway. If the intersection between the set of
critical states and a reachable set $\mathcal{R}^{x_{i}}(k)$ is not empty;
then, there exist attack signals $\delta_{i,j}(k)$ satisfying (22a) that can
drive the vehicle to a critical state. Consider the inter-vehicle distance
state $z_{i}$, and note that $q_{i-1}-q_{i}-L_{i}=z_{i}+r_{i}\leq 0$ indicates
that a collision between vehicles $i$ and $i-1$ has occurred. Therefore, a
subset of states $\hat{x}_{i}$ and $\bar{x}_{i}$ that represents collision can
be written as $z_{i}\leq r_{i}$. Similarly, the vehicle velocities $v_{i}$
exceeding a speed limit, say $\bar{v}_{i}$, can be formulated as
$\tfrac{1}{h}z_{i}-\tfrac{1}{h}e_{i}>\bar{v}_{i}$.

These two sets of critical states and ellipsoidal approximations, projected
onto the $v_{i}$-$z_{i}$ plane via Lemma 2 and applying a coordinate
transformation
$\tilde{x}=\begin{bmatrix}v_{i}&z_{i}&\dot{e}_{i}&\zeta_{i,1}\end{bmatrix}^{\top}=S\hat{x}$,
(similarly for $\tilde{x}$), such that,
$\mathcal{E}^{\tilde{x}_{i}}(\infty)\coloneqq\\{\tilde{x}_{i}\\!\\!\mid\\!\\!\tilde{x}^{\top}_{i}(S^{-1})^{\top}\mathcal{P}^{\hat{x}_{i}}S^{-1}\tilde{x}_{i}\leq(N-a)/(1-a)\\}$.
This transformation allows the characterizing of security using the size of
the ellipsoids and their intersection with critical states. Note that the
proposed critical states are used as an example, but the analysis can also be
applied to different safety constraints.

We consider the closed-loop dynamics (20a), (LABEL:eq:DiscreteSystemMatrices)
for $\mathcal{C}_{1}$, and (20b), (LABEL:eq:DiscreteSystemMatrices) for
$\mathcal{C}_{2}$, with a desired inter-vehicle distance of $r_{i}=3\,$m,
driveline dynamics constant $\tau=0.1\,$s, time headway constant $h=0.5\,$s,
controller gains of $(k_{p},k_{d},k_{dd})=(0.2,0.7,0)$, and sampling rate of
$T_{s}=0.01\,$s. Additionally, we assume a speed limit of
$\bar{v}_{i}=35.83\,$m/s. For the resource-limited FDI attacks
$\delta_{i,j}(k)$, we assume that the attacks remain within the bound
specified by (22a) with $W_{i,j}=1$, for all $j\in\mathcal{L}$. The bound
$W_{i,j}$ is an arbitrarily chosen value, as we are only interested in the
differences in the proposed metrics between the two controller realizations.

###  V-A Sensor Sensitivity

The first case study focuses on individual sensor attacks, offering valuable
insights into the importance of protecting specific sensors during cyber
attacks. This case study also indicates which sensors are more critical to be
protected when there are resource limitations and not all sensors can be
secured. In Table I, the numerical values of volumes of
$\mathcal{E}^{\hat{x}_{1}}(\infty)$ and $\mathcal{E}^{\bar{x}_{1}}(\infty)$
(i.e., for both realized controllers $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$)
are given. Upon comparing the different individual attacks, $\mathcal{C}_{2}$
proves to be highly sensitive to an attack on the onboard acceleration
measurement $y_{i,3}$. As for the realization it holds that $k_{dd}=0$,
resulting in an equivalent attack on $\xi_{i}$ when comparing
$\hat{\Gamma}_{3}^{c}$ and $\bar{\Gamma}_{3}^{c}$. However, due to the
different realization, the error dynamics $\ddot{e}$ in $\mathcal{C}_{2}$ is
also affected by an attack on $y_{i,3}$, hence the non-zero entry in
$\bar{\Gamma}_{3}^{c}$, resulting in an increased sensitivity to an attack on
this particular sensor. In Fig. 2, the projection of
$\mathcal{E}^{\hat{x}_{1}}$ and $\mathcal{E}^{\bar{x}_{1}}$ (onto the
$v_{i}$-$z_{i}$ plane) for $\mathcal{L}=3$ is shown. The orange dashed lines
indicate the boundaries of the critical states, where it can be observed that
$\mathcal{C}_{2}$ suffers significantly more as the number of states the
attack can induce is much larger.

Based on the comparison of the different volumes in Table I, it can be
concluded that $\mathcal{C}_{1}$ has greater overall robustness against
resource-limited attacks. The attack in which $\mathcal{C}_{2}$ outperforms
$\mathcal{C}_{1}$ is in the case of a cyber-attack on $u_{i-1}$
($\mathcal{L}=6$). However, it should be noted that an attack on $u_{i-1}$ is
equivalent to an attack on $a_{i-1}$, as both values are typically obtained
through V2V communication. As a result, the comparison between scenarios
$\mathcal{L}=5$ and $\mathcal{L}=6$ does not indicate any advantage of using
one realization over the other. Furthermore, it is worth noting that for
$\mathcal{C}_{1}$, the information of the predecessor — namely $v_{i-1}$ and
$u_{i-1}$ — is important to protect, especially when resources are limited.
This emphasizes the need for enhanced security against cyber-attacks,
highlighting the importance of safeguarding such critical information.

Figure 2: Projection of $\mathcal{E}^{\hat{x}_{i}}(\infty)$ and $\mathcal{E}^{\bar{x}_{i}}(\infty)$ for an attack on acceleration sensor $y_{i,3}$, hence $\mathcal{L}=3$. $\mathcal{L}$ | 1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---|---
Vol($\mathcal{E}^{\hat{x}_{i}}$) | 192.92 | 96.46 | 337.64 | 675.59 | 0.01 | 965.73
Vol($\mathcal{E}^{\bar{x}_{i}}$) | 192.92 | 96.46 | 3523.42 | 675.59 | 951.81 | 0.01
TABLE I: Numerical values of volumes of $\mathcal{E}^{\hat{x}_{i}}(\infty)$
and $\mathcal{E}^{\bar{x}_{i}}(\infty)$ (i.e., for both realized controllers
$\mathcal{C}_{1}$ and $\mathcal{C}_{2}$).

###  V-B Varying Constant Headway $h$

In this section, we present a second case study, which explores the impact of
the time headway constant $h$ on the ellipsoidal approximation of the
adversarial reachable set for the same system introduced in section V-A.

We assume that $\mathcal{L}=\\{1,2,3,4,5,6\\}$, indicating that all sensors in
(10) are compromised. The left plot in Fig. 3 shows the projected ellipsoids’
volume of both $\mathcal{E}^{\hat{x}_{i}}(\infty)$ and
$\mathcal{E}^{\bar{x}_{i}}(\infty)$ on the $v_{i}$-$z_{i}$ plane for different
values of $h\in[0.01,0.02,...,1.2]$. The results show that the volume of
$\mathcal{E}^{\hat{x}_{i}}$ has an exponential decay for $h<1$, indicating
more resiliency, however for $h>1$ the volume slightly increases. It is
observed that the volume of $\mathcal{E}^{\hat{x}_{i}}$ is always smaller than
$\mathcal{E}^{\bar{x}_{i}}$, but decays more slowly. However, for $h>0.1$, the
volume of $\mathcal{E}^{\bar{x}_{i}}$ increases exponentially. To analyze this
behavior, the right plot in Fig. 3 shows the volume of
$\mathcal{E}^{\bar{x}_{i}}$ for single sensor attacks. It is clear that for
$\mathcal{L}=3$ and $h>0.1$, the volume begins to increase exponentially.
Since $k_{dd}$ is set to be zero, the only difference between
$\hat{\Gamma}_{3}$ and $\bar{\Gamma}_{3}$ is the additional term
$1-\frac{h}{\tau}$, where the volume starts increasing when this term switches
to a negative term. Future work should include an analysis of why the
additional term in $\bar{\Gamma}_{3}$ causes exponential growth of the volume.

Figure 3: (Left) The volume of $\mathcal{E}^{\hat{x}_{i}}(\infty)$ and
$\mathcal{E}^{\bar{x}_{i}}(\infty)$ for $\mathcal{L}=\\{1,2,3,4,5,6\\}$ for
varying headway constant $h$. (Right) The volume of
$\mathcal{E}^{\bar{x}_{i}}(\infty)$ for varying headway constant $h$ and
individual sensor attacks.

Additionally, it is noted that the volume alone does not provide a
representative metric for selecting the optimal value of $h$. In Fig. 3
$\mathcal{E}^{\hat{x}_{i}}(\infty)$ and $\mathcal{E}^{\bar{x}_{i}}(\infty)$
are projected onto the $v_{i}$-$z_{i}$ plane, showing that the orientation of
the ellipsoids are affected for different values of $h$. Thus, the optimal
controller does not necessarily have the smallest volume, but has the smallest
intersection with the critical states, indicating a potential new security
metric.

Figure 4: (Left) Projection $\mathcal{E}^{\hat{x}_{i}}(\infty)$ onto
$v_{i}$-$z_{i}$ plane for different $h$ and $\mathcal{L}=\\{1,2,3,4,5,6\\}$.
(Right) Projection $\mathcal{E}^{\bar{x}_{i}}(\infty)$ onto $v_{i}$-$z_{i}$
plane for different $h$ and $\mathcal{L}=\\{1,2,3,4,5,6\\}$. The green area
represents the Non-Critical States (NC-States).

###  V-C Varying Sampling Constant $T_{s}$

This section discusses the final case study, where the effect of the sampling
rate $T_{s}$ on $\mathcal{E}^{\hat{x}_{i}}(\infty)$ and
$\mathcal{E}^{\bar{x}_{i}}(\infty)$ is examined. Since the CACC can be applied
to various vehicles / operating systems, it is most likely for the sampling
rate to differ. Assuming a zero-order hold for the controller input, the
closed-loop system performance can be affected.

The obtained results are similar to the previous two case studies, where in
Fig. 5 $\mathcal{E}^{\hat{x}_{i}}(\infty)$ and
$\mathcal{E}^{\bar{x}_{i}}(\infty)$ are projected onto the $v_{i}$-$z_{i}$
plane for different values of $T_{s}$, indicating that $\mathcal{C}_{1}$ is
more resilient against attacks than $\mathcal{C}_{2}$ for varying $T_{s}$.
However, where $h$ also affected the orientation of the ellipsoid, $T_{s}$
only affects the size of the ellipsoid. Since $T_{s}$ only alters the input
rate, it is expected to only affect the volume, as changing $h$ results in a
different control goal and increased distance between vehicle $i$ and its
predecessor $i-1$.

Figure 5: (Left) Projection $\mathcal{E}^{\hat{x}_{i}}(\infty)$ onto
$v_{i}$-$z_{i}$ plane for different $T_{s}$ and
$\mathcal{L}=\\{1,2,3,4,5,6\\}$. (Right) Projection
$\mathcal{E}^{\bar{x}_{i}}(\infty)$ onto $v_{i}$-$z_{i}$ plane for different
$T_{s}$ and $\mathcal{L}=\\{1,2,3,4,5,6\\}$. The green area represents the
Non-Critical States (NC-States).

##  VI CONCLUSIONS AND FUTURE WORKS

CACC schemes must ensure safety and reliability in adversarial environments.
In this paper, we have argued that for a given dynamic CACC scheme, an
infinite number of real-time realizations of the same controller exist given
the available sensors. It is shown that different controller realizations can
significantly affect the impact of resource-limited attacks. Two different
controller realizations are compared by computing outer ellipsoidal
approximations of reachable sets induced by attacks, and evaluated how the
sampling and headway constant change these sets. As a result, it is concluded
that the sensitivity of the system changes significantly for the same class of
attacks. Therefore, these results indicate that there exist optimal
controllers that minimize the system sensitivity to resource-limited attacks.

In this manuscript, we have also highlighted the importance of incorporating
new security metrics. Changing the controller affects the orientation of the
ellipsoidal approximation, resulting in different intersections between
critical states and adversarial reachable sets. Therefore, comparing different
controller realizations by means of these intersections provides more insight
into the vulnerabilities of the system in terms of safety. Additionally,
future work should incorporate an analysis of how an attack propagates through
the platooning behavior by considering more vehicles.

## References

  * [1]
  * [2] J. Ploeg, D. P. Shukla, N. van de Wouw, and H. Nijmeijer, ”Lp String Stability of Cascaded Systems: Application to Vehicle Platooning”, IEEE Trans. on Control Syst. Techn., vol. 22, p. 786–793, 2014
  * [3] M. Amoozadeh, A. Raghuramu, C. Chuah, D. Ghosal, M. Zhang, J. Rowe, and K. Levitt, ”Security vulnerabilities of connected vehicle streams and their impact on cooperative driving”, IEEE Communications Magazine, vol. 63, p. 126–132, 2015
  * [4] Z.+ El-Rewini, K. Sadatsharan, D. F. Selvaraj, S. J. Plathottam, and P. Ranganathan, ”Cybersecurity Challenges in Vehicular Communications”, Vehicular Communications, vol. 23, 2020
  * [5] Z. Ju, H. Zhang, L. Ziang, C. Xiaoguang, H. Jinpeng, and M. Yang, ”A Survey on Attack Detection and Resilience for Connected and Automated Vehicles: From Vehicle Dynamics and Control Perspective,” IEEE Transactions on Intelligent Vehicles, vol. 7, p. 815–837, 2022
  * [6] X. Sun, F. R. Yu, and Z. Zhang, ”A Survey on Cyber-Security of Connected and Autonomous Vehicles (CAVs)”, in IEEE Transactions on Intelligent Transportation Systems, vol. 23, no. 7, p. 6240-6259, Jul. 2022
  * [7] A. Teixeira, I. Shames, H. Sandberg, and K. H. Johansson, ”A Secure Control Framework for Resource-Limited Adversaries, in Automatica, vol. 51, p 135-148, Jan. 2015
  * [8] A. Chowdhury, G. Karmakar, J. Kamruzzaman, A. Jolfaei, and R. Das, ”Attacks on Self-Driving Cars and Their Countermeasures: A Survey”, in IEEE Access, vol. 8, p. 207308 - 207342, 2020
  * [9] Z. Ju, H. Zhang, X. Li, X. Chen, J. Han, and M. Yang, ”A Survey on Attack Detection and Ressilence for Connected and Automated Vehicles: From Vehicle Dynamics and Control Perspective”, in IEEE Transactions on Intelligent Vehicles, vol. 7, no. 4, p. 815-837, Dec. 2022
  * [10] X.-M. Zhang, Q.-L Han, X. Ge et al., ”Networked Control Systems: A Survey of Trends and Techniques”, in IEEE/CAA Journal of Automotica Sinica, p. 1-17, 2019
  * [11] Z. van der Heijden, T. Lukaseder, and F. Kargl, ”Analyzing Attacks on Cooperative Adaptive Cruise Control (CACC)”, 2017 IEEE Vehicular Networking Conference (VNC), p. 45–52, 2017
  * [12] S. Dadras, S. Dadras, and C. Winstead, ”Reachable Set Analysis of Vehicular Platooning in Adversarial Environment”, 2018 Annual American Control Conference (ACC), p. 5568–5575, 2018
  * [13] C. Murguia, I. Shames, J. Ruths, and D. Nešić, ”Security metrics and synthesis of secure control systems,” Automatica, vol. 115, p. 108757, 2020
  * [14] S. H. Kafash, J. Giraldo, C. Murguia, A. A. Cardensas, and J. Ruths, ”Constraining Attack Capabilities Through Actuator Saturation”, in 2018 Annual American Control Conference (ACC), p. 986-991, Jun. 2018
  * [15] S. Boyd, L. El Ghaoi, E. Feron, and V. Balakrishnan, ”Linear Matrix Inequalities in System and Control Theory”, SIAM, 1994
  * [16] E. Lefeber, J. Ploeg, and H. Nijmeijer, ”Cooperative Adaptive Cruise Control of Heterogeneous Vehicle Platoons”, in IFAC-PapersOnLine, vol. 53, no. 2, pp. 15217 - 15222, 2020


# Selecting the Points for Training using Graph Centrality

Sandeep CR
Vikram Sarabhai Space Centre,
Thiruvananthapuram, India
Asif Salim, Sumitra. S
Department of Mathematics,
Indian Institute of Space Science and Technology,
Thiruvananthapuram, India
cr_sandeep@vssc.gov.in,asifsalim.16<EMAIL_ADDRESS>

###### Abstract

We describe a method to select the nodes in Graph datasets for training so
that the model trained on the points selected will be be better than the ones
if we select other points for the purpose of training. This is a very
important aspect as the process of labelling the points is often a costly
affair. The usual Active Learning methods are good but the penalty involved
with these methods is that, we need to re-train the model after selecting the
nodes in each iteration of Active Learning cycle. We come up with a method
which use the concept of Graph Centrality to select the nodes for labeling and
training initially and the training is needed to perform only once. We have
tested this idea on three graph datasets - Cora, Citeseer and Pubmed- and the
results are really encouraging.

##  1 Introduction

Consider the problem of classifying the vertices in a graph, $G=(V,E)$, where
$V$ is the set of vertices with $|V|=N$,$N$ being the number of nodes and $E$
is the edge set. The usual way adopted in Graph Semi-Supervised Learning (SSL)
is to select a few number of nodes upfront randomly as the nodes for which we
seek the labels from an Oracle and use these nodes for training the model.
There are number of attempts to effectively perform this task, the popular one
being the approach of using Graph Convolutional Networks (GCN) as proposed by
Kipf et.al.[1] The nodes which we select for labeling may not be the most
ideal or informative points for the model to learn, so if we select the points
in a more smart way, the model can be made better.

Another popular idea for selecting the points for training is Active Learning,
where the model is initially given a few points for training and from the
trained model, new points are selected for training based on some form of
acquisition function, which uses either the model uncertaininty or the ability
to cover the data distribution as a measure to rank the points. The penalty
involved in such a method is that we need to re-train the model every time
after we select the points.

To make a better selection of nodes for training, we propose to use the
concept of Graph Centrality. Graph Centrality is a concept from graph theory,
where the centrality of a node is defined as the ’importance’ of that node in
the graphical structure. This importance can be defined in many ways, degree
centrality, closeness centrality, shortest path centrality, page rank
centrality etc being the most popular measures of centrality.

Our attempt is to select the nodes using the centrality, so that the nodes
which are selected for training will be more ’important’ and hence more
’informative’ for the model to learn. We propose a simple but efficient method
to select the points based on centrality and the experiments have shown that
this selection indeed results in models which are better than the ones which
select the points randomly.

Our method does not have the issue of retraining the model every time, as we
select all the points upfront and the training is carried out only once. To
the best of our knowledge, this is the first attempt to make use of graph
centrality to select the points efficiently for training.

Our contribution in this paper are summarized as below:

  1. 1.

Using the concept of graph centrality to select the training points

  2. 2.

Using graph centrality combined with graph convolutional networks(GCN) to
select the training points in a smart way so that the model trained on the
points selected gives better results

  3. 3.

Applying the same concept in the active learning set up

##  2 Related Works

Semi-Supervised Classification on Graphs: The spectral graph convolution
neural networks was introduced by Bruna et al.[2] where the Graph Fourier
Transform on the nodes of the graph was utilized. The convolution is defined
on the space spanned by the eigenvectors of the graph Laplacian. In the work
of Defferrard et al.[3], convolution filter is defined as the linear
combination of the powers of Laplacian. Kipf et al. [1] modified this approach
by using the first order approximation of the convolution defined using the
graph Laplacian. In [4], a method GraphHeat is put forward, where a negative
exponential on the eigen-values of the Laplacian is used, which penalizes the
higher frequency components.There were a number of attempts which tried to
improve the GCN. Some of the important ones are Graph Attention Networks,
which introduced the concept of attention to the graph convolutional networks,
Conf GCN by Vashishth et al. [5], which estimated the label score along with
their confidences jointly in a GCN setting.

Active Learning:Active Learning algorithm has to learn from a small amount of
data and also come up with ways to represent the uncertainities in the model
effectively. This restricts the models that are available for active learning
especially in deep learning scenarios. The earlier works in this direction
were mostly based on low-dimensional problems such as the one suggested in
[6]. New algorithms were developed to process the higher dimensional data in
the deep learning era and especially with the arrival of Convolutional Neural
Networks (CNN).

There are new approaches like the one mentioned in [7] where given a training
data point $x$, target model gives $\hat{y}=\Theta_{target}(x)$ and a
predicted loss through the loss prediction module as
$\hat{l}=\Theta_{loss}(h)$, where $h$ is the feature set of $x$ extracted from
the several hidden layers of target model. Since annotation for $x$, $y$ is
known, the target loss is computed as $l=L_{target}(y,\hat{y})$. Since this
loss $l$ is a ground-truth target of $h$ for the loss prediction module, we
can also compute the loss for the loss prediction module as
$L_{loss}(l,\hat{l})$.

The method prescribed in [8], where the idea is to allow thes training set to
capture the diversity in the dataset. To find the data that isn’t represented
well yet by the training set, we need to find the “Core Set” at every step.
The core set is defined as a batch of points such that when added to the
training set, the distance between a point in the unlabeled pool and it’s
closest point in the training set, will be minimized.

Most of the Active Learning algorithms acquisition function relies on the
uncertainity of model predictions. But deep learning rarely represent this
uncertainity. There are specialized models such as Deep Bayesian CNNs [9],
which has formed the base line for the paper [10]. To predict the model
uncertainities for Active Learning scenario, stochastic regularization
techniques such as drop-out is used. Inference is done by training a model
with dropout before every weight layer, and by performing dropout at test time
as well to sample from the approximate posterior. The idea is to try and get
the uncertainity measure of the neural network through the drop-out.

Another novel idea which is discussed in [11], is a diffusion based approach.
In this, the data points are represented as a graph whose node representations
are taken from the penultimate layer of a neural network. A graph is
constructed from K-Nearest Neighbours and an algorithm is used to find the
most informative points for annotation.

##  3 Graph Centrality

In Graph Theory, Centrality measures try to identify the most important
vertices in a graph. Graph Centrality is defined as a real-valued function on
the vertices of a graph, where the values produced are expected to provide a
ranking which identifies the most important nodes. he definition of
’importance’ may vary according to the context. The popular measures of
’importance’ are Degree, Betweenness, Closeness etc

###  3.1 Degree Centrality

This is one of the basic measures of centrality. It is equal to the number of
immediate neighbors of a node. That is Degree is simply the number of nodes at
distance one. Thus the more neighbors a node have the more central and highly
connected that node is. We assume that the higher degree nodes have more
influence on the graph. Though simple, degree is often a highly effective
measure of the influence of a node.

###  3.2 Closeness Centrality

This measures the ’closeness’ of a node to all other nodes. The farness of a
node $\mathnormal{v}$ is defined as the sum of its distances to all other
nodes and closeness is the inverse of farness.

$closeness(\mathnormal{v})=\frac{1}{\sum_{\mathnormal{i}\neq\mathnormal{v}}d_{\mathnormal{v}\mathnormal{i}}}$

The more central a node is, the lower its total distance to all other nodes.

###  3.3 Betweenness Centrality

Betweenness centrality quantifies the number of times a node acts as a bridge
along the shortest path between two other nodes. The vertices that have a high
probability to occur on a randomly chosen shortest path between two randomly
chosen vertices have a high betweenness

$Betweenness(\mathnormal{v})=\sum_{\mathnormal{s}\neq\mathnormal{t}\neq\mathnormal{v}\in
V}\frac{\sigma_{\mathnormal{st}}(\mathnormal{v})}{\sigma_{\mathnormal{st}}}$

Where $\sigma_{\mathnormal{st}}$ is the total number of shortest paths from
$\mathnormal{s}$ to $\mathnormal{t}$ and
$\sigma_{\mathnormal{st}}(\mathnormal{v})$ is the number of those shortest
paths which pass through $\mathnormal{v}$

###  3.4 Pagerank Centrality

Here Google PageRank algorithm is used to rank the nodes. We define a column
stochastic matrix

$N=AD^{-1}$

where $A$ is the Adjascency matrix of the graph and $D$ is the diagonal
matrix, with $D_{ii}=\sum_{j}A_{ij}$. We need to ensure that the link matrix
is a positive column stochastic matrix. So the link matrix to find the
PageRank is given by,

$M=(1-\alpha)N+\alpha S$

where $\alpha\in[0,1]$ and $S=\frac{1}{N}\mathnormal{I}$, $N$, being the
number of nodes and $\mathnormal{I}$ represent the Identity Matrix. $M$ is a
positive column stochastic matrix which will have only one L.I eigen vector
corresponding to eignevalue=1.

PageRank centrality of the node $\mathnormal{i}$ is the rank of
$\mathnormal{x}_{\mathnormal{i}}$ in the eigenvector
$\mathnormal{x}=M\mathnormal{x}$

###  3.5 Vote Rank Centrality

The paper [12] presents a centrality measure called Vote Rank Centrality which
is used to identify a set of decentralized spreaders with the best spreading
ability. This is a paper in the area of influence maximization problem in
Graph Theory. As influential nodes have strong ability to affect other nodes,
selecting top-ranked influential nodes as source spreaders is a common
strategy. The key idea here is that if one node A has the supported another
node B, then the support strength of A to other nodes will decrease. Under
this approach, a Vote based algorithm to identify the most influential nodes
is put forward.

In this algorithm, each node $\mathnormal{u}$, is attached with a tuple
$(s_{\mathnormal{u}},va_{\mathnormal{u}})$, where $s_{\mathnormal{u}}$ is the
voting score, which is the number of votes the node $\mathnormal{u}$ has
obtained from its neighbors and $va_{\mathnormal{u}}$ is the value of vote
which $\mathnormal{u}$ can give to its neighbors.

The algorithm is as follows:

  * •

Step-1 \- Initialize - For all nodes,
$(s_{\mathnormal{u}},va_{\mathnormal{u}})=(0,1)$

  * •

Step-2 \- Vote. The nodes vote for their neighbors. After this, voting score
of each node will be calculated. Voting score of a node already selected as a
leading node in an earlier round will be set to zero so as to avoid electing
it again.

  * •

Step-3 \- Select the node which gets the maximum votes. This node will not
participate in the subsequent votings as its voting ability also will be set
to zero

  * •

Step-4 \- Update the voting abilities - Weaken the voting ability of the nodes
which has voted for the node which got selected in the earlier round

  * •

Step-5 \- Repeat the Steps-2 to 4 until we select the $\mathnormal{r}$ number
of influential nodes

##  4 Graph Convolutional Networks

Let $G=(V,E)$ represents a graph with $V$ being the set of Vertices and $E$
the set of edges between the vertices. The adjacency matrix is defined as $W$,
where $W_{ij}$ denotes the weight of the edge $(i,j)$ and 0 if there is no
edge between two vertices. The degree matrix $D$ is defined as a diagonal
matrix with $D_{ii}=\sum_{j}W_{ij}$. If $G$ is an un-weighted graph, the
adjacency matrix entries are defined as $W_{ij}=1$, if $i\sim j$. For
undirected graphs, $W$ will be a symmetric matrix.

The Laplacian of the graph is defined as $L=D-W$ and the normalized Laplacian
is
$\tilde{L}=D^{-\frac{1}{2}}LD^{-\frac{1}{2}}=I-D^{-\frac{1}{2}}WD^{-\frac{1}{2}}$.
The $\tilde{L}$ is a real symmetric positive semi definite matrix and has a
complete orthonormal eigen vectors
$\\{u_{l}\\}_{\mathnormal{l}=1}^{\mathnormal{l}=N}$, and the associated
ordered real non negative eigen values
$\\{\lambda_{l}\\}_{\mathnormal{l}=1}^{\mathnormal{l}=N}$.

Graph Fourier transform is a transformation where we decompose the Laplacian
matrix into its eigen-values and eigen-vectors. It is a process of projecting
a signal $x$ defined on the graph to the space spanned by the eigen-vectors of
the graph Laplacian. The eigen-values of $\tilde{L}$ are called the
frequencies of the graph and the eigen-vectors are called the Fourier modes
for the graph. We could define the eigen decomposition of $\tilde{L}$ as
$\tilde{L}=U\Lambda U^{T}$, where $U$ is the matrix of eigen vectors and
$\Lambda$ is the diagonal matrix of eigen values. The Graph Fourier transform
of a signal $\mathnormal{x}$, given by,
$\mathnormal{F}(x)=\hat{\mathnormal{x}}=U^{T}\mathnormal{x}$. The Inverse
Graph Fourier Transform is defined
as,$\mathnormal{F}^{-1}(\hat{\mathnormal{x}})=\mathnormal{x}=U\hat{\mathnormal{x}}$,
where $\hat{\mathnormal{x}}$ is the resultant signal from the Fourier
Transform.

###  4.1 Spectral Graph Convolutional Networks

The spectral convolution on a graph can be defined as the defined as the
convolution of a signal $x\in\mathbb{R}^{N}$ with a filter
$g\in\mathbb{R}^{N}$. This can be written in the Fourier domain as the
multiplication of the Fourier transforms.
So,$g\circledast\mathnormal{x}=\mathnormal{F}^{-1}(\mathnormal{F}(g)\odot\mathnormal{F}(x))=U(U^{T}g\odot
U^{T}x)$. Considering $g$ being parametrized by $\theta$, and $g_{\theta}$ can
be considered as function of eigen values of
$\tilde{L},g_{\theta}(\Lambda)\in\mathbb{R}^{N\ X\ N}$ (where $\Lambda$ is the
diagonal matrix of eigen values of $\tilde{L}$), we get
$g_{\theta}\circledast\mathnormal{x}=Ug_{\theta}(\Lambda)U^{T}\mathnormal{x}$
The computation of the Eigen decomposition and the matrix multiplications are
costly especially for large graphs. Hence the method suggested in [13] is
used, where $g_{\theta}(\Lambda)$ is approximated by truncated expansion in
terms of Chebyshev polynomials (see Appendix A) upto $K^{th}$ order. So the
expression reduces to $K^{th}$ order polynomial in the Laplacian, ie: the
nodes that are $K$-steps away from a central node only are considered.

So the spectral convolution can be approximated [1] as
$g_{\theta}\circledast\mathnormal{x}\approx
U\left(\sum_{k=0}^{K}\theta_{k}T_{k}(\Lambda)\right)U^{T}\mathnormal{x}$ where
$T_{k}(\mathnormal{x})$ is the $k^{th}$ order Chebyshev Polynomial. Since
$\tilde{L}=U\Lambda U^{T}$ and $(U\Lambda U^{T})^{k}=U\Lambda^{k}U^{T}$, we
get
$g_{\theta}\circledast\mathnormal{x}\approx\sum_{k=0}^{K}\theta_{k}T_{k}(\tilde{L})\mathnormal{x}$.
Limiting the $K=1$, ie: as a linear function on the graph Laplacian, also
assuming $\theta_{0}=-\theta_{1}=\theta$, to reduce the number of parameters
and then applying the renormalization trick, where we add the self loop
connection to ensure the training stability, we get
$g_{\theta}\circledast\mathnormal{x}\approx\theta(\tilde{D}^{-\frac{1}{2}}\tilde{W}\tilde{D}^{-\frac{1}{2}})\mathnormal{x}$,
where $\tilde{W}=W+I$ and $\tilde{D}_{ii}=\sum_{j}\tilde{W}_{ij}$

##  5 Problem Statement

Given a graph $G=(V,E)$, where $V$ is the set of nodes and $|V|=N$, the number
of nodes and $E$ is the edge set defined on the vertices of $G$. Let the
training points for the Semi-Supervised Learning, be $X_{train}$ and let
$N_{train}$ be the number of points that can be chosen for training. For these
$N_{t}rain$, we need to get the labels and using these labels we train the
model. The model can be any neural network model, but for this experiment, we
define the model defined by Kipf et al. [1] as our model.

The problem is to find the optimum $X_{train}$ using the graph centrality
measures, so that the model trained on the points selected will be better than
the models trained on any other points.

##  6 Using Graph Centrality to Select the Nodes for Training

Since the Graph Centrality tries to rank the nodes based on their
importance/influence, can we use the concept of centrality to select the
points for training. For the Graph datasets, the graph structure is already
defined and we could directly apply centrality measures to find out the
important nodes. From the graph structure we could extract the adjacency
matrix and using the adjacency matrix, we could compute the importance score
for each node based on the centrality. From this, we could select the nodes
having high centrality scores and use them for training.

###  6.1 Selecting all nodes at once for Training

This is the most simple and baseline method to select the points for training.
Here, after finding the adjacency matrix $W$, we apply different centrality
measures. The top $N_{train}$ points from the centrality list are selected as
the training points. The training is done only once.

###  6.2 Smart Selection

The points which are very high on the centrality measure, may have neighbours
who also tend to be more central. This may lead to a scenario where the points
selected on centrality may be more clustered and hence may not represent the
diversity present in the dataset. To avoid this, a different, but simple
approach is introduced. We call this ’Smart Selection’ which is given in the
following algorithm.

  * •

Step-1 \- Make the adjacency matrix, A

  * •

Step-2 \- Using the adjacency matrix A, find the centrality of nodes

  * •

Step-3 \- From the centrality list, choose the Top-10 or 5 nodes and assign it
as training points

  * •

Step-4 \- Remove these nodes from the graph and find the centrality again

  * •

Step-5 \- Repeat Step-3 and Step-4 till we reach the labelling
budget($N_{train}$)

  * •

Step-6 \- Once the labelling points are selected, do the training with these
selected points as the training set

  * •

Step-7 \- Apply the model on the test set

The intuition here is that, when we select only top-10 or top-5 points based
on centrality and then by removing them we ensure that the training points are
not concentrated on one particular part of the graph. When the top points are
removed, and we find the centrality, the new top central points tend to cover
the parts of the graph which were not covered initially. By continuing this,
till we reach the labelling budget, the graph structure is well covered and
hence the chance of mapping the distribution effectively is more.

For Vote Rank centrality though, the process of diminishing the effect of the
neighbours of a highly central node is done within the centrality algorithm
itself. So for Vote Rank centrality, we could select the top points all at
once.

##  7 Active Learning using Graph Centrality

For Active Learning, we need to select the data points/nodes which are more
informative so that the model trained on those points will be better than the
model trained on other points. Since the Graph Centrality tries to rank the
nodes based on their importance/influence, the question is whether we can use
the concept of centrality to select the points for Active Learning. Here
instead of using the graph structure as it is, the attempt is to utilize the
features extracted using a neural network.

For this, we start with a small number of training points for which the labels
are sought and using them, we train a GCN and the feature reprsentation from
the penultimate layer of the neural network is taken. The final layer being
the softmax classification layer, penultimate layer gives more of the features
learned. Then using the features learned, we could construct another graph by
applying nearest neighbours on the feature space. On the newly constructed
graph, we can apply the centrality measures and select the important points
based on the centrality and for the top most central points, labels can be
sought from an oracle and re-train the model. This process can be repeated
till we reach the labelling budget and the effectiveness of the method can be
studied.

Since the process of finding the centrality is applied on a graph which is
created from the neural network representations, the idea can be applied to
regular non-graph datasets as well.

##  8 Implementation

The method is attempted on Cora, Citeseer and Pubmed datasets. A 2-layer GCN
on the graph with symmetric adjacency matrix $W$ is designed. First the
$\hat{W}=\tilde{D}^{-\frac{1}{2}}\tilde{W}\tilde{D}^{-\frac{1}{2}}$ is
calculated in the pre-processing step. The model is defined as

$Z=f(X,W)=softmax(\hat{W}ReLU(\hat{W}X\Theta^{(0)})\Theta^{(1)})$ (1)

where $\Theta^{(0)}$ is the Input-to-Hidden weight matrix, $\Theta^{(1)}$ is
the Hidden-to-Output weight matrix. The Loss used is the negative log-
likelihood loss.

The labelling budget for all three datasets is fixed as 140 points as done in
[1]. Different centrality measures are applied on the datasets. Two methods
were attempted, the first one where all 140 points are selected after applying
the centrality and the second one where points are selected using the Smart
Selection algorithm mentioned above.

For the active learning purpose, we start with 10 points initially, and train
a GCN. Then from the model learned, another graph is constructed using
sklearn’s nearest neighbors. On this graph, different centrality measures are
applied and the top-10 points are chosen for labelling in each iteration.
Using the newly added labelled points, network is re-trained and centrality is
applied again. This process is repeated until we reach the labelling budget.

##  9 Results

The results of the method where we select all the points at once, using the
smart selection without using the active learning and when we use active
learning is shown below in 3 tables for 3 datasets. The methods are ranked
based on the statistical t-test to check the significance of the results.

Results for Cora

Method | Cora | Citeseer | Pubmed
---|---|---|---
Using Smart Selection applying Degree Centrality | #1 84.23$\pm$0.05 | #1 72.78$\pm$0.35 | #1 82.69$\pm$0.23
Using Smart Selection applying Closeness Centrality | #2 83.53$\pm$0.024 | #3 71.59$\pm$0.36 | #2 79.5$\pm$0.34
Using Smart Selection applying Betweenness Centrality | #3 83.3$\pm$0.06 | #2 72.19$\pm$0.21 | #2 80.1$\pm$0.21
AL-with Degree Centrality | #4 82.7$\pm$0.014 | #4 70.4$\pm$0.34 | #2 79.8$\pm$0.31
AL-with Closeness Centrality | #5 82.4$\pm$0.06 | #6 67.9$\pm$0.21 | #2 79.5 $\pm 0.34$
AL-with Vote Rank Centrality | #5 82.5$\pm$0.004 | #1 72.8$\pm$0.16 | #2 79.6$\pm$0.27
Using Smart Selection applying Vote Rank Centrality | #6 82.34$\pm$0.07 | #4 70.3$\pm$0.23 | #3 78.82$\pm$0.35
GCN [1] | #7 81.5$\pm$0.63 | #4 70.3$\pm$0.54 | #3 78.48$\pm$0.58
Using Smart Selection applying Pagerank Centrality | #7 81.03$\pm$0.064 | #4 70.59$\pm$0.30 | #3 78.53$\pm$0.36
AL-with PageRank Centrality | #8 80.5$\pm$0.005 | #2 72.1$\pm$0.32 | #3 78.5 $\pm$0.36
By selecting all points at once applying Degree Centrality | #9 78.9$\pm$0.72 | #5 69.2$\pm$0.64 | #4 77.2$\pm$0.53
AL-with Betweenness Centrality | #10 78.4$\pm$0.06 | #7 67.2$\pm$0.24 | #5 76.3$\pm$0.44

Note: The ’#’ before the accuracy value represent the rank for that method
based on the statistical t-test. Same rank for different methods tells that
statistically there is no significant difference among those methods.

The t-SNE Visualization of the GCN embeddings of the points and the training
points selected for the Cora datset is shown below.

Figure 1:

##  10 Discussion

We could see that by applying a smart selection method using degree
centrality, there is siginificant improvement in accuracy for all three
datasets. The important points is that this simple centrality measure is the
fastest to compute and is most effective. Closeness centrality also gives good
results although not as much improvement as with degree-centrality.
Betweenness centrality also improves the performance. But the computation cost
involved in closeness and betweenness centralities is much more compared to
degree centrality.

The performance for the active learning set up, does improve for degree and
vote rank centralities. But not as good as the one with degree centrality and
smart selection. But this could be attempted in the case of non-graphical
data, where we can construct a graph from the features extracted using the
neural network.

The major point to note is that unlike in the active learning set up, where
model is trained each time after selection, for the smart selection, no
training is done until we select all the points upfront. Hence there is no re-
training penalty is involved.

The t-SNE visualization of the GCN embeddings and the training points for Cora
dataset shows that the training points selected are well distributed. Similar
observation is made for the other two datasets as well.

##  11 Conclusion

In this paper, we present a way to select training points for a dataset using
the concept of graph centrality. The concept is used to select the points for
training using a smart selection where we do the training only once after
selecting the required number of points using different centralities. The
method was also applied in the active learning set up, where we select a batch
of points, do the training and from the model output again select the next
batch of points for training. It is seen that, when the smart selection
strategy is applied using the most basic centrality-degree centrality, the
results are really promising. The active learning set up also improves the
performance for degree, vote rank and closeness centrality, but the
computational cost involved is more. However for non-graph datasets, active
learning strategy can be applied. The future work involves applying the method
on tabular datasets to see whether the selection strategy yields better
results for them.

## References

  * [1] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, OpenReview.net, 2017.
  * [2] J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun, “Spectral networks and locally connected networks on graphs,” arXiv preprint arXiv:1312.6203, 2013.
  * [3] M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,” in Advances in neural information processing systems, pp. 3844–3852, 2016.
  * [4] B. Xu, H. Shen, Q. Cao, K. Cen, and X. Cheng, “Graph convolutional networks using heat kernel for semi-supervised learning,” in Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pp. 1928–1934, International Joint Conferences on Artificial Intelligence Organization, 7 2019.
  * [5] S. Vashishth, P. Yadav, M. Bhandari, and P. Talukdar, “Confidence-based graph convolutional networks for semi-supervised learning,” in Proceedings of Machine Learning Research (K. Chaudhuri and M. Sugiyama, eds.), vol. 89 of Proceedings of Machine Learning Research, pp. 1792–1801, PMLR, 16–18 Apr 2019.
  * [6] S. Tong, Active learning: theory and applications, vol. 1.  Stanford University USA, 2001.
  * [7] D. Yoo and I. S. Kweon, “Learning loss for active learning,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 93–102, 2019.
  * [8] O. Sener and S. Savarese, “Active learning for convolutional neural networks: A core-set approach.,” in ICLR, OpenReview.net, 2018.
  * [9] Y. Gal and Z. Ghahramani, “Bayesian convolutional neural networks with bernoulli approximate variational inference,” ICLR workshop track, 2016a, 2016.
  * [10] Y. Gal, R. Islam, and Z. Ghahramani, “Deep bayesian active learning with image data,” in ICML, 2017.
  * [11] D. Kushnir and L. Venturi, “Diffusion-based deep active learning,” arXiv preprint arXiv:2003.10339, 2020.
  * [12] J.-X. Zhang, D.-B. Chen, Q. Dong, and Z.-D. Zhao, “Identifying a set of influential spreaders in complex networks,” Scientific reports, vol. 6, p. 27823, 2016.
  * [13] D. K. Hammond, P. Vandergheynst, and R. Gribonval, “Wavelets on graphs via spectral graph theory,” Applied and Computational Harmonic Analysis, vol. 30, no. 2, pp. 129 – 150, 2011.