# Approximating DTW with a convolutional neural network on EEG data

Hugo Lerogeron
Saagie
LITIS
Rouen
<EMAIL_ADDRESS>&Romain Picot-Clémente
Saagie
Rouen
<EMAIL_ADDRESS>&Alain Rakotomamonjy
Paris
<EMAIL_ADDRESS>&Laurent Heutte
LITIS
Rouen
<EMAIL_ADDRESS>
###### Abstract

Dynamic Time Wrapping (DTW) is a widely used algorithm for measuring
similarities between two time series. It is especially valuable in a wide
variety of applications, such as clustering, anomaly detection,
classification, or video segmentation, where the time-series have different
timescales, are irregularly sampled, or are shifted. However, it is not prone
to be considered as a loss function in an end-to-end learning framework
because of its non-differentiability and its quadratic temporal complexity.
While differentiable variants of DTW have been introduced by the community,
they still present some drawbacks: computing the distance is still expensive
and this similarity tends to blur some differences in the time-series. In this
paper, we propose a fast and differentiable approximation of DTW by comparing
two architectures: the first one for learning an embedding in which the
Euclidean distance mimics the DTW, and the second one for directly predicting
the DTW output using regression. We build the former by training a siamese
neural network to regress the DTW value between two time-series. Depending on
the nature of the activation function, this approximation naturally supports
differentiation, and it is efficient to compute. We show, in a time-series
retrieval context on EEG datasets, that our methods achieve at least the same
level of accuracy as other DTW main approximations with higher computational
efficiency. We also show that it can be used to learn in an end-to-end setting
on long time series by proposing generative models of EEGs.

##  1 Introduction

Proposed by Sakoe and al [1], Dynamic Time Wrapping (DTW) algorithm is an
alignment-based similarity measure for temporal sequences. Initially used for
speech applications, its properties, notably its invariance to time shifts and
its ability to compare series of different lengths, make the DTW useful in
various time-series related applications. For instance, Seto and al [2] make
use of the DTW to create meaningful features for human activity recognition,
Laperre and al [3] employ the DTW as a regularization tool in disturbance
storm time forecasting and Zifan and al [4] consider DTW on piecewise
approximation of time series to segment ECG data. Nevertheless, due to its
non-differentiability (see Tavenard [5]), DTW can not be considered as a loss
function for end-to-end training of deep neural networks. To circumvent those
limitations, differentiable approximations of the DTW have been proposed, such
as SoftDTW by Cuturi and al [6], which notably replace the min operator by a
softmin.

While this approximation enables kernel machine and end-to-end deep neural
network training, it keeps the quadratic complexity in time of DTW which
creates a running time problem for applications in which longer time series
are considered such as EEG signals. For instance, the widely used SleepEDF
dataset introduced by Kemp and al [7] uses splits of size 3000. Therefore, in
order to be able to use DTW as a loss in an end-to-end training on EEG
signals, we propose a neural model that approximates DTW similarity between
two time-series.

To do so, we propose two architectures to compare : an encoder-decoder scheme
in which the backbone is a siamese convolutional neural network and a direct
regression model. We show that this enables to obtain an accurate, scalable
and differentiable approximation of DTW.

In this paper, our contributions are the following ones:

  * •

we compare a direct regression architecture and a siamese encoder-decoder
inspired by Courty and al [8] to approximate DTW;

  * •

we show how such an approximation is fast, more faithful to the objective
function than other approximations (namely FastDTW [9] and SoftDTW [6]) and
can be used in end-to-end training;

  * •

we show how such an approximation can be transferred to others similar EEG
signals using another public dataset.

After considering related works in Section 2, we detail our approach used to
approximate DTW on time series in Section 3 and our experimental setup in
Section 4. We then discuss in Section 5 the differentiability, time efficiency
and performance on classification tasks of our proposed method. We conclude in
Section 6 and draw future works from our results.

##  2 Related Works

###  2.1 Approximation of the DTW

While the advantages of DTW are well-known, its quadratic complexity in both
time and space has limited its practical use to small datasets of short time
series. To counteract those limitations, some efforts have been made to
introduce approximated versions of DTW.
Salvador and al [9] introduced FastDTW, an approximation with linear
complexity in both time and space. However, because FastDTW is not
differentiable, it cannot be used directly as a loss in gradient based
algorithms.
To allow for differentiable end-to-end learning with DTW, Cuturi and al [6]
introduced SoftDTW. The algorithm computes the soft minimum of all costs
spanned by all possible alignments between two time series, which leads to a
differentiable approximation of the DTW. While the forward pass has a linear
time complexity, the backward pass needs to consider all the alignments,
resulting in a quadratic complexity in time and a linear complexity in space.
The addition of the smoothing factor $\gamma$, also may force more
hyperparameter tuning.

With DTWNet [10], Cai and al introduced a stochastic backpropagation of DTW.
They leverage the fact that once the warping path of the DTW is obtained, it
is fixed for the iteration, cannot have more than $(n+m)$ elements (if $n$ and
$m$ are the respective lengths of the input signals) and is in itself
differentiable. While the gradient can be computed in $O(n+m)$, the warping
path needs to be obtained, which still requires $O(n.m)$ operations.

Therefore, while various approaches have been proposed to approximate DTW, to
the best of our knowledge none of them enables both differentiability and at
most linear complexity in time.

###  2.2 Approximation of distances via neural networks

As far as we know, no one has attempted to mimic the DTW with a neural
network. However, Courty and al [8] similarly approximate the Wasserstein
distance using a siamese network to make the squared Euclidean distance of the
embedded vectors mimic the Wasserstein distance between the base vectors. The
two input vectors are fed through the same (hence siamese) encoder $\phi$.
Then a decoder $\psi$, in that case two fully connected layers, tries to
reconstruct the original vector. The encoder learns through the MSE loss,
while a KL divergence loss is used for the reconstruction error of the
decoder.

Authors choose to use the KL divergence because the Wasserstein distance
operates on probability distributions. This allows for interpretation of the
embedding space, and also fulfills two conditions of a distance (identity and
symmetry) since the model is deterministic in inference.

##  3 Architecture for learning to approximate DTW

In this section, we introduce the two architectures we use to approximate DTW
that will be compared in sections 4 and 5. Because of all the advantages of
the method mentioned in 2.2, we first choose to use a similar siamese
architecture as in Courty and al [8]. Our adapted global architecture is shown
in figure 1.

Figure 1: Global architecture of the model. Two signals are drawn from the
dataset and encoded by the same encoder. The goal is to get the L2 distance
between the encoded vectors as close as possible to DTW between the drawn
signals. The encoded signals then pass through a decoder, which tries to
reconstruct the original signal.

Contrary to the Wasserstein distance used in Courty and al [8], DTW does not
work with probabilities distributions but directly with the time series.
Therefore, we use the MSE loss instead of the KL divergence to evaluate the
reconstruction error made by the decoder. The goal of the decoder is to force
the encoder to keep as much information as possible when projecting the
signals. That way, the encoder can not collapse into embedding all the signals
to the same representation. It also helps to regularize the training. Overall,
the encoder $\phi$ takes as input two signals $x\in\mathbb{R}^{L}$ and
$x^{\prime}\in\mathbb{R}^{L^{\prime}}$ and projects them to two signals
$z\in\mathbb{R}^{H}$ and $z^{\prime}\in\mathbb{R}^{H}$, where $H$ is the
hidden dimension. Feeding pairs of signals $\\{x_{i},x_{j}^{\prime}\\}_{i,j\in
1,...,n}$ to the model, the global objective function is then, with
$z=\phi(x),z^{\prime}=\phi(x^{\prime})$ denoting the encoded signals, $\psi$
the decoder, and $y_{i,j}$ the target DTW value:

$\min_{\phi,\psi}\underbrace{\sum_{i,j}\big{\lVert}\|z_{i}-z_{j}^{\prime}\|^{2}-y_{i,j}\big{\rVert}^{2}}_{\textrm{approximation
loss}}+\lambda\underbrace{\left(\sum_{i,j}\|\psi(z_{i})-x_{i}\|^{2}+\sum_{i,j}\|\psi(z_{j}^{\prime})-x_{j}^{\prime}\|^{2}\right)}_{\textrm{reconstruction
loss}}$ (1)

$\lambda$ is a hyperparameter and aims at balancing the losses.

###  3.1 Training Procedure

We describe our training loop with the algorithm 1. We directly feed pairs of
signals $\\{x_{i},x_{j}^{\prime}\\}_{i,j\in 1,...,n}$ of length $L$ and
dimension $d=1$ to the encoder, which processes both signals independently. We
use their corresponding DTW distance
$\\{y_{i,j}=DTW(x_{i},x_{j}^{\prime})\\}_{i,j\in 1,...,n}$ as label. Once we
have encoded signals, we get the predicted DTW value by taking the Euclidean
distance between them and compare it to the reference value via MSE to get the
encoder loss. We then use the decoder to get the decoded signals from the
encoded ones, then compare them to the input signals to get the decoder loss.
We then sum the losses with a balancing parameter $\lambda$ and update the
parameters of the encoder and decoder at the same time.

Input Mini-batch $\bar{D}$, encoder $\phi$, decoder $\psi$
Output Updated $\phi$, $\psi$

for $\forall\>(x,\>x^{\prime})$ in $\bar{D}$ do:

$y\leftarrow DTW(x,x^{\prime})$ $\triangleright$ Reference value, pre-
calculated in practice to save time

$z,\>z^{\prime}\leftarrow\phi(x,\>x^{\prime})$ $\triangleright$
$z\in\mathbb{R}^{H}$

$y_{pred}\leftarrow\|z-z^{\prime}\|_{2}$

$L_{encoder}\leftarrow MSE(y_{pred},y)$

$\hat{x},\>\hat{x}^{\prime}\leftarrow\psi(z,\>z^{\prime})$

$L_{decoder}\leftarrow MSE(\hat{x},x)+MSE(\hat{x}^{\prime},x^{\prime})$

$L\leftarrow L_{encoder}+\lambda*L_{decoder}$

update $\phi$, $\psi$ with $L$

end for

Algorithm 1 Training loop for each mini-batch for the approximation of DTW.

###  3.2 Encoder architecture

The global architecture of our approach is independent of the type of time
series we train it on. On the other hand, if we want a reliable approximation,
the encoder needs to be able to project the signals meaningfully, and
therefore must be adapted to each type of data. In our case, we choose to
focus on EEG data. As a result, we use SorsNet introduced by Sors and al [11]
as encoder. SorsNet is a 1D convolutional neural network consisting of a
series of blocks. Each block contains a convolutional layer, a batch
normalization layer and a ReLU activation function. We choose SorsNet because
it has been shown to work well on sleep staging on EEG signals ([11]), thus we
assume that the architecture allows for a good representation of EEG data. The
network is also fully convolutional, with kernel sizes, strides and padding
carefully chosen to always get a projected vector $z\in\mathbb{R}^{1,H}$ as
long as the length of the time series is less or equal than 3000, the usual
size for EEG data. This permits us to use the same model with the same weights
for time series of different lengths, thus allowing to mimic the DTW ability
to compare time series of different lengths. Finally, the network being fully
convolutional also enables low inference time.

###  3.3 Decoder

We want to force the encoder to learn a meaningful embedding that keeps as
much information about the original signals as possible, in order to improve
the accuracy of the approximation of DTW.
Inspired by Thill and al [12], we first use an upsampling layer so that $z$ is
of the same dimension as the input signal $x$, then use a Temporal
Convolutional Network (TCN, Bai and al [13]) to decode $z$ and try to retrieve
$x$. We use $q=[32,16,8,4,2,1]$ as dilation rates and $k=20$ as kernel size.
The choice of a TCN allows our decoder to be independent of the length of time
series $x$ since all the layers are convolutional.

###  3.4 Direct Regression

While the architecture of our encoder-decoder allows comparing signals of
different lengths, a simpler architecture may work better on signals of fixed
lengths. To investigate this, we also introduce a simpler architecture that we
call direct regression. It takes as input pairs of signals
$\\{x_{i},x_{j}^{\prime}\\}_{i,j\in 1,...,n}$, concatenates them to get a
tensor $x_{cat}\in\mathbb{R}^{B,L,2}$ with $B$ the batch size, then feeds
$x_{cat}$ as input to the SorsNet encoder. Afterwards, a dense layer with
batch normalization and ReLU activation processes the tensor, before a final
dense layer outputs the predicted DTW value. In this case, we do not need a
decoder since we directly get the value to predict. Everything else is kept
identical to the siamese encoder-decoder architecture.

##  4 Experimental Setup

###  4.1 Datasets

While ideally our model should be able to approximate the DTW no matter the
origin of the time series, we decide to first focus only on sleep data. We
choose to use the SleepEDF-78 dataset [7], which contains recording of various
sensors during sleep. The participants were involved in two studies: Sleep
Cassette, which focuses on age effect on sleep and Sleep Telemetry, which
focuses on the impact of temazepam on sleep. For these two datasets, each PSG
file contains two EEG channels (Fpz-Cz, Pz-Oz) sampled at 100 Hz, one EOG
channel and one chin EMG channel. We decided, following the literature (Phan
and al [14], Tsinalis and al [15]) to use only the Sleep Cassette files. To
train our model, we are however able to use all the different channels, while
previous studies focus on the Fpz-Cz channel only. We randomly split the
patients, keeping 70 patients for training and validation and 8 patients for
testing. For each patient, we split the signals in cuts of size $L$ along a
randomly chosen signal. The dataset is then made of $N$ randomly selected
cuts.

Data preprocessing
Since we use multiple channels of the sleep files, we have to process various
types of data. This creates scaling problems, which is to say that some series
will have values in much bigger ranges than others. Moreover, it will lead to
big ranges for the reference DTW values and thus for the training loss. To
face this difficulty, we preprocess the dataset as follows. We first clip all
the values in the dataset $Ds$ i.e., for every value $a_{k}$ in each signal
$x_{i}$ in $Ds$, we compute $p_{1}$ and $p_{99}$, respectively 1st and 99th
percentile.
Then $\forall a_{k}\in Ds:$

$a_{k}=\begin{cases}p_{1}&\text{if}\ a_{k}<p_{1}\\\ p_{99}&\text{if}\
a_{k}>p_{99}\\\ a_{k}&\text{otherwise}\end{cases}$ (2)

This allows to limit the impact of outliers without losing much information.
We then apply the min-max normalization. It projects all the data to $[0,1]$,
which bounds the reference DTW to $[0,L]$ where $L$ is the length of the time-
series $x$ since DTW is ultimately the sum of Euclidean distances along the
alignment path. Knowing the lower and upper bounds of the DTW allows us to
normalize its values to $[0,1]$, greatly helping to balance the training
losses. Creation of the DTW matrix
We then fill the ground truth DTW matrix $Y_{DTW}$. To do so, we randomly
choose $N_{pairs}$ pairs of signals and fill the corresponding parts of the
ground truth matrix with DTW results between the pairs of selected signals,
following Courty and al [8].

###  4.2 Training Parameters

To speed up the training, we restrain the signals to length $L=1000$ by
randomly slicing the signal. We select $N=10,000$ signals as explained in
section 4.1 for the train set and randomly select $N_{pairs}=10^{6}$ over the
$10^{8}$ possible pairs in order to train the model on a decent number of
signals without overfitting. It also limits the training time. We do the same
for the validation set and the test set with 1000 signals and 100,000 pairs.
We use SorsNet as encoder, setting the dropout to 0 and replacing the
classification layer by a dense layer with $H=500$. We define the decoder as
described in section 3.3 and use Adam optimizer with a $10^{-5}$ learning rate
to optimize both the encoder and the decoder parameters at the same time. We
set the batch size to 128 and $\lambda$ to 1. We train for 50 epochs with an
early stopping if the validation loss does not improve for 8 straight epochs.
Note that because of time constraints (training lasts for approximately 20
hours on one TITAN V), no extensive hyperparameter search was done.

##  5 Study of performance on downstream tasks

###  5.1 Illustration of Efficiency and Approximation Properties on a Nearest
Neighbour Retrieval Task

In itself, the output value of DTW is not our main goal. What matters is the
ability to compare time series and rank similarity between time series.
Therefore, instead of comparing the raw values of our approximation with DTW,
once we have trained our model we study its performance on downstream tasks.

We want to study how our model can compare series and how close it is to DTW.
To do so, we first select $N_{t}$ signals in the test set. We then fit a
nearest neighbor algorithm 111https://scikit-
learn.org/stable/modules/neighbors.html using as custom metric our model
(DeepDTW) on the test set. We do the same operation using DTW (we use the
implementation from pyts by Faouzi and al [16]) as custom metric. We select
the top1 nearest neighbor $\tilde{x}_{top1}$ for all signals $x\in N_{t}$ with
$x\neq\tilde{x}_{top1}$ and evaluate the number of times $\tilde{x}_{top1}$ is
in the top 5 ranking of nearest neighbors according to DTW. Since we use
random subsets of the test set, we run the same experiment 8 times for
increasing numbers of signals $N_{t}$. We also add the two main approximations
of DTW, FastDTW and SoftDTW, to the comparison. Since SoftDTW running time is
dependent on the hyperparameter $\gamma$ (the closer $\gamma$ to 0, the more
faithful SoftDTW to the standard DTW, but also the slower as explained by
Cuturi and al [6]), we choose a middle ground with $\gamma=0.1$.

One of the major perks of DTW is its ability to compare time series of
different lengths, and so a good approximation should mimic this feature. To
study this property, we modify our dataset by restricting the size of EEG
signals to random lengths following the uniform sampling method from Tan and
al[17] i.e., $\forall x\in N_{t}$ , $x\in\mathbb{R}^{L}$ with
$L\in[500;1000]$. While in inference no change is required for our siamese
architecture to compute signals of varying lengths, we have to pad the signals
to the size of the longest in a batch to make the direct regression
architecture work. We show the results in table 1. We can see that the direct
regression (DeepDTW Direct) model learns to order signals the closest to DTW,
even outperforming FastDTW when the task is easy or moderately easy (50-200
signals). FastDTW is less impacted by the task getting harder and is the best
with 400 and 600 signals in the set. Both our approximations outperform
SoftDTW no matter the number of signals, with the direct approach above by
$\sim$43 percentage points (pp) when the task is easy and still $\sim$21pp
above in the hardest setting, while the siamese approach is $\sim$20pp above
at 50 signals and about equal at 600 signals.

It illustrates how our model can mimic DTW ability to compare series of
different lengths well enough.

N signals | SoftDTW(0.1) | DeepDTW Direct | DeepDTW Siamese | FastDTW
---|---|---|---|---
50 | 42.25 ± 4.79 | 85.75 ± 4.74 | 62.0 ± 6.48 | 74.25 ± 7.45
100 | 28.12 ± 3.82 | 75.25 ± 1.39 | 45.25 ± 6.76 | 65.25 ± 3.67
200 | 23.06 ± 2.16 | 61.0 ± 2.76 | 33.0 ± 3.22 | 57.56 ± 4.44
400 | 20.22 ± 1.33 | 47.31 ± 3.12 | 22.84 ± 2.43 | 52.47 ± 1.83
600 | 18.0 ± 1.43 | 39.88 ± 2.33 | 18.52 ± 0.83 | 49.75 ± 1.86
Table 1: Percentage of time the closest different signal of length
$L\in[500;1000]$ of a given signal according to our model is among the top 5
closest according to DTW. N signals is the number of signals in the test set.

###  5.2 Sleep Staging

To complete the study of the faithfulness of our approximation, we evaluate
how our model can be used in time-series classification context. We choose the
sleep staging task to do so. It consists in classifying segments of sleep data
in different classes.

Dataset
We use the test set from the SleepEDF dataset, with the same processing as in
section 4.1. This time we use the labels of the states of sleep. The classes
in SleepEDF include wake (W), rapid eye movement (REM), four stages of
different deep sleep (N1, N2, N3, N4), M (movement time) and ’?’ (no data).
Following Mousavi and al [18], we merge the stages N3 and N4, and remove the
sequences labelled as M and ’?’. It results in sequences of signals of
$length=3000$ distributed in 5 different classes.

KNN classification
We want to compare our approximation to DTW and its other main approximations
for sleep staging. To do that, we create 4 instances of KNN classifiers, each
with a different base metric: standard DTW, our model with the direct
architecture (DeepDTW Direct), our model with the siamese architecture
(DeepDTW Siamese) and FastDTW. We then run 5 iterations of the following
experiment: select a number $N$ of random signals in the set and split them in
training and test sets at 50/50 proportion, fit the KNN instance of each
metric on the training set and compute the corresponding macro F1 score (MF1)
on the test set. We modify the SleepEDF test set to get time series of varying
length in the same way as in section 5.1. We show the results on the SleepEDF
dataset in table 2.

N signals | DTW | DeepDTW Direct | DeepDTW Siamese | FastDTW
---|---|---|---|---
500 | 0.25 ± 0.02 | 0.26 ± 0.04 | 0.21 ± 0.02 | 0.26 ± 0.01
1000 | 0.34 ± 0.02 | 0.33 ± 0.01 | 0.37 ± 0.02 | 0.35 ± 0.02
2000 | 0.44 ± 0.01 | 0.44 ± 0.01 | 0.43 ± 0.01 | 0.43 ± 0.01
Table 2: Macro F1 score of sleep staging on SleepEDF with KNN using various
metrics as base for the KNN. We run 5 iterations. For any given iteration, all
the methods use the same data.

Overall, both our approximation and FastDTW behave very similarly to standard
DTW. Small variations due to variance aside, we can see that both our models
and FastDTW lead to very similar classification score to DTW, which shows that
they tend to compare series in the same way.

###  5.3 Computation Time Study

While the main drawback of FastDTW is the fact that it is not differentiable,
the main drawback of SoftDTW is its low computation speed. To illustrate this
point, we study the time needed to compute DTW between two uni-dimensional
time series 1000 times. To fairly compare all the metrics, all the experiments
are run only on CPU. We keep $\gamma=0.1$ for SoftDTW. We show the results in
figure 2. We can see how the computation times needed for both versions of our
models (in blue and black) are very slowly increasing with the size of the
time series, while FastDTW and especially SoftDTW running times are quickly
increasing. At $L=3000$, the standard size for sleep staging, our direct model
is 100 times faster than SoftDTW. Our direct model is only approximately 3
times slower than FastDTW, can be run on GPU, and is differentiable, as shown
in the following section.

Figure 2: Time needed in seconds to run 1000 computations on CPU of the
metric, depending on the lengths of uni-dimensional signals.

###  5.4 Differentiability

The goal of our model is to be accurate, fast, and differentiable. In this
section, we illustrate the latter.

Chang and al [19] introduced a way to learn class specific prototypes in order
to classify time series. For a given dataset $D$, they learn as many
prototypes $p$ as the number of classes $k$ in the dataset: the inter-class
distance between prototypes should be as large as possible, while at the same
time a prototype should represent its class well enough to get good
classification results. Once prototypes are learned, times series can be
classified by using the nearest neighbor algorithm with the prototypes. They
are learned by computing DTW between a given signal $x_{n}\in D$ and each
prototype $p_{k}$ corresponding to each class $k$. Since the idea is to learn
the prototype end-to-end, to circumvent the non-differentiabilty of DTW, the
authors choose to differentiate DTW by using the determined form along the
warping path, i.e., the sum of Euclidean distances of paired points as done by
Cai and al [10].
We apply the method to the SleepEDF dataset and compare the classification
score obtained by computing DTW with our approximation. We show the results in
figure 3. We can see that with our model used as distance to compare the
signals, we learn prototypes that represent the classes better since the
classification accuracy is higher. It is also faster to train, even on CPU
(854 minutes for our method, versus 1773 minutes).

Figure 3: Accuracy score of prototype-based classification on the validation
set during the training of class specific prototypes. The metric is used to
compute the distance between an input signal and prototypes, and so is crucial
for the training. FastDTW is used to compute the alignment path following Cai
and al [10] (see section 5.4).

We have shown that our approximation performs well in time series
classifications tasks, is fast, and can be used to learn end-to-end. However,
a good approximation of DTW should perform well independently of the dataset.
This is what we illustrate in the following section.

###  5.5 Adaptation to others datasets

In this section, we study the generalization capacity of our model to similar
EEG data.

Dataset
Following other sleep staging related contributions (Olesen and al [20], Phan
and al [21], Eldele and al [22]) we evaluate the generalization capabilities
of our model to another widely used EEG dataset: SHHS, introduced by Quan and
al [23] and later updated by Zhang and al [24]. SHHS is a multichannel health
signal database, aimed at studying the effect of sleep-disordered breathing on
cardiovascular diseases. There are two rounds of PSG records in the dataset,
SHHS-1 for Visit 1 and SHHS-2 for Visit 2. We only focus on the first set in
this section. It contains 5791 subjects. Similar to other databases like
SleepEDF annotated with the R&K rule, N3 and N4 stages were merged into N3
stage and MOVEMENT (M) and UNKNOWN (?) signals were removed. As we did in
section 5.2, for each signal we randomly choose a channel among the pre-
selected ones (EEG, EOG(L), EOG(R), ECG and EMG channels for this study).

Nearest Neighbor Retrieval
We reproduce the experiments from section 5.1, this time on the SHHS dataset.
We choose to only use the direct architecture as it gave the best results on
SleepEDF. To study how our model transfers its knowledge to other datasets, we
first use the best model learned on SleepEDF according to the nearest neighbor
test, and directly use it without fine-tuning to do the same test on the SHHS
dataset. We use the same preprocessing as in section 4.1.

We also learn our approximation model on the SHHS dataset in the same way as
in section 4.2 and do the nearest neighbor experiment on a separated test set.
We summarize the results in table 3. The model learned on SleepEDF and tested
on SHHS gives almost identical results to the one learned on SHHS, showing
that for similar data with consistent preprocessing, our approximation model
generalizes very well to new data.

N signals | Model trained on SHHS | Model trained on SleepEDF
---|---|---
50 | $0.89\pm 0.04$ | $0.86\pm 0.03$
100 | $0.75\pm 0.05$ | $0.74\pm 0.04$
200 | $0.61\pm 0.03$ | $0.62\pm 0.02$
400 | $0.50\pm 0.03$ | $0.48\pm 0.02$
600 | $0.44\pm 0.02$ | $0.43\pm 0.02$
Table 3: Nearest neighbor test score on SHHS. The model trained of SleepEDF is
not fine-tuned.

KNN Classification on SHHS
We reproduce the experiment from section 5.2 on the SHHS dataset. We apply
exactly the same processing on SHHS, generating time series of varying length.
We compare the classification performance of 3 KNNs, one based on FastDTW, one
on our direct regression model learned on SleepEDF (DeepDTW SleepEDF) and one
learned on SHHS (DeepDTW SHHS). We show the results in table 4. Our models are
very close to each other, showing that they also generalize well in the
classification context.

N signals | DeepDTW SHHS | DeepDTW SleepEDF | FastDTW
---|---|---|---
500 | 0.250 ± 0.02 | 0.246 ± 0.02 | 0.249 ± 0.01
1000 | 0.329 ± 0.01 | 0.327 ± 0.01 | 0.342 ± 0.04
2000 | 0.427 ± 0.01 | 0.437 ± 0.01 | 0.472 ± 0.01
Table 4: Macro F1 score of sleep staging on SHHS with KNN using various
metrics as base for the KNN. DeepDTW SleepEDF stands for the model learned on
the SleepEDF set and not fine-tuned, while DeepDTW SHHS indicates the model
trained on SHHS. Both use direct architecture.

##  6 Conclusion and future works

In this paper, we presented and compared two architectures to approximate DTW.
The first one is done by creating an embedding in which the Euclidean distance
mimics the DTW. Such an embedding is obtained by training a siamese encoder-
decoder model to both regress the DTW value and retrieve the original signals
from the embedded ones. The second method concatenates signals to directly
predict DTW value, allowing for better retrieval performance and slightly
faster training time, and is therefore a better approach. We showed how our
approximations can be used in an end-to-end training, are faster and more
faithful to DTW than other approximations, and perform well in time series
classification tasks. Finally, we also showed that we can extend the results
to similar datasets.
However, although multidimensional time series are quite common in DTW use
cases, they were not addressed in this paper and are left for future works.
Particularly, being able to embed signals in a space where the Euclidean
distance mimics DTW no matter the length or number of dimensions of the
signals would be the end goal.
Finally, a perfect approximation of DTW should be usable on various types of
data without the need for fine-tuning. Like it has been done in the literature
for natural language processing, we leave for future work to build a huge
dataset of various types of time series and create a generalist model able to
approximate DTW on all those types of data.

## References

  * [1] Hiroaki Sakoe and Seibi Chiba.  Dynamic programming algorithm optimization for spoken word recognition.  IEEE transactions on acoustics, speech, and signal processing, 26(1):43–49, 1978.
  * [2] Skyler Seto, Wenyu Zhang, and Yichen Zhou.  Multivariate time series classification using dynamic time warping template selection for human activity recognition.  In 2015 IEEE symposium series on computational intelligence, pages 1399–1406. IEEE, 2015.
  * [3] Brecht Laperre, Jorge Amaya, and Giovanni Lapenta.  Dynamic time warping as a new evaluation for dst forecast with machine learning.  Frontiers in Astronomy and Space Sciences, 7:39, 2020.
  * [4] Ali Zifan, Sohrab Saberi, Mohammad Hassan Moradi, and Farzad Towhidkhah.  Automated ecg segmentation using piecewise derivative dynamic time warping.  International Journal of Biological and Medical Sciences, 1(3), 2006\.
  * [5] Romain Tavenard.  Dtw blog, 2021.
  * [6] Marco Cuturi and Mathieu Blondel.  Soft-dtw: a differentiable loss function for time-series.  In International conference on machine learning, pages 894–903. PMLR, 2017.
  * [7] B. Kemp, A.H. Zwinderman, B. Tuk, H.A.C. Kamphuisen, and J.J.L. Oberye.  Analysis of a sleep-dependent neuronal feedback loop: the slow-wave microcontinuity of the eeg.  IEEE Transactions on Biomedical Engineering, 47(9):1185–1194, 2000\.
  * [8] Nicolas Courty, Rémi Flamary, and Mélanie Ducoffe.  Learning wasserstein embeddings, 2017.
  * [9] Stan Salvador and Philip Chan.  Toward accurate dynamic time warping in linear time and space.  Intelligent Data Analysis, 11(5):561–580, 2007.
  * [10] Xingyu Cai, Tingyang Xu, Jinfeng Yi, Junzhou Huang, and Sanguthevar Rajasekaran.  Dtwnet: a dynamic time warping network.  Advances in neural information processing systems, 32, 2019.
  * [11] Arnaud Sors, Stéphane Bonnet, Sébastien Mirek, Laurent Vercueil, and Jean-François Payen.  A convolutional neural network for sleep stage scoring from raw single-channel eeg, 2017.
  * [12] Markus Thill, Wolfgang Konen, Hao Wang, and Thomas Bäck.  Temporal convolutional autoencoder for unsupervised anomaly detection in time series.  Applied Soft Computing, 112:107751, 2021.
  * [13] Shaojie Bai, J Zico Kolter, and Vladlen Koltun.  An empirical evaluation of generic convolutional and recurrent networks for sequence modeling.  arXiv preprint arXiv:1803.01271, 2018.
  * [14] Huy Phan, Fernando Andreotti, Navin Cooray, Oliver Chén, and Maarten de Vos.  Joint classification and prediction cnn framework for automatic sleep stage classification.  IEEE Transactions on Biomedical Engineering, 66:1285–1296, 05 2019\.
  * [15] Orestis Tsinalis, Paul M. Matthews, Yike Guo, and Stefanos Zafeiriou.  Automatic sleep stage scoring with single-channel eeg using convolutional neural networks, 2016.
  * [16] Johann Faouzi and Hicham Janati.  pyts: A python package for time series classification.  Journal of Machine Learning Research, 21(46):1–6, 2020.
  * [17] Chang Wei Tan, François Petitjean, Eamonn Keogh, and Geoffrey I Webb.  Time series classification for varying length series.  arXiv preprint arXiv:1910.04341, 2019.
  * [18] Sajad Mousavi, Fatemeh Afghah, and U Rajendra Acharya.  Sleepeegnet: Automated sleep stage scoring with sequence to sequence deep learning approach.  PloS one, 14(5):e0216456, 2019.
  * [19] Xiaobin Chang, Frederick Tung, and Greg Mori.  Learning discriminative prototypes with dynamic time warping.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8395–8404, 2021.
  * [20] Alexander Neergaard Olesen, Poul Jørgen Jennum, Emmanuel Mignot, and Helge Bjarup Dissing Sorensen.  Automatic sleep stage classification with deep residual networks in a mixed-cohort setting.  Sleep, 44(1):zsaa161, 2021.
  * [21] Huy Phan, Oliver Y Chén, Minh C Tran, Philipp Koch, Alfred Mertins, and Maarten De Vos.  Xsleepnet: Multi-view sequential model for automatic sleep staging.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021\.
  * [22] Emadeldeen Eldele, Zhenghua Chen, Chengyu Liu, Min Wu, Chee-Keong Kwoh, Xiaoli Li, and Cuntai Guan.  An attention-based deep learning approach for sleep stage classification with single-channel eeg.  IEEE Transactions on Neural Systems and Rehabilitation Engineering, 29:809–818, 2021.
  * [23] Stuart F Quan, Barbara V Howard, Conrad Iber, James P Kiley, F Javier Nieto, George T O’Connor, David M Rapoport, Susan Redline, John Robbins, Jonathan M Samet, et al.  The sleep heart health study: design, rationale, and methods.  Sleep, 20(12):1077–1085, 1997.
  * [24] Guo-Qiang Zhang, Licong Cui, Remo Mueller, Shiqiang Tao, Matthew Kim, Michael Rueschman, Sara Mariani, Daniel Mobley, and Susan Redline.  The national sleep research resource: towards a sleep data commons.  Journal of the American Medical Informatics Association, 25(10):1351–1358, 2018.


# Political Communities on Twitter: Case Study of the 2022 French Presidential
Election

###### Abstract

With the significant increase in users on social media platforms, a new means
of political campaigning has appeared. Twitter and Facebook are now notable
campaigning tools during elections. Indeed, the candidates and their parties
now take to the internet to interact and spread their ideas. In this paper, we
aim to identify political communities formed on Twitter during the 2022 French
presidential election and analyze each respective community. We create a
large-scale Twitter dataset containing 1.2 million users and 62.6 million
tweets that mention keywords relevant to the election. We perform community
detection on a retweet graph of users and propose an in-depth analysis of the
stance of each community. Finally, we attempt to detect offensive tweets and
automatic bots, comparing across communities in order to gain insight into
each candidate’s supporter demographics and online campaign strategy.
Keywords: French Presidential Election 2022, Natural Language Processing,
Political Community Detection, Social Media

languageresourceLanguage Resources

Political Communities on Twitter: Case Study of the 2022 French Presidential
Election

Hadi Abdine1∗, Yanzhu Guo1∗, Virgile Rennard1,2∗, Michalis Vazirgiannis1,3
---
1Ecole Polytechnique, 2Linagora, 3AUEB
{hadi.abdine, yanzhu.guo<EMAIL_ADDRESS>
<EMAIL_ADDRESS>

Abstract content

## 1\. Introduction

**footnotetext: These authors contributed equally to this work

Social media has created a forum for everyone to express themselves, bringing
disputes to a wide audience and playing an increasingly crucial part in
today’s information economy. With the 2008 U.S. presidential election, a
relatively new paradigm was observed, where a large part of the political
campaign was held on either Facebook or Twitter. The extensive outreach of
these platforms has been shown to bring multiple benefits to politicians, such
as increases in donations [Petrova et al., 2021], or an amplified impact on
the politically inattentive youth [Utz, 2009]. The tremendous amount of data
provided by social media platforms gives us insight into the inner workings of
the online political horizon.

This paper aims to present an in-depth study on the Twitter landscape of the
2022 French elections. We start by creating a Twitter dataset containing more
than 60 million tweets from more than a million users. The tweets are
extracted based on keywords related to the election. We use this dataset to
build a retweet graph among the users and run a graph-based algorithm for
community detection. By analyzing the top hashtags and word clouds of tweets
posted by users of each community, we are able to interpret which candidate
they each support. We go on to visualize the geographical distribution of each
candidate’s online supporters across different regions, making comparisons
between communities. Eventually, we perform offensiveness detection and bot
detection in all the communities. The detection of offensive tweets reveals
that supporters of certain candidates are more likely to post offensive
contents. The results of bot detection also indicates that there are higher
levels of bot activities in certain online communities than in others.
However, we would like to emphasize that the results of both offensiveness
detection and bot detection are produced by automatic classification models
reflecting patterns of the datasets they were trained on. Such models are
subject to various limitations and by no means reflect our personal opinions.

The rest of this paper is organized as follows. Section 2 provides an overview
of the related work. Section 3 describes our the dataset we use and how we
collected it. Section 4 supplies a detailed description of the graph-based
communities. Section 5 detects offensive tweets in each community while
section 6 studies the use of automated bot accounts. Finally, section 7
summarizes our research and presents potential future work.

## 2\. Related Work

Early work on Twitter analysis of political elections dates back to when
Twitter was founded. An example is a study on the 2008 U.S. presidential
election [Diakopoulos and Shamma, 2010] where the debate performance of
presidential candidates is characterized by aggregated Twitter sentiment. This
initiated a branch of research centered around monitoring online public
reactions during election periods. Relevant studies have been carried out on a
wide range of elections in different countries, including the 2012 South Korea
presidential election [Bae et al., 2013], the 2013 German parliamentary
election [Rill et al., 2014], and the 2017 UK general election [Yaqub et al.,
2020].

Another popular branch of research aims at forecasting election results based
on Twitter data. For example, a study on the 2009 German federal election
[Tumasjan et al., 2010] claims that the respective shares of Twitter volume
can accurately reflect the distribution of electoral votes for the six main
parties. However, another study on the 2011 Singapore presidential election
using Twitter sentiment succeeded in picking out the top two candidates but
failed to predict the final ranking [Choy et al., 2011]. It is generally
agreed upon that Twitter analysis for election outcome prediction cannot
substitute traditional polling approaches [Bermingham and Smeaton, 2011], and
that explainable models should accompany the predictive results [Gayo-Avello
et al., 2011].

More recently, attention has been drawn to the diffusion of misinformation and
toxicity during online campaigns. Relevant topics include the detection of
fake news [Cinelli et al., 2020], social bots [Pastor-Galindo et al., 2020],
political trolls [Badawy et al., 2018] as well as hate speech [Siegel et al.,
2021] and offensive language [Grimminger and Klinger, 2021]. Our work is
closely related to this field of study while also drawing upon graph-based
analysis of Twitter network structures [Radicioni et al., 2021].

(a)

(b)

(c)

(d)

(e)

(f)

Figure 1: Word clouds generated from tweets posted by users in each community.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 2: Choropleth map of users in each community.

## 3\. Dataset

We create a novel Twitter dataset with the 2022 French presidential election
as the central topic. The tweets used for building this dataset date from
February 14, 2022 to April 5, 2022. This dataset corresponds to a large and
coherent corpus consisting of small pieces of text related to the election
candidates and major events during their campaigns. In our case, we focus on
tweets that include tokens such as “présidentielle” and “élection”, as well as
the names of candidates and their parties. We extract tweets in the French
language containing the keywords mentioned above through Twitter’s public
streaming API. The public streaming API is able to extract a subset of the
real-time Twitter stream. The resulting dataset consists of 62.6 million
tweets and 1.2 million users.

## 4\. Graph-based Community Detection

Given that the election has been at the center of attention in France since
the beginning of 2022, daily campaigns, scandals, and debates are widespread
through social media. We believe that there would be detectable online
communities related to the different candidates and that each community will
contain important information about each party’s campaign. Therefore, we
construct a retweet graph of Twitter users based on our dataset.

Community | # Accounts | Frequent hashtags
---|---|---
Mélenchon | 15,001 | #melenchonvagagner, #melenchonsecondtour, #jevotemelenchon
Anti-Macron | 12,428 | #macrondehors, #toutsaufmacron, #macrondegage
Zemmour | 12,101 | #zemmourpresident, #jevotezemmour, #zemmourpresident2022
Macron | 5,816 | #avecvous, #macron2022, #5ansdeplus
Pécresse | 1,035 | #valeriepresidente, #pecresse2022, #nouvellefrance
Le Pen | 1,001 | #marinepresidente, #dimanchejevotemarine, #jevotemarine
Jadot | 196 | #jadot2022, #jevotejadot, #totalsoutienàjadot
Table 1: Statistics of different communities.

### 4.1. Graph Creation

With our set of extracted tweets, their authors, and the users who retweet
these tweets, we create a directed weighted graph $G=(V,E)$ where $n=|V|$
denotes the number of nodes. Specifically, each node represents a user on
Twitter, and a weighted edge connects two nodes if one user retweets the
other. For instance, the weight $A_{u,v}$ of the edge $(u,v)$ from vertex $v$
to vertex $u$ notes the number of times that the user $u$ retweeted the user
$v$. We believe that a normal retweet indicates approval of the tweet’s
content, unlike the quote retweets and the replies. Therefore, the graph does
not model the textual similarity of the tweets but only the relation between
users. Note that the obtained graph G might contain self-loops that correspond
to self-retweets. The obtained graph contains 1.2M nodes and 12.4M edges.

To avoid small, non-dense clusters formed from few numbers of users with few
retweets, we decided to work on a dense subset of the graph that we obtained
using the k-core decomposition algorithm instead of working on a full graph.
The k-core decomposition algorithm [Seidman, 1983] aims to find subsets of a
graph G. The subsets are called k-cores of G and are obtained by a recursive
pruning strategy. Each node inside a k-core is connected to at least k other
nodes inside this subset. The hyperparameter k is chosen so that we do not get
a cluster with less than ten users. The final used k-core graph has 47,578
nodes and 8.2M edges. Seven communities are found in our dataset through
applying this approach.

### 4.2. Community Detection

In graph mining, community detection helps to reveal the hidden relations
among the nodes in a graph. Hence, to discern opinion groups inside the k-core
graph, we apply the Louvain community detection method [Blondel et al., 2008]
on an undirected version of our graph without self-loops. The Louvain method
is chosen as it has reasonable computation costs while maximizing modularity.
Moreover, it does not require fine-tuning of hyperparameters. It is therefore
the only applicable method for finding communities in large graphs.

Seven communities were found after applying this approach to the user-based
k-core graph. To get a general overview of the communities, we compute the
frequencies of hashtags used by the users inside each community. We define the
frequency of a hashtag as the number of users using this hashtag inside a
community. We notice that first six out of these seven communities have
remarkable hashtags with high frequencies that relate each community to a
candidate in the election. For example, in one community with 16,190 users,
the top three hashtags are #melenchonvagagner, #melenchonsecondtour and
#jevotemelenchon with respectively 16,073, 14,378 and 10,127 users. In
contrast, no other hashtags supporting other candidates appear in this
community’s 50 most frequent hashtags. Thus, we label this community with
”Mélenchon”. Finally, the seventh and last community only holds keywords
against the current President of France in the top 50 hashtags. We thus label
it as the ”Anti-Macron” community. In table 1 we detail the labels, the number
of users, as well as the most biased and frequent hashtags for each community.

### 4.3. Word Cloud Analysis

To further analyze the political stances of the seven communities, we group
the tweets posted by users of each community and generate a word cloud for
each group of tweets. The resulting word clouds assemble the set of the most
frequent unigrams and bigrams (after removing stop words) in each group of
tweets, with their sizes proportional to their frequencies. Our analysis shows
that except for the community with the ”Anti-Macron” theme, all the other
communities are distinctively composed of users who support one of the
candidates among Emmanuel Macron, Valérie Pécresse, Éric Zemmour, Jean-Luc
Mélenchon, Marine Le Pen and Yannick Jadot. The word clouds for each of these
communities are shown in Figure 1. In addition to identifying which candidate
each community of users supports, we can also use the word clouds to obtain a
general idea of each candidate’s campaign program. For example, the word cloud
for Jadot’s community contains words such as ”justice social (social justice)”
and ”écologiste (ecologist)” with significant weights, and these concepts
precisely lie at the center of his campaign program.

### 4.4. Geolocation Analysis

For each community of users, we plot the distribution of their geolocations
within different regions of Metropolitan France. We select users with
geolocation information and feed the declared locations into the geolocator
from geopy***https://github.com/geopy/geopy to obtain the region each area
belongs to. We only consider users who are located within Metropolitan France.
Although this limits our analysis to a subset of users from the dataset, the
distribution can still reflect the overall situation.

Given that users are remarkably concentrated in the Île de France region for
all the communities, we plot the choropleth map with the number of users
scaled by logarithm to visualize the variations for the other areas more
clearly. The choropleth map is shown in Figure 2. Through observing these
maps, we can gain insights into each candidate’s respective heartland. For
instance, Le Pen has a much higher proportion of supporters in Occitanie,
Provence-Alpes-Côte d’Azur and Hauts-de-France than all the other candidates.
We also find that the supporters of Macron, Pécresse and Mélenchon are more
evenly distributed among different regions outside of Île de France than the
other three candidates. Zemmour and Le Pen both lack Twitter supporters in the
middle and northwestern areas, while Jadot lacks supporters in the whole
northern half of France except the region Hauts-de-France.

Our study was carried out right before the first turn of the election. We
later did a follow-up of the actual results and found that the choropleth map
of votes***https://tinyurl.com/ycxya5dx bear a striking resemblance to our
choropleth maps of communities.

Community | # Unique Tweets | # Offensive Tweets | Proportion of Offensive Tweets
---|---|---|---
Mélenchon | 756,318 | 208,178 | 0.275
Anti-Macron | 549,138 | 168,685 | 0.307
Zemmour | 1,034,538 | 316,214 | 0.305
Macron | 468,138 | 126,122 | 0.269
Pécresse | 80,365 | 19,487 | 0.242
Le Pen | 86,272 | 25,368 | 0.294
Jadot | 12,340 | 1,632 | 0.132
Table 2: Offensive Tweets in Each Community

## 5\. Detection of Offensive Tweets

Along with the growing popularity of social media and online platforms, the
use of offensive online language has become a significant problem. Under such
circumstances, automatic detection of offensive language has received much
research attention [Risch et al., 2020]. With presidential elections being
such a controversial topic, relevant tweets are bound to contain offensive
language. It is expected that online supporters of a given candidate would
make offensive comments towards other candidates and their supporters.
However, supporters of the more extreme candidates might also be more inclined
to use offensive language. The targets of offensive tweets might include other
public groups in addition to opposing candidates and their supporters. We
build an automatic classification model to detect offensive tweets in each
political community and eventually compare the results across communities.

### 5.1. Detection Model

We initialize our model using BERTweetFR [Guo et al., 2021] and fine-tune it
on the MLMA Hate Speech Dataset [Ousidhoum et al., 2019]. BERTweetFR is a
French RoBERTa model [Liu et al., 2019], initialized using the general-domain
French language model CamemBERT [Martin et al., 2020] and further fine-tuned
on 16GB of French tweets. It achieves the state-of-the-art performance on
French Twitter tasks. The MLMA Hate Speech Dataset is a multilingual multi-
aspect Twitter dataset for hate speech analysis. We take a subset of this
dataset selecting only French tweets labeled as either ”normal” or
”offensive”. The resulting subset contains 821 normal tweets and 1690
offensive tweets. After fine-tuning for 3 epochs, our classification model
achieves a f1 score of $83.96\%$ on a 80/20 train-test split.

### 5.2. Detection Results

We run our classification model for tweets posted by users in each political
community. We only consider unique tweets, discarding retweets by
deduplicating them based on the text content. This choice is made because we
aim to detect the origination of offensive language rather than to analyze its
propagation pattern. The detection results are shown in Table 2. A key
observation is that users from the Anti-Macron and Zemmour communities are the
most likely to post offensive tweets, reaching respective proportions of 0.307
and 0.305. This is in line with our expectations: the Anti-Macron community is
naturally supposed to be more offensive as the main goal is to oppose and
defy; as for Zemmour, he is a far-right candidate who has been personally
fined €10,000 for hate speech by a Paris court
***https://www.bbc.com/news/world-europe-60022996. We also observe that the
communities of right-wing candidates tend to have more offensive content in
general, with the only exception being Pécresse’s who is a more moderate
candidate. A possible explanation is the employment of automatic bots in her
community. We will further elaborate on the topic of bots in the following
section.

## 6\. Detection of Automatic Bots

It has come to light in recent years that a significant amount of Twitter
accounts are controlled, at least partly, by software. Some research estimate
that between 9% to 15% of all twitter accounts are somewhat automated [Varol
et al., 2017]. Bots are an important tool for opinion manipulation
[Subrahmanian et al., 2016], and are being used to influence important
subjects such as political elections ([Ferrara, 2017],[Deb et al., 2019]).
Bots also help spread misinformation ([Shao et al., 2017]), and have impacted
the online debate on vaccination [Broniatowski et al., 2018], with an
estimated 45% of COVID-19 related Twitter accounts exhibiting bot-like
behavior ([Memon and Carley, 2020]). This section proposes to estimate the
role bots are playing in the 2022 French election by comparing their relative
use within each community.

### 6.1. Detection model

There is a multitude of available Twitter bot detection models ([Lee et al.,
2021], [Kudugunta and Ferrara, 2018], [Miller et al., 2014], [Ali Alhosseini
et al., 2019]), and APIs ([Davis et al., 2016]) that use semantic, statistical
or neighborhood properties to evaluate the likelihood of an account being a
bot. However, due to the large amount of data we have to process, we need to
use a scalable and generalizable models. This study is therefore going to rely
on statistical features available in the user metadata object given by the
Twitter API. Our employed model is similar to the one presented in [Yang et
al., 2019b], which is scalable and yields adequate generalization results on
the task of bot detection [Feng et al., 2021] in different scenarios.

#### 6.1.1. Feature Selection

The list of available user metadata features relevant to bot detection is
listed as below:

  * •

statuses count

  * •

followers count

  * •

friends count

  * •

favourites count

  * •

listed count

  * •

default profile

  * •

verified

  * •

geographical location enabled

These available features give other interesting statistical information that
we compute as additional derived features for the model. Such features include
the frequency of tweets (statuses count/user age), the respective growth rate
of followers, friends, favorites and listed accounts (respective counts/user
age). We also take into account information from the username, such as its
length and the number of digits it contains. The length of user description is
also proven to be a relevant feature [Yang et al., 2019b].

We choose random forest as our classifier, as it yields near-perfect results
on any individually labeled dataset.

Community | # Accounts | # Bots | Proportion of bots in community | # Tweets | # Automated Tweets | proportion Automated tweets
---|---|---|---|---|---|---
Mélenchon | 15,001 | 2,507 | 0.167 | 5,755,664 | 1,273,656 | 0.284
Anti-Macron | 12,428 | 2,181 | 0.175 | 5,435,820 | 1,268,240 | 0.304
Zemmour | 12,101 | 2,217 | 0.183 | 6,160,153 | 1,501,207 | 0.322
Macron | 5,816 | 1,001 | 0.172 | 2,219,491 | 514,820 | 0.302
Pécresse | 1,035 | 208 | 0.200 | 408,319 | 134,373 | 0.490
Le Pen | 1001 | 184 | 0.184 | 463,290 | 127,633 | 0.380
Jadot | 196 | 30 | 0.153 | 66,541 | 19,876 | 0.426

Table 3: Bots statistics of different communities

#### 6.1.2. Training Data

The choice of training data for such a task is crucial. There are many
different types of bots for different domains, and there is generally poor
classification generalization across datasets [Echeverría et al., 2018].
Considering the task at hand which is the classification of politically
oriented Twitter users into bots or human labels, we decided to train our
model on a concatenation of multiple available datasets: Political-bots-2019
[Yang et al., 2019a] (a compendium of political bots), midterm-2018 [Yang et
al., 2019b] (a hand-labeled dataset of users and bots during the 2018 American
midterm elections), botwiki [Yang et al., 2019b] (a collection of self
identified Twitter bots), verified-2019 [Yang et al., 2019b] (a collection of
verified Twitter users), Cresci 2019-2018 ([Mazza et al., 2019], [Cresci et
al., 2018]) (datasets of manually annotated bots), and finally Twibot-20 [Feng
et al., 2021] (a comprehensive hand labeled dataset of Twitter bots). The
statistics of each dataset is shown in Table 4.

Datasets | # human | # bots
---|---|---
Political-bots-2019 | 0 | 62
Midterm-2018 | 8,092 | 42,446
botwiki | 0 | 698
verified-2019 | 1,987 | 0
twibot-20 | 5,237 | 6,589
cresci-18/19 | 6,514 | 7,455
total | 21,830 | 57,250

Table 4: Statistics of training datasets.

#### 6.1.3. Training results

##### Correlation

It is crucial to consider the most discriminative features when attempting a
task like bot detection, the model should be interpretable. For example, as we
see in Figure 3, there is a strong correlation between the automation of an
account and the age of the account, whether or not the account is verified or
geolocalisation enabled. Another strong indicator of automation is the
presence of a default-profile, which means an account with a lack of
personalization (i.e. custom banner or profile picture).

Figure 3: Heatmap of Pearson correlation between features and labels.)

##### Feature importance

By studying the importance of each feature, we find that the number of
statuses, the information of followers (such as its raw count and growth rate)
and the age of the user are the most critical features for the classifier.

##### Results

Our random forest classifier achieves a $95.0\%$ f1 score with 10-fold cross
validation.

### 6.2. Bot Detection Results

From our experiments, we observe that there is a significant amount of
automated accounts in our dataset – with an estimation of at least 15%, with a
conservative labeling threshold, of accounts partaking in the debate coming
from bots. We have tuned the classification threshold, which is usually at 50%
certainty to 75%, considering the importance of precision in the case of bot
classification.

As shown in Table 3, while the number of users in each community is
significantly different, we find a similar proportion of bots for each
cluster. Therefore, we conjecture that there has not been any large-scale
operation to influence the election with bots from any side.

Another insight we can get from Table 3 is the campaigning approach of each
community. We do not deduplicate tweets to remove retweets, considering the
importance of retweeting in automated accounts. For example, the cluster
supporting Zemmour, while being smaller than some of the others, has
significantly more tweets, including retweets per person, showing the
particular engagement Zemmour supporters seem to offer online. Similarly, we
can see that it is the only large cluster with the most considerable bot
activity, albeit by a small margin. On the other side, we can see that the
Pécresse cluster, smaller in scale, has heavy activities from bots. This
difference in bot activity for the three smallest communities may come from
factors such as some very dynamic automated news pages.

#### 6.2.1. Limitations of Automatic Bot Detection

It is important to keep in mind that bot detection, while being effective, is
a limited approach, especially in the case of political elections. While a lot
of bots can be found, a nuance is to be made, as bots in a cluster are not
necessarily promoting the candidate. Some of the more basic bots that promote
cryptocurrency or fishing sites usually simply post the same messages
repeatedly, along with all the popular hashtag at a time $t$. Such a behavior
artificially inflates the number of bots we find in the community of
candidates that are naturally more active on twitter. The same goes for
”automatized behavior”, as we see in figure 3 and in our feature importance
section. While algorithms are accurate, their most discriminative features are
the number of statuses, followers, and the age of the user. The situation can
be more complicated in the case of politics, as there are actual people who
are willing to tweet with the hashtag #MélenchonPrésident one hundred times a
day simply because they are extremely passionate about the campaign.

## 7\. Conclusion and Future Work

In this paper, we have leveraged graph-based community detection methods to
gather insights into each of the most significant candidates’ online campaigns
for the 2022 French presidential election. We have been able to build a
portrait of the average voter for each candidate, the interest they carry in
different political subjects, their geolocalization, and their language
habits. We have also presented results on the usage of automated accounts, or
the lack thereof, in each community.

Many future tasks are possible to be performed on this dataset. Based on the
community detection of political communities, a relevant study could be to
analyze of the impact of major political events or debates. Considering that
we have collected tweets from February to April on a daily basis, we could
quantify the shift in the communities after debates between two candidates or
how the start of the Ukraine war influenced electors. In the same way, we
could also investigate the shift between the two turn of votes. French
elections are based on a two-turn system, with the first turn aiming at
narrowing down the the list of candidates and only keeping the two largest
ones. The continued gathering of data and community detection could show us
which communities turn to which candidate during the period between the two
turns and how their language habits evolve.

## 8\. Bibliographical References

## References

  * Ali Alhosseini et al., 2019 Ali Alhosseini, S., Bin Tareaf, R., Najafi, P., and Meinel, C.  (2019).  Detect me if you can: Spam bot detection using inductive representation learning.  In Companion Proceedings of The 2019 World Wide Web Conference, WWW ’19, page 148–153, New York, NY, USA. Association for Computing Machinery.
  * Badawy et al., 2018 Badawy, A., Ferrara, E., and Lerman, K.  (2018).  Analyzing the digital traces of political manipulation: The 2016 russian interference twitter campaign.  In 2018 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM), pages 258–265. IEEE.
  * Bae et al., 2013 Bae, J.-h., Son, J.-e., and Song, M.  (2013).  Analysis of twitter for 2012 south korea presidential election by text mining techniques.  Journal of Intelligence and Information Systems, 19(3):141–156.
  * Bermingham and Smeaton, 2011 Bermingham, A. and Smeaton, A.  (2011).  On using twitter to monitor political sentiment and predict election results.  In Proceedings of the Workshop on Sentiment Analysis where AI meets Psychology (SAAIP 2011), pages 2–10.
  * Blondel et al., 2008 Blondel, V. D., Guillaume, J.-L., Lambiotte, R., and Lefebvre, E.  (2008).  Fast unfolding of communities in large networks.  Journal of Statistical Mechanics: Theory and Experiment, 2008(10):P10008, oct.
  * Broniatowski et al., 2018 Broniatowski, D. A., Jamison, A. M., Qi, S., AlKulaib, L., Chen, T., Benton, A., Quinn, S. C., and Dredze, M.  (2018).  Weaponized health communication: Twitter bots and russian trolls amplify the vaccine debate.  American Journal of Public Health, 108(10):1378–1384.  PMID: 30138075.
  * Choy et al., 2011 Choy, M., Cheong, M. L., Laik, M. N., and Shung, K. P.  (2011).  A sentiment analysis of singapore presidential election 2011 using twitter data with census correction.  arXiv preprint arXiv:1108.5520.
  * Cinelli et al., 2020 Cinelli, M., Cresci, S., Galeazzi, A., Quattrociocchi, W., and Tesconi, M.  (2020).  The limited reach of fake news on twitter during 2019 european elections.  PloS one, 15(6):e0234689.
  * Cresci et al., 2018 Cresci, S., Lillo, F., Regoli, D., Tardelli, S., and Tesconi, M.  (2018).  Cashtag piggybacking: uncovering spam and bot activity in stock microblogs on twitter.  CoRR, abs/1804.04406.
  * Davis et al., 2016 Davis, C. A., Varol, O., Ferrara, E., Flammini, A., and Menczer, F.  (2016).  Botornot: A system to evaluate social bots.  CoRR, abs/1602.00975.
  * Deb et al., 2019 Deb, A., Luceri, L., Badawy, A., and Ferrara, E.  (2019).  Perils and challenges of social media and election manipulation analysis: The 2018 US midterms.  CoRR, abs/1902.00043.
  * Diakopoulos and Shamma, 2010 Diakopoulos, N. A. and Shamma, D. A.  (2010).  Characterizing debate performance via aggregated twitter sentiment.  In Proceedings of the SIGCHI conference on human factors in computing systems, pages 1195–1198.
  * Echeverría et al., 2018 Echeverría, J., Cristofaro, E. D., Kourtellis, N., Leontiadis, I., Stringhini, G., and Zhou, S.  (2018).  LOBO - evaluation of generalization deficiencies in twitter bot classifiers.  CoRR, abs/1809.09684.
  * Feng et al., 2021 Feng, S., Wan, H., Wang, N., Li, J., and Luo, M.  (2021).  Twibot-20: A comprehensive twitter bot detection benchmark.  CoRR, abs/2106.13088.
  * Ferrara, 2017 Ferrara, E.  (2017).  Disinformation and social bot operations in the run up to the 2017 french presidential election.  CoRR, abs/1707.00086.
  * Gayo-Avello et al., 2011 Gayo-Avello, D., Metaxas, P., and Mustafaraj, E.  (2011).  Limits of electoral predictions using twitter.  In Proceedings of the International AAAI Conference on Web and Social Media, volume 5, pages 490–493.
  * Grimminger and Klinger, 2021 Grimminger, L. and Klinger, R.  (2021).  Hate towards the political opponent: A twitter corpus study of the 2020 us elections on the basis of offensive speech and stance detection.  In Proceedings of the Eleventh Workshop on Computational Approaches to Subjectivity, Sentiment and Social Media Analysis, pages 171–180.
  * Guo et al., 2021 Guo, Y., Rennard, V., Xypolopoulos, C., and Vazirgiannis, M.  (2021).  BERTweetFR : Domain adaptation of pre-trained language models for French tweets.  In Proceedings of the Seventh Workshop on Noisy User-generated Text (W-NUT 2021), pages 445–450, Online, November. Association for Computational Linguistics.
  * Kudugunta and Ferrara, 2018 Kudugunta, S. and Ferrara, E.  (2018).  Deep neural networks for bot detection.  CoRR, abs/1802.04289.
  * Lee et al., 2021 Lee, K., Eoff, B., and Caverlee, J.  (2021).  Seven months with the devils: A long-term study of content polluters on twitter.  Proceedings of the International AAAI Conference on Web and Social Media, 5(1):185–192, Aug.
  * Liu et al., 2019 Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L., and Stoyanov, V.  (2019).  Roberta: A robustly optimized bert pretraining approach.  arXiv preprint arXiv:1907.11692.
  * Martin et al., 2020 Martin, L., Muller, B., Ortiz Suárez, P. J., Dupont, Y., Romary, L., de la Clergerie, É., Seddah, D., and Sagot, B.  (2020).  CamemBERT: a tasty French language model.  In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 7203–7219, Online, July. Association for Computational Linguistics.
  * Mazza et al., 2019 Mazza, M., Cresci, S., Avvenuti, M., Quattrociocchi, W., and Tesconi, M.  (2019).  Rtbust: Exploiting temporal patterns for botnet detection on twitter.  CoRR, abs/1902.04506.
  * Memon and Carley, 2020 Memon, S. A. and Carley, K. M.  (2020).  Characterizing COVID-19 misinformation communities using a novel twitter dataset.  CoRR, abs/2008.00791.
  * Miller et al., 2014 Miller, Z., Dickinson, B., Deitrick, W., Hu, W., and Wang, A.  (2014).  Twitter spammer detection using data stream clustering.  Information Sciences, 260:64–73, 03.
  * Ousidhoum et al., 2019 Ousidhoum, N., Lin, Z., Zhang, H., Song, Y., and Yeung, D.-Y.  (2019).  Multilingual and multi-aspect hate speech analysis.  In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 4675–4684, Hong Kong, China, November. Association for Computational Linguistics.
  * Pastor-Galindo et al., 2020 Pastor-Galindo, J., Zago, M., Nespoli, P., Bernal, S. L., Celdrán, A. H., Pérez, M. G., Ruipérez-Valiente, J. A., Pérez, G. M., and Mármol, F. G.  (2020).  Spotting political social bots in twitter: A use case of the 2019 spanish general election.  IEEE Transactions on Network and Service Management, 17(4):2156–2170.
  * Petrova et al., 2021 Petrova, M., Sen, A., and Yildirim, P.  (2021).  Social media and political contributions: The impact of new technology on political competition.  Manag. Sci., 67:2997–3021.
  * Radicioni et al., 2021 Radicioni, T., Saracco, F., Pavan, E., and Squartini, T.  (2021).  Analysing twitter semantic networks: the case of 2018 italian elections.  Scientific Reports, 11(1):1–22.
  * Rill et al., 2014 Rill, S., Reinel, D., Scheidt, J., and Zicari, R. V.  (2014).  Politwi: Early detection of emerging political topics on twitter and the impact on concept-level sentiment analysis.  Knowledge-Based Systems, 69:24–33.
  * Risch et al., 2020 Risch, J., Ruff, R., and Krestel, R.  (2020).  Offensive language detection explained.  In Proceedings of the Second Workshop on Trolling, Aggression and Cyberbullying, pages 137–143, Marseille, France, May. European Language Resources Association (ELRA).
  * Seidman, 1983 Seidman, S.  (1983).  Network structure and minimum degree.soc netw 5:269-287.  Social Networks, 5:269–287, 09.
  * Shao et al., 2017 Shao, C., Ciampaglia, G. L., Varol, O., Flammini, A., and Menczer, F.  (2017).  The spread of fake news by social bots.  CoRR, abs/1707.07592.
  * Siegel et al., 2021 Siegel, A. A., Nikitin, E., Barberá, P., Sterling, J., Pullen, B., Bonneau, R., Nagler, J., Tucker, J. A., et al.  (2021).  Trumping hate on twitter? online hate speech in the 2016 us election campaign and its aftermath.  Quarterly Journal of Political Science, 16(1):71–104.
  * Subrahmanian et al., 2016 Subrahmanian, V. S., Azaria, A., Durst, S., Kagan, V., Galstyan, A., Lerman, K., Zhu, L., Ferrara, E., Flammini, A., Menczer, F., Waltzman, R., Stevens, A., Dekhtyar, A., Gao, S., Hogg, T., Kooti, F., Liu, Y., Varol, O., Shiralkar, P., Vydiswaran, V. G. V., Mei, Q., and Huang, T.  (2016).  The DARPA twitter bot challenge.  CoRR, abs/1601.05140.
  * Tumasjan et al., 2010 Tumasjan, A., Sprenger, T., Sandner, P., and Welpe, I.  (2010).  Predicting elections with twitter: What 140 characters reveal about political sentiment.  In Proceedings of the International AAAI Conference on Web and Social Media, volume 4, pages 178–185.
  * Utz, 2009 Utz, S.  (2009).  The (Potential) Benefits of Campaigning via Social Network Sites.  Journal of Computer-Mediated Communication, 14(2):221–243, 01.
  * Varol et al., 2017 Varol, O., Ferrara, E., Davis, C. A., Menczer, F., and Flammini, A.  (2017).  Online human-bot interactions: Detection, estimation, and characterization.  CoRR, abs/1703.03107.
  * Yang et al., 2019a Yang, K., Varol, O., Davis, C. A., Ferrara, E., Flammini, A., and Menczer, F.  (2019a).  Arming the public with AI to counter social bots.  CoRR, abs/1901.00912.
  * Yang et al., 2019b Yang, K., Varol, O., Hui, P., and Menczer, F.  (2019b).  Scalable and generalizable social bot detection through data selection.  CoRR, abs/1911.09179.
  * Yaqub et al., 2020 Yaqub, U., Sharma, N., Pabreja, R., Chun, S. A., Atluri, V., and Vaidya, J.  (2020).  Location-based sentiment analyses and visualization of twitter election data.  Digit. Gov.: Res. Pract., 1(2), apr.