# Versal deformations: a tool of linear algebra††thanks: Received by the
editors on Month/Day/Year. Accepted for publication on Month/Day/Year.
Handling Editor: Namie of Handling Editor. Corresponding Author: Andrii
Dmytryshyn

Andrii Dmytryshyn School of Science and Technology, Örebro University
(andrii.dmytryshyn@oru.se). The author is supported by the Swedish Research
Council (VR) grant 2021-05393.

###### Abstract

Versal deformation of a matrix $A$ is a normal form to which all matrices
$A+E$, close to $A$, can be reduced by similarity transformation smoothly
depending on the entries of $A+E$. In this paper we discuss versal
deformations and their use in codimension computations, in investigation of
closure relations of orbits and bundles, in studying changes of canonical
forms under perturbations, as well as in reduction of unstructured
perturbations to structured perturbations.

###### keywords:

Perturbation, Versal deformation, Jordan Canonical Form, Canonical form,
Similarity, Codimension

15A21, 15A63.

##  1 Introduction

To investigate and understand the properties of a matrix we may need to
transform this matrix to a simpler form, e.g., Jordan canonical form (JCF) or
Weyr canonical form. However, the reduction to these forms may be an unstable
operation, meaning that both the corresponding canonical form and the
reduction transformation can be highly sensitive to small changes in the
entries of a given matrix. In the following we recall JCF and illustrate its
sensitivity.

Let $A$ be an $n\times n$ matrix over the field of complex numbers, denoted by
$\mathbb{C}$, and $GL_{n}(\mathbb{C})$ be a group of $n\times n$ nonsingular
complex matrices. Recall that the similarity transformation is defined as
follows

$A\mapsto S^{-1}AS,\text{ where }S\in GL_{n}(\mathbb{C}).$

By similarity transformation any matrix can be reduced to its JCF, i.e., for a
matrix $A$ there exists a nonsingular matrix $S$, such that
$S^{-1}AS=J_{\text{can}}$, where

(1.1) $\displaystyle J_{\text{can}}$ $\displaystyle=J(\lambda_{1})\oplus
J(\lambda_{2})\oplus\dots\oplus J(\lambda_{n}),$ $\displaystyle
J(\lambda_{i})$
$\displaystyle=\bigoplus_{j=1}^{t_{i}}J_{k_{i,j}}(\lambda_{i}),\quad\lambda_{i}\neq\lambda_{j},\quad
k_{i,1}\geq k_{i,2}\geq\dots\geq k_{i,t_{i}},\text{ and }$ $\displaystyle
J_{k_{i,j}}(\lambda_{i})$ $\displaystyle=\begin{bmatrix}\lambda_{i}&1&&0\\\
&\lambda_{i}&\ddots&\\\ &&\ddots&1\\\ 0&&&\lambda_{i}\end{bmatrix},\ \
(\text{the size is }k_{i,j}\times k_{i,j}),$

for more details, see, e.g., [31]. The JCF of a matrix is well known classical
result that has been studied with various purposes. In examples 1.1 and 1.2,
we compute JCF of some matrices.

######  Example 1.1.

Consider the following perturbation of the diagonal matrix

$A(\varepsilon,\delta)=\begin{bmatrix}\lambda&0&0\\\ 0&\lambda&0\\\
0&0&\lambda\end{bmatrix}+\begin{bmatrix}0&\varepsilon&0\\\ 0&0&\delta\\\
0&0&0\end{bmatrix}.$

What is JCF of $A(\varepsilon,\delta)$? In the case of $\varepsilon\neq 0$ and
$\delta\neq 0$ (but possibly being very small), a simple computation gives us
the following JCF:

$\begin{bmatrix}1&0&0\\\ 0&\varepsilon^{-1}&0\\\
0&0&\varepsilon^{-1}\delta^{-1}\end{bmatrix}^{-1}\begin{bmatrix}\lambda&\varepsilon&0\\\
0&\lambda&\delta\\\ 0&0&\lambda\end{bmatrix}\begin{bmatrix}1&0&0\\\
0&\varepsilon^{-1}&0\\\
0&0&\varepsilon^{-1}\delta^{-1}\end{bmatrix}=\begin{bmatrix}\lambda&1&0\\\
0&\lambda&1\\\ 0&0&\lambda\end{bmatrix}=J_{3}(\lambda).$

While, in the case of $\varepsilon\neq 0$ and $\delta=0$, we obtain

$\begin{bmatrix}1&0&0\\\ 0&\varepsilon^{-1}&0\\\
0&0&1\end{bmatrix}^{-1}\begin{bmatrix}\lambda&\varepsilon&0\\\ 0&\lambda&0\\\
0&0&\lambda\end{bmatrix}\begin{bmatrix}1&0&0\\\ 0&\varepsilon^{-1}&0\\\
0&0&1\end{bmatrix}=\begin{bmatrix}\lambda&1&0\\\ 0&\lambda&0\\\
0&0&\lambda\end{bmatrix}=J_{2}(\lambda)\oplus J_{1}(\lambda).$

The above shows that the small change in one entry of the matrix, i.e.,
$\delta$ being arbitralily small but non zero versus $\delta=0$, causes a big
effect on the JCF ($J_{3}(\lambda)$ versus $J_{2}(\lambda)+J_{1}(\lambda)$).

######  Example 1.2.

Consider a perturbation of $J_{3}(0)$ and compute its JCF using a matrix
$S(\varepsilon)$:

$S(\varepsilon)^{-1}\begin{bmatrix}\lambda&1&0\\\ 0&\lambda&1\\\
\varepsilon&0&\lambda\end{bmatrix}S(\varepsilon)=\begin{cases}\begin{bmatrix}\lambda_{1}&0&0\\\
0&\lambda_{2}&0\\\ 0&0&\lambda_{3}\end{bmatrix},\quad\text{ if
}\varepsilon\neq 0,\\\ \begin{bmatrix}\lambda&1&0\\\ 0&\lambda&1\\\
0&0&\lambda\end{bmatrix},\quad\text{ if }\varepsilon=0.\end{cases}$

In this example the perturbation changes both the sizes of the Jordan blocks
and the values of the eigenvalues.

As can be seen from examples 1.1 and 1.2, reduction to JCF is an unstable
operation: the computed canonical form and the reduction transformation depend
discontinuously on the entries of an original matrix. To put it simply, small
changes in the entries of an original matrix can cause a big change in its JCF
and the transformation that reduces the matrix to this JCF. So reduction of a
matrix to its JCF is an ill-posed problem. As a consequence of the ill-
posedness of reduction to JCF, V.I. Arnold introduced a normal form, with the
minimal number of independent parameters, to which an arbitrary family of
matrices $\tilde{A}$ close to a given matrix $A$ can be reduced by similarity
transformations smoothly depending on the entries of $\tilde{A}$. He called
such a normal form a miniversal deformation of $A$ [1, 2, 3].

The rest of the paper is organized as follows. In Section 2 we recall the
necessary definitions. In Section 3, we explore the use of miniversal
deformations in codimension computations. The characterization of closure
relations for bundles of matrices and investigation of possible changes in the
JCF (eigenstructures) of matrices in response to small perturbations are
discussed in Section 4. Section 5 provides an algorithm for the reduction of
unstructured perturbations to structured perturbations for monic matrix
polynomials.

The main goal of this paper is to present, as simply as possible, various
known uses of miniversal deformations, but the paper also contains some new
developments. Namely, our proof of Theorem 4.1, about the characterization of
closure relations for bundles of matrices, has not appeared in the literature
before. Neither has Algorithms 1, but it solves a problem that is a partial
case of already solved problem, see Section 5 for more details. The advantage
of using Algorithms 1 (when possible) is that it deals with matrices (rather
than matrix pencils) and thus requires less memory and computations.

##  2 Versal deformations of JCF

In this section we present a formal definition of (mini)versal deformations
and a theorem that provides miniversal deformations of JCF. We also present
illustrative examples.

######  Definition 2.1.

A deformation of a matrix $A\in{\mathbb{C}}^{n\times n}$ is a holomorphic map
${\cal A}\colon\Lambda\to{\mathbb{C}}^{n\times n}$ in which
$\Lambda\subset\mathbb{C}^{k}$ is a neighborhood of $\vec{0}=(0,\dots,0)$ and
${\cal A}(\vec{0})=A$.

On the set of deformations we have an equivalence relation induced by
similarity, which is defined as follows.

######  Definition 2.2.

Deformations ${\cal A}(\vec{\varepsilon})$ and ${\cal B}(\vec{\varepsilon})$
of a matrix $A$ are called equivalent if the identity matrix $I_{n}$ possesses
a deformation ${\cal I}(\vec{\varepsilon})$ such that

$\begin{split}{\cal B}(\vec{\varepsilon})={\cal
I}(\vec{\varepsilon})^{-1}{\cal A}(\vec{\varepsilon}){\cal
I}(\vec{\varepsilon})\end{split}$

for all $\vec{\varepsilon}=(\varepsilon_{1},\dots,\varepsilon_{k})$ in some
neighborhood of $\vec{0}$.

Using the equivalence relation from Definition 2.2 we are able to find such a
deformation that any other deformation can be “induced” from it.

######  Definition 2.3.

A deformation ${\cal A}(\delta_{1},\dots,\delta_{k})$ of a matrix $A$ is
called versal if every deformation ${\cal B}(\vec{\varepsilon})={\cal
B}(\varepsilon_{1},\dots,\varepsilon_{l})$ of $A$ is equivalent to a
deformation of the form ${\cal
A}(\varphi_{1}(\vec{\varepsilon}),\dots,\varphi_{k}(\vec{\varepsilon})),$ in
which all $\varphi_{i}(\vec{\varepsilon})$ are power series that are
convergent in a neighborhood of $\vec{0}$ and $\varphi_{i}(\vec{0})=0$.

If a versal deformation ${\cal A}(\delta_{1},\dots,\delta_{k})$ of a matrix
$A$ has a minimal number of independent parameters, i.e., $k$ is minimal, then
it is called miniversal.

For constructing the miniversal deformations of JCF we need to define the
following $m\times n$ matrices

$0_{mn}^{\leftarrow}=\begin{bmatrix}\begin{matrix}*\\\ *\\\ \vdots\\\
*\end{matrix}&0_{m,n-1}\end{bmatrix}\quad\text{if $m\leq n$ \ \ and \ \
}0_{mn}^{\downarrow}=\begin{bmatrix}\\\\[2.84526pt] 0_{m-1,n}\\\\[2.84526pt]
*\ *\ \dots\ *\end{bmatrix}\quad\text{if $m\geq n$},$

where the stars denote all possibly non-zero entries. Further, we will usually
omit the indices $m$ and $n$. Consider a matrix in the Jordan canonical form
$J_{\text{can}}$, see (1.1), and define

(2.2) $\displaystyle J_{\text{can}}+D$
$\displaystyle=(J(\lambda_{1})+D_{1})\oplus(J(\lambda_{2})+D_{2})\oplus\dots\oplus(J(\lambda_{n})+D_{n}),\text{
where }$ $\displaystyle J(\lambda_{i})+D_{i}$
$\displaystyle=\begin{bmatrix}J_{k_{i,1}}(\lambda_{i})+0^{\downarrow}&0^{\downarrow}&0^{\downarrow}&\dots&0^{\downarrow}\\\
0^{\leftarrow}&J_{k_{i,2}}(\lambda_{i})+0^{\downarrow}&0^{\downarrow}&\dots&0^{\downarrow}\\\
0^{\leftarrow}&0^{\leftarrow}&J_{k_{i,3}}(\lambda_{i})+0^{\downarrow}&\dots&0^{\downarrow}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
0^{\leftarrow}&0^{\leftarrow}&0^{\leftarrow}&\dots&J_{k_{i,t_{i}}}(\lambda_{i})+0^{\downarrow}\\\
\end{bmatrix}.$

Theorem 2.4 below shows that miniversal deformation of a matrix in JCF can be
taken in the shape defined in (2.2).

######  Theorem 2.4 ([1, 29, 33]).

Let $J_{\text{can}}$ be a matrix in Jordan canonical form. All matrices
$J_{\text{can}}+E$ that are sufficiently close to $J_{\text{can}}$ can be
reduced by transformations

$J_{\text{can}}+E\mapsto{S}(E)^{-1}(J_{\text{can}}+E){S}(E),\quad\begin{matrix}\text{${S}(E)$
is analytic at 0}\\\ \text{and ${S}(0)=I$,}\end{matrix}$

to the form $J_{\text{can}}+D(E)$, defined in (2.2), the non-zero entries of
$D(E)$ (i.e., entries at the positions of the stars $*$) depend
holomorphically on the entries of $E$.

To illustrate the result of Theorem 2.4 we consider the following three
examples.

######  Example 2.5.

Theorem 2.4 tells us that the perturbed matrix

$\displaystyle J_{\text{can}}+E=J_{3}(\lambda)\oplus J_{2}(\lambda)\oplus
J_{1}(\lambda)\oplus J_{2}(\mu)+E$
$\displaystyle=\left(\begin{array}[]{c|c|c|c}\begin{matrix}\lambda&1&0\\\
0&\lambda&1\\\ 0&0&\lambda\end{matrix}&&&\\\
\hline\cr&\begin{matrix}\lambda&1\\\ 0&\lambda\end{matrix}&&\\\
\hline\cr&&\begin{matrix}\lambda\end{matrix}&\\\
\hline\cr&&&\begin{matrix}\mu&1\\\
0&\mu\end{matrix}\end{array}\right)+\left(\begin{array}[]{ccc|cc|c|cc}\varepsilon_{11}&\varepsilon_{12}&\varepsilon_{13}&\varepsilon_{14}&\varepsilon_{15}&\varepsilon_{16}&\varepsilon_{17}&\varepsilon_{18}\\\
\varepsilon_{21}&\varepsilon_{22}&\varepsilon_{23}&\varepsilon_{24}&\varepsilon_{25}&\varepsilon_{26}&\varepsilon_{27}&\varepsilon_{28}\\\
\varepsilon_{31}&\varepsilon_{32}&\varepsilon_{33}&\varepsilon_{34}&\varepsilon_{35}&\varepsilon_{36}&\varepsilon_{37}&\varepsilon_{38}\\\
\hline\cr\varepsilon_{41}&\varepsilon_{42}&\varepsilon_{43}&\varepsilon_{44}&\varepsilon_{45}&\varepsilon_{46}&\varepsilon_{47}&\varepsilon_{48}\\\
\varepsilon_{51}&\varepsilon_{52}&\varepsilon_{53}&\varepsilon_{54}&\varepsilon_{55}&\varepsilon_{56}&\varepsilon_{57}&\varepsilon_{58}\\\
\hline\cr\varepsilon_{61}&\varepsilon_{62}&\varepsilon_{63}&\varepsilon_{64}&\varepsilon_{65}&\varepsilon_{66}&\varepsilon_{67}&\varepsilon_{68}\\\
\hline\cr\varepsilon_{71}&\varepsilon_{72}&\varepsilon_{73}&\varepsilon_{74}&\varepsilon_{75}&\varepsilon_{76}&\varepsilon_{77}&\varepsilon_{78}\\\
\varepsilon_{81}&\varepsilon_{82}&\varepsilon_{83}&\varepsilon_{84}&\varepsilon_{85}&\varepsilon_{86}&\varepsilon_{87}&\varepsilon_{88}\\\
\end{array}\right)$

can be reduced, by transformation
$J_{\text{can}}+E\mapsto{S}(E)^{-1}(J_{\text{can}}+E){S}(E),$ to the form

$\displaystyle J_{\text{can}}+D(E)=J_{3}(\lambda)\oplus J_{2}(\lambda)\oplus
J_{1}(\lambda)\oplus J_{2}(\mu)+D(E)$
$\displaystyle=\left(\begin{array}[]{c|c|c|c}\begin{matrix}\lambda&1&0\\\
0&\lambda&1\\\ 0&0&\lambda\end{matrix}&&&\\\
\hline\cr&\begin{matrix}\lambda&1\\\ 0&\lambda\end{matrix}&&\\\
\hline\cr&&\begin{matrix}\lambda\end{matrix}&\\\
\hline\cr&&&\begin{matrix}\mu&1\\\
0&\mu\end{matrix}\end{array}\right)+\left(\begin{array}[]{c|c|c|c}\begin{matrix}0&0&0\\\
0&0&0\\\ \delta_{1}&\delta_{2}&\delta_{3}\end{matrix}&\begin{matrix}0&0\\\
0&0\\\ \delta_{4}&\delta_{5}\end{matrix}&\begin{matrix}0\\\ 0\\\
\delta_{6}\end{matrix}&\\\
\hline\cr\begin{matrix}\delta_{7}&0_{\phantom{1}}&0\\\
\delta_{8}&0_{\phantom{1}}&0\\\ \end{matrix}&\begin{matrix}0&0\\\
\delta_{10}&\delta_{11}\end{matrix}&\begin{matrix}0\\\
\delta_{12}\end{matrix}&\\\
\hline\cr\begin{matrix}\delta_{9}&0_{\phantom{1}}&0\\\
\end{matrix}&\begin{matrix}\delta_{13\phantom{1}}&0\\\
\end{matrix}&\begin{matrix}\delta_{14}\end{matrix}&\\\
\hline\cr\begin{matrix}&&&&\\\ &&&&\\\ \end{matrix}&\begin{matrix}&\\\
&\end{matrix}&\begin{matrix}\\\ \end{matrix}&\begin{matrix}0&0\\\
\delta_{15}&\delta_{16}\end{matrix}\\\ \end{array}\right)$

and $\delta_{i}=\varphi_{i}(\vec{\varepsilon})$.

In Example 2.6 we consider the case of a perturbed $2\times 2$ Jordan block.
We present explicitly the functions
$\delta_{i}=\varphi_{i}(\vec{\varepsilon})$ in the miniversal deformation of
the block and the transformation $S(E)$.

######  Example 2.6 (Reduction to a miniversal deformation for $2\times 2$
Jordan block).

We present a reduction of a perturbed $2\times 2$ Jordan block $J_{2}(0)+E$ to
its miniversal deformation $J_{2}(0)+D(E)$. Define:

$J_{2}(0)+E=\left[\begin{matrix}0&1\\\ 0&0\\\
\end{matrix}\right]+\left[\begin{matrix}\varepsilon_{11}&\varepsilon_{12}\\\
\varepsilon_{21}&\varepsilon_{22}\\\ \end{matrix}\right]\quad\text{and}\quad
S(E)=\left[\begin{matrix}1&0\\\
\frac{-\varepsilon_{11}}{1+\varepsilon_{12}}&\frac{1}{1+\varepsilon_{12}}\\\
\end{matrix}\right].$

Then

$\displaystyle J_{2}(0)+D(E)=$ $\displaystyle
S(E)^{-1}(J_{2}(0)+E)S(E)=\left[\begin{matrix}1&0\\\
\varepsilon_{11}&1+\varepsilon_{12}\\\
\end{matrix}\right]\left[\begin{matrix}\varepsilon_{11}&1+\varepsilon_{12}\\\
\varepsilon_{21}&\varepsilon_{22}\\\
\end{matrix}\right]\left[\begin{matrix}1&0\\\
\frac{-\varepsilon_{11}}{1+\varepsilon_{12}}&\frac{1}{1+\varepsilon_{12}}\\\
\end{matrix}\right]$ $\displaystyle=\left[\begin{matrix}0&1\\\
\varepsilon_{21}(1+\varepsilon_{12})-\varepsilon_{11}\varepsilon_{22}&\varepsilon_{11}+\varepsilon_{22}\\\
\end{matrix}\right]=\left[\begin{matrix}0&1\\\ -{\rm det}(J_{2}(0)+E)&{\rm
trace}(J_{2}(0)+E)\\\ \end{matrix}\right].$

In terms of Definition 2.3 we have

$\displaystyle{\cal A}(\delta_{1},\delta_{2})={\cal
A}(\varphi_{1}(\vec{\varepsilon}),$
$\displaystyle\varphi_{2}(\vec{\varepsilon}))=\left[\begin{matrix}0&1\\\
\varphi_{1}(\vec{\varepsilon})&\varphi_{2}(\vec{\varepsilon})\\\
\end{matrix}\right]=\left[\begin{matrix}0&1\\\
\varepsilon_{21}(1+\varepsilon_{12})-\varepsilon_{11}\varepsilon_{22}&\varepsilon_{11}+\varepsilon_{22}\\\
\end{matrix}\right],$

i.e.,
$\delta_{1}=\varphi_{1}(\vec{\varepsilon})=\varepsilon_{21}(1+\varepsilon_{12})-\varepsilon_{11}\varepsilon_{22}$
and
$\delta_{2}=\varphi_{2}(\vec{\varepsilon})=\varepsilon_{11}+\varepsilon_{22}$.

It is possible to directly generalize Example 2.6 to a single Jordan block of
any size, since we can easily see what elementary operations with rows and
columns of the matrix are needed to eliminate the unwanted entries. Such a
reduction can also be done in Matlab using symbolic computations, see Example
2.7. For the general case (many Jordan blocks), we refer to [33, pp. 5–7].

######  Example 2.7 (Reduction to a miniversal deformations for $3\times 3$
Jordan block).

In this example we present Matlab code that performs a reduction of a
perturbed $3\times 3$ Jordan block to its miniversal deformation.

⬇

1% Creating a fully perturbed 3x3 Jordan block

2

3syms E [3 3];

4J3 = [0 1 0; 0 0 1; 0 0 0];

5

6AE = J3 + E

7

8% Setting the first row to [0 1 0]

9

10S1 = [1 0 0;

11 -AE(1,1)/AE(1,2) 1/AE(1,2) -AE(1,3)/AE(1,2);

12 0 0 1];

13

14A1=inv(S1)*(AE)*S1;

15

16% Setting the second row to [0 0 1]

17

18S2 = [1 0 0;

19 0 1 0;

20 -A1(2,1)/A1(2,3) -A1(2,2)/A1(2,3) 1/A1(2,3)];

21

22A2 = inv(S2)*(A1)*S2;

23

24% Simplyfying the expressions in the third row

25

26AD = simplify(A2)

Figure 1: Matlab code for reduction to miniversal deformation of perturbed
$J_{3}(0)$.

Running the code in Figure 1 results in the output presented in Figure 2.

⬇

1AE =

2[e1_1, e1_2 + 1, e1_3]

3[e2_1, e2_2, e2_3 + 1]

4[e3_1, e3_2, e3_3]

5

6AD =

7[ 0, 1, 0]

8[ 0, 0, 1]

9[e3_1 - e1_1*e3_2 + e1_2*e3_1 - e2_1*e3_3 + e2_3*e3_1 + e1_1*e2_2*e3_3 -
e1_1*e2_3*e3_2 - e1_2*e2_1*e3_3 + e1_2*e2_3*e3_1 + e1_3*e2_1*e3_2 -
e1_3*e2_2*e3_1, e2_1 + e3_2 - e1_1*e2_2 + e1_2*e2_1 - e1_1*e3_3 + e1_3*e3_1 -
e2_2*e3_3 + e2_3*e3_2, e1_1 + e2_2 + e3_3]

Figure 2: Perturbed $J_{3}(0)$ (denoted AE) and its miniversal deformation
(denoted AD). The expressions in the last row of AD are the coefficients, with
the opposite signs, of the characteristic polynomial of AE.

Beside the miniversal deformations, examples 2.6 and 2.7, as well as the
reduction process in [33], give us an idea of how to construct the
transformation matrix, see also algorithms in [15, 16, 37, 38] and Section 5.

As one may notice, looking at the definition of versality (see also the
characterization in Lemma 3.1, presented in Section 3), versal or even
miniversal deformation of a matrix is not unique. For example, the perturbed
matrix $J_{\text{can}}+E$ from Example 2.5 can also be reduced by similarity
transformation to $J_{\text{can}}+\widetilde{D}(E)$, where

$\displaystyle J_{3}(\lambda)\oplus J_{2}(\lambda)\oplus J_{1}(\lambda)\oplus
J_{2}(\mu)+\widetilde{D}(E)$
$\displaystyle=\left(\begin{array}[]{c|c|c|c}\begin{matrix}\lambda&1&0\\\
0&\lambda&1\\\ 0&0&\lambda\end{matrix}&&&\\\
\hline\cr&\begin{matrix}\lambda&1\\\ 0&\lambda\end{matrix}&&\\\
\hline\cr&&\begin{matrix}\lambda\end{matrix}&\\\
\hline\cr&&&\begin{matrix}\mu&1\\\
0&\mu\end{matrix}\end{array}\right)+\left(\begin{array}[]{c|c|c|c}\begin{matrix}\delta_{3}&0&0\\\
\delta_{2}&\delta_{3}&0\\\
\delta_{1}&\delta_{2}&\delta_{3}\end{matrix}&\begin{matrix}0&0\\\
\delta_{5}&0\\\ \delta_{4}&\delta_{5}\end{matrix}&\begin{matrix}0\\\ 0\\\
\delta_{6}\end{matrix}&\\\
\hline\cr\begin{matrix}\delta_{7}&0_{\phantom{1}}&0\\\
\delta_{8}&\delta_{7}&0\\\ \end{matrix}&\begin{matrix}\delta_{11}&0\\\
\delta_{10}&\delta_{11}\end{matrix}&\begin{matrix}0\\\
\delta_{12}\end{matrix}&\\\
\hline\cr\begin{matrix}\delta_{9}&0_{\phantom{1}}&0\\\
\end{matrix}&\begin{matrix}\delta_{13\phantom{1}}&0\\\
\end{matrix}&\begin{matrix}\delta_{14}\end{matrix}&\\\
\hline\cr\begin{matrix}&&&&\\\ &&&&\\\ \end{matrix}&\begin{matrix}&\\\
&\end{matrix}&\begin{matrix}\\\ \end{matrix}&\begin{matrix}\delta_{16}&0\\\
\delta_{15}&\delta_{16}\end{matrix}\\\ \end{array}\right)$

and $\delta_{i}=\varphi_{i}(\vec{\varepsilon})$. Note, that the number of
different functions $\delta_{i}$ in $\widetilde{D}(E)$ is the same as in
$D(E)$ ($D(E)$ is given in Example 2.5) but $\widetilde{D}(E)$ has fewer non-
zero entries, see more on the miniversal deformations of the shape
$\widetilde{D}(E)$ in [1, 24].

This paper focuses on versal deformations of JCF of complex matrices.
Nevertheless, we also name other known results concerning miniversal
deformations and their applications for matrices and matrix pencils in the
remarks throughout the paper.

######  Remark 2.8 (Known deformations for matrices and matrix pencils).

The notion of miniversal deformations has been extended to

  * •

matrices under similarity over various fields, see [4, 28, 29];

  * •

matrices of bilinear forms ($A\mapsto S^{T}AS,\text{ det }S\neq 0$), see [15];

  * •

matrices of sesquilinear forms ($A\mapsto S^{H}AS,\text{ det }S\neq 0$), see
[16];

  * •

general matrix pencils under strict equivalence ($A-\lambda B\mapsto
RAS-\lambda RBS,\text{ det }S\neq 0,\text{ det }R\neq 0$), see [24, 29, 32];

  * •

general matrix pencils under contragredient equivalence ($A-\lambda B\mapsto
R^{-1}AS-\lambda S^{-1}BR,\text{ det }S\neq 0,\text{ det }R\neq 0$), see [29];

  * •

structured matrix pencils under congruence ($A-\lambda B\mapsto
S^{T}(A-\lambda B)S,\text{ det }S\neq 0,A^{T}=\pm A,B^{T}=\pm B$), see [9, 11,
15, 16].

We also refer the reader to the introductions of [15, 16] for more
information.

In the rest of the paper we discuss the use of miniverasal deformations for
solving various problems, namely: codimension computations, characterization
of closure relations for orbits and bundles, and reduction of the unstructured
perturbations to structured perturbations.

##  3 Codimension computation via miniversal deformations

The set of matrices similar to an $n\times n$ matrix $A$ forms a manifold in
the complex $n^{2}$ dimensional space. This manifold is the orbit of $A$ under
the action of similarity:

$\displaystyle{\cal O}(A)=\\{C^{-1}AC:C\in GL_{n}(\mathbb{C})\\}.$

The vector space

$\displaystyle T(A):=\\{XA-AX:X\in{\mathbb{C}}^{n\times n}\\}$

is the tangent space to the similarity orbit of $A$ at the point $A$ since

$(I-\varepsilon X)^{-1}A(I-\varepsilon X)=(I+\varepsilon
X+\varepsilon^{2}X^{2}+\varepsilon^{3}X^{3}+\dots)A(I-\varepsilon X)\\\ =\ A\
+\ \underbrace{\varepsilon(XA-AX)}_{\text{order 1 in $\varepsilon$}}\ +\
\underbrace{\varepsilon^{2}X(I-\varepsilon X)^{-1}(XA-AX)}_{\text{order 2 in
$\varepsilon$}}\,$

for all $n$-by-$n$ matrices $X$ and each $\varepsilon\in\mathbb{C}$. Lemma 3.1
shows that the tangent space plays an important role in the characterization
of versal deformations.

######  Lemma 3.1 (Section 2.3 in [1]).

Let $A$ and $E$ be $n\times n$ matrices. Then

$A+{D}(E)\text{ is versal if and only if }\ {\mathbb{C}}^{\,n\times
n}=T(A)+{D}({\mathbb{C}}),$

where $T(A)$ is the tangent space to ${\cal O}(A)$, at the point $A$ and
${D}({\mathbb{C}})$ is a space of matrices of the form ${D}(E)$, where the
functions $\varphi_{i}(\vec{\varepsilon})$ are replaced by complex numbers.

The dimension of the orbit of $A$ is the dimension of its tangent space at the
point $A$. The codimension of the orbit $A$ is the dimension of the normal
space of its orbit at the point $A$ which is equal to $n^{2}$ minus the
dimension of the orbit. Lemma 3.1 implies that the codimension of the orbit of
$A$ is equal to the minimal possible dimension of the space ${\cal
D}(\mathbb{C})$ and the latter is also equal to the minimal number of
independent parameters in the matrices from ${\cal D}(\mathbb{C})$. Therefore
miniversal deformations automatically provide us the codimensions of orbits.
Summing up,

$\begin{split}\operatorname{codim}(&\mathcal{O}(A))=\text{ \\# \\{functions
$\varphi_{i}(\vec{\varepsilon})$ in the miniversal deformation of
$A$\\},}\end{split}$

where $\\#\Omega$ is the number of elements in the set $\Omega$. Note that the
codimension of the orbit of $A$ is also equal to the number of linearly
independent solutions of the matrix equation $XA-AX=0$, for more details, see
e.g., [8].

A bundle $\mathcal{B}(A)$ is a union of matrix orbits with the same Jordan
structures except that the distinct eigenvalues may be different. Bundles
appear naturally in various applications and have been studied extensively,
see, e.g., [7, 14, 25]. Since the eigenvalues in bundles may vary, they become
additional parameters resulting in the following codimension formula:

(3.3)
$\begin{split}\operatorname{codim}(\mathcal{B}&(A))=\operatorname{codim}(\mathcal{O}(A))-\\#\text{
\\{different eigenvalues of $A$\\} }\\\ &=\text{\\# \\{functions
$\varphi_{i}(\vec{\varepsilon})$ in the miniversal deformation of $A$\\}}\\\
&-\text{\\# \\{different eigenvalues of $A$\\}}.\end{split}$

From (3.3) we can conclude that the blocks corresponding to eigenvalues of
algebraic multiplicity one, contribute nothing to the codimension of the
corresponding bundle. Example 3.2 illustrates this and shows how easy it can
be to compute the codimensions via miniversal deformations.

######  Example 3.2.

Let $A_{q}$ be a matrix in JCF that has one $J_{3}(\lambda_{1})$ block and
$q-1$ $J_{1}(\lambda_{k}),k=2,\dots,q$ blocks. Miniversal defrmation of
$A_{q}$ is

$A_{q}+D_{q}=\left[\begin{array}[]{c}\begin{matrix}\lambda_{1}&1&0\\\
0&\lambda_{1}&1\\\
\delta_{1}&\delta_{2}&\lambda_{1}+\delta_{3}\end{matrix}\end{array}\right]\oplus[\lambda_{2}+\delta_{4}]\oplus\cdots\oplus[\lambda_{q}+\delta_{q+2}].$

By counting the number of $\delta_{i}$ in $A_{q}+D_{q}$ (it is equal to
${q+2}$) and subtracting from it the number of different eigenvalues that
$A_{q}+D_{q}$ has (it is equal to $q$), we obtain that
$\operatorname{codim}(\mathcal{B}(A_{q}))=2$ for any value of $q$. Note that
the dimensions of bundles $\mathcal{B}(A_{q})$ are different for different
$q$.

It is possible to compute the codimension of the similarity orbit of a matrix
using the Matrix Canonical Structure Toolbox for Matlab (MCS Toolbox) [17].
The toolbox was created to simplify working with canonical forms and it can
compute codimensions for various cases, see Remark 3.3 for more details.

######  Remark 3.3 (MCS Toolbox).

MCS Toolbox’s functionality includes computation of the codimensions of orbits
and bundles for

  * •

matrices under congruence, and *congruence, for the theoretical results, see,
e.g., [5, 6, 15, 16];

  * •

matrix pencils under strict equivalence [8];

  * •

controllability and observability matrix pairs [26];

  * •

symmetric matrix pencils under congruence [11, 22];

  * •

skew-symmetric matrix pencils under congruence [10, 21].

Summary of codimension computations. The number of functions
$\varphi_{i}(\vec{\varepsilon})$ in a miniversal deformation of a matrix is
equal to the codimension of the similarity orbit of this matrix. Therefore
computing a miniversal deformation automatically provides us with the
codimension.

##  4 Closure relation of orbits and bundles

The problem of changes of JCF under arbitrarily small perturbations is
equivalent to the problem of describing what similarity orbits are in the
closure of a given similarity orbit. More precisely,
$\mathcal{O}(A)\subset\overline{\mathcal{O}(B)}$ is equivalent to the fact
that for every positive $\varepsilon>0$ there is a perturbation $E,\
\|E\|_{F}<\varepsilon,$ and a nonsingular matrix $S$ such that
$S^{-1}(A+E)S=B$. Recall that $\|\cdot\|_{F}$ denotes the Frobenius norm of a
matrix. If we allow the values of the distinct eigenvalues of $A+E$ to vary,
i.e., $S^{-1}(A+E)S=B_{E}$ and $B_{E}\in\mathcal{B}(B)$, then the problem of
changes of JCF (up to the values of the distinct eigenvalues) of $A+E$ is
equivalent to deciding whether the bundle $\mathcal{B}(A)$ is in
$\overline{\mathcal{B}(B)}$. Notice that we perturb only a single matrix $A$
but make a conclusion about the whole $\mathcal{O}(A)$ or $\mathcal{B}(A)$
belonging to $\overline{\mathcal{O}(B)}$ or $\overline{\mathcal{B}(B)}$,
respectively. For the orbits this conclusion is indeed straightforward but for
the bundles it requires some explanations. In [7] Dopico and De Terán
considered such a question about closure relations for bundles of matrix
pencils. Moreover, their arguments may be applied to the case of closure
relations for bundles of matrices, see [7, Section 4.1]. In Theorem 4.1 we
provide a new proof of the latter case using miniversal deformations.

######  Theorem 4.1.

Let $A\in\operatorname{\cal B}(B)$ and $B\in\overline{\operatorname{\cal
B}(C)}$ then $A\in\overline{\operatorname{\cal B}(C)}$.

######  Proof 4.2.

Without a loss of generality we may assume that $B$ is in its JCF:

(4.4) $B=J(\lambda_{1})\oplus J(\lambda_{2})\oplus\dots\oplus J(\lambda_{n}),\
\text{ where }\
J(\lambda_{i})=\bigoplus_{j}J_{k_{i,j}}(\lambda_{i}),\quad\lambda_{i}\neq\lambda_{j}.$

For $A$ there is a non-singular matrix $P$ such that

(4.5) $P^{-1}AP=J(\mu_{1})\oplus J(\mu_{2})\oplus\dots\oplus J(\mu_{n}),\
\text{ where }\
J(\mu_{i})=\bigoplus_{j}J_{k_{i,j}}(\mu_{i}),\quad\mu_{i}\neq\mu_{j}.$

We emphasize, that the values $n$ and $k_{i,j}$ for all $i,j$ in (4.4) and
(4.5) are the same, since $A\in\operatorname{\cal B}(B)$ (i.e., $A$ and $B$
have the same JCF up to the values of eigenvalues).

Since $B\in\overline{\operatorname{\cal B}(C)}$ then there is a perturbation
$D$ of $B$, such that $B+D\in\operatorname{\cal B}(C)$ and $D$ is in the shape
of miniversal deformation (2.2), i.e.,

$B+D=(J(\lambda_{1})+D_{1})\oplus(J(\lambda_{2})+D_{2})\oplus\dots\oplus(J(\lambda_{n})+D_{n}).$

The JCF of $B+D$ is a direct sum of the JCF of direct summands
$J(\lambda_{i})+D_{i}$. Therefore let $S=\oplus_{i=1}^{n}S_{i}$ be a non-
singular matrix that reduces $B+D$ to its JCF, i.e.,

(4.6) $\displaystyle S^{-1}(B+D)S$
$\displaystyle=S^{-1}\big{(}(J(\lambda_{1})+D_{1})\oplus(J(\lambda_{2})+D_{2})\oplus\dots\oplus(J(\lambda_{n})+D_{n})\big{)}S$
$\displaystyle=\bigoplus_{i=1}^{n}S^{-1}_{i}(J(\lambda_{i})+D_{i})S_{i}=\bigoplus_{i=1}^{n}\big{(}S^{-1}_{i}(J(0)+D_{i})S_{i}+\lambda_{i}I\big{)}.$

Now consider the perturbation $D$ of $P^{-1}AP$ and apply the similarity
transformation with the matrix $S$ to it:

(4.7) $\displaystyle S^{-1}(P^{-1}AP+D)S$
$\displaystyle=\bigoplus_{i=1}^{n}S^{-1}_{i}(J(\mu_{i})+D_{i})S_{i}=\bigoplus_{i=1}^{n}\big{(}S^{-1}_{i}(J(0)+D_{i})S_{i}+\mu_{i}I\big{)}.$

Note that since $D$ can be chosen with arbitrarily small entries, we can
assume that the direct summands $S^{-1}_{i}(J(0)+D_{i})S_{i}+\lambda_{i}I$ and
$S^{-1}_{j}(J(0)+D_{j})S_{j}+\lambda_{j}I$ have no eigenvalues in common for
$i\neq j$ as well as that the direct summands
$S^{-1}_{i}(J(0)+D_{i})S_{i}+\mu_{i}I$ and
$S^{-1}_{j}(J(0)+D_{j})S_{j}+\mu_{j}I$ have no eigenvalues in common for
$i\neq j$. Therefore, (4.6) and (4.7) show the JCFs of $B+D$ and $P^{-1}AP+D$
only differ in the values of eigenvalues (the eigenvalues of each
$S^{-1}_{i}(J(0)+D_{i})S_{i}$ are shifted with $\lambda_{i}$ and $\mu_{i}$,
respectively). Thus $P^{-1}AP+D\in\operatorname{\cal B}(C)$ and, since $D$ is
arbitrarily small, we have $P^{-1}AP\in\overline{\operatorname{\cal B}(C)}$.
Therefore $A\in\overline{\operatorname{\cal B}(C)}$.

For the necessary and sufficient conditions for a matrix $A$ (or, by Theorem
4.1, a bundle $\mathcal{B}(A)$) being in the closure of another bundle, see,
e.g., [24, 34, 35]. The closure hierarchies of bundles (and also orbits) can
be represented as graphs, so called stratification graphs [10, 18, 19, 20,
25]. Construction of such graphs is a way to study qualitatively how small
perturbations can change the JCF of a matrix and find out what JCF matrices
may have in an arbitrarily small neighbourhood of a given matrix. Miniversal
deformations may simplify construction of such graphs since they allow us to
take into account all possible perturbations of a matrix while working with
the matrix, where only a few entries are perturbed, see Example 4.3. Note also
that codimensions (discussed in Section 3) play an important role in
investigation of closure relation for orbits and bundles due to the fact that
a given orbit (or bundle) has only orbits (or bundles) with higher
codimensions in its closure. Thus codimension count provides us with a
necessary but not sufficient condition for one orbit (or bundle) being in the
closure of another orbit (or bundle).

######  Example 4.3.

To investigate what JCFs matrices in an arbitrarily small neighbourhood of a
matrix $J_{3}(\lambda)\oplus J_{2}(\lambda)$ may have, i.e., what JCFs
$J_{3}(\lambda)\oplus J_{2}(\lambda)+E$ (25 parameters, that are the entries
of $E$) may have, it is enough to investigate what JCFs $J_{3}(\lambda)\oplus
J_{2}(\lambda)+D(E)$ (9 parameters, see the matrix to the left in Figure 3)
may have. For example, matrices with the JCFs
$J_{5}(\lambda),J_{4}(\lambda)\oplus J_{1}(\lambda),$ and
$J_{1}(\lambda_{1})\oplus J_{1}(\lambda_{2})\oplus J_{1}(\lambda_{3})\oplus
J_{2}(\lambda)$ are in an arbitrarily small neighbourhood of a matrix
$J_{3}(\lambda)\oplus J_{2}(\lambda)$, see Figure 3.

$\left[\begin{array}[]{c|c}\begin{matrix}\lambda&1&\\\ &\lambda&1\\\
\delta_{1}&\delta_{2}&\lambda+\delta_{3}\end{matrix}&\begin{matrix}&\\\ &\\\
\delta_{4}&&\delta_{5}\end{matrix}\\\
\hline\cr\begin{matrix}\delta_{6}&&&&&&\\\ \delta_{7}&&&&&&\\\
\end{matrix}&\begin{matrix}\lambda&1\\\
\delta_{8}&\lambda+\delta_{9}\end{matrix}\end{array}\right]\ \ \sim\ \
\begin{cases}\left[\begin{array}[]{c}\begin{matrix}\lambda&1&&&\\\
&\lambda&1&&\\\ &&\lambda&1&\\\ &&&\lambda&1\\\ &&&&\lambda\\\
\end{matrix}\end{array}\right]\quad&\text{if only }\delta_{4}\neq 0,\\\
\left[\begin{array}[]{c|c}\begin{matrix}\lambda&1&&\\\ &\lambda&1&\\\
&&\lambda&1\\\ &&&\lambda\\\ \end{matrix}&\\\
\hline\cr&\lambda\end{array}\right]\quad&\text{if only }\delta_{5}\neq 0,\\\
\left[\begin{array}[]{c|c}\begin{matrix}\lambda_{1}&&\\\ &\lambda_{2}&\\\
&&\lambda_{3}\end{matrix}&\\\ \hline\cr&\begin{matrix}\lambda&1\\\
&\lambda\end{matrix}\end{array}\right]\quad&\text{if only }\delta_{1}\neq
0.\\\ \end{cases}$ Figure 3: We state what
$\vec{\delta}=(\delta_{1},\dots,\delta_{9})$ can be chosen to show that
$J_{5}(\lambda),J_{4}(\lambda)\oplus J_{1}(\lambda),$ and
$J_{1}(\lambda_{1})\oplus J_{1}(\lambda_{2})\oplus J_{1}(\lambda_{3})\oplus
J_{2}(\lambda)$ are in an arbitrarily small neighbourhood of a matrix
$J_{3}(\lambda)\oplus J_{2}(\lambda)$. ($A\sim B$ means that
$S^{-1}A(\vec{\delta})S=B$ for some $\vec{\delta}$ and nonsingular $S$.)

In Remark 4.4 we provide a few examples of how various miniversal deformations
were used for showing which canonical forms matrices and matrix pencils, have
or can not have in an arbitrarily small neighbourhood of a given matrix or
matrix pencil.

######  Remark 4.4 (Changes of canonical forms under perturbations).

Miniversal deformations can be used for studying changes of other (than JCF)
canonical forms under arbitrarily small perturbations. Here we list a few
examples of such usage:

  * •

In [9, Example 2.1], miniversal deformations of skew-symmetric matrix pencils
are used to show that in an arbitrarily small neighbourhood of a matrix pencil
with the canonical form ${\cal L}_{1}\oplus{\cal L}_{0}$ there is always a
matrix pencil with the canonical form ${\cal H}_{2}(\lambda),\lambda\neq 0$,
for the definitions of canonical blocks ${\cal L}_{k}$ and ${\cal
H}_{n}(\lambda)$ and more details, see [9].

  * •

In [14, Theorem 2.3] miniversal deformations of matrices of bilinear form are
used to show that there is a small neighbourhood of a matrix with the
canonical form $\begin{bmatrix}0&1&0\\\ -1&0&0\\\ 0&0&0\end{bmatrix}$ that
does not contain a matrix with the canonical form $\begin{bmatrix}0&1&0\\\
\lambda&0&0\\\ 0&0&0\end{bmatrix}$.

  * •

In [27] miniversal deformations of matrix pencils are used to calculate the
Kronecker canonical form of pencils that are close to any given matrix pencil,
i.e., the authors develop a qualitative perturbation theory of matrix pencils
through miniversal deformations.

Summary of closure relations of orbits and bundles. Miniversal deformations
can be used for studying when a closure of an orbit (or a bundle) contains
another orbit (or bundle). Such a closure relation for orbits or bundles
corresponds to changes in the canonical forms (eigenvalues, their
multiplicities, minimal indices) of matrices under arbitrarily small
perturbations.

##  5 Reduction to structured perturbations.

(Mini)versal deformations have or may be forced to have a certain structure,
e.g., blocking, sparcity. Therefore the theory of versal deformations provides
a possibility to take into account all the possible perturbations of a given
matrix while working only with their versal deformations, i.e., only with
particularly structured matrices. This property of versal deformations may be
used in various ways. In particular, in this section, we show how to reduce a
perturbation of monic matrix polynomial linearization to a linearization of
the perturbed polynomial, or in the other words, how to find which
perturbations of the matrix coefficients of a monic matrix polynomial
correspond to a given perturbation of the entire linearization. Perturbed
polynomial must remain monic, i.e., the identity matrix in front of
$\lambda^{d}$ is not perturbed. We also derive the transformation matrix that,
via similarity, transforms perturbation of the linearization to the
linearization of perturbed polynomial. The described reduction is possible
since linearization of a perturbed polynomial is a versal deformation for
perturbation of matrix polynomial linearization [19, 23, 39].

Let $P(\lambda)=\lambda^{d}+A_{d-1}\lambda^{d-1}+\ldots+A_{1}\lambda+A_{0}$,
where $A_{i}\in\mathbb{C}^{n\times n},i=0,\ldots d-1,$ be a matrix polynomial.
To compute the eigenvalues of $P(\lambda)$ it is enough to compute the
eigenvalues of

(5.8) $C_{P}=\begin{bmatrix}-A_{d-1}&-A_{d-2}&\dots&-A_{0}\\\
I_{n}&0&\dots&0\\\ &\ddots&\ddots&\vdots\\\ 0&&I_{n}&0\\\ \end{bmatrix},$

since this matrix is a linearization of the polynomial $P(\lambda)$, see e.g.,
[36] (note also that (5.8) is similar to the first companion matrix of
$P(\lambda)$ [30, p.13, Theorem 1.1]). We define a full perturbation of
$C_{P}$ as follows

$C_{P}+E=C_{P}+\begin{bmatrix}E_{11}&E_{12}&\dots&E_{1d}\\\
E_{21}&E_{22}&\dots&E_{2d}\\\ \vdots&\vdots&\ddots&\vdots\\\
E_{d1}&E_{d2}&\dots&E_{dd}\\\ \end{bmatrix}.$

Notably, the full perturbation does not preserve the block-structure of
$C_{P}$. Therefore we also define the structured perturbation

$C_{P+F(E)}=C_{P}+\begin{bmatrix}F_{d-1}&F_{d-2}&\dots&F_{0}\\\ 0&0&\dots&0\\\
\vdots&\vdots&&\vdots\\\ 0&0&\dots&0\\\ \end{bmatrix}.$

$C_{P+F(E)}$ preserves the block-structure of $C_{P}$ and perturbs only the
blocks that correspond to the matrix coefficients of the matrix polynomial
$P(\lambda)$. As mentioned before, this structured perturbation is actually a
versal (but not miniversal) deformation of $C_{P}$ and thus it is always
possible to find a nonsingular matrix $S:=S(E)$, such that
$S^{-1}\cdot\left(C_{P}+E\right)\cdot S=C_{P+F(E)}$, see e.g., [13, 19, 23,
39]. Below we present an algorithm for finding this structured perturbation.

Define a split of a matrix $M=[M_{ij}]$ into a sum of its structured and
unstructured parts, ${M}^{s}$ and ${M}^{u}$, respectively, as follows:

$\begin{bmatrix}{M_{11}}&{M_{12}}&{\dots}&{M_{1d}}\\\
{M_{21}}&{M_{22}}&{\dots}&{M_{2d}}\\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\\
{M_{d1}}&{M_{d2}}&{\dots}&{M_{dd}}\\\
\end{bmatrix}=\begin{bmatrix}{M_{11}}&{M_{12}}&{\dots}&{M_{1d}}\\\
0&0&{\dots}&0\\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\\ 0&0&{\dots}&0\\\
\end{bmatrix}+\begin{bmatrix}0&0&{\dots}&0\\\
{M_{21}}&{M_{22}}&{\dots}&{M_{2d}}\\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\\
{M_{d1}}&{M_{d2}}&{\dots}&{M_{dd}}\\\ \end{bmatrix},\\\ \text{and }\ \
{{M}^{s}}:=\begin{bmatrix}{M_{11}}&{M_{12}}&{\dots}&{M_{1d}}\\\
0&0&{\dots}&0\\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\\ 0&0&{\dots}&0\\\
\end{bmatrix},\quad{{M}^{u}}:=\begin{bmatrix}0&0&{\dots}&0\\\
{M_{21}}&{M_{22}}&{\dots}&{M_{2d}}\\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\\
{M_{d1}}&{M_{d2}}&{\dots}&{M_{dd}}\\\ \end{bmatrix}.$

The idea of the algorithm is based on performing similarity transformations on
$C_{P}+E$ that decreases the norm of the unstructured part of the
perturbation, i.e., the norm of $E^{u}$:

$\displaystyle(I-X)^{-1}$
$\displaystyle(C_{P}+E)(I-X)=(I+X+X^{2}+X^{3}+\dots)(C_{P}+E)(I-X)$
$\displaystyle=C_{P}+(E+X(C_{P}+E^{s})-(C_{P}+E^{s})X)^{s}$
$\displaystyle\phantom{C_{P}+(E++(E++(}+\underbrace{(E+X(C_{P}+E^{s})-(C_{P}+E^{s})X)^{u}}_{\text{we
set it to zero, i.e., we find $X$ that eliminates
$E^{u}$;}}+\underbrace{XE^{u}-E^{u}X+O(X^{2}).}_{\text{spoils the unstructured
part again;}}\,$

Note that the norm of the unstructured part actually decreases since the norm
of $X$ is small ($(I-X)$ is a small perturbation of $I$ and the norm of $E$ is
small). We repeat the above procedure until the norm of the unstructured part
becomes sufficiently small. This is formalized in Algorithm 1 below.

Algorithm 1 (Recovering a perturbation of a monic matrix polynomial from a
perturbation of its linearization)

Let ${C}_{P}$ be a linearization of a monic matrix polynomial $P(\lambda)$ and
${E}_{1}$ be a full perturbation of ${C}_{P}$. Let also $I$ be the identity
matrix.

  * Input: Monic matrix polynomial $P(\lambda)$, perturbed matrix $C_{P}+{E}_{1}$, and the tolerance parameter ${\rm tol}$;

  * Initialization: $S:=I$;

  * Computation: While $\|{E^{u}_{i}}\|_{F}>{\rm tol}$

    * –

find the minimum norm least-squares solution to the Sylvester matrix equation:

$\big{(}X_{i}(C_{P}+E_{i}^{s})-(C_{P}+E_{i}^{s})X_{i}\big{)}^{u}=-{E}^{u}_{i}$;

    * –

by solving a system of linear equations with multiple right-hand sides,
extract the new perturbation ${E}_{i+1}$:
$(I-X_{i})E_{i+1}=E_{i}(I-X_{i})-C_{P}X_{i}+X_{i}C_{P}$;

    * –

construct the new perturbation $C_{P}+{E}_{i+1}$ of the matrix $C_{P}$ (note
that the perturbed linearization $C_{P}+E_{i+1}$ remains similar to the
original one $C_{P}+E_{1}$);

    * –

update the transformation matrix: $S_{i+1}:=S_{i}(I-X_{i})$;

    * –

increase the counter: $i:=i+1$;

  * Output: A structurally perturbed linearization $C_{P+F(E)}:=C_{P}+{E}_{k}$, where ${E}_{k}$ is a structured perturbation (since $\|{E}^{u}_{k}\|_{F}<{\rm tol}$), and the transformation matrix $S$.

In [12] an algorithm that performs such a reduction for general (possibly non-
monic) matrix polynomials and their first companion linearization is
presented. Therefore, we refer the interested readers to [12] for more details
and analysis of such algorithms.

We note also that the construction of the transformation matrices in Algorithm
1 is similar to the construction of the transformation matrices for the
reduction to miniversal deformations of matrices in [15, 16].

Reduction to structured perturbations. The theory of versal deformations
provides a possibility to take into account all the possible perturbations of
a given matrix while working only with its versal deformations. And since
versal deformations have or may be forced to have a certain structure, e.g.,
blocking, sparcity, then we only need to investigate particularly structured
matrices.

## Acknowledgements

This research was supported by the Swedish Research Council (VR) grant
2021-05393. The author is thankful to Froilán Dopico for the encouragement to
write this paper.

## References

  * [1] V.I. Arnold.  On matrices depending on parameters.  R. Math. Surveys, 26:29–43, 1971.
  * [2] V.I. Arnold.  Lectures on bifurcations in versal families.  R. Math. Surveys, 27(5):54–123, 1972.
  * [3] V.I. Arnold.  Geometrical methods in the theory of ordinary differential equations.  Springer-Verlag, New York, 2nd edition, 1997.
  * [4] V.A. Bovdi, M.A. Salim, and V.V. Sergeichuk.  Neighborhood radius estimation for Arnold’s miniversal deformations of complex and p-adic matrices.  Linear Algebra Appl., 512:97–112, 2017.
  * [5] F. De Terán and F. M. Dopico.  The equation $XA+AX^{\ast}=0$ and the dimension of ∗congruence orbits.  Electron. J. Linear Algebra, 22:448–465, 2011.
  * [6] F. De Terán and F. M. Dopico.  The solution of the equation ${XA}+{AX}^{T}=0$ and its application to the theory of orbits.  Linear Algebra Appl., 434:44–67, 2011.
  * [7] F. De Terán and F. M Dopico.  On bundles of matrix pencils under strict equivalence.  Linear Algebra and its Applications, 658:1–31, 2023.
  * [8] J. W. Demmel and A. Edelman.  The dimension of matrices (matrix pencils) with given Jordan (Kronecker) canonical forms.  Linear Algebra Appl., 230:61–87, 1995.
  * [9] A. Dmytryshyn.  Miniversal deformations of pairs of skew-symmetric matrices under congruence.  Linear Algebra Appl., 506:506–534, 2016.
  * [10] A. Dmytryshyn.  Structure preserving stratification of skew-symmetric matrix polynomials.  Linear Algebra Appl., 532:266–286, 2017.
  * [11] A. Dmytryshyn.  Miniversal deformations of pairs of symmetric matrices under congruence.  Linear Algebra Appl., 568:84–105, 2019.
  * [12] A. Dmytryshyn.  Recovering a perturbation of a matrix polynomial from a perturbation of its first companion linearization.  BIT Numer. Math., 62(1):69–88, 2022.
  * [13] A. Dmytryshyn and F. M. Dopico.  Generic complete eigenstructures for sets of matrix polynomials with bounded rank and degree.  Linear Algebra Appl., 535:213–230, 2017.
  * [14] A. Dmytryshyn, V. Futorny, B. Kågström, L. Klimenko, and V.V. Sergeichuk.  Change of the congruence canonical form of 2-by-2 and 3-by-3 matrices under perturbations and bundles of matrices under congruence.  Linear Algebra Appl., 469:305–334, 2015.
  * [15] A. Dmytryshyn, V. Futorny, and V.V. Sergeichuk.  Miniversal deformations of matrices of bilinear forms.  Linear Algebra Appl., 436:2670–2700, 2012.
  * [16] A. Dmytryshyn, V. Futorny, and V.V. Sergeichuk.  Miniversal deformations of matrices under *congruence and reducing transformations.  Linear Algebra Appl., 446:388–420, 2014.
  * [17] A. Dmytryshyn, S. Johansson, and B. Kågström.  Codimension computations of congruence orbits of matrices, symmetric and skew-symmetric matrix pencils using Matlab.  Technical Report UMINF 13.18, Department of Computing Science, Umeå University, Sweden, 2013.
  * [18] A. Dmytryshyn, S. Johansson, and B. Kågström.  Canonical structure transitions of system pencils.  SIAM J. Matrix Anal. Appl., 38(4):1249–1267, 2017.
  * [19] A. Dmytryshyn, S. Johansson, B. Kågström, and P. Van Dooren.  Geometry of matrix polynomial spaces.  Found. Comput. Math., 20:423–450, 2020.
  * [20] A. Dmytryshyn and B. Kågström.  Orbit closure hierarchies of skew-symmetric matrix pencils.  SIAM J. Matrix Anal. Appl., 35(4):1429–1443, 2014.
  * [21] A. Dmytryshyn, B. Kågström, and V.V. Sergeichuk.  Skew-symmetric matrix pencils: Codimension counts and the solution of a pair of matrix equations.  Linear Algebra Appl., 438(8):3375–3396, 2013.
  * [22] A. Dmytryshyn, B. Kågström, and V.V. Sergeichuk.  Symmetric matrix pencils: codimension counts and the solution of a pair of matrix equations.  Electron. J. Linear Algebra, 27:1–18, 2014.
  * [23] F. M. Dopico, P. Lawrence, J. Pérez, and P. Van Dooren.  Block Kronecker linearizations of matrix polynomials and their backward errors.  Numer. Math., 140:373–426, 2018.
  * [24] A. Edelman, E. Elmroth, and B. Kågström.  A geometric approach to perturbation theory of matrices and matrix pencils. Part I: Versal deformations.  SIAM J. Matrix Anal. Appl., 18(3):653–692, 1997.
  * [25] A. Edelman, E. Elmroth, and B. Kågström.  A geometric approach to perturbation theory of matrices and matrix pencils. Part II: A stratification-enhanced staircase algorithm.  SIAM J. Matrix Anal. Appl., 20(3):667–669, 1999.
  * [26] E. Elmroth, S. Johansson, and B. Kågström.  Stratification of controllability and observability pairs — Theory and use in applications.  SIAM J. Matrix Anal. Appl., 31(2):203–226, 2009.
  * [27] V. Futorny, T. Klymchuk, O. Klymenko, V. V. Sergeichuk, and N. Shvai.  Perturbation theory of matrix pencils through miniversal deformations.  Linear Algebra Appl., 614:455–499, 2021.  Special Issue ILAS 2019.
  * [28] D. M. Galin.  Real matrices depending on parameters.  Uspehi Mat. Nauk, 27(1(163)):241–242, 1972.
  * [29] M.I. García-Planas and V.V. Sergeichuk.  Simplest miniversal deformations of matrices, matrix pencils, and contragredient matrix pencils.  Linear Algebra Appl., 302–303:45–61, 1999.
  * [30] I. Gohberg, P. Lancaster, and L. Rodman.  Matrix polynomials, volume 58 of Classics in Applied Mathematics.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2009.
  * [31] R.A. Horn and C.R. Johnson.  Matrix analysis.  Cambridge University Press, Cambridge, 1985.
  * [32] L. Klimenko and V.V. Sergeichuk.  Block triangular miniversal deformations of matrices and matrix pencils.  In Matrix Methods: Theory, Algorithms and Applications: Dedicated to the Memory of Gene Golub, pages 69–84. World Scientific, 2010.
  * [33] L. Klimenko and V.V. Sergeichuk.  An informal introduction to perturbations of matrices determined up to similarity or congruence.  São Paulo Journal of Mathematical Sciences, 8(1):1–22, 2014.
  * [34] H. Kraft.  Geometrische Methoden in der Invariantentheorie.  Aspects of Mathematics, D1. Friedr. Vieweg & Sohn, Braunschweig, 1984\.
  * [35] H. Kraft and C. Procesi.  On the geometry of conjugacy classes in classical groups.  Comment. Math. Helv., 57(4):539–602, 1982.
  * [36] D. S. Mackey, N. Mackey, and F. Tisseur.  Polynomial Eigenvalue Problems: Theory, Computation, and Structure.  In Numerical Algebra, Matrix Theory, Differential-Algebraic Equations and Control Theory, pages 319–348. Springer, 2015.
  * [37] A.A. Mailybaev.  A method for reducing families of matrices to normal forms.  Dokl. Akad. Nauk, 367(2):168–172, 1999.
  * [38] A.A. Mailybaev.  Transformation to versal deformations of matrices.  Linear Algebra Appl., 337:87–108, 2001.
  * [39] P. Van Dooren and P. Dewilde.  The eigenstructure of a polynomial matrix: Computational aspects.  Linear Algebra Appl., 50:545–579, 1983.


# Predicting Hateful Discussions on Reddit using Graph Transformer Networks
and Communal Context

Liam Hebert  University of Waterloo
Waterloo, Canada
<EMAIL_ADDRESS>Lukasz Golab  University of Waterloo
Waterloo, Canada
<EMAIL_ADDRESS>Robin Cohen  University of Waterloo
Waterloo, Canada
<EMAIL_ADDRESS>
###### Abstract

We propose a system to predict harmful discussions on social media platforms.
Our solution uses contextual deep language models and proposes the novel idea
of integrating state-of-the-art Graph Transformer Networks to analyze all
conversations that follow an initial post. This framework also supports
adapting to future comments as the conversation unfolds. In addition, we study
whether a community-specific analysis of hate speech leads to more effective
detection of hateful discussions. We evaluate our approach on 333,487 Reddit
discussions from various communities. We find that community-specific modeling
improves performance two-fold and that models which capture wider-discussion
context improve accuracy by 28% (35% for the most hateful content) compared to
limited context models.

###### Index Terms:

Hate Speech, Social Media and Social Discourse, AI for Social Good, Graph
Neural Networks, Natural Language Processing

##  I Introduction

The rise of social media has led to increased harmful discourse with damaging
mental health effects. A recent study by Gao et al. measured the mental health
of over 4800 Chinese citizens and found a high correlation between increased
anxiety and depression with high social media usage [1]. These alarming trends
have motivated the usage of automated detection methods to help moderate these
platforms and prevent further harms.

A common approach of methods that tackle this problem is to detect the
hatefulness of individual comments that belong to a wider discussion [2, 3,
4]. Two central challenges arise, however. First, conversational hate speech
is deeply contextual. To properly understand if a comment is hateful, it is
important to understand the context in which it was said. Second, by only
analyzing the hatefulness of individual comments, we are bound to a reactive
kind of moderation, which requires the damaging comment and the discussion
that led to it be published first. This can lead to the spread of
conversations that discuss harmful or sensitive subjects which can incite
further hateful discourse. As such, it is important to proactively detect the
tone and trend of conversations before they can delve into explicit hate
speech.

Towards the goal of proactive detection, we also believe that it is important
to consider the unique latent communal norms and behaviours that underpin
social groups. Content which may trigger a hateful reaction from members of
one group can trigger a different reaction from another group. This focus is
inspired by a recent study by Cinellie et al., which found that online
communities are prone to the “echo chamber” effect, where extreme ideals can
be encouraged and amplified [5]. As such, learning these cultural norms and
behaviours is essential to properly model the direction of a conversation and
whether that direction leads to hate speech.

Taking all these observations into consideration, the question is how to
design a framework that can perform a rich analysis of branching social media
discussions with a view of proactive hate speech prediction, and also how best
to design experiments to demonstrate whether community-specific analysis
provides important benefits.

To study the behaviours of diverse communities, we focus on the social
platform Reddit, where discussions take place in topic-orientated communities
called subreddits. These communities are highly varied, ranging from aww, to
discuss cute animals, and politics, to discuss political affairs. Beyond their
subject differences, prior work by Waller et al. found that these communities
exhibit significant differences in their social makeup and discussion
behaviours [6]. For example, discussions that take place on The_Donald were
found to have a significant political right leaning bias whereas politics has
an opposing left leaning bias. Within these communities, conversations take
place in branching trees structures where any user can reply to the comments
of other users, forming a linked chain of replies that can branch off into
sub-discussions. In addition to textual replies, users can explicitly provide
their opinion by up-voting (approving) or down-voting (disapproving) the
comments of other users.

Figure 1: Example of a Reddit Discussion

The need for a deeper analysis of discussions with critical consideration of
the relevant context becomes apparent when examining the excerpt from Reddit
provided in Figure 1. Focusing on the first interaction is insufficient in
properly detecting the tendency towards hate, as these initial comments are
actually quite benign. Indeed, what is perhaps most troubling with this
excerpt is the kind of snowball effect of anti-social sentiment, as the
discussion progresses.

In this work, we propose a novel approach to prevent hate speech on social
platforms which addresses these challenges. First, it is important to properly
encode the complex lexicon unique to online discussions [7]. To do this, we
utilize a fine-tuned BERT language model that was trained on hateful text from
various social media platforms [8, 9]. This allows our system to utilize
contextual language embeddings of each node in the discussion graph as initial
feature representations. Next, to capture the structure of conversations, we
propose adaptations to Graphormer [10], a state-of-the-art graph transformer
network. We adapt Graphormer away from its original purpose of detecting
global qualities of molecules, a large difference from our intended use case.
Instead, we predict whether specific nodes in our discussion graph will lead
to discussions that encourage and contain hateful behaviour. By adapting this
model, we benefit from a self-attention aggregation operation over the entire
graph, allowing the model to learn contextual relationships between relevant
comments in the discussion. Our end-to-end solution utilizes the embeddings
generated by the language model as the representation of each vertex in our
discussion graph, which are then aggregated and transformed by our Graphormer
model to make final node-level predictions.

To train such a system, we assemble a dataset of 333,487 discussion graphs
from different Reddit communities. Each node in a discussion tree is then
algorithmically labeled with an ordinal value (0-4) according to how prevalent
the hate speech is within the discussion that follows under that node. By
utilizing a ranked representation of hate, we recognize that encouraged
hateful behaviour can be more damaging than discouraged hateful behaviour, and
that not all hateful behaviour is equivalent. In addition, users can leverage
these scores to specify which level of hateful content they are comfortable
viewing and can be used to help social platforms prioritize moderation for the
most extreme content. We then investigate the impact of modeling specific
communal influence by measuring performance of our system against variants
that are trained on only one Reddit community.

We conclude this work with a reflection on how our proactive approach to
predicting hate speech can be used to improve the mental health of users
online. This final discussion will shed more light on the significant value we
derive from considering trees of discussion in social media, and not simply
interpreting whether a single comment is conveying hate speech. Our codebase
is available at github.com/liamhebert/CommunityHateFormer.

##  II Background and Related Work

###  II-A Deep Language Models

Our approach draws on recent advancements in deep language models and graph
neural networks. To encode the textual content of a comment, we make use of
the Transformer language model architecture proposed by Vaswani et al. [11].
This architecture has resulted in many performance gains in various natural
language tasks [11, 9].

Core to the transformer is the scaled dot product self-attention mechanism.
Let $H^{k}=[h_{0},h_{1},...,h_{n}]\in R^{n\times d}$ be the set of hidden
embeddings of each word $h_{i}$ of size $d$ at layer $k$. Given three
learnable weight matrices, $W_{Q}\in R^{d\times d}$, $W_{K}\in R^{d\times d}$
and $W_{V}\in R^{d\times d}$, the self-attention operation computes

$\displaystyle Q=H^{(k)}W_{Q},~{}K=H^{(k)}W_{K},~{}V=H^{(k)}W_{V},$
$\displaystyle Attn(H^{(k+1)})=softmax(\frac{QK^{\top}}{\sqrt{d}})V$

where $Attn(H^{k})$ represents an attention-weighed representation of the
input. This representation is then processed by a feedforward neural network
to create $H^{(k+1)}$ [11, 10]. The use of a self-attention mechanism allows
the model to encode the contextual relationship between words in a sentence
[11]. BERT, proposed by Devlin et al., extends this architecture by adding a
special token [CLS] to the initial input and using the final embedding
$h_{[CLS]}$ to encode the entire sentence [9].

Transformer models can be fined-tuned to perform a variety of tasks, including
hate speech detection on social media. To utilize this architecture towards
hate speech detection, Mathew et al. curated a corpus of comments from social
platforms Twitter and Gab, labeled as containing either Normal, Hateful or
Offensive content [8]. The authors then fine-tuned a BERT model on this corpus
to classify comments into these three categories. Their final system, BERT-
HateXplain, achieved $\approx 70\%$ classification accuracy according to these
three classes [8]. Our approach utilizes the $h_{[CLS]}$ embeddings created
from a pre-trained BERT-HateXplain model to initially encode each comment in a
discussion graph.

###  II-B Graph Neural Networks

Figure 2: Aggregate-Combine Operations in a Graph Neural Network

Given a Graph $G=(V,E)$ with vertices $V$ connected by edges $E$, Graph Neural
Networks (GNNs) compute representations of the vertices based on their feature
embeddings $v$. Each layer of a GNN consists of two steps: AGGREGATE and
COMBINE (Figure 2). The AGGREGATE operator combines the feature embeddings
$v_{k}$ of all neighbouring vertices of a given vertex $Vi$ into an aggregated
embedding $a_{i}$. Common aggregation operators include taking the mean, max
and sum of the feature embeddings of neighbouring vertices [12, 13, 14, 15].

Following the AGGREGATE operator, the COMBINE operator creates a new
representation of $Vi$ by transforming $v_{i}$ with respect to $a_{i}$. This
new representation can then be used in subsequent layers for further
aggregation. In practice, COMBINE operations are typically implemented as
feed-forward neural networks, which transform the concatenation of $a_{i}$ and
$v_{i}$ [10]. Key to the expressiveness of GNNs is that both the COMBINE and
AGGREGATE steps are structure-independent. It is trivial to add vertices and
edges to a GNN input and compute new inferences by simply expanding the number
of vertices in the AGGREGATE operator. This aspect allows GNNs to be well
suited for inputs that can take multiple shapes, such as branching social
media conversations.

Figure 3: Graphormer Architecture [10]

Motivated by the performance increases achieved by Transformer models, Ying et
al. adapted the self-attention mechanism to GNNs [10] for use in molecular
modeling, which they name Graphormer. A key feature of this architecture is
the ability to use the self-attention mechanism to encode relationships
between any nodes in the entire graph during each model layer, regardless of
position and structure (Figure 3). To encode graph structure, Ying et al.
propose four proxy variables. Centrality Encoding, representing the in-degree
and out-degree of each node, is given as

$H_{i}^{(0)}=x_{i}+z_{deg^{-}(v_{i})}^{-}+z_{deg^{+}(v_{i})}^{+}$

where $H_{i}^{(0)}$ is the initial representation of node $v_{i}$ with
features $x_{i}$ and where $z_{deg^{-}(v_{i})}^{-}$ and
$z_{deg^{-}(v_{i})}^{+}$ are learnable embeddings corresponding to the in-
degree $deg^{-}(v_{i})$ and out-degree $deg^{+}(v_{i})$ of that node. These
features are only added to the initial representations of each node. Next,
Spatial Encoding is introduced to encode the structure of the graph according
to inter-node distance. This encoding is added during the self attention
mechanism, where the encoding of node $v_{i}$ with respect to node $v_{j}$ is
given as

$A_{ij}=\frac{(H_{i}W_{Q})(H_{j}W_{K})^{T}}{\sqrt{d}}+b_{\phi(v_{i},v_{j})}$

where $H_{i}$ and $H_{j}$ are the embeddings of nodes $v_{i}$ and $v_{j}$,
$W_{Q}$ and $W_{K}$ are learnable weight matrices and $b$ is a learnable
embedding representing the shortest distance between $v_{i}$ and $v_{j}$ in
the graph ($\phi(v_{i},v_{j})$). The last two features are Edge Encoding,
which encodes features corresponding to edge features that connect nodes, and
[CLS] nodes, to represent the entire structure. Following the self-attention
mechanism, the next layer representation $H^{(k+1)}_{i}$ of node $i$ is given
as

$H^{(k+1)}_{i}=softmax(A_{i})\times H^{(k)}W_{v}$

where $W_{v}$ is a learnable weight matrix and $softmax(A_{i})$ is the softmax
operation over all $A_{i}$ embeddings. These $A_{i}$ embeddings are created
for every node pair in the graph regardless of position, allowing node
embeddings to be created with respect to the entire graph structure.

###  II-C Prior Work

The urgency of detecting hate speech online has led to a large research
interest in natural language processing tools. However, preventative hate
speech detection is still a difficult problem to solve. Prior work on this
problem by Brassard-Gourdeau et al. proposed utilizing features from the first
two messages of a linear conversation, in addition to features in the current
message, as useful predictors for future hate speech [4]. Parallel work by
Huang et al. proposed methods to pre-filter comments before being published to
a wider audience [3]. However, both of these systems operate on a limited
context, narrowed to the first few messages of a discussion or on the next
comment to be made. In addition, many of these systems are trained to
generalize to all kinds of social discourse, which may hinder the detection of
nuanced culture-specific hate speech. A final concern is that the systems are
often designed to handle linear discussions, whereas online social media
typically have branching discussions instead.

GNNs have recently been proposed to capture the importance of context to
predict hateful discourse in complex discussion graphs. Parmentier et al.
investigated using GNNs to detect traits of individual comments by aggregating
features of their immediate neighbours [16]. This included traits such as
predicting the “upvote” and “downvote” score of a comment and whether the
comment contained hateful content [17, 16]. However, while predicting the
behaviour stemming from a comment, Parmentier et al. only examined immediate
node neighbours. This was a constraint originating from the methods and
computational resources available at the time.

We differ from this prior work in two ways. First, instead of predicting
qualities of individual nodes, we predict whether specific nodes will lead to
future hateful discourse by consuming the entire discussion graph during
inference. To do this, we treat predictions of each node in the graph as the
prediction of the future subtree rooted at that node. This allows our system
to be utilized towards preventative detection of hate speech, rather then
analyzing comments after they have been published. In addition, the self-
attention mechanism allows our model to only pay attention to contextually
relevant nodes when computing new representations, avoiding noise.

Second, we differ from this prior work by incorporating fine-tuned contextual
deep language models rather than using context-free GloVE language modeling
[18]. By utilizing deep language models, we create embeddings that are fine-
tuned on the lexicon that is present on online social platforms, rather than
relying on embeddings generated from formal sources, such as Wikipedia.
Additionally, self-attention allows the language model to contextualize to the
entire input, as opposed to GloVE which relies on word co-occurrence ratios of
the training corpus [18]. Notably, the usage of self-attention mechanisms
resulted in much better performance in context-dependent tasks, such as
sentiment analysis [11]. In summary, the novelty of our approach lies on
combining deep language models with recent innovations in GNNs that can
efficiently capture longer range relationships.

##  III Methodology

###  III-A RedditHate Dataset

To train our model, we collected Reddit posts created between 2018 and 2019
using the Pushshift API111https://github.com/pushshift/api, focusing on the
The_Donald, IAmA, AmITheAsshole and Politics communities. This resulted in a
dataset of 333,487 posts and 6,531,455 comments. These communities were
selected due to their frequent lively discussion around various topics and
known differences in community norms [17, 6].

Due to the size of the dataset, it is not feasible to label every subtree by
hand. Instead, we rely on several proxy features. First, we make use of the
scores (upvotes and downvotes) that users assign to comments on Reddit. We
utilize an aggregated tally of these scores to model how inflammatory a given
comment was to a community. We also make use of the hatefulness prediction of
comment text from BERT Hate-Explain [8] (retaining the definition of hate by
the authors) and the graph structure as further proxy variables. For each
vertex $v_{i}$ in the graph, we compute the hate label of a comment
$L_{v_{i}}$ by summing over three symbolic terms that estimate how hateful the
conversation is stemming from that node: Context $C_{v_{i}}$, Reaction
$R_{v_{i}}$ and Influence $I_{v_{i}}$. These terms are computed as:

$\displaystyle C_{v_{i}}$ $\displaystyle=0.25\times hate_{p_{i}}\times
score_{p_{i}}$ (1) $\displaystyle R_{v_{i}}$ $\displaystyle=0.25\times
hate_{v_{i}}\times score_{v_{i}}$ (2) $\displaystyle I_{v_{i}}$
$\displaystyle=\sum_{c\in S_{v}}0.25\times L_{c}$ (3) $\displaystyle
L_{v_{i}}$ $\displaystyle=C_{v_{i}}+R_{v_{i}}+I_{v_{i}}$ (4)

where $hate_{v}$ is the HateXplain predicted score of vertex $v$ scaled to
$(-0.7-1.5)$, $score_{v}$ is the upvote/downvote score, $p$ is the parent node
of $v$ and $S_{v}$ is the set of child nodes under $v$. The Context term
$C_{v_{i}}$ aims to capture the context in which a comment was made, focusing
on the hatefulness of the parent comment. The Reaction $R_{v_{i}}$ term then
captures the hatefulness of the instigating comment that led to the
conversation that followed. Lastly, the Influence term $I_{v_{i}}$ recursively
sums the discounted hatefulness of the conversation that followed as a result
of the current node. Each label is created in a bottom-up approach starting
from the leaves of the discussion tree. The factor 0.25 in each formula is
selected to equally weigh the contribution of each component. As part of our
design process, we conducted a sensitivity analysis of these weights, detailed
in Section IV-D, and found no significant differences in performance when
perturbed.

In each term comprising our hate label $L_{v_{i}}$ (Equations 1 through 3),
the multiplication ensures that hateful posts that are encouraged with a
positive score have a similar score to non-hateful posts that have a negative
score. Additionally, the weights attached to each term allow lively hateful
discussions with many subtrees to decisively influence the label of the
current comment. We then standardize each label into five ordinal classes,
([$<0$], [0 - 5], [6 - 20], [21 - 500], [$500<$]), corresponding to increasing
levels of hatefulness. The intuition behind the use of ordinal values is to
enable social media moderators to prioritize the most hateful content and
deploy different policies for different criteria. The range of values chosen
for each of these classes was selected as a result of inspection of the
overall distribution of hate labels and the comments contained within them.
Our classification of hate can then be seen as a regression problem. The final
label distribution can be seen in Table II. With each discussion tree labeled,
we then convert each graph into Pytorch Geometric (PyG) Data Graphs objects
for inference [19].

This approach of using algorithmic labeling follows prior work for labeling
hate speech on social platforms, such as [17] and [4], among other works. In
each of these systems, algorithmic methods such as HateXplain replace human
reviewers to label a sufficiently large dataset.

Next, to analyze the ability of our model to proactively predict hate speech,
we take a subset of each labeled discussion tree as the model’s input. We do
this by taking a horizontal slice of the discussion tree such that the maximum
depth of the tree is four comments from the root. We then remove all comments
that did not lead to a sub-discussion of at least two comments. As a result,
the leaf nodes of our trimmed discussion tree are parent nodes of at least two
other comments, requiring the model to predict the hatefulness of an unseen
future discussion. Our trimming strategy also focuses our model’s input on the
most relevant parts of the discussion [16]. Table I shows the number of nodes
before and after filtering for the four communities we selected.

TABLE I: Community Sample Size for the RedditHate Dataset Subreddit | Nodes | Nodes after Filtering
---|---|---
The_Donald | 6 531 455 | 3 005 612
Politics | 6 127 723 | 1 457 321
AmItheAsshole | 4 135 270 | 1 381 200
IAmA | 183 284 | 30 415
TABLE II: RedditHate Label Distribution Subreddit / Label | 0 | 1 | 2 | 3 | 4
---|---|---|---|---|---
AmItheAsshole | 1 103 308 | 183 108 | 39 815 | 45 371 | 9598
IAmA | 27 890 | 2 240 | 216 | 68 | 1
The_Donald | 2 310 601 | 441 746 | 133 534 | 117 091 | 2640
Politics | 1 087 286 | 264 570 | 54 311 | 45 563 | 5 591
Total | 4 529 085 | 891 664 | 227 876 | 208 093 | 17 830

###  III-B Model Architecture

Our approach modifies the Graphormer model by Ying et al. [10] with the
HateXplain model by Mathew et al. [8]. Notably, the original Graphormer
architecture was proposed and geared towards molecular modeling and graph-
level predictions (Section II-B). However, with respect to the RedditHate
Dataset (Section III-A), our task is instead to have node-level predictions
regarding the future direction of discussions. Despite this, our focus on
capturing the entire discussion context makes the Graphormer architecture
appealing.

To adapt the Graphormer architecture towards our task, we first omit the usage
of [CLS] nodes and Edge Encoding since we are not concerned with graph level
predictions or edge features. Second, we adapt the model output to predict
ordinal labels for each node in the graph. These labels correspond to the
predicted hate score defined in Section III-A. Finally, to encode each comment
in the graph, we utilize a pre-trained BERT model trained on the HateXplain
dataset (Section II-A). We use the [CLS] embedding of each comment as the
feature representation in the graph. As a result, each comment in the
discussion graph is encoded as a 769-dimension embedding. The usage of BERT-
HateXplain allows each contextual comment embedding to be learned from common
social media discourse, rather than formal and clean text. We also concatenate
the upvote/downvote score to the input vector. In our experiments, we utilize
the Graphormer-BASE variant which consists of ten layers of Graphormer self-
attention, resulting in 144 million total parameters (36 million excluding
BERT-HateXplain).

##  IV Results

In our experimental evaluation, we start by investigating whether global
discussion context allows for more accurate detection of future hateful
discussions (results in Section IV-A). This is motivated by contrasting
against other attempts at detecting hate speech, which often rely on just a
single comment or the closest neighbours of a comment [16, 4, 3]. Second,
under the lens of modeling diverse discussion semantics, we investigate
whether models that are trained on specific communities outperform models that
are trained on all communities (results in Section IV-B). Expanding on these
questions, in Section IV-C we present a qualitative comparison of our approach
against existing approaches, giving examples of discussions that were
predicted more effectively by our method, compared to others. We then conclude
with a sensitivity analysis of our hate labelling function in Section IV-D.

We use the standard Graphormer variant, which consists of ten transformer
layers with a hidden dimension size of 769, as described in the original work.
Additionally, we utilized the AdamW optimizer with a peak learning rate of
2e-4, which linearly decayed after a warmup period [20]. We applied an L2
regression loss for training and as an evaluation metric, which assigns
heavier penalties towards incorrect values. This is important due to the
imbalance in our dataset towards smaller hate label values. Due to compute
constraints, a batch size of 16 was used over ten epochs and only the
Graphormer model was fine-tuned. To evaluate the performance of the model, we
masked 10% of comments for use in validation and 20% for use in testing,
following prior work by Chen et al. [21]. We utilize the validation set for
hyper-parameter tuning in our experiments. Each model was trained for $\approx
5$ hours with 3 RTX 2080 Ti GPUs.

###  IV-A Impact of Deeper Context

TABLE III: Model Performance (L2 Loss) of our approach, labelled Graphormer, and GAT Method / Label | All | 0 | 1 | 2 | 3 | 4
---|---|---|---|---|---|---
Graphormer | 1.066 | 0.556 | 0.946 | 1.275 | 2.213 | 3.817
GAT | 1.485 | 0.473 | 1.228 | 1.872 | 2.661 | 5.883

We begin by investigating the impact of including the entire discussion graph
during inference. To measure this, we selected the Graph Attention Network
architecture (GAT) [13] as a baseline, as implemented in Pytorch Geometric
[19]. This is inspired by previous efforts to utilize graph models to detect
hate speech on social networks, in particular [16], which utilized this
architecture. It is important to note that our use case differs, where we
instead seek to detect comments that will lead to hateful discussion. Similar
to the Graphormer architecture, the GAT architecture utilizes an attention
mechanism to aggregate neighbouring node embeddings. However, an important
difference with this architecture is that the aggregation operation is
constrained to the direct neighbouring comments in each layer. This is
contrasted by our proposed approach, which performs self-attention aggregation
over the entire graph at each layer.

We compare our approach against a two-layer GAT model, following the
recommended configuration by the original authors and prior work [16]. This
implies two iterations of the Aggregation-Combine operation. Table III shows
the results: our approach (Graphormer) outperforms GAT by an average L2 loss
of 0.419. Our results illustrate that both models perform well at classifying
comments with a low level of future hateful discussion (0-1). This can be
attributed to the prevalence of these comments in our dataset. However,
notable differences in model performance can be seen when detecting comments
which led to more prevalent hatespeech (2-4), where our model outperforms GAT
by an average L2 loss of 2.066.

We hypothesize that the gains made by Graphormer are due to its ability to
contextualize better to the discourse of larger discussion graphs, which are
often good indicators of future lively discussions. An example of this would
be an instigating comment in a debate, where a better understanding of the
entire debate could serve as a better predictor of what could be considered
hateful and instigating rebuttal. That being said, it is still important to
note that the performance at the higher echelon is not optimal, having an
average prediction inaccuracy of $\approx 2$ ordinal levels; however,
Graphormer still presents an improvement over GAT.

###  IV-B Impact of Community Specific Models

TABLE IV: Model L2Loss Performance on Different Communities Target Communities | Train | Test
---|---|---
All | 1.060 | 1.066
The_Donald | 0.4913 | 0.4911
Politics | 0.4042 | 0.4041
IAmA | 0.3687 | 0.3444
AmITheAsshole | 0.4388 | 0.4397

A key question in this work was whether hate could be better predicted by
modeling the behaviours and cultural norms of specific communities. To
evaluate this, we trained variations of the model on specific communities
present in our dataset. We compare these results against a general purpose
variant that was trained on data from all four communities (Table IV). We see
that general models trained on all subreddits perform significantly worse than
community-specific models. When comparing L2 loss, each community-specific
model outperforms general models by a factor of two, for an average loss of
$\approx 0.4$. The model for the IAmA subreddit benefited the most from having
a community-specific focus, with an average L2 loss of 0.3687, followed by the
politics subreddit.

We hypothesize that this performance boost came from two advantages. First,
each community we selected is associated with vastly different topics, with
The_Donald created to discuss alt-right politics and AmITheAsshole discussing
personal advice. As such, it is likely that comments that would be ignored in
The_Donald could be inflammatory in other communities. A similar trend can be
noticed in politics, which is politically left leaning and would be more
sensitive to hateful political discourse [6]. By modeling specific
communities, we hypothesize that our model captured these different cultural
norms.

Second, some communities discuss in a formal and structured manner, such as
question-answer format. IAmA is an example of this, a community that focuses
on interviewing celebrities by asking public questions, contrasting other
communities which have free-flowing discussion. This difference was
highlighted in our results, where we found that IAmA benefited the most from a
community-specific approach. By modeling the question and answer format and by
sampling the entire interview, we hypothesize that our model was able to
better understand the topics discussed and the unique conversational flow.

###  IV-C Qualitative Analysis

TABLE V: Example conversation requiring long range forecasting from community
cues (/r/politics)
* indicates comments outside of initial input context and predicted in subsequent iterations Depth |  Text | Label | Graphormer | GAT | Bert-HateXplain
---|---|---|---|---|---
0 |  How could Flynn have any information that would implicate the president, if the president were innocent? | 3 | 4 | 1 | 0
1 |  Because, according to the GOP Hive Mind, the information is a combination of completely fabricated and not illegal. Trump’s narrative has always been ”Witch Hunt!” i.e., that there was no basis for the investigation, so any information is obviously fake. […] It still boggles my mind that conservatives don’t seem to possess the basic cognitive function required to utilize simple logic. | 3 | 3 | 2 | 1
1 |  Going further, why would Trump himself attempt or instruct others to attempt the 10 obstructive acts detailed in the report if he was innocent? Why would his associates have had to stonewall, destroy evidence, tamper with witnesses, and lie to investigators if he was innocent? | 2 | 3 | 0 | 1
|  […] |  |  |  |
6 |  If Republicans continue the trend, their next candidate will only be grunting and throwing feces. | 4 |  4* | 4* | 4*
7 |  I think we can go dumber.. | 4 |  3* |  1* | 2*

To better capture the behaviours of our approach, we conducted a qualitative
analysis against GAT and comment-text only Bert-HateXplain. Since the Bert-
HateXplain values are originally between 0-1, we map them to increasing
ordinal values of [0-0.2], [0.2-0.4], [0.4-0.6], [0.6-0.8] and [0.8-1.0], for
a matching 0-4 scale. We focused on investigating conversations where
predictions between all three models differed. An example of such a
conversation, found in the politics subreddit, is shown in Table V. The
subject of this conversation is regarding U.S. politics and then-recent news
regarding Michael Flynn, former security advisor to President Donald Trump. On
the politics subreddit, prior work has discovered a strong left leaning bias,
resulting in heated discussion when talking about topics concerning the
political right [6]. In this discussion, the conversation starts with negative
but still relatively tame comments. However, as the conversation deepens, it
devolves into hate speech against the Republican party (”If Republicans
continue the trend, their next candidate will only be grunting and throwing
feces”).

Investigating the predicted values of all three methods, we see that
Graphormer more accurately predict the direction the discussion will be
heading, even stemming from the first comment. Our approach predicted an
ordinal score of 4 compared to a label of 3. This is compared to predictions
made from GAT and HateXplain, which fail to capture the longer dependency (1
and 0 respectively). We also see a recurring trend with single comment Bert-
HateXplain, which seems to downplay the intensity of the hateful content early
on compared to the ground truth labels. It is important to note that the input
discussion is cut off after a depth of four comments (the limit used in [16]),
and therefore predictions must be made from that limited context.

###  IV-D Sensitivity of RedditHate Labeling Function

TABLE VI: Model Performance on Different Labeling Weights Labeling Weight Variant | Train L2Loss | Test L2Loss
---|---|---
Equal | 1.060 | 1.066
Influence-Weighted | 1.180 | 1.200
Reaction-Weighted | 1.072 | 1.073
Context-Weighted | 0.985 | 0.994

We now investigate the sensitivity of the weights defined in the HateReddit
labeling function, which combines the value of the Context-term (original node
focused), Reaction-term (parent node focused) and Influence-term (aggregated
child nodes focused) (Section III-A). This evaluates the likelihood of our
results to be dependent on the labeling weights chosen. To do this, we created
four variants of the dataset based on different weighting configurations:
Equal, which consists of weighting each term equally, as well as Influence-
Weighted, Reaction-Weighted and Context-Weighted, which doubles the weight of
each respective term in the labeling function (weighted by 0.5 instead of
0.25). We conducted each experiment on the entirety of the HateReddit dataset.

Table VI shows the results. Each variant performs similarly, with a Loss range
of (0.994 - 1.200). As a result, we conclude that the labeling weights are not
sensitive to specific values. We see that the Context-Weighted variant of the
dataset produced the best performance with a Test L2 loss of 0.994, whereas
the worst performing variant was the Influence-Weighted variant, with a Test
L2 loss of 1.200. It is important to note that the Influence term of each node
is calculated from the entire discussion tree, despite the input constrained
to a depth of four with each remaining comment being the parent of at least
two others, potentially hidden, comments. As a result, the Influence-weighted
variant represents a more difficult task compared to the other variants.

##  V Future Work

There are several potential avenues for future work. First, recall that the
RedditHate dataset is founded on algorithmic deduction that approximates
ground truth. Ideally, the RedditHate dataset would be annotated by human
evaluators or more advanced labeling strategies. Potential future work could
also explore creating an expanded and balanced dataset of hateful and non-
hateful discussions. This could be done by considering a longer time period
and then carefully selecting discussions to fit a desired distribution. In
addition, the collection of communities discussed could be further expanded to
consider more diverse and topic orientated communities.

Second, we hypothesize that it would be beneficial to train the model end-to-
end by fine-tuning the BERT-HateXplain and Graphormer models together. In this
work, we circumvented the need to train the BERT model by using a publicly
available pre-trained variant that was trained on Twitter and Gab data towards
detecting hateful comments. By fine-tuning a model directly on comments from
specific communities and towards our target task, we can create embeddings
that directly reflect the behaviours of the target community. We believe that
this could allow for better subreddit-specific performance.

Third, future work could investigate the interpretability of the graph
attention weights during inference, following past work in NLP [22]. This
could enable an exploration of the kinds of comments that enable hateful
discussions in specific communities, and the communal influence that enables
them.

Fourth, further analysis could be performed to compare community-specific
models. By analyzing the performance of one community model on posts from a
different community, it would be possible to derive insights on cultural
similarities. That is, models that perform well on other communities likely
share similar discussion norms. An example of such a comparison would be
evaluating the performance of the politics model on the_donald subreddit,
communities that are known to reflect contrasting political biases. This
direction could also expand to applying our model on other social platforms,
such as Twitter, in order to learn whether the performance of the approach is
equally strong in all environments. We will need to decide how best to model
discussions and communities within a platform such as Twitter, in order to
generate our results.

Lastly, it would be beneficial to conduct additional experiments in order to
draw out the real strength of our predictive approach to hate detection, in
comparison with simpler baselines which rely on simply tagging existing
comments. We would code a competitor which assumes that the initial post sets
the tone for the overall conversation of each discussion (i.e., all comments
that follow this post are labelled with the same level of hate detection). We
would then examine the performance of this method for detecting hate speech in
Reddit, both across all subreddits as well as in the specific communities
listed in Table IV, where the performance of our own approach in terms of L2
loss has already been measured. We would expect to see, for the baseline,
significant degradation on each subreddit. This would then confirm that the
initial post is often not indicative to predict the hateful labels of the
conversation and thus that our approach of incorporating attention to predict
hate patterns has significant value. For future work, we can also examine
other competitors that fail to incorporate context, perhaps in other social
media environments, to continue to calibrate the relative benefit of our
solution.

##  VI Conclusion

Social media have increasingly become the source of many damaging mental
health effects [1]. In this work, we proposed a system based on state-of-the-
art graph transformer models and deep language models to prevent the spread of
harmful discourse that has perpetuated these damaging effects. To evaluate our
system, we created a dataset that contains a collection of Reddit posts from
various communities. We hope that our system can be used by social media
moderators to curb the spread of harmful discourse by motivating the usage of
community specific models and the importance of capturing discourse context.

The scope of this work differs in several ways from previous work. First, we
studied the influence of communities regarding what content is shared and how
that content is reacted to. We accomplished this by including the entire
discussion graph during inference and creating specific models for individual
communities. This scope is different from traditional hate speech systems that
only examine the text of a comment in isolation, without considering the
discussion context or the community. As we have shown in our experimental
results, including more context, in terms of the discussion and the community,
can lead to better performance.

Second, the output of the model differed from previous work by predicting
ordinal values from 0 to 4, denoting how intense and encouraged the hateful
discussion will be following an initial comment. There are two benefits that
come with this objective. First, due to the increasing scope of social
platforms, it becomes important for moderators to prioritize which content to
investigate first and which content should be immediately quarantined. By
including a range of intensity values, we also support users of these
platforms to choose an intensity level that they are comfortable with. This
would allow users with mental health challenges to self-regulate the content
they want to see without restricting the free speech of users who are more
comfortable seeing intense content.

We also hope that the insights and tools created in this research can be used
to drive future research into enhanced social media moderation under a
proactive lens, especially as our lives and mental health become increasingly
connected to social platforms. With a deeper exploration of an entire tree of
discussion following a post and with a contextual attention mechanism that
improves the efficiency of predicting what may be yet to come, our approach
has the chance of detecting when a growing surge of negative expression may be
unleashed. By adapting a more proactive and less reactive approach to hate
speech, the hope is that fragile users may be better protected from the
effects of anti-social behaviour.

## Acknowledgment

The authors thank the Natural Sciences and Engineering Research Council of
Canada, the Canada Research Chairs Program and the University of Waterloo
Cheriton Scholarship for financial support. We are also grateful to the
reviewers for their valued feedback on the paper.

## References

  * [1] J. Gao, P. Zheng, Y. Jia, H. Chen, Y. Mao, S. Chen, Y. Wang, H. Fu, and J. Dai, “Mental health problems and social media exposure during covid-19 outbreak,” _PLOS ONE_ , no. 4, 2020.
  * [2] S. Obadinma, H. Guo, and X. Zhu, “Class-wise calibration: A case study on covid-19 hate speech,” _Canadian Conference on Artificial Intelligence_ , 6 2021.
  * [3] Q. Huang, D. Inkpen, J. Zhang, and D. Van Bruwaene, “Cyberbullying intervention based on convolutional neural networks,” in _First Workshop on Trolling, Aggression and Cyberbullying (TRAC-2018)_. Association for Computational Linguistics, Aug. 2018, pp. 42–51.
  * [4] E. Brassard-Gourdeau and R. Khoury, “Using sentiment information for preemptive detection of harmful comments in online conversations,” _Canadian Conference on Artificial Intelligence_ , 6 2021.
  * [5] M. Cinelli, G. De Francisci Morales, A. Galeazzi, W. Quattrociocchi, and M. Starnini, “The echo chamber effect on social media,” _National Academy of Sciences_ , vol. 118, no. 9, 2021.
  * [6] I. Waller and A. Anderson, “Quantifying social organization and political polarization in online platforms,” _Nature_ , vol. 600, no. 7888, pp. 264–268, Dec 2021.
  * [7] L. Belli, S. I. Ktena, A. Tejani, A. Lung-Yut-Fon, F. Portman, X. Zhu, Y. Xie, A. Gupta, M. Bronstein, A. Delić _et al._ , “Privacy-aware recommender systems challenge on twitter’s home timeline,” _arXiv_ , 2020\.
  * [8] B. Mathew, P. Saha, S. M. Yimam, C. Biemann, P. Goyal, and A. Mukherjee, “Hatexplain: A benchmark dataset for explainable hate speech detection,” in _AAAI_ , vol. 35, no. 17, 2021, pp. 14 867–14 875.
  * [9] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” _arXiv_ , 2019.
  * [10] C. Ying, T. Cai, S. Luo, S. Zheng, G. Ke, D. He, Y. Shen, and T.-Y. Liu, “Do transformers really perform badly for graph representation?” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 28 877–28 888, 2021\.
  * [11] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention is all you need,” 2017.
  * [12] W. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” _NeurIPS_ , vol. 30, 2017.
  * [13] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, “Graph attention networks,” _arXiv_ , 2017.
  * [14] M. Welling and T. N. Kipf, “Semi-supervised classification with graph convolutional networks,” in _ICLR_ , 2016.
  * [15] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural networks?” in _ICLR_ , 2019.
  * [16] A. Parmentier, J. P’ng, X. Tan, and R. Cohen, “Learning reddit user reputation using graphical attention networks,” in _Future Technologies Conference (FTC) 2020, Volume 1_ , 2021, pp. 777–789.
  * [17] A. Parmentier and R. Cohen, “Learning user reputation on reddit,” in _Web Intelligence (WI)_ , 2019, pp. 242–247.
  * [18] J. Pennington, R. Socher, and C. D. Manning, “Glove: Global vectors for word representation,” in _EMNLP_ , 2014, pp. 1532–1543.
  * [19] M. Fey and J. E. Lenssen, “Fast graph representation learning with pytorch geometric,” _arXiv_ , 2019.
  * [20] I. Loshchilov and F. Hutter, “Decoupled weight decay regularization,” in _ICLR_ , 2018.
  * [21] J. Chen, T. Ma, and C. Xiao, “Fastgcn: Fast learning with graph convolutional networks via importance sampling,” in _ICLR_ , 2018.
  * [22] S. Vashishth, S. Upadhyay, G. S. Tomar, and M. Faruqui, “Attention interpretability across nlp tasks,” _arXiv_ , 2019.