11institutetext: University of Pavia, Department of
Mathematics22institutetext: University of Milano-Bicocca, Department of
Mathematics and its Applications33institutetext: INdAM 44institutetext:
University of Strasbourg, IRMA

# A SAT Encoding to Compute Aperiodic Tiling Rhythmic Canons

Gennaro Auricchio 11 Luca Ferrarini 112233 Stefano Gualandi 11
Greta Lanzarotto 11223344 Ludovico Pernazza  11

###### Abstract

In Mathematical Music theory, the Aperiodic Tiling Complements Problem
consists in finding all the possible aperiodic complements of a given rhythm
$A$. The complexity of this problem depends on the size of the period $n$ of
the canon and on the cardinality of the given rhythm $A$. The current state-
of-the-art algorithms can solve instances with $n$ smaller than $180$. In this
paper we propose an ILP formulation and a SAT Encoding to solve this
mathemusical problem, and we use the Maplesat solver to enumerate all the
aperiodic complements. We validate our SAT Encoding using several different
periods and rhythms and we compute for the first time the complete list of
aperiodic tiling complements of standard Vuza rhythms for canons of period
$n=\\{180,420,900\\}$.

###### Keywords:

Mathematical models for music Aperiodic tiling rhythms SAT Encoding Integer
Linear Programming

##  1 Introduction

Mathematical Music Theory is the study of Music from a mathematical point of
view. Many connections have been discovered, some of which have a long
tradition, but they seem to be still offering new problems and ideas to
researchers, whether they be music composers or computer scientists. The first
attempt to produce music through a computational model dates back to $1957$,
when the authors composed a string quartet, also known as the Illiac Suite,
through random number generators and Markov chains [11]. Since then, a
plethora of other works have explored how computer science and music can
interact: to compose music [20, 21], to analyse existing compositions and
melodies [7, 8, 9], or even to represent human gestures of the music performer
[18]. In particular, Constraint Programming has been used to model harmony,
counterpoint and other aspects of music (e.g., see [4]), to compose music of
various genres as described in the book [3], or to impose musical
harmonization constraints in [16].

In this paper, we deal with Tiling Rhythmic Canons, that are purely rhythmic
contrapuntal compositions. For a fixed period $n$, a tiling rhythmic canon is
a couple of sets $A,B\subset\\{0,1,2,\dots,n-1\\}$ such that at every instant
there is exactly one voice playing; $A$ defines the sequence of beats played
by every voice, $B$ the instants at which voices start to play. If one of the
sets, say $A$, is given, it is well-known that the problem of finding a
_complement_ $B$ has in general no unique solution. It is very easy to find
tiling canons in which at least one of the set is _periodic_ , i.e. it is
built repeating a shorter rhythm. From a mathematical point of view, the most
interesting canons are therefore those in which both sets are _aperiodic_ (the
problem can be equivalently rephrased as a research of tessellations of a
special kind). Enumerating all aperiodic tiling canons has to face two main
hurdles: on one side, the problem lacks the structure of other algebraic ones,
such as ring or group theory; on the other side, the combinatorial size of the
domain becomes enormous very soon. Starting from the first works in the 1940s,
research has gradually shed some light on parts of the problem from a
theoretical point of view, and several heuristics and algorithms that allow to
compute tiling complements have been introduced, but a complete solution
appears to still be out of reach.

##### Contributions.

The main contributions of this paper are the Integer Linear Programming (ILP)
model and the SAT Encoding to solve the Aperiodic Tiling Complements Problem
presented in Section 3. Using a modern SAT solver we are able to compute the
complete list of aperiodic tiling complements of a class of Vuza rhythms for
periods $n=\\{180,420,900\\}$.

##### Outline.

The outline of the paper is as follows. Section 2 reviews the main notions on
Tiling Rhythmic Canons and defines formally the problem we tackle. In Section
3, we introduce an ILP model and a SAT Encoding of the Aperiodic Tiling
Complements Problem expressing the tiling and the aperiodicity constraints in
terms of Boolean variables. Finally, in Section 4, we include our
computational results to compare the efficiency of the aforementioned ILP
model and SAT Encoding with the current state-of-the-art algorithms.

##  2 The Aperiodic Tiling Complements Problem

We begin fixing some notation and giving the main definitions. In the
following, we conventionally denote the cyclic group of remainder classes
modulo $n$ by $\mathbb{Z}_{n}$ and its elements with the integers
$\\{0,1,\dots,n-1\\}$, i.e. identifying each class with its least non-negative
member.

######  Definition 1.

Let $A,B\subset\mathbb{Z}_{n}$. Let us define the application

$\sigma:A\times B\rightarrow\mathbb{Z}_{n},(a,b)\mapsto a+b.$

We set $A+B:=\mbox{Im}(\sigma)$; if $\sigma$ is bijective we say that $A$ and
$B$ are in direct sum, and we write

$A\oplus B:=\mbox{Im}(\sigma).$

If $\mathbb{Z}_{n}=A\oplus B$, we call $(A,B)$ a tiling rhythmic canon of
period $n$; $A$ is called the inner voice and $B$ the outer voice of the
canon.

######  Remark 1.

It is easy to see that the tiling property is invariant under translations,
i.e. if $A$ is a tiling complement of some set $B$, also any translate $A+z$
of $A$ is a tiling complement of $B$ (and any translate of $B$ is a tiling
complement of $A$). In fact, suppose that $A\oplus B=\mathbb{Z}_{n}$; for
every $k,z\in\mathbb{Z}_{n}$ by definition there exists one and only one pair
$(a,b)\in A\times B$ such that $k-z=a+b$. Consequently, there exists one and
only one pair $(a+z,b)\in(A+z)\times B$ such that $k=(a+z)+b$, that is
$(A+z)\oplus B=\mathbb{Z}_{n}$. In view of this, without loss of generality,
we shall limit our investigation to rhythms containing 0 and consider
equivalence classes under translation.

012345678 Figure 1: $A=\\{0,1,5\\}$ as inner voice.

012345678 Figure 2: $B=\\{0,3,6\\}$ as inner voice.

######  Example 1.

We consider a period $n=9$, and the two rhythms
$A=\\{0,1,5\\}\subset\mathbb{Z}_{9}$ and $B=\\{0,3,6\\}\subset\mathbb{Z}_{9}$
in Figure 2 and Figure 2. They provide the canon $A\oplus B=\mathbb{Z}_{9}$,
since $\\{0,1,5\\}\oplus\\{0,3,6\\}=\\{0,3,6,1,4,7,5,8,2\\}$, where the last
number is obtained by $(5+6)\mod 9=2$.

######  Definition 2.

A rhythm $A\subset\mathbb{Z}_{n}$ is periodic (of period $z$) if and only if
there exists an element $z\in\mathbb{Z}_{n}$, $z\neq 0$, such that $z+A=A$. In
this case, $A$ is also called periodic modulo $z\in\mathbb{Z}_{n}$. A rhythm
$A\subset\mathbb{Z}_{n}$ is aperiodic if and only if it is not periodic.

Coming back to Example 1, it is easy to note the periodicity $z=3$ in rhythm
$B=\\{0,3,6\\}$: indeed, $3+B=B$. Notice that if $A$ is periodic of period
$z$, $z$ must be a strict divisor of the period $n$ of the canon.

Tiling rhythmic canons can be characterised using polynomials, as follows.

######  Lemma 1.

Let $A$ be a rhythm in $\mathbb{Z}_{n}$ and let $p_{A}(x)$ be the
characteristic polynomial of $A$, that is, $p_{A}(x)=\sum_{k\in A}x^{k}$.
Given $B\subset\mathbb{Z}_{n}$ and its characteristic polynomial $p_{B}(x)$,
we have that

$p_{A}(x)\cdot p_{B}(x)\equiv\sum_{k=0}^{n-1}x^{k},\quad\quad\mod(x^{n}-1)$
(1)

if and only if $p_{A}(x),p_{B}(x)$ are polynomials with coefficients in
$\\{0,1\\}$ and $A\oplus B=\mathbb{Z}_{n}$.

######  Definition 3.

A tiling rhythmic canon $(A,B)$ in $\mathbb{Z}_{n}$ is a Vuza canon if both
$A$ and $B$ are aperiodic.

######  Remark 2.

Note that a set $A$ is periodic modulo $z$ if and only if it is periodic
modulo all the non-trivial multiples of $z$ dividing $n$. For this reason,
when it comes to check whether $A$ is periodic or not, it suffices to check if
$A$ is periodic modulo $m$ for every $m$ in the set of maximal divisors of
$n$. We denote by $\mathcal{D}_{n}$ this set:

$\mathcal{D}_{n}:=\big{\\{}n/p\mid p\mbox{ is a prime factor of }n\big{\\}}.$

We also denote with $k_{n}$ the cardinality of $\mathcal{D}_{n}$, so that
$n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\dots p_{k_{n}}^{\alpha_{k_{n}}}$ is
the unique prime factorization of $n$, where
$\alpha_{1},\dots,\alpha_{k_{n}}\in\mathbb{N^{+}}$ .

For a complete and exhaustive discussion on tiling problems, we refer the
reader to [2]. In this paper, we are interested in the following tiling
problem.

######  Definition 4.

Given a period $n\in\mathbb{N}$ and a rhythm $A\subset\mathbb{Z}_{n}$, the
Aperiodic Tiling Complements Problem consists in finding all aperiodic
complements $B$ i.e., subsets $B$ of $\mathbb{Z}_{n}$ such that $A\oplus
B=\mathbb{Z}_{n}$.

Some problems very similar to the decision of tiling (i.e., the tiling
decision problem DIFF in [13]) have been shown to be NP-complete; a strong
lower bound for computational complexity of the tiling decision problem is to
be expected, too.

##  3 A SAT Encoding

In this section, we present in parallel an ILP model and a new SAT Encoding
for the Aperiodic Tiling Complements Problem that are both used to enumerate
all complements of $A$. We define two sets of constraints: (i) the tiling
constraints that impose the condition $A\oplus B=\mathbb{Z}_{n}$, and (ii) the
aperiodicity constraints that impose that the canon $B$ is aperiodic.

##### Tiling constraints.

Given the period $n$ and the rhythm $A$, let
$\bm{a}=[a_{0},\dots,a_{n-1}]^{\intercal}$ be its characteristic (column)
vector, that is, $a_{i}=1$ if and only if $i\in A$. Using vector $\bm{a}$ we
define the circulant matrix $T\in\\{0,1\\}^{n\times n}$ of rhythm $A$, that
is, each column of $T$ is the circular shift of the first column, which
corresponds to vector $\bm{a}$. Thus, the matrix $T$ is equal to

$T=\begin{bmatrix}a_{0}&a_{n-1}&a_{n-2}&\dots&a_{1}\\\
a_{1}&a_{0}&a_{n-1}&\dots&a_{2}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
a_{n-1}&a_{n-2}&a_{n-3}&\dots&a_{0}\end{bmatrix}.$

We can use the circulant matrix $T$ to impose the tiling conditions as
follows. Let us introduce a literal $x_{i}$ for $i=0,\dots,n-1$, that
represents the characteristic vector of the tiling rhythm $B$, that is,
$x_{i}=1$ if and only if $i\in B$. Note that a literal is equivalent to a 0–1
variable in ILP terminology. Then, the tiling condition can be written with
the following linear constraint:

$\sum_{i\in\\{0,\dots,n-1\\}}T_{ij}x_{i}=1,\quad\forall j=0,\dots,n-1.$ (2)

Notice that the set of linear constraints (2) imposes that exactly one
variable (literal) in the set $\\{x_{{n+i-j\mod n}}\\}_{j\in A}$ is equal to
one. Hence, we encode this condition as an Exactly-one constraint, that is,
exactly one literal can take the value one. The Exactly-one constraint can be
expressed as the conjunction of the two constraints At-least-one and At-most-
one, for which standard SAT encoding exist (e.g., see [6, 17]). Hence, the
tiling constraints (2) are encoded with the following set of clauses depending
on $i=0,\dots,n-1$:

$\bigvee_{j\in A}\left(x_{n-(j-i)\mod n}\right)\bigwedge_{k,l\in A,k\neq
l}\left(\lnot x_{{n-(k-i)\mod n}}\lor\lnot x_{{n-(l-i)\mod n}}\right).$ (3)

##### Aperiodicity constraints.

In view of Definition 2, if there exists a $b\in B$ such that $(d+b)\mod n\neq
b$, then the canon $B$ is not periodic modulo $d$. Notice that by Remark 2 we
need to check this condition only for the values of $d\in\mathcal{D}_{n}$.

We formulate the aperiodicity constraints introducing auxiliary variables
$y_{d,i},z_{d,i},u_{d,i}\in\\{0,1\\}$ for every prime divisor
$d\in\mathcal{D}_{n}$ and for every integer $i=0,\dots,d-1$. We set

$u_{d,i}=1\;\Leftrightarrow\;\left(\sum_{k=0}^{n/d-1}x_{i+kd}=\frac{n}{d}\right)\vee\left(\sum_{k=0}^{n/d-1}x_{i+kd}=0\right),$
(4)

for all $d\in\mathcal{D}_{n}$, $i=0,\dots,d-1$, with the condition

$\sum_{i=0}^{d-1}u_{d,i}\leq d-1,\quad\forall d\in\mathcal{D}_{n}.$ (5)

Similarly to [5], the constraints (4) can be linearized using standard
reformulation techniques as follows:

$\displaystyle
0\leq\sum_{k=0}^{n/d}x_{i+kd}-\frac{n}{d}y_{d,i}\leq\frac{n}{d}-1$
$\displaystyle\forall d\in\mathcal{D}_{n},\;\;i=0,\dots,d-1,$ (6)
$\displaystyle
0\leq\sum_{k=0}^{n/d}(1-x_{i+kd})-\frac{n}{d}z_{d,i}\leq\frac{n}{d}-1$
$\displaystyle\forall d\in\mathcal{D}_{n},\;\;i=0,\dots,d-1,$ (7)
$\displaystyle y_{d,i}+z_{d,i}=u_{d,i}$ $\displaystyle\forall
d\in\mathcal{D}_{n},\;\;i=0,\dots,d-1.$ (8)

Notice that when $u_{d,i}=1$ exactly one of the two incompatible alternatives
in the right hand side of (4) is true, while whenever $u_{d,i}=0$ the two
constraints are false. Correspondingly, the constraint (8) imposes that the
variables $y_{d,i}$ and $z_{d,i}$ cannot be equal to $1$ at the same time. On
the other hand, constraint (5) imposes that at least one of the auxiliary
variables $u_{d,i}$ be equal to zero.

Next, we encode the previous conditions as a SAT formula. To encode the if and
only if clause, we make use of the logical equivalence between
$C_{1}\Leftrightarrow C_{2}$ and $(\lnot C_{1}\lor C_{2})\land(C_{1}\lor\lnot
C_{2})$. The clause $C_{1}$ is given directly by the literal $u_{d,i}$. The
clause $C_{2}$, expressing the right hand side of (4), i.e. the constraint
that the variables must be either all true or all false, can be written as

$C_{2}=\left(\bigwedge_{k=0}^{n/d}x_{i+kd}\right)\vee\left(\bigwedge_{k=0}^{n/d}\bar{x}_{i+kd}\right),\quad\forall
d\in\mathcal{D}_{n}.$

Then, the linear constraint (5) can be stated as the SAT formula:

$\lnot\left(u_{d,0}\land u_{d,1}\land\dots\land
u_{d,(d-1)}\right)=\bigvee_{l=0}^{d-1}\bar{u}_{d,l},\quad\forall
d\in\mathcal{D}_{n}.$

Finally, we express the aperiodicity constraints using

$\bigwedge\limits_{i=0}^{d-1}\left[\left(\lnot C_{2}\lor
u_{d,i}\right)\land\left(C_{2}\lor\bar{u}_{d,i}\right)\right]\land\bigvee_{l=0}^{d-1}\bar{u}_{d,l},\,\forall
d\in\mathcal{D}_{n}.$ (9)

Note that joining (2), (6)–(8) with a constant objective function gives a
complete ILP model, which can be solved with a modern ILP solver such as
Gurobi to enumerate all possible solutions. At the same time, joining (3) and
(9) into a unique CNF formula, we get our complete SAT Encoding of the
Aperiodic Tiling Complements Problem. (see Section 4 for computational
results).

###  3.1 Existing solution approaches

For the computation of all the aperiodic tiling complements of a given rhythm
the two most successful approaches already known are the _Fill-Out Procedure_
[14] and the Cutting Sequential Algorithm [5].

##### The Fill-Out Procedure.

The _Fill-Out Procedure_ is the heuristic algorithm introduced in [14]. The
key idea behind this algorithm is the following: given a rhythm
$A\subset\mathbb{Z}_{n}$ such that $0\in A$, the algorithm sets $P=\\{0\\}$
and starts the search for possible expansions of the set $P$. The expansion is
accomplished by adding an element $\alpha\in\mathbb{Z}_{n}$ to $P$ according
to the reverse order induced by a ranking function $r(x,P)$, which counts all
the possible ways in which $x$ can be covered through a translation of $A$.
This defines a new set, $\tilde{P}\supset P$, which is again expanded until
either it can no longer be expanded or the set becomes a tiling complement.
The search ends when all the possibilities have been explored. The algorithm
finds also periodic solutions that must removed in post-processing, as well as
multiple translations of the same rhythm.

##### The Cutting Sequential Algorithm (CSA).

In [5], the authors formulate the Aperiodic Tiling Complements Problem using
an Integer Linear Programming (ILP) model that is based on the polynomial
characterization of tiling canons. The ILP model uses auxiliary 0–1 variables
to encode the product $p_{A}(x)\cdot p_{B}(x)$ which characterizes tiling
canons. The aperiodicity constraint is formulated analogously to what done
above. The objective function is equal to a constant and does not impact the
solutions found by the model. The ILP model is used within a sequential
cutting algorithm that adds a no-good constraint every time a new canon $B$ is
found to prevent finding solutions twice. In addition, the sequential
algorithm sets a new no-good constraints for every translation of $B$; hence,
in contrast to the _Fill-Out Procedure_ , the _CSA Algorithm_ does not need
any post-processing.

##  4 Computational Results

First, we compare the results obtained using our ILP model and SAT Encoding
with the runtimes of the _Fill-Out Procedure_ and of the _CSA Algorithm_. We
use the canons with periods 72, 108, 120, 144 and 168 that have been
completely enumerated by Vuza [19], Fripertinger [10], Amiot [1], Kolountzakis
and Matolcsi [14]. Table 1 shows clearly that the two new approaches
outperform the state-of-the-art, and in particular, that SAT provides the best
solution approach. We then choose some periods $n$ with more complex prime
factorizations, such as $n=p^{2}q^{2}r=180$, $n=p^{2}qrs=420$, and
$n=p^{2}q^{2}r^{2}=900$. To find aperiodic rhythms $A$, we apply Vuza’s
construction [19] with different choices of parameters $p_{1}$, $p_{2}$,
$n_{1}$, $n_{2}$, $n_{3}$. Thus, having $n$ and $A$ as inputs, we search for
all the possible aperiodic complements and then we filter out the solutions
under translation. Since the post-processing is based on sorting canons, it
requires a comparatively small amount of time. We report the results in Table
2: the solution approach based on the SAT Encoding is the clear winner (from a
Music theory perspective, it is also noteworthy that this is the first time
that all the tiling complements, whose number is reported in the last column
of the two tables, of the studied rhythms are computed).

##### Implementation Details.

We have implemented in Python the ILP model and in PySat [12] the SAT Encoding
discussed in Section 3. We use Gurobi 9.1.1 as ILP solver and Maplesat [15] as
SAT solver. The experiments are run on a Dell Workstation with a Intel Xeon
W-2155 CPU with 10 physical cores at 3.3GHz and 32 GB of RAM. In case of
acceptance, we will release the source code and the instances on GitHub.

####  4.0.1 Conclusions and Future Work.

It is thinkable to devise an algorithm that, for a given $n$, finds all the
pairs $(A,B)$ that give rise to a Vuza canon of period $n$. This could provide
in-depth information on the structure of Vuza canons.

####  4.0.2 Acknowledgements.

This research was partially supported by: Italian Ministry of Education,
University and Research (MIUR), Dipartimenti di Eccellenza Program (2018–2022)
- Dept. of Mathematics “F. Casorati”, University of Pavia; Dept. of
Mathematics and its Applications, University of Milano-Bicocca; National
Institute of High Mathematics (INdAM) “F. Severi”; Institute for Advanced
Mathematical Research (IRMA), University of Strasbourg.

Table 1: Aperiodic tiling complements for periods
$n\in\\{72,108,120,144,168\\}$.

$n$ $\mathcal{D}_{n}$ $p_{1}$ $n_{1}$ $p_{2}$ $n_{2}$ $n_{3}$ runtimes (s)
$\\#B$ _FOP_ _CSA_ _SAT_ _ILP_ 72 $\\{24,36\\}$ 2 2 3 3 2 1.59 0.10 $<0.01$
0.03 6 108 $\\{36,54\\}$ 2 2 3 3 3 896.06 7.84 0.09 0.19 252 120
$\\{24,40,60\\}$ 2 2 5 3 2 24.16 0.27 0.02 0.04 18 2 2 3 5 2 10.92 0.14 0.01
0.04 20 144 $\\{48,72\\}$ 4 2 3 3 2 82.53 2.93 0.02 0.11 36 2 2 3 3 4
$>10800.00$ $>10800.00$ 11.04 46.96 8640 2 2 3 3 4 7.13 0.10 $<0.01$ 0.05 6 2
4 3 3 2 80.04 0.94 0.02 0.08 60 168 $\\{24,56,84\\}$ 2 2 7 3 2 461.53 17.61
0.04 0.20 54 2 2 3 7 2 46.11 0.91 0.02 0.07 42

Table 2: Aperiodic tiling complements for periods $n\in\\{180,420,900\\}$.

$n$ $\mathcal{D}_{n}$ $p_{1}$ $n_{1}$ $p_{2}$ $n_{2}$ $n_{3}$ runtimes (s)
$\\#B$ _SAT_ _ILP_ 180 $\\{36,60,90\\}$ 2 2 5 3 3 2.57 5.62 2052 3 3 5 2 2
0.07 0.14 96 2 2 3 5 3 1.25 2.23 1800 2 5 3 3 2 0.05 0.16 120 2 2 3 3 5
8079.07 $>10800.00$ 281232 420 $\\{60,84,140,210\\}$ 7 5 3 2 2 2.13 3.57 720 5
7 3 2 2 1.52 4.08 672 7 5 2 3 2 7.73 16.11 3120 5 7 2 3 2 1.63 4.18 1008 7 3 5
2 2 4.76 7.45 864 3 7 5 2 2 12.78 32.19 6720 7 3 2 5 2 107.83 1186.21 33480 3
7 2 5 2 0.73 2.36 840 7 2 5 3 2 11.14 21.19 1872 2 7 5 3 2 17.31 52.90 10080 7
2 3 5 2 89.97 691.56 22320 2 7 3 5 2 1.17 4.13 1120 900 $\\{180,300,450\\}$ 2
25 3 3 2 43.60 110.65 15600 5 10 3 3 2 107.36 741.79 15840 2 9 5 5 2 958.58
$>10800.00$ 118080 6 3 5 5 2 5559.76 $>10800.00$ 123840 3 6 5 5 2 486.39
8290.35 62160

## References

  * [1] Amiot, E.: New perspectives on rhythmic canons and the spectral conjecture. Journal of Mathematics and Music 3(2), 71–84 (2009)

  * [2] Amiot, E.: Structures, algorithms, and algebraic tools for rhythmic canons. Perspectives of new music 49(2), 93–142 (2011)
  * [3] Anders, T.: Compositions created with constraint programming. The Oxford Handbook of Algorithmic Music (2018)
  * [4] Anders, T., Miranda, E.R.: Constraint programming systems for modeling music theories and composition. ACM Computing Surveys (CSUR) 43(4), 1–38 (2011)
  * [5] Auricchio, G., Ferrarini, L., Lanzarotto, G.: An integer linear programming model for tilings. arXiv preprint arXiv:2107.04108 (2021)
  * [6] Bailleux, O., Boufkhad, Y.: Efficient cnf encoding of boolean cardinality constraints. In: International conference on principles and practice of constraint programming. pp. 108–122. Springer (2003)
  * [7] Chemillier, M., Truchet, C.: Two musical csps. In: CP 01 Workshop on Musical Constraints. pp. 1–1 (2001)
  * [8] Courtot, F.: A constraint-based logic program for generating polyphonies. Ann Arbor, MI: Michigan Publishing, University of Michigan Library (1990)
  * [9] Ebcioğlu, K.: An expert system for harmonizing four-part chorales. Computer Music Journal 12(3), 43–51 (1988)
  * [10] Fripertinger, H., Reich, L., et al.: Remarks on rhythmical canons. Citeseer (2005)
  * [11] Hiller Jr, L.A., Isaacson, L.M.: Musical composition with a high speed digital computer. In: Audio Engineering Society Convention 9. Audio Engineering Society (1957)
  * [12] Ignatiev, A., Morgado, A., Marques-Silva, J.: PySAT: A Python toolkit for prototyping with SAT oracles. In: SAT. pp. 428–437 (2018)
  * [13] Kolountzakis, M.N., Matolcsi, M.: Complex Hadamard matrices and the spectral set conjecture. Collectanea Mathematica Extra, 281–291 (2006)
  * [14] Kolountzakis, M.N., Matolcsi, M.: Algorithms for translational tiling. Journal of Mathematics and Music 3(2), 85–97 (2009)
  * [15] Liang, J.H.: Machine Learning for SAT Solvers. Ph.D. thesis, University of Waterloo (Dec 2018)
  * [16] Pachet, F., Roy, P.: Musical harmonization with constraints: A survey. Constraints 6(1), 7–19 (2001)
  * [17] Philipp, T., Steinke, P.: Pblib–a library for encoding pseudo-boolean constraints into cnf. In: International Conference on Theory and Applications of Satisfiability Testing. pp. 9–16. Springer (2015)
  * [18] Radicioni, D.P., Lombardo, V.: A constraint-based approach for annotating music scores with gestural information. Constraints 12(4), 405–428 (2007)
  * [19] Vuza, D.T.: Supplementary sets and regular complementary unending canons (part one, two, three, four). Perspectives of New Music (1991-93)
  * [20] Wiggins, G., Harris, M., Smaill, A.: Representing music for analysis and composition. In: Proceedings of the 2nd IJCAI AI/Music Workshop. pp. 63–71 (1989)
  * [21] Zimmermann, D.: Modelling musical structures. Constraints 6(1), 53–83 (2001)


# Are GAN-based Morphs Threatening Face Recognition?

###### Abstract

Morphing attacks are a threat to biometric systems where the biometric
reference in an identity document can be altered. This form of attack presents
an important issue in applications relying on identity documents such as
border security or access control. Research in generation of face morphs and
their detection is developing rapidly, however very few datasets with morphing
attacks and open-source detection toolkits are publicly available. This paper
bridges this gap by providing two datasets and the corresponding code for four
types of morphing attacks: two that rely on facial landmarks based on OpenCV
and FaceMorpher, and two that use StyleGAN 2 to generate synthetic morphs. We
also conduct extensive experiments to assess the vulnerability of four state-
of-the-art face recognition systems, including FaceNet, VGG-Face, ArcFace, and
ISV. Surprisingly, the experiments demonstrate that, although visually more
appealing, morphs based on StyleGAN 2 do not pose a significant threat to the
state to face recognition systems, as these morphs were outmatched by the
simple morphs that are based facial landmarks.

Index Terms—  Biometrics, Face Recognition, Vulnerability Analysis, Morphing
Attack, StyleGAN 2

##  1 Introduction

00footnotetext: Work funded by the Swiss Center for Biometrics Research and
Testing.

(a) Identity A

(b) OpenCV

(c) FaceMorpher

(d) StyleGAN2

(e) MIPGAN-II

(h) Identity B

Fig. 1: Different types of generated morphed images from two identities in the
FRLL dataset.

After Ferrara _et al._ [1] showed that by using a morphed photo of two
different people an adversary can circumvent passport registration process,
morphing attacks and how to detect them received a lot of attention from
academic, industrial, and security communities. The vulnerability of state-of-
the-art (SOTA) face recognition systems (FR) and the threat such vulnerability
poses to the security systems relying on recognition technologies led to the
explosion of research work in this area.

Most of the work related to morphing attacks (MAs) focuses on their detection.
Recently proposed techniques for morphing attack detection (MAD) include
methods based on _so called_ classical approaches using local binary patterns
(LBP) and support vector machines (SVM) [2], approaches rooted in image
forensics that rely on photo response non uniformity (PRNU) function [3], deep
neural networks specifically trained to detect morph images [4], and FR
systems themselves serving as feature extractors for an support vector machine
(SVM) classifier [5]. The National Institute of Standards and Technology
(NIST) is now conducting independent evaluations of MAD technologies [6].

However the research in the area of morphing attacks and their detection
suffers from a lack of datasets, evaluation protocols, and clear understanding
of whether the latest face recognition systems are vulnerable to both
‘classical’ and the latest generative adversarial network (GAN)-based morphing
attacks. So called ‘classical’ landmark-based morphing techniques are widely
available, but the modern ones are rarely publicly released. Novel methods are
often either proprietary, such as Combined Morphs [7], or are difficult to
replicate from a published description without knowing the minutes technical
details. Pre-generated databases of morphing attacks are therefore essential
for biometrics research, yet only a few, like the Face Morph Image dataset [7]
by Advanced Multimedia Security Lab, are publicly available.

Therefore, this paper provides the following contributions:

  1. 1.

We provide an open source morphing
tool111https://gitlab.idiap.ch/bob/bob.paper.icassp2022_morph_generate for
generation of morphing attacks based on OpenCV [8], FaceMorpher [9], StyleGAN
2 [10], and our modified implementation of MIPGAN-II [11].

  2. 2.

We provide publicly available datasets11footnotemark: 1 with morphed images
generated using the aforementioned techniques, including the latest GAN-based
morphs, on the publicly available FERET [12] and Face Research Lab London
(FRLL) [13] datasets.

  3. 3.

We conduct an extensive vulnerability assessment of the different morphing
attacks images in our generated dataset against SOTA face recognition systems,
used in some of the latest morphing attacks vulnerability studies [14]. We
specifically use the FaceNet [15] VGG-Face [16], ArcFace [17], and ISV [18]
systems, which are pre-trained on ‘clean’ bona fide databases.

We also highlight that the majority of existing work on Morphing Attacks (MAs)
only consider the ‘typical’ scenario where the morphs are used to attack the
enrollment process of face recognition. This paper, to the best of our
knowledge is amount the the first to evaluate two scenarios: i) when morphs
attack the the enrollment process, and ii) when they are used to attack the
probing process, which is similar to a presentation attack [19].

##  2 Morph Generation

In this section, we present the datasets with bona fide faces and the
different tools, including GAN-based, that we use to generate the morphing
images for the vulnerability experiments.

###  2.1 Datasets

We used FERET [12] and FRLL [13] datasets of facial images to generate the
morphs. FERET was selected because it is the _de facto_ the standard datasets
commonly used in papers on morphing attack detection [20, 14] and it has large
number of images of different identities. The FRLL dataset is also ideal for
creating morphing attacks because it contains close-up frontal face images of
very high visual quality and $1350\times 1350$ resolution, shot under uniform
illumination with large varieties in ethnicity, pose, and expression. Each
face is annotated using $189$ facial landmarks, which is notably a very high
number, as typical landmarks detectors provide no more than $68$-$70$
landmarks. The main limitation of FRLL dataset, compared to FERET, is the
limited number $102$ of different identities with $53$ males and $49$ females.

For each dataset, we select bona fide (or original) face pairs for morph
generation by following the existing protocols used in previous work. For
FERET, we follow the protocols used in the work by Scherhag _et al._ [14] that
were kindly provided by the authors. For FRLL dataset, we follow the protocols
used in AMSL Face Morph Image dataset by Neubert _et al._ [7]. Using these
protocols (essentially, which facial image pairs to morph), we generated
morphs using four different methods: based on OpenCV, based on FaceMorpher,
based on StyleGAN 2, and a modified MIPGAN-II [11].

###  2.2 Morphing Tools

As representatives of the ‘classical‘ landmark-based morphing tools, we
provide two commonly used open source face morphing algorithms. First one is
the OpenCV-based algorithm, referred throughout the paper as OpenCV, which is
an adaptation of an open-source implementation [8] for morphing faces using
$68$-point annotator from Dlib library [21]. Face landmarks are obtained for
each of the two bona fide source images and are used to form Delaunay
triangles, which are in-turn warped and alpha blended.

FaceMorpher [9], referred to as FaceMorpher, is another open-source landmark-
based morphing algorithm, but with the STASM [22] landmark detector instead.
Both algorithms create morphs with noticeable ghosting artefacts for all three
datasets, as the region outside the area covered by these landmarks is simply
averaged.

Following the advances in generative adversarial networks (GANs), there were
attempts to generate morphed images using a GAN instead of landmark-based
methods [23, 24]. In this paper, we adapted the latest StyleGAN 2 [10],
referred throughout the paper as StyleGAN2, to develop a morphing algorithm
which can generate high resolution realistic looking faces with no noticeable
artifacts. The StyleGAN 2 was pre-trained on the FFHQ dataset introduced in
[25].

The faces are cropped to obtain the same landmark alignment as in the FFHQ
dataset. The images are then projected into the $\mathcal{W}$ space of
StyleGAN 2 by optimizing the input latent style vector that is fed to the
generator network, such that it minimizes the perceptual loss between the
generated and real image [10]. Once an associated latent vector has been
computed for each of the source images, morphs can be generated by linearly
interpolating between two latent vectors, and feeding the interpolated vector
back into the generator.

This technique yields very realistic looking morphs without visual artefacts,
however, since StyleGAN does not have any information about the identities in
bona fide images, there is no guarantee that the resulted morph is actually a
blend of these identities (see the example in Figure 1(d) for an idea).

For this purpose, we implemented a modified version of the recent MIPGAN-II
technique [11], referred throughout the paper as MIPGAN-II, which improves on
the StyleGAN 2 morphs, by further optimizing the interpolated latent vector
with four additional weighted losses, which help to preserve the identity
information and structural correspondence of the two bona-fide images. The
main difference in our versions of MIPGAN is that we use the pre-trained
VGGFace model with the ResNet50 backbone as feature extractor in the identity
loss, instead of a pre-trained embedding extractor with ResNet50 as backbone
using the ArcFace loss.

Both, StyleGAN2 and MIPGAN-II GAN-based morphs require the projected images to
be at a high resolution ($1024\times 1024$ after cropping), and work better
with an uniform background, which makes the FRLL dataset particularly
appropriate. A side note observation of using GAN-based techniques for
generating morphs is that it is equally easy to generate high-quality morphs
for smiling expressions as it is for the neutral faces, which is not possible
with typical landmark-based tools.

Using four (two ‘classical’ and two GAN-based) morphing tools, we generate
$529$ morphs per each tool for FERET datasets using the same protocols as in
[14], and $1222$ morphs per tool images for FRLL, following the morph
generation protocol defined in ASML Face Morph Image dataset. It is to be
noted that the protocols insure not to morph across genders and ethnicities,
and only interpolate images if neither or only one of the two subjects is
wearing glasses.

##  3 Evaluation Protocols

###  3.1 Face Recognition Systems

To evaluate vulnerability of face recognition against morphing attacks, we
used publicly available pre-trained FaceNet [15], ArcFace [17], and VGG-Face
[16] architectures. We used the last fully connected layers of these networks
as features and the cosine distance as a classifier. For a given test face,
the confidence score of whether it belongs to a reference model is the cosine
distance between the average reference feature vector and the feature vector
of a test face. These systems are the state of the art recognition systems
with Facenet showing $99.63\%$ [15], ArcFace – $99.53$ [17], and VGG-Face –
$98.95\%$ [16] accuracies on the labeled faces in the wild (LFW) dataset.

We also used an inter-session variability (ISV) based face recognition [18],
pre-trained on the MOBIO [26] dataset, as a ‘classical’ baseline. The DCT
features computed on overlapping blocks of $40\times 40$ were used for the
ISV-based system of $512$ Gaussian mixture models (GMMs) and $160$ dimensional
subspace.

###  3.2 Evaluation Metrics

In a verification process, the user attempting to authenticate presents a
biometric probe and a claimed identity, and can be classified into one of the
following 3 categories. A) Genuine user (BF): probe and claimed identity both
correctly belong to the user. B) Zero-effort impostor (BF): probe belongs to
the user, but the claimed identity corresponds to a different enrolled user.
C) Morph attack impostor (MA): probe matches the claimed identity but does not
correspond to the user.

The verification performance is typically evaluated with the following
metrics.

  * •

False Match Rate (FMR) [20]: proportion of zero-effort impostors that are
falsely authenticated.

  * •

False Non-Match Rate (FNMR) [20]: proportion of genuine users which are
falsely rejected.

  * •

Mated Morph Presentation Match Rate (MMPMR) [27]: proportion of morphs attacks
impostors accepted by the face recognition system.

###  3.3 Evaluation scenarios

In general, there are two main scenarios under which a face recognition system
is evaluated: a bona fide (BF) scenario where both the reference and probes
images as genuine, so there are no attacks and the system is assumed to
perform under the conditions it was designed for; and the morphing attack (MA)
scenario when morphs are introduced to the face recognition with a malicious
intent to spoof the recognition. There are also two variants of MA scenario,
when a morphed image can be either used as a reference, i.e., FR system is
hijacked during enrollment process (typical morphing attack scenario), or a
morphed image is used as a probe, which is similar to presentation attack
scenario [19].

The number of reference and probe images for each evaluation scenario is
summarized in Table 1.

Table 1: Number of images in different evaluation scenarios. Dataset | Morphs as | BF | MA | Impostors
---|---|---|---|---
FERET | References | 529 | 791 | 418,439
Probes | 791 | 529 | 418,439
FRLL | References | 91 | 584 | 1,984
Probes | 584 | 91 | 4,153

It is also to be noted that we did not split datasets into training,
development, and test subsets but used each whole dataset as one single test
set, as all used FR systems were pre-trained on other databases. Furthermore,
we choose the decision threshold to compute MMPMR value for MA scenario based
on FMR value computed in the bona fide scenario, thus removing the need for a
development set.

##  4 Experimental Results

Table 2 summarizes the results of the vulnerability assessment of the several
face recognition systems (described in section 3.1) under the different
morphing attack scenarios (as explained in section 3.3). The MMPMR metric is
calculated by setting the decision threshold at FMR=$0.1$% in the bona fide
scenario.

Table 2: MMPMR @ FMR = 0.1%
(Morphs as references — Morphs as probes) [%] Tools | FRS | FRLL | FERET
---|---|---|---
OpenCV | FaceNet | 83.3 — 72.0 | 41.1 — 40.6
Arcface | 59.8 — 73.8 | 34.6 — 35.2
VGG | 39.7 — 48.6 | 22.0 — 21.0
| ISV | 59.8 — 97.8 | 44.8 — 58.4
FaceMorpher | FaceNet | 64.5 — 68.2 | 39.9 — 40.3
Arcface | 57.6 — 75.3 | 34.1 — 34.8
VGG | 23.4 — 47.1 | 20.5 — 18.3
ISV | 56.1 — 96.1 | 42.6 — 56.5
StyleGAN2 | FaceNet | 5.9 — 11.0 | 1.6 — 1.3
Arcface | 9.8 — 18.3 | 2.4 — 2.5
VGG | 3.0 — 9.1 | 2.0 — 1.5
ISV | 9.2 — 43.6 | 2.7 — 3.4
MIPGAN-II | FaceNet | 47.2 — 62.7 | 32.9 — 32.3
Arcface | 32.0 — 46.5 | 26.0 — 25.1
VGG | 15.9 — 30.4 | 14.5 — 13.2
ISV | 3.6 — 23.7 | 7.3 — 9.6

The results in Table 2 reveal a number of interesting observations. The
StyleGAN2-morphs do not pose a significant threat to the state of the art face
recognition systems, compared to landmark-based morphs, despite being of
higher visual quality, and with very few ghosting artefacts. This likely
occurs because the original pixels of both contributing images are still
present in the features after landmark-based morph-generation pipeline is
applied, and are later picked up during face recognition, thus successfully
fooling the FR systems. Conversely, the StyleGAN pipeline conserves no pixel
traces of the original contributing subjects, other than the positions of the
facial landmarks, as it generates the morphed image by interpolating the
projected vectors in the $\mathcal{W}$ latent space. The interpolated vector
fed back through the synthesis network does not contain the features of both
identities, and instead is perceived as a new, different identity altogether.

This is further proved when the MIPGAN-II morphs which purposefully use four
additional losses to further optimize the generated morph in an attempt to
conserve the identities of the two source subjects: the vulnerability is
significantly higher than with naive linear-interpolation in the StyleGAN
$\mathcal{W}$ space. However, our implementation of MIPGAN-II lead to twice as
low MMPMR rates compared to the numbers reported in original MIPGAN-II paper
[11]. Such significant disparity in results is puzzling but a few elements
could contribute to it:

A) It appears that rather than using the $\mathcal{W}$ space of StyleGAN 2 for
generating the morphs, as we did in our implementation, the authors of MIPGAN-
II paper [11] instead used the $\mathcal{W+}$ [28] latent space of StyleGAN,
as they seem to describe their latent projections as a concatenation of $18$
different $512$-dimensional $w$ vectors, one for each layer of the StyleGAN
architecture. We believe that using $\mathcal{W}$ space is more reasonable as
operating in $\mathcal{W+}$ does not guarantee a visual realism of resulted
morphs. However, this point is hard to verify, since the authors of MIPGAN-II
[11] did not release their code and their paper is not very explicit about
this aspect.

B) The pre-trained StyleGAN model in [11] was fine-tuned on their test dataset
(FRGCv2 [29]), which made the generated morphs to appear visually and
structurally very similar to the original images in the dataset. This type of
‘trick’ clearly would increase the chanced of the morphs to be more
threatening to face recognition, which was tested on the same dataset.

Table 2 also demonstrates that the more accurate face recognition system is
the more vulnerable it is to morphing attacks, which is also in line with the
findings reported for presentation attacks [30]. This trend is especially
evident when we compare a more accurate and deeper FaceNet architecture with
VGG for all databases and types of morphs.

We can also notice that the results for the scenario when morphs attack the
enrollment process (see ‘morphs as references’ sub-columns in Table 2) are
very similar to the results for the scenario when morphs are used as probes
(see ‘morphs as probes’ sub-columns) for the FERET morphs database. However,
in the case of FRLL, the face recognition systems are clearly more vulnerable
to the scenario when morphs are used as probes. It means that the quality of
original images used to create morphs may lead to more threatening morphs in
the presentation attack scenarios, rather than when attacking FR systems from
the inside.

##  5 Conclusion

In this paper, we assess the level of vulnerability of existing face
recognition systems, based on VGG-Face, ArcFace, and FaceNet neural network
models, against four morphing attacks, including two ‘classical’ morphs based
on facial landmarks and two based on StyleGAN 2. The results demonstrate that
‘classical’ morphs still are of the highest threat to the face recognition
while GAN-based morphs, despite their higher visual appeal, do not pose as
much of a thread to automated system. We also note that the face recognition
systems that are better at recognition are also more vulnerable to morphing
attacks. We publicly release the databases we generated and used, and provide
all tools for generating morphs and running the evaluation experiments as an
open source package.

## References

  * [1] M. Ferrara, A. Franco, and D. Maltoni,  “The magic passport,”  in IEEE International Joint Conference on Biometrics, 2014, pp. 1–7.
  * [2] L. Spreeuwers, M. Schils, and R. Veldhuis,  “Towards robust evaluation of face morphing detection,”  in 2018 26th European Signal Processing Conference (EUSIPCO), 2018, pp. 1027–1031.
  * [3] U. Scherhag, L. Debiasi, C. Rathgeb, C. Busch, and A. Uhl,  “Detection of face morphing attacks based on prnu analysis,”  IEEE Transactions on Biometrics, Behavior, and Identity Science, vol. 1, no. 4, pp. 302–317, 2019.
  * [4] Clemens Seibold, Wojciech Samek, Anna Hilsmann, and Peter Eisert,  “Accurate and robust neural networks for face morphing attack detection,”  Journal of Information Security and Applications, vol. 53, pp. 102526, 2020.
  * [5] L. Wandzik, G. Kaeding, and R. V. Garcia,  “Morphing detection using a general- purpose face recognition system,”  in 2018 26th European Signal Processing Conference (EUSIPCO), 2018, pp. 1012–1016.
  * [6] Mei L. Ngan, Patrick J. Grother, Kayee K. Hanaoka, and Jason M. Kuo,  “Face recognition vendor test (frvt) part 4: Morph - performance of automated face morph detection,”  Tech. Rep., National Institute of Standards and Technology, 2020.
  * [7] T. Neubert, A. Makrushin, M. Hildebrandt, C. Kraetzer, and J. Dittmann,  “Extended stirtrace benchmarking of biometric and forensic qualities of morphed face images,”  IET Biometrics, vol. 7, no. 4, pp. 325–332, 2018.
  * [8] Satya Mallick,  “Face morph using opencv — c++ / python,” March 2016.
  * [9] Alyssa Quek,  “Facemorpher,” January 2019.
  * [10] T. Karras, S. Laine, M. Aittala, J. Hellsten, J. Lehtinen, and T. Aila,  “Analyzing and improving the image quality of StyleGAN,”  in 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2020, pp. 8107–8116.
  * [11] Haoyu Zhang, Sushma Venkatesh, Raghavendra Ramachandra, Kiran Raja, Naser Damer, and Christoph Busch,  “Mipgan—generating strong and high quality morphing attacks using identity prior driven gan,”  IEEE Transactions on Biometrics, Behavior, and Identity Science, vol. 3, no. 3, pp. 365–383, 2021.
  * [12] P.Jonathon Phillips, Harry Wechsler, Jeffery Huang, and Patrick J. Rauss,  “The feret database and evaluation procedure for face-recognition algorithms,”  Image and Vision Computing, vol. 16, no. 5, pp. 295 – 306, 1998\.
  * [13] Lisa DeBruine and Benedict Jones,  “Face Research Lab London Set,” 5 2017.
  * [14] U. Scherhag, C. Rathgeb, J. Merkle, and C. Busch,  “Deep face representations for differential morphing attack detection,”  IEEE Transactions on Information Forensics and Security, vol. 15, pp. 3625–3639, 2020.
  * [15] F. Schroff, D. Kalenichenko, and J. Philbin,  “Facenet: A unified embedding for face recognition and clustering,”  in 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015, pp. 815–823.
  * [16] Omkar M. Parkhi, Andrea Vedaldi, and Andrew Zisserman,  “Deep face recognition,”  in British Machine Vision Conference, 2015.
  * [17] Jiankang Deng, Jia Guo, Xue Niannan, and Stefanos Zafeiriou,  “Arcface: Additive angular margin loss for deep face recognition,”  in CVPR, 2019.
  * [18] R. Wallace, M. McLaren, C. McCool, and S. Marcel,  “Inter-session variability modelling and joint factor analysis for face authentication,”  in 2011 International Joint Conference on Biometrics (IJCB), 2011, pp. 1–8.
  * [19] ISO/IEC FDIS 30107-3:2017,  “Information technology — Biometric presentation attack detection — Part 3: Testing and reporting,”  Standard, International Organization for Standardization, Geneva, Switzerland, 09 2017.
  * [20] Raghavendra Ramachandra and Christoph Busch,  “Presentation attack detection methods for face recognition systems: A comprehensive survey,”  ACM Comput. Surv., vol. 50, no. 1, Mar. 2017.
  * [21] Davis E. King,  “Dlib-ml: A machine learning toolkit,”  Journal of Machine Learning Research, vol. 10, pp. 1755–1758, 2009\.
  * [22] S. Milborrow and F. Nicolls,  “Active Shape Models with SIFT Descriptors and MARS,”  VISAPP, 2014.
  * [23] S. Venkatesh, H. Zhang, R. Ramachandra, K. Raja, N. Damer, and C. Busch,  “Can gan generated morphs threaten face recognition systems equally as landmark based morphs? - vulnerability and detection,”  in 2020 8th International Workshop on Biometrics and Forensics (IWBF), 2020, pp. 1–6.
  * [24] Pavel Korshunov and Sébastien Marcel,  “Vulnerability of face recognition to deep morphing,”  in International Conference on Biometrics for Borders, oct 2019, pp. 1–5.
  * [25] T. Karras, S. Laine, and T. Aila,  “A style-based generator architecture for generative adversarial networks,”  in 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019, pp. 4396–4405.
  * [26] Chris McCool, Sébastien Marcel, Abdenour Hadid, Matti Pietikäinen, Pavel Matějka, Jan Černocký, Norman Poh, Josef Kittler, Anthony Larcher, Christophe Lévy, Driss Matrouf, Jean-François Bonastre, Phil Tresadern, and Timothy Cootes,  “Bi-modal person recognition on a mobile phone: using mobile phone data,”  in IEEE ICME Workshop on Hot Topic in Mobile Multimedia, 2012.
  * [27] U. Scherhag, A. Nautsch, C. Rathgeb, M. Gomez-Barrero, R. N. J. Veldhuis, L. Spreeuwers, M. Schils, D. Maltoni, P. Grother, S. Marcel, R. Breithaupt, R. Ramachandra, and C. Busch,  “Biometric systems under morphing attacks: Assessment of morphing techniques and vulnerability reporting,”  in 2017 International Conference of the Biometrics Special Interest Group (BIOSIG), 2017, pp. 1–7.
  * [28] Rameen Abdal, Yipeng Qin, and Peter Wonka,  “Image2stylegan: How to embed images into the stylegan latent space?,”  in 2019 IEEE/CVF International Conference on Computer Vision (ICCV), 2019, pp. 4431–4440.
  * [29] P. J. Phillips, P. J. Flynn, T. Scruggs, K. W. Bowyer, Jin Chang, K. Hoffman, J. Marques, Jaesik Min, and W. Worek,  “Overview of the face recognition grand challenge,”  in 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05), 2005, vol. 1, pp. 947–954 vol. 1.
  * [30] A. Mohammadi, S. Bhattacharjee, and S. Marcel,  “Deeply vulnerable: a study of the robustness of face recognition to presentation attacks,”  IET Biometrics, vol. 7, no. 1, pp. 15–26, 2018.


# Conversation Derailment Forecasting with Graph Convolutional Networks

Enas Altarawneh
York University
<EMAIL_ADDRESS>
Ameeta Agrawal
Portland State University
<EMAIL_ADDRESS>

Michael Jenkin
York University
<EMAIL_ADDRESS>

Manos Papagelis
York University
<EMAIL_ADDRESS>

###### Abstract

Online conversations are particularly susceptible to derailment, which can
manifest itself in the form of toxic communication patterns like disrespectful
comments or verbal abuse. Forecasting conversation derailment predicts signs
of derailment in advance enabling proactive moderation of conversations.
Current state-of-the-art approaches to address this problem rely on sequence
models that treat dialogues as text streams. We propose a novel model based on
a graph convolutional neural network that considers dialogue user dynamics and
the influence of public perception on conversation utterances. Through
empirical evaluation, we show that our model effectively captures conversation
dynamics and outperforms the state-of-the-art models on the CGA and CMV
benchmark datasets by 1.5% and 1.7%, respectively.

##  1 Introduction

The widespread availability of chat or messaging platforms, social media,
forums and other online communities has led to an increase in the number of
online conversations between individuals and groups. In contrast to offline or
face-to-face communication, online conversations require moderation to
maintain the integrity of the platform and protect users’ privacy and safety
Kilvington (2021). Moderation can help to prevent harassment, trolling, hate
speech, and other forms of abusive behavior Tontodimamma et al. (2021). It can
also help to prevent and address conversation derailment.

(a) Conversation $C_{CGA}$

(b) Conversation $C_{CMV}$

Figure 1: Conversation derailment examples coming from two benchmark datasets,
CGA and CMV; (a) illustrates graph dynamics in a conversation, and (b)
illustrates public perception through votes in a conversation. Our FGCN model
exploits these features to improve the accuracy of conversation derailment
forecasting.

Conversation derailment refers to the process by which a conversation or
discussion is redirected away from its original topic or purpose, typically as
a result of inappropriate or off-topic comments or actions by one or more
participants. In online conversations, derailment can be exacerbated by the
lack of nonverbal cues and the perceived anonymity that can be provided by the
internet. Conversation derailment can lead to confusion, frustration, and a
lack of productivity or progress in the conversation. Table 1 shows an example
conversation taken from the popular CGA benchmark dataset Zhang et al. (2018).
One can observe that there is offensive language used by one of the
participants that leads the conversation to derail. The severity of the verbal
attack may indicate a prior history between the two participants in previous
conversations.

Turn | User |  Text | Label
---|---|---|---
$N-3$ | $\mathcal{A}$ |  “Proper use of an editor’s history includes fixing errors or violations of Wikipedia policy or correcting related problems on multiple articles." |
$N-2$ | $\mathcal{B}$ |  “It’s very clear that you just go to my contributions list and look to see what biography articles I’ve worked on, then you go and look to see if you can find something wrong with them. " |
$N-1$ | $\mathcal{A}$ |  “So, what is wrong with fixing things? At the top of my talk page, it says to keep it on your watchlist. " |
$N$ | $\mathcal{B}$ |  “You cannot possibly be too stupid to understand the warning I’m giving you. I’m not going to repeat it." | ?
Table 1: A sample conversation from the Conversation Gone Awry (CGA) dataset
showing a sequence of text utterances that end with a verbal abuse. Given the
conversation context up to $N-1$ turns, the task is to predict whether turn
$N$ will be a respectful or offensive statement prior to it being presented
leading to derailment (it is offensive, in this case).

In this research, we examine the problem of forecasting conversation
derailment. The ability to predict conversation derailment early has multifold
benefits: (i) it is more timely, as it allows for proactive moderation of
conversations (before they cause any harm) due to early warning, (ii) it is
more scalable, as it allows to automatically monitor large active online
communities, a task that is otherwise time-consuming, (iii) it is more cost-
effective, as it may provide enough aid to limit the number of human
moderators needed, and (iv) it may identify upsetting content early and
prevent human moderators from being exposed to it.

Early efforts towards automatic moderation focused on detecting inappropriate
comments once they have occurred. But the utility of such an approach is
limited as participants have already been exposed to an abusive behavior and
any potential harm has already been caused. The current state-of-the-art
approach to predict conversation derailment relies on sequence models that
treat dialogues as text streams Chang et al. (2022); Kementchedjhieva and
Søgaard (2021). However, this approach has limitations, as it ignores the
semantics and dynamicity of a multi-party dialogue involving individuals’
intrinsic tendencies and the history of interactions with other individuals.

Based on these observations, we propose a graph-based model to capture multi-
party multi-turn dialogue dynamics. In addition, we leverage information
associated with conversation utterances that provide public perception on
whether an utterance is perceived as positive or negative.

There exist two popular benchmark datasets typically employed for the problem
of interest: Conversations Gone Awry (CGA) Zhang et al. (2018) and Reddit
ChangeMyView (CMV) Chang and Danescu-Niculescu-Mizil (2019). Both datasets
contain multi-party conversations, including the text and an anonymous user ID
of each utterance, along with a label annotation on whether the conversation
will derail or not. CMV also includes a public vote on each of the utterances
that provides the public perception of individuals towards it.

Figure 1(a) shows an example multi-party conversation from CGA that is not
sequential in nature. Note as well that some participants are in either
agreement or disagreement of a heated argument. Graph models are more
accustomed to represent such dialogue dynamics. Figure 1(b) shows an example
conversation from CMV that shows sample voting scores on each utterance in the
conversation that could be related to derailment.

Graph neural networks have been successfully used to model conversations for
downstream classification tasks. For example, they have shown promise in
forecasting the next emotion in a conversation Li et al. (2021), a problem
similar to that of interest in this work. This motivated us to explore this
line of research and make the following contributions:

  * •

We propose a novel model based on a graph convolutional neural network, the
Forecasting Graph Convolutional Network (FGCN), that captures dialogue user
dynamics and public perception of conversation utterances.

  * •

We perform an extensive empirical evaluation of FGCN that shows it outperforms
the state-of-the-art models on the GCA and CMV benchmark datasets by 1.5% and
1.7%, respectively.

The remainder of the paper is organized as follows. Section 2 reviews related
work. The technical problem of interest is presented in Section 3. Section 4
presents the proposed models. Section 5 presents the experimental setup, and
Section 6 presents the results and a discussion. We conclude in Section 7.

##  2 Related Work

There has been considerable research attention on the problem of detecting
various forms of toxicity in text data. There are methods for identifying
cyberbullying Wiegand et al. (2019), hate speech Davidson et al. (2017), or
negative sentiment Agrawal and An (2014); Wang and Cardie (2016) or lowering
the intensity of emotions Ziems et al. (2022); Xie and Agrawal (2023). These
methods are useful in filtering unacceptable content. However, the focus of
these models is on mostly analyzing or classifying already posted harmful
texts.

The CRAFT models introduced by Chang et al. (2022) are the first models to go
beyond classification of hate speech to addressing the problem of forecasting
conversation derailment. The CRAFT models integrate two components: (a) a
generative dialog model that learns to represent conversational dynamics in an
unsupervised fashion, and (b) a supervised component that fine-tunes this
representation to forecast future events. As a proof of concept, a mixed
methods approach combining surveys with randomized controlled experiments
investigated how conversation forecasting using the CRAFT model can help users
Chang et al. (2022) and moderators Schluger et al. (2022) to proactively
assess and deescalate tension in online discussions.

Extending the hierarchical recurrent neural network architecture with three
task-specific loss functions proposed by Janiszewski et al. (2021) was shown
to improve the CRAFT models. After pretrained transformer language encoders
such as BERT Devlin et al. (2018) proved to be successful at various NLP
tasks, Kementchedjhieva and Søgaard (2021) explored how they can be used for
forecasting derailment. The model in this work consists of a BERT checkpoint
with a sequence classification (SC) head. Similarly, De Kock and Vlachos
(2021) evaluated feature-based and neural models to predict whether
disagreements in Wikipedia Talk page conversations will be escalated to
mediation by a moderator.

Saveski et al. (2021) studied the relationship between structure and toxicity
in conversations on Twitter at individual, dyad, and group level, and found
that social relationships among users influence their behaviors. Salehabadi et
al. (2022) also studied the differences between toxic and non-toxic
conversations on Twitter, highlighting important differences between user
engagement and toxicity. While these recent works stress the importance of
user characteristics in conversation modeling, to our knowledge, models that
incorporate such signals for the task of predicting derailment have remained
unexplored.

Here we propose graph-based models for leveraging user-specific information.
Graph convolutional neural networks have been used for conversation
classification. In one popular application, emotion estimation, the graph
model is used to account for speaker related information Ghosal et al. (2019);
Sun et al. (2021). Other work have used similar graph neural networks to
forecast emotions Zhong et al. (2019); Lubis et al. (2019); Liang et al.
(2022); Li et al. (2021).

##  3 Problem Definition

In this section, we formally define the problem of forecasting conversation
derailment. For a conversation
$\mathcal{C}=\\{\\{t_{1},t_{2},...,t_{N}\\}\mathbin{,}\\{u_{1},u_{2},...,u_{N}\\}\mathbin{,}\\{s_{1},s_{2},...,s_{N}\\}\\}$
consisting of $N$ turns, the last turn (i.e., the $N$’th turn) is the
potential site of derailment where $l=\\{civil,personal$ $attack\\}$ denotes
the label of this turn.

For the $i$th turn, $t_{i}$ denotes its text, $u_{i}$ denotes its user, and
$s_{i}$ denotes an optional score, e.g., number of votes (up-vote/down-vote).
An up-vote is a positive impression and a down-vote is a negative impression
on the turn utterance. The goal is to forecast the derailment label $l$ of the
$N$’th turn given a conversation $\mathcal{C}$ up to $N-1$ turns (i.e.,
without any information about the $N$th turn).

##  4 Model for Forecasting Conversation Derailment

Figure 2: The FGCN model architecture.

In this section, we describe our proposed Forecasting Graph Convolutional
neural Network model, (FGCN), visualized in Figure 2.

###  4.1 Sequential encoding

The input to the model consists of the text $t_{i}$, user ID $u_{i}$ and/or
the public perception score $s_{i}$ for each turn in the conversation
$i\in[1,2,...,N-1]$, as described below:

Textual input — the input consists of an encoding of the turn text $t_{i}$
using BERT embeddings extracted after fine tuning as described in
Kementchedjhieva and Søgaard (2021), resulting in the sequential encoding of
the text as vector $t^{{}^{\prime}}_{i}$ .

User ID input — the input consists of an encoding of the user ID as a randomly
initialized vector $u_{i}$, where each user has a unique vector; we use BiLSTM
sequential encoding to obtain the utterance user ID vectors
$u^{{}^{\prime}}_{i}$. We use unique randomly initialized vectors to avoid
privacy issues that may arise using actual IDs.

Public perception input — the input consists of a popularity score where the
up-votes on a turn is subtracted by the down-votes on the same. To obtain the
score vector $s_{i}$ we use equal depth binning to capture three levels of
popularity for positive scores and three levels of unpopularity for negative
scores. We use a BiLSTM sequential encoder on $s_{i}$ resulting in utterance
public perception vectors $s^{{}^{\prime}}_{i}$.

###  4.2 Graph Construction

For a given conversation, the output of the sequential encoder for each one of
these input types $t^{{}^{\prime}}_{i}$, $u^{{}^{\prime}}_{i}$ and
$s^{{}^{\prime}}_{i}$ is used to initialize the vertices in the homogeneous
graphs shown in Figure 2. The vertices in the graphs represent the turns in
the conversation. Each graph $G_{x}=(V,E,R,W)$, for each type of input
$x\in\\{t,u,s\\}$, is constructed with vertices $v_{i}\in V$, $r_{ij}\in E$ is
the labeled edges between $v_{i}$ and $v_{j}$, the edge labels (relations)
$\in R$ and $\alpha_{ij}$ is the weight of the labeled edge $r_{ij}$, with
$0\leq\alpha_{ij}\leq 1$, where $\alpha_{ij}\in W$, $i\in[1,2,...,N-1]$ and
$j\in$ the set of all neighboring vertices to $v_{i}$.

For each conversation we construct three types of graphs; a text-based
$G_{t}$, a user-based $G_{u}$ and a public perception score-based $G_{s}$. In
$G_{t}$, each conversation turn is represented as a vertex $v_{i}\in V$ and is
initialized with the textual sequentially encoded feature vector
$t^{{}^{\prime}}_{i}$, for all $i\in[1,2,...,N-1]$. In $G_{u}$ each vertex is
initialized with a utterance user ID vector $u^{{}^{\prime}}_{i}$, for all
$i\in[1,2,...,N-1]$ provided by the sequential encoder. Similarly, in $G_{s}$
each vertex is initialized with a utterance public score vector
$s^{{}^{\prime}}_{i}$, for all $i\in[1,2,...,N-1]$ provided by the sequential
encoder.

User to user relationship edge construction. We establish the direct user to
user relationship in a conversation through the edge construction of each
graph. This results in efficient graph modeling with less complexity compared
to complete graphs. Figure 3 shows an example graph edge construction for a
given conversation. In user-to-user relationship edge construction, each
vertex $v_{i}$ representing a turn in the conversation has directed edges
connecting it to its preceding (parent) and succeeding comments/turns
(children). Same user comments (turns) are also connected through directed
edges. The user-to-user relation $\in R$ of an edge $r_{ij}$ is set based on
the user-to-user dependency between user $u_{i}$ (of turn $v_{i}$) and user
$u_{j}$ (of turn $v_{j}$).

For example, in Figure 3, there are four users, so the set of edge labels $R$
has the relation types shown under user-to-user dependency. Furthermore, as
the graph is directed, two vertices can have edges in both directions with
different relations. We use this to represent the past (backward) and future
(forward) temporal dependency between the vertices, shown as temporal user
dependency. The edge weights are set using a similarity based attention
module. The attention function is computed such that, for each vertex, the
incoming set of edges has a sum total weight of 1. The weights are calculated
as, $\alpha_{ij}=softmax(v^{T}_{i}W_{e}[v_{j_{1}},...,v_{j_{m}}])$, for
$j_{k}$, where $k=1,2,..,m$, for the $m$ vertices connected to $v_{i}$,
ensuring the vertex $v_{i}$ receives a total weight contribution of 1.

Figure 3: An example graph edge construction for the given conversation with
user-to-user and temporal dependency.

###  4.3 Feature Transformation

The sequentially encoded text features $t^{{}^{\prime}}_{i}$, the user
features $u^{{}^{\prime}}_{i}$, and the public perception features
$s^{{}^{\prime}}_{i}$ of the graph network are transformed from user dynamic
independent into user dynamic dependent feature vectors using a two-step graph
convolution process employed by Ghosal et al. (2019). In the first step, a new
feature vector is computed for each vertex in all three graphs by aggregating
local neighbourhood information:

$u^{{}^{\prime\prime}}_{i}=\sigma(\sum\limits_{r\in R}\sum\limits_{j\in
N^{r}_{i}}\frac{\alpha_{ij}}{c_{i,r}}W_{r}\,u^{{}^{\prime}}_{j}+\alpha_{ii}W_{0}\,u^{{}^{\prime}}_{i}),$

$t^{{}^{\prime\prime}}_{i}=\sigma(\sum\limits_{r\in R}\sum\limits_{j\in
N^{r}_{i}}\frac{\alpha_{ij}}{c_{i,r}}W_{r}\,t^{{}^{\prime}}_{j}+\alpha_{ii}W_{0}\,t^{{}^{\prime}}_{i})$

$s^{{}^{\prime\prime}}_{i}=\sigma(\sum\limits_{r\in R}\sum\limits_{j\in
N^{r}_{i}}\frac{\alpha_{ij}}{c_{i,r}}W_{r}\,s^{{}^{\prime}}_{j}+\alpha_{ii}W_{0}\,s^{{}^{\prime}}_{i})$

for $i=1,2,...,N-1,$ where, $\alpha_{ii}$ and $\alpha_{ij}$ are the edge
weights, and $N^{r}_{i}$ is the neighbouring indices of vertex $i$ under
relation $r\in R$. $c_{i,r}$ is a problem specific normalization constant
automatically learned in a gradient based learning setup. $\Sigma$ is an
activation function such as ReLU, and $W_{r}$ and $W_{0}$ are learnable
parameters of the transformation. In the second step, another local
neighbourhood based transformation is applied over the outputs of the first
step, as follows:

$u^{{}^{\prime\prime}}_{i}=\sigma(\sum\limits_{j\in
N^{r}_{i}}W\,u^{{}^{\prime\prime}}_{j}+\alpha_{ii}W_{0}\,u^{{}^{\prime\prime}}_{i}),$

$t^{{}^{\prime\prime}}_{i}=\sigma(\sum\limits_{j\in
N^{r}_{i}}W\,t^{{}^{\prime\prime}}_{j}+\alpha_{ii}W_{0}\,t^{{}^{\prime\prime}}_{i})$

$s^{{}^{\prime\prime}}_{i}=\sigma(\sum\limits_{j\in
N^{r}_{i}}W\,s^{{}^{\prime\prime}}_{j}+\alpha_{ii}W_{0}\,s^{{}^{\prime\prime}}_{i})$

for $i=1,2,...,N-1$, where, $W$ and $W_{0}$ are transformation parameters, and
$\sigma$ is the activation function. This two step transformation accumulates
the normalized sum of the local neighbourhood.

###  4.4 Forecasting Derailment

To form the final turn representation, the sequential encoded vectors
$t^{{}^{\prime}}_{i}$, $u^{{}^{\prime}}_{i}$ and $s^{{}^{\prime}}_{i}$, and
the user dynamic encoded vectors $t^{{}^{\prime\prime}}_{i}$,
$u^{{}^{\prime\prime}}_{i}$ and $s^{{}^{\prime\prime}}_{i}$ are concatenated
for each turn $i$ in a conversation to form:

$g_{i}=[t^{{}^{\prime}}_{i},u^{{}^{\prime}}_{i},s^{{}^{\prime}}_{i},t^{{}^{\prime\prime}}_{i},u^{{}^{\prime\prime}}_{i},s^{{}^{\prime\prime}}_{i}]$

Then, each $g_{i}$, $i\in\\{1,2....,N-1\\}$ is concatenated to form a
representation of the conversation $C$:

$C^{{}^{\prime}}=[g_{1},g_{2}...,g_{N-1}]$

Finally, $C^{{}^{\prime}}$ is fed to a classifier with a linear layer, a full
connected network and a sigmoid activation function, as described by Ghosal et
al. (2019), to obtain the label $\hat{l}$ of each conversation $C$.

###  4.5 Model variants

To understand the effect of each type of input on forecasting derailment, we
create variants of our model where the types of input are gradually included.
The following is a more detailed description of the models used in this work.

FGCN-T — this variant of the model constructs one graph using the output of
the sequential encoder on the textual data $t^{{}^{\prime}}_{i}$. It is
created for both CGA and CMV, as both contain the textual data. FGCN-T uses
only the textual layer shown in Figure 2. At classification it concatenates
$t^{{}^{\prime}}_{i}$ with the result of the GCN feature transformation
$t^{{}^{\prime\prime}}_{i}$ during user dynamic encoding.

FCGN-TU — this variant of the model constructs two graphs using the output of
the sequential encoder, one for the textual output $t^{{}^{\prime}}_{i}$ and
the other for the user ID output $u^{{}^{\prime}}_{i}$. It is created for both
CGA and CMV, as both contain the textual and user ID data. FGCN-TU uses the
textual and user ID layer shown in Figure 2. At classification it concatenates
$t^{{}^{\prime}}_{i}$ and $u^{{}^{\prime}}_{i}$ with the result of the GCN
feature transformation $t^{{}^{\prime\prime}}_{i}$ and
$u^{{}^{\prime\prime}}_{i}$ during user dynamic encoding.

FGCN-TS — this variant of the model constructs two graphs using the output of
the sequential encoder, one for the textual output $t^{{}^{\prime}}_{i}$ and
the other for the public perception score output $s^{{}^{\prime}}_{i}$. It is
created for CMV, as only CMV contains the public perception data. FGCN-TS uses
the textual and public score layer shown in Figure 2. At classification it
concatenates $t^{{}^{\prime}}_{i}$ and $s^{{}^{\prime}}_{i}$ with the result
of the GCN feature transformation $t^{{}^{\prime\prime}}_{i}$ and
$s^{{}^{\prime\prime}}_{i}$ during user dynamic encoding.

FGCN-TSU — this variant of the model constructs three graphs using the output
of the sequential encoder, one for the textual output $t^{{}^{\prime}}_{i}$,
the user ID output $u^{{}^{\prime}}_{i}$ and the public perception score
output $s^{{}^{\prime}}_{i}$. It is created for CMV, as only CMV contains the
public perception data. FGCN-TSU uses all layers shown in Figure 2. At
classification it concatenates $t^{{}^{\prime}}_{i}$, $u^{{}^{\prime}}_{i}$
and $s^{{}^{\prime}}_{i}$ with the result of the GCN feature transformation
$s^{{}^{\prime\prime}}_{i}$ and $s^{{}^{\prime\prime}}_{i}$ during user
dynamic encoding.

Dataset | Input | Train | Val | Test
---|---|---|---|---
| $t$ | $u$ | $s$ |  |  |
CGA | ✓ | ✓ | ✕ | 2508 | 840 | 840
CMV | ✓ | ✓ | ✓ | 4106 | 1368 | 1368
Table 2: Statistics of the datasets. $t$ denotes text input, $u$ denotes user ID input and $s$ denotes public perception score input. All splits are balanced between the two classes. |  | CGA | CMV
---|---|---|---
Traning |  Model |  Acc |  P |  R |  F1 |  Acc |  P |  R |  F1
Static |  CRAFT |  64.4 |  62.7 |  71.7 |  66.9 |  60.5 |  57.5 |  81.3 |  67.3
|  BERT·SC |  64.7 |  61.5 |  79.4 |  69.3 |  62.0 |  58.6 |  82.8 |  68.5
|  FGCN-T |  66.4 |  63.0 |  79.5 |  70.3 |  62.9 |  59.2 |  83.0 |  69.1
|  FGCN-TU |  66.9 |  63.3 |  80.2 |  70.8 |  63.2 |  59.5 |  83.0 |  69.3
|  FGCN-TS |  - |  - |  - |  - |  64.2 |  60.3 |  83.2 |  69.9
|  FGCN-TSU |  - |  - |  - |  - |  64.7 |  60.7 |  83.3 |  70.2
Dynamic |  BERT·SC+ |  64.3 |  61.2 |  78.9 |  68.8 |  56.5 |  56.0 |  73.2 |  61.7
|  FGCN-T+ |  65.7 |  62.2 |  79.7 |  69.9 |  62.1 |  58.5 |  82.0 |  68.3
|  FGCN-TU+ |  65.9 |  62.4 |  80.2 |  70.2 |  62.7 |  58.8 |  82.7 |  68.8
|  FGCN-TS+ |  - |  - |  - |  - |  62.9 |  59.2 |  82.9 |  69.1
|  FGCN-TSU+ |  - |  - |  - |  - |  63.5 |  59.7 |  83.1 |  69.5
Table 3:  Experimental results for forecasting conversation derailment. Best
F1-score are in bold.

##  5 Experimental Setup

###  5.1 Datasets

We use two datasets for the task of forecasting derailment in conversations.
Some statistics of the datasets are summarized in Table 2.

Conversations Gone Awry (CGA) dataset Zhang et al. (2018) was extracted from
Wikipedia Talk Page conversations. The conversations were sampled from
WikiConv Hua et al. (2018) based on an automatic measure of toxicity that
ranges from 0 (not toxic) to 1 (is toxic). A conversation is extracted as a
sample of derailment if the $N$th comment in it has a toxicity score higher
than 0.6 and all the preceding comments have a score lower than 0.4.
Conversations having all comments with a toxicity score below 0.4 are
extracted as samples of non-derailment. This set of conversations is further
filtered through manual annotation to determine whether after an initial civil
exchange a personal attack occurs from one user towards another. The
conversations include the turn with the personal attack. This means all $N-1$
turns in a conversation are civil and the $N$’th one is either civil or
contains a personal attack. The dataset also contains additional information
about each comment in the conversation such as the user posting the comment
and the ID of the parent comment that this comment was a reply to.

Reddit ChangeMyView (CMV) dataset Chang and Danescu-Niculescu-Mizil (2019) was
extracted from Reddit conversations held under the ChangeMyView subreddit.
Conversations were identified as derailed if there was a deletion of a turn by
the platform moderators. This could have been done under Reddit’s Rule: “Don’t
be rude or hostile to other users.” Unlike CGA, there is no control to ensure
that all the preceding comments to the last one would be civil, resulting in
some noise in the data. The dataset also contains additional information about
each comment in the conversation such as the user posting the comment, the ID
of the parent comment that this comment was a reply to, and a votes score
(i.e., the number of up-votes minus the number of down-votes).

###  5.2 Evaluation Metrics

Following prior work, we report the performance of the models in terms of
accuracy (Acc), precision (P), recall (R), and F1-score. We also report the
forecast horizon H introduced by Kementchedjhieva and Søgaard (2021), which is
the mean of the turns in which the first detection of derailment occurred for
the set of conversations that derail.

###  5.3 Baselines

Our FGCN model and its variants are evaluated against the state-of-the-art
methods below.

CRAFT Chang and Danescu-Niculescu-Mizil (2019) is a model with a hierarchical
recurrent neural network architecture, which integrates a generative dialog
model that learns to represent conversational dynamics in an unsupervised
fashion, and a supervised component that fine-tunes this representation to
forecast future events. This model is trained statically. Static training
entails that all $N-1$ turns $\\{t_{1},...,t_{N-1}\\}$ of a conversation of
$N$ turns are used as one input instance.

BERT·SC Kementchedjhieva and Søgaard (2021) is a model consisting of the BERT
checkpoint with a sequence classification (SC) head, trained statically, i.e.
in the same manner as CRAFT.

BERT·SC+ Kementchedjhieva and Søgaard (2021) similar to BERT·SC consists of
the BERT checkpoint with a sequence classification (SC) head, but is instead
trained dynamically. Dynamic training entails that a conversation of $N$ turns
$\\{t_{1},...,t_{N-1}\\}$ with label $l$ is mapped to multiple training
samples, each representing a different phase of the conversation unfolding,
but all labeled with the same label $l$. So a conversation of $N$ turns is
converted into $N-1$ training instances samples
$\\{t_{1}\\},\\{t_{1},t_{2}\\},...,\\{t_{1},...,t_{N-1}\\}$ instead of just
the one $\\{t_{1},...,t_{N-1}\\}$.

###  5.4 Implementation

We use two training paradigms, static and dynamic: In static training, for
each conversation we use one training instance with all turns
$\\{\\{t_{1},...,t_{N-1}\\}$, $\\{u_{1},...,u_{N-1}\\}$ and/or
$\\{s_{1},...,s_{N-1}\\}\\}$ as input. In dynamic training, we use multiple
instances of each conversation, by varying the last turn used in each training
instance. So, we use $\\{t_{1}$, $u_{1}$ and/or $s_{1}\\}$ as an instance,
$\\{\\{t_{1},t_{2}\\}$, $\\{u_{1},u_{2}\\}$ , and/or $\\{s_{1},s_{2}\\}\\}$ as
another instance, and so on until the last instance
$\\{\\{t_{1},...,t_{N-1}\\}$, $\\{u_{1},...,u_{N-1}\\}$ and/or
$\\{s_{1},...,s_{N-1}\\}\\}$. So we have $N-1$ instances of each conversation.
We denote all dynamically trained models with an added “+” at the end of the
model name.

At inference time, the model is tested dynamically, i.e., by using turn
$\\{t_{1}$, $u_{1}$ and/or $s_{1}\\}$ as input, and making a prediction
$\hat{l_{1}}$, then using turns $\\{\\{t_{1},t_{2}\\}$, $\\{u_{1},u_{2}\\}$,
and/or $\\{s_{1},s_{2}\\}\\}$, and making a prediction $\hat{l_{2}}$, and so
on until $N-1$ predictions have been accumulated. The overall predicted label
for a given conversation is then obtained as
$\hat{l}=\max^{N-1}_{i=1}\hat{l_{i}}$.

Our models used the same BERT implementation (i.e., bert-base-uncased) as in
the baseline models Kementchedjhieva and Søgaard (2021), for our textual
sequential encoding, to ensure a comparable evaluation setting. However, it is
worth mentioning that any pretrained language model can be used. The graph
neural network component described in this work is implemented with settings
similar to that reported by Ghosal et al. (2019). The results are reported as
an average over 10 different runs with random initialization, to account for
variance in model performance.

Figure 4: Forecast horizon on the CGA dataset with a model drawn at random
from among the 10 available ones. A horizon of 1 means that an upcoming
derailment was only predicted on the last turn before it occurred.

##  6 Results and Discussion

In the forecasting conversation derailment experiment we report the results of
the static and dynamic training of our model and its variants and compare with
baselines. In the analyzing mean forecast horizon experiment we show how early
each model can forecast derailment.

###  6.1 Forecasting Conversation Derailment

The results in Table 3 show that across both the datasets, FGCN-T, our text
based graph neural network model, outperforms baseline models when given
similar text input. FGCN-TU, which explicitly uses user ID’s in addition to
text data, further improves the results for both the datasets. FGCN-TS, which
uses text and public perception data in the CMV dataset, brings similar
improvements. Furthermore, the results of the FGCN-TSU model, which uses text,
user and public perception data, indicate that incorporating all three
features when available can be beneficial. Note that CGA does not provide any
public perception data and was excluded from this experiment.

Statically trained models outperform their corresponding dynamically trained
models. However, our dynamically trained models outperform both statically and
dynamically trained baselines.

Taken together, these results indicate that modeling conversations using a
graph neural network improves the models’ forecasting F1-score. They also
demonstrate that this modeling framework is flexible and allows for
incorporating more types of data that may be beneficial. For instance, future
work could investigate the potential benefit of integrating explicit emotion
or sentiment values Babanejad et al. (2019); Agrawal et al. (2016) into
derailment forecasting models.

|  CGA |  CMV
---|---|---
CRAFT |  2.36 |  4.01
BERT·SC |  2.60 |  3.90
BERT·SC+ |  2.85 |  4.06
FGCN-T |  2.73 |  4.03
FGCN-T+ |  2.96 |  4.12
Table 4:  Experimental results of mean forecast horizon (H).The best result is
shown in bold whereas the second best result has been underlined.

###  6.2 Analyzing Mean Forecast Horizon

How early can the model forecast the derailment? To answer this question we
calculate the forecast horizon $H$, the mean of the turn in which the first
detection of derailment occurred for the set of conversations that derail. A
forecast horizon $H$ of 1 means that a derailment coming up on turn $N$ was
first detected on turn $N-1$. A longer forecast horizon (i.e., a higher H)
allows for earlier interventions and potentially allows moderators to delete
the upcoming personal attack as soon as it appears on their platform to avoid
any form of escalation. Models that are able to detect a potential
intervention earlier have a clear advantage.

In Table 4 we report the results of the mean forecast horizon $H$. The results
show that our model FGCN-T+ with its dynamic training provides the earliest
overall forecasting of derailment with a mean H of 4.12 for CMV, and 2.95 for
CGA. Followed by another dynamically trained model BERT.SC+. For the
statically trained models (CRAFT, BERT.SC, and FGCN-T), FGCN-T has the best
performance as it seems to be able to better model the dynamic relationships
between the users of the turns with its graph model, obtaining a mean H of
4.03 for CMV and, 2.73 for CGA.

We perform further analysis of the forecast horizon results for CGA. Figure 4
illustrates the forecast horizon of the different models. In earlier work,
both CRAFT and BERT·SC, the models make a prediction with a forecast horizon
$H>1$ turn at a high rate. Only 20% of CRAFT’s forecasts and 17.5% of
BERT·SC’s forecasts came on the last turn before the derailment. Turning to
BERT·SC+, we see that dynamic training has helped in shifting a lot of the
density from $H<=3$ towards $H>3$. The last-minute forecasts for BERT·SC+
model come at a rate of only 7.5%. FGCN-T and FGCN-T+ uses BERT.SC in its
sequential textual component and combines it with a graph component. FGCN-T
was also able to shift density from $H<=3$ towards $H>3$ even though it was
trained statically, indicating that the result was due to the graph modeling.
The dynamiclly trained FGCN-T+ outperforms all by shifting even more density
towards $H>3$ and a last minute forecast at a rate of only 7%.

##  7 Conclusion

Unlike previous models which were based on simpler sequence models, FGCN is
built on a graph convolutional neural network and is able to capture the
dynamics of multi-party dialogue, including user relationships and public
perception of conversation statements. FGCN performed significantly better
than state-of-the-art models on two widely used benchmark datasets, CGA and
CMV. Conversation derailment is a significant issue that frequently and
severely impacts our online social interactions, whether in casual settings or
more formal contexts such as online learning or remote work. The ability to
accurately predict derailment has the potential to enhance the effectiveness
of moderation and thus protect individuals who are vulnerable to emotional
abuse or harm and improve the overall quality of online interactions.

## Limitations

Graph models require four or more utterances to form meaningful conversation
connections and model their dynamics. In some cases, conversations that derail
are not sufficiently long and may be best modeled by simpler sequential
models. Any of these models will work best with asynchronous conversations
where there is a time lag between the turns to allow for moderation after
forecasting.

## Ethics Statement

In our paper, we focus on the problem of forecast- ing conversation
derailment. The practical employ- ment of any such system on online platforms
has potential positive impact, but several things would be important to first
consider, including whether forecasting is fair Williamson and Menon (2019),
how to inform users about the forecasting (in ad- vance, and when the
forecasting affects users), and finally what other action is taken when
derailment is forecast. Please refer to Kiritchenko et al. (2020) for a
related overview of such considerations, in the context of abusive language
detection.

## Acknowledgments

We are grateful to the anonymous reviewers for their insightful feedback. The
financial support of NSERC, the NCRN, VISTA and the IDEaS network is
gratefully acknowledged.

## References

  * Agrawal and An (2014) Ameeta Agrawal and Aijun An. 2014.  Kea: Sentiment analysis of phrases within short texts.  In _Proceedings of the 8th International Workshop on Semantic Evaluation (SemEval 2014)_.
  * Agrawal et al. (2016) Ameeta Agrawal, Raghavender Sahdev, Heidar Davoudi, Forouq Khonsari, Aijun An, and Susan McGrath. 2016.  Detecting the magnitude of events from news articles.  In _2016 IEEE/WIC/ACM International Conference on Web Intelligence (WI)_. IEEE.
  * Babanejad et al. (2019) Nastaran Babanejad, Ameeta Agrawal, Heidar Davoudi, Aijun An, and Manos Papagelis. 2019.  Leveraging emotion features in news recommendations.  In _Proceedings of the 7th International Workshop on News Recommendation and Analytics (INRA)_.
  * Chang and Danescu-Niculescu-Mizil (2019) Jonathan P. Chang and Cristian Danescu-Niculescu-Mizil. 2019.  Trouble on the horizon: Forecasting the derailment of online conversations as they develop.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 4743–4754, Hong Kong, China. Association for Computational Linguistics.
  * Chang et al. (2022) Jonathan P Chang, Charlotte Schluger, and Cristian Danescu-Niculescu-Mizil. 2022\.  Thread with caution: Proactively helping users assess and deescalate tension in their online discussions.  _Proceedings of the ACM on Human-Computer Interaction_ , 6(CSCW2):1–37.
  * Davidson et al. (2017) Thomas Davidson, Dana Warmsley, Michael W. Macy, and Ingmar Weber. 2017.  Automated hate speech detection and the problem of offensive language.  _CoRR_ , abs/1703.04009.
  * De Kock and Vlachos (2021) Christine De Kock and Andreas Vlachos. 2021.  I beg to differ: A study of constructive disagreement in online conversations.  _arXiv preprint arXiv:2101.10917_.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  BERT: pre-training of deep bidirectional transformers for language understanding.  _CoRR_ , abs/1810.04805.
  * Ghosal et al. (2019) Deepanway Ghosal, Navonil Majumder, Soujanya Poria, Niyati Chhaya, and Alexander F. Gelbukh. 2019.  Dialoguegcn: A graph convolutional neural network for emotion recognition in conversation.  _CoRR_ , abs/1908.11540.
  * Hua et al. (2018) Yiqing Hua, Cristian Danescu-Niculescu-Mizil, Dario Taraborelli, Nithum Thain, Jeffery Sorensen, and Lucas Dixon. 2018.  WikiConv: A corpus of the complete conversational history of a large online collaborative community.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 2818–2823, Brussels, Belgium. Association for Computational Linguistics.
  * Janiszewski et al. (2021) Piotr Janiszewski, Mateusz Lango, and Jerzy Stefanowski. 2021.  Time aspect in making an actionable prediction of a conversation breakdown.  page 351–364, Berlin, Heidelberg. Springer-Verlag.
  * Kementchedjhieva and Søgaard (2021) Yova Kementchedjhieva and Anders Søgaard. 2021.  Dynamic forecasting of conversation derailment.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 7915–7919, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Kilvington (2021) Daniel Kilvington. 2021.  The virtual stages of hate: Using goffman’s work to conceptualise the motivations for online hate.  _Media, Culture & Society_, 43(2).
  * Kiritchenko et al. (2020) Svetlana Kiritchenko, Isar Nejadgholi, and Kathleen C. Fraser. 2020.  Confronting abusive language online: A survey from the ethical and human rights perspective.  _CoRR_ , abs/2012.12305.
  * Li et al. (2021) Dayu Li, Xiaodan Zhu, Yang Li, Suge Wang, Deyu Li, Jian Liao, and Jianxing Zheng. 2021.  Emotion inference in multi-turn conversations with addressee-aware module and ensemble strategy.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 3935–3941.
  * Liang et al. (2022) Yunlong Liang, Fandong Meng, Ying Zhang, Yufeng Chen, Jinan Xu, and Jie Zhou. 2022\.  Emotional conversation generation with heterogeneous graph neural network.  _Artificial Intelligence_ , 308:103714.
  * Lubis et al. (2019) Nurul Lubis, Sakriani Sakti, Koichiro Yoshino, and Satoshi Nakamura. 2019.  Positive emotion elicitation in chat-based dialogue systems.  _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , 27:866–877.
  * Salehabadi et al. (2022) Nazanin Salehabadi, Anne Groggel, Mohit Singhal, Sayak Saha Roy, and Shirin Nilizadeh. 2022.  User engagement and the toxicity of tweets.  _arXiv preprint arXiv:2211.03856_.
  * Saveski et al. (2021) Martin Saveski, Brandon Roy, and Deb Roy. 2021.  The structure of toxic conversations on twitter.  In _Proceedings of the Web Conference_.
  * Schluger et al. (2022) Charlotte Schluger, Jonathan P Chang, Cristian Danescu-Niculescu-Mizil, and Karen Levy. 2022.  Proactive moderation of online discussions: Existing practices and the potential for algorithmic support.  _Proceedings of the ACM on Human-Computer Interaction_ , 6(CSCW2):1–27.
  * Sun et al. (2021) Yang Sun, Nan Yu, and Guohong Fu. 2021.  A discourse-aware graph neural network for emotion recognition in multi-party conversation.  pages 2949–2958.
  * Tontodimamma et al. (2021) Alice Tontodimamma, Eugenia Nissi, Annalina Sarra, and Lara Fontanella. 2021.  Thirty years of research into hate speech: topics of interest and their evolution.  _Scientometrics_ , 126(1):157–179.
  * Wang and Cardie (2016) Lu Wang and Claire Cardie. 2016.  A piece of my mind: A sentiment analysis approach for online dispute detection.  _CoRR_ , abs/1606.05704.
  * Wiegand et al. (2019) Michael Wiegand, Josef Ruppenhofer, and Thomas Kleinbauer. 2019.  Detection of Abusive Language: the Problem of Biased Datasets.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 602–608, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Williamson and Menon (2019) Robert Williamson and Aditya Menon. 2019.  Fairness risk measures.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 6786–6797. PMLR.
  * Xie and Agrawal (2023) Justin Xie and Ameeta Agrawal. 2023.  Emotion and sentiment guided paraphrasing.  In _Proceedings of the 13th Workshop on Computational Approaches to Subjectivity, Sentiment and Social Media Analysis_.
  * Zhang et al. (2018) Justine Zhang, Jonathan P. Chang, Cristian Danescu-Niculescu-Mizil, Lucas Dixon, Dario Taraborelli, Nithum Thain, and Dario Taraborelli. 2018.  Conversations gone awry: Detecting warning signs of conversational failure.  In _Proceedings of ACL_.
  * Zhong et al. (2019) Peixiang Zhong, Di Wang, and Chunyan Miao. 2019.  An affect-rich neural conversational model with biased attention and weighted cross-entropy loss.
  * Ziems et al. (2022) Caleb Ziems, Minzhi Li, Anthony Zhang, and Diyi Yang. 2022.  Inducing positive perspectives with text reframing.  _arXiv preprint arXiv:2204.02952_.