<figure><img src="image_1.png" /></figure>

HAL
open science

# Combining Graph and Text to Model Conversations: An Application to Online Abuse Detection

Noé Cecillon

<figure><img src="image_2.png" /></figure>

## To cite this version:

Noé Cecillon. Combining Graph and Text to Model Conversations: An Application to Online Abuse Detection. Computer Science [cs]. Avignon Université, 2024. English. NNT: tel-04441308

HAL Id: tel-04441308

https://theses.hal.science/tel-04441308

Submitted on 6 Feb 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_4.png" /></figure>

# THÈSE DE DOCTORAT D'AVIGNON UNIVERSITÉ

École Doctorale n°536
Agrosciences & Sciences

Mention de doctorat :
Informatique

Laboratoire Informatique d'Avignon

Présentée par
Noé CÉCILLON

## Combining Graph and Text to Model Conversations:
An Application to Online Abuse Detection

Soutenue publiquement le 18 janvier 2024 devant le jury composé de :

<table><tr><td>Irina ILLINA</td><td>MCF HDR à Université de Lorraine, LORIA/INRIA</td><td>Rapporteuse</td></tr><tr><td>Julien VELCIN</td><td>PR à Université Lyon 2, ERIC</td><td>Rapporteur</td></tr><tr><td>Serena VILLATA</td><td>DR à Institut 3IA Côte d'Azur</td><td>Examinatrice</td></tr><tr><td>Harold MOUCHÈRE</td><td>PR à Nantes Université, LS2N</td><td>Président du jury</td></tr><tr><td>Vincent LABATUT</td><td>MCF HDR à Avignon Université, LIA</td><td>Directeur de thèse</td></tr><tr><td>Richard DUFOUR</td><td>MCF à Avignon Université, LIA</td><td>Co-directeur de thèse</td></tr></table>
ACKNOWLEDGEMENTS

This work would not have been accomplished without the help and encouragement of many people.

Firstly, I would like to sincerely thank Irina Illina and Julien Velcin for accepting to review my
PhD thesis. I thank them for all the time and efforts they have committed to thoroughly read this
manuscript. I also extend my thanks to Serena Villata and Harold Mouchère for participating in my
thesis defense.

I would like to express my deepest gratitude to my advisors Vincent Labatut and Richard Dufour.
I thank you for the trust you placed in me and all the help you have given me over the past 4 years.
This entire thesis would not have been possible without your advice and expertise. I believe that
the end of this thesis only marks a fresh start for future and fruitful collaborations with you.

Thanks to all my colleagues from the LIA for your welcome and for the numerous and various
discussions.

I am also grateful to all the people involved in any way in this thesis. Particular thanks to
Thomas without whom none of this would have happened.

I warmly thank all my friends for the great moments we spent together. Special thanks to Laure
and Renzo, we're going to hell, but we had a good laugh.

Last but not least, I would like to heartily thank my parents for their support during my studies.
Mom, you are the one that convinced me I was able to do this. I thank you for that, though you still
do not fully understand what I am working on. Thanks to my sisters and brother for their continuous
encouragements.
ABSTRACT

Online abusive behaviors can have devastating consequences on individuals and communities. With the global expansion of internet and the social networks, anyone can be confronted with these behaviors. Over the past few years, laws and regulations have been established to regulate this kind of abuse but the responsibility ultimately lies with the platforms that host online communications. They are asked to monitor their users in order to prevent the proliferation of abusive content. Timely detection and moderation is a key factor to reduce the quantity and impact of abusive behaviors. However, due to the sheer quantity of online messages posted every day, platforms struggle to provide adequate resources. Since this implies high human and financial costs, companies have a keen interest in automating this process. Although it may seem a relatively simple task, it turns out to be quite complex. Indeed, malicious users have developed numerous techniques to bypass the standard automated methods. Allusions or implied meaning are other examples of strategies that automatic methods struggle to detect. While usually performed on individual messages taken out of their context, it has been shown that automatic abuse detection can benefit from considering the context in which the message was posted.

In this thesis, we want to focus on the combination of content and structure of conversations to tackle the abuse detection task. Using the textual content of messages is the standard approach which was first developed in the literature. It has the advantage of being easy to set up, but on the other hand, it is vulnerable to text-based attacks such as obfuscation. The structure of the conversation which represent the context is less frequently used as it is more complicated to manipulate. Yet it allows to introduce a contextual aspect which helps detecting abuse occurrences when the text on its own is not sufficient. This context can be modeled as a contextual graph representing the conversation which includes the message. By comparing two methods based on feature engineering on a dataset of conversations extracted from a video games, we could show that a method relying exclusively on conversational graphs and ignoring the content was able to obtain better detection performance. The literature suggest that combining multiple modalities often result in a better detection of abusive messages. We propose multiple strategies to combine the content and structure of conversations and prove that their combination is indeed beneficial to the detection.

A limitation of feature-based methods is that they are costly in time and computational resources. Our study also highlights that only a fraction of the computed features are truly relevant for the task. Representation learning methods can be used to mitigate these issues by automati-
cally learning the representations of text and conversational graphs. For graphs, we demonstrated that using edge weights, signs and directions improved the performance. As no method exists for signed whole-graph embedding, we fill this gap in the literature by developing two such methods. We assess them on a newly constituted benchmark of three datasets of signed graphs and show that they perform better than their unsigned counterparts.

Lastly, we perform a comparative study of several lexical and graph-embedding method for abuse detection by applying them to our dataset of conversations. Our results show that they perform better than feature-based approaches on text and are slightly less effective on graphs. Still, they obtain promising results given that they are completely task independent, much more scalable and time-efficient than feature-based approaches.
# RÉSUMÉ

Les comportements abusifs en ligne peuvent avoir des conséquences dramatiques sur les utilisateurs et les communautés. Avec l'avènement d'internet et des réseaux sociaux, personne n'est à l'abri de ce genre de comportement. Ces dernières années, de nombreux pays ont mis en place des lois visant à réduire ce type d'abus. Cependant, la responsabilité incombe principalement aux entreprises hébergant ces plateformes de discussion. Celles-ci se doivent de surveiller le comportement de ses utilisateurs afin d'éviter la prolifération de propos abusifs. Une détection et un traitement rapide des cas abusifs est un facteur important afin de réduire leur impact et leur nombre. Cependant, les plateformes en ligne ont souvent du mal à fournir les ressources nécessaires à cette détection à cause de la très grande quantité de messages postés chaque jour. Cette tâche de modération impliquant d'importants coûts humains et financiers, les entreprises ont un gros intérêt à l'automatiser. Bien que celà puisse paraître assez basique au premier abord, la détection automatique de contenu abusif se révèle assez complexe. En effet, les utilisateurs malveillants ont développé de nombreuses techniques pour tromper les méthodes automatiques. Par exemple, les propos implicites et l'utilisation de sous-entendus permettent souvent de ne pas se faire détecter par les méthodes automatiques standards. Pour contrer ce problème, il a été montré que prendre en compte le contexte dans lequel un message est posté permet d'améliorer la détection. Cependant la méthode la plus courante dans la littérature consiste à traiter des messages individuels, pris en dehors de leur contexte.

Dans ce manuscrit, on s'intéresse plus particulièrement à la combinaison du contenu et de la structure pour la détection de contenu abusif. Utiliser le contenu textuel des messages est l'approche la plus courante dans la littérature. Cette méthode présente l'avantage d'être facile à mettre en place, mais elle est aussi très vulnérable aux attaques basées sur le texte, notamment aux techniques d'obfuscation. La structure de la conversation, représentant le contexte, est beaucoup moins étudiée car elle est plus complexe à manipuler. Pourtant, elle permet d'introduire une notion de contexte qui permet de détecter des cas abusifs là où le texte seul n'en est pas capable. Ce contexte peut être modélisé sous la forme d'un graphe conversationnel représentant la conversation contenant le message étudié. En comparant deux méthodes construites à partir d'un procédé d'extraction de caractéristiques (feature engineering), nous avons montré qu'une méthode n'utilisant que des graphes conversationnels et ignorant le contenu textuel des messages était capable d'obtenir de meilleures performances. Des auteurs dans la littérature suggèrent que combiner plusieurs modalités d'information permet d'améliorer la détection de messages abusifs. À
cet effet, nous proposons plusieurs stratégies pour combiner le contenu et la structure des conve-
sations et par nos expériences, nous prouvons que celà est en effet bénéfique pour la détection.

Une limitation de ces méthodes basées sur un ensemble de mesures est qu'elle sont assez
coûteuses tant en ressources informatiques qu'en temps de conception. Notre étude montre égale-
ment que seule une fraction des mesures calculées sont réellement importantes pour cette tâche.
Les méthodes d'apprentissage de représentations peuvent être une solution à ce problème, en per-
mettant d'apprendre automatiquement la représentation numérique d'un message ou d'un graphe
conversationnel. Pour les graphes, nous avons démontré que considérer les attributs des liens,
à savoir la direction, le poids et le signe, permet d'améliorer les performances. La littérature ne
proposant aucune méthode de plongement de graphe entier signé, nous comblons ce vide en
développant deux méthodes de ce type. Nous les évaluons sur un benchmark nouvellement créé
et constitué de trois jeux de données de graphes signés, et prouvons qu'ils obtiennent de meilleurs
résultats que leurs équivalents ne prenant pas en compte les signes.

Finalement, nous menons une étude comparative de plusieurs méthodes de plongement lexí-
cal et de graphes pour la détection de messages abusifs en les appliquant à un jeu de données de
conversations. Nos résultats montrent qu'elles sont plus efficaces que les méthodes se basant sur
un ensemble de mesures pour le texte, et légèrement moins efficaces pour les graphes. Cepen-
dant, ces résultats restent très encourageants car ces méthodes possèdent de nombreux autres
avantages tels qu'être complètement indépendantes de la tâche, plus faciles à adapter à d'autres
environnements d'utilisation, et beaucoup plus efficaces en termes de temps.
TABLE OF CONTENTS

<table><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>1 Introduction</td><td>11</td></tr><tr><td>1.1 Contributions</td><td>13</td></tr><tr><td>1.2 Personal Bibliography</td><td>14</td></tr><tr><td>1.3 Thesis Outline</td><td>15</td></tr><tr><td>2 Survey of Online Abuse Detection</td><td>17</td></tr><tr><td>2.1 Definition of Online Abuse</td><td>18</td></tr><tr><td>2.2 Abuse Detection Methods</td><td>19</td></tr><tr><td>2.2.1 Textual Methods</td><td>19</td></tr><tr><td>2.2.2 Contextual Methods</td><td>22</td></tr><tr><td>2.3 Datasets</td><td>25</td></tr><tr><td>2.3.1 Existing Datasets</td><td>25</td></tr><tr><td>2.3.2 Datasets Related to this Thesis</td><td>27</td></tr><tr><td>2.4 Formalization and Evaluation</td><td>29</td></tr><tr><td>2.4.1 Formalization of Abuse Detection</td><td>29</td></tr><tr><td>2.4.2 Evaluation Metrics</td><td>30</td></tr><tr><td>2.5 Conclusion</td><td>31</td></tr><tr><td>3 Graph metrics as graph features</td><td>33</td></tr><tr><td>3.1 Definitions and Notations</td><td>34</td></tr><tr><td>3.2 Vertex-Focused Topological Measures</td><td>35</td></tr><tr><td>3.2.1 Microscopic Measures</td><td>35</td></tr><tr><td>3.2.2 Macroscopic Measures</td><td>37</td></tr><tr><td>3.2.3 Mesoscopic Measures</td><td>41</td></tr><tr><td>3.3 Graph-Focused Topological Measures</td><td>42</td></tr><tr><td>3.3.1 Microscopic Measures</td><td>42</td></tr><tr><td>3.3.2 Macroscopic Measures</td><td>43</td></tr><tr><td>3.3.3 Mesoscopic Measures</td><td>44</td></tr><tr><td>3.4 Conclusion</td><td>44</td></tr></tbody></table>
<table>
  <tbody>
    <tr>
      <td><b>4</b></td>
      <td><b>Feature Engineering for Abuse Detection</b></td>
      <td><b>45</b></td>
    </tr>
    <tr>
      <td>4.1</td>
      <td>Graph Extraction from Conversations</td>
      <td>47</td>
    </tr>
    <tr>
      <td>4.2</td>
      <td>Proposed Representation Methods</td>
      <td>51</td>
    </tr>
    <tr>
      <td>4.2.1</td>
      <td>Text-Based Features</td>
      <td>51</td>
    </tr>
    <tr>
      <td>4.2.2</td>
      <td>Graph-Based Features</td>
      <td>54</td>
    </tr>
    <tr>
      <td>4.2.3</td>
      <td>Combining the Textual and Structural Information</td>
      <td>56</td>
    </tr>
    <tr>
      <td>4.3</td>
      <td>Experiments</td>
      <td>58</td>
    </tr>
    <tr>
      <td>4.3.1</td>
      <td>Experimental Protocol</td>
      <td>58</td>
    </tr>
    <tr>
      <td>4.3.2</td>
      <td>Classification Results</td>
      <td>59</td>
    </tr>
    <tr>
      <td>4.3.3</td>
      <td>Feature Study</td>
      <td>61</td>
    </tr>
    <tr>
      <td>4.4</td>
      <td>Analysis and Discussion</td>
      <td>65</td>
    </tr>
    <tr>
      <td>4.4.1</td>
      <td>Temporal Aspect</td>
      <td>65</td>
    </tr>
    <tr>
      <td>4.4.2</td>
      <td>Impact of Edge Attributes</td>
      <td>66</td>
    </tr>
    <tr>
      <td>4.5</td>
      <td>Conclusion</td>
      <td>67</td>
    </tr>
    <tr>
      <td><b>5</b></td>
      <td><b>Signed Whole-Graph Embedding</b></td>
      <td><b>69</b></td>
    </tr>
    <tr>
      <td>5.1</td>
      <td>Definitions and Notations</td>
      <td>71</td>
    </tr>
    <tr>
      <td>5.2</td>
      <td>Graph Representation Learning</td>
      <td>72</td>
    </tr>
    <tr>
      <td>5.2.1</td>
      <td>Vertex Embedding</td>
      <td>73</td>
    </tr>
    <tr>
      <td>5.2.2</td>
      <td>Whole-Graph Embedding</td>
      <td>76</td>
    </tr>
    <tr>
      <td>5.2.3</td>
      <td>Signed Graph Embedding</td>
      <td>78</td>
    </tr>
    <tr>
      <td>5.3</td>
      <td>Datasets</td>
      <td>80</td>
    </tr>
    <tr>
      <td>5.3.1</td>
      <td>Correlation Clustering Instances</td>
      <td>81</td>
    </tr>
    <tr>
      <td>5.3.2</td>
      <td>European Parliament Roll-Calls</td>
      <td>81</td>
    </tr>
    <tr>
      <td>5.3.3</td>
      <td>Brief Comparison</td>
      <td>82</td>
    </tr>
    <tr>
      <td>5.4</td>
      <td>Proposed Methods</td>
      <td>83</td>
    </tr>
    <tr>
      <td>5.4.1</td>
      <td>Signed Network Embedding</td>
      <td>83</td>
    </tr>
    <tr>
      <td>5.4.2</td>
      <td>Signed Graph2vec</td>
      <td>84</td>
    </tr>
    <tr>
      <td>5.4.3</td>
      <td>Signed Graph Convolutional Networks</td>
      <td>85</td>
    </tr>
    <tr>
      <td>5.5</td>
      <td>Experiments</td>
      <td>86</td>
    </tr>
    <tr>
      <td>5.5.1</td>
      <td>Results</td>
      <td>87</td>
    </tr>
    <tr>
      <td>5.5.2</td>
      <td>Comparison</td>
      <td>92</td>
    </tr>
    <tr>
      <td>5.6</td>
      <td>Conclusion</td>
      <td>93</td>
    </tr>
    <tr>
      <td><b>6</b></td>
      <td><b>Representation Learning for Abuse Detection</b></td>
      <td><b>95</b></td>
    </tr>
    <tr>
      <td>6.1</td>
      <td>Embedding Methods</td>
      <td>98</td>
    </tr>
    <tr>
      <td>6.1.1</td>
      <td>Lexical Embedding Methods</td>
      <td>98</td>
    </tr>
    <tr>
      <td>6.1.2</td>
      <td>Selected Graph Embedding Methods</td>
      <td>100</td>
    </tr>
  </tbody>
</table>
<table><tbody><tr><td>6.1.3 Proposed Whole-Graph Embedding Methods</td><td>103</td></tr><tr><td>6.2 Experiments</td><td>106</td></tr><tr><td>6.2.1 Experimental Protocol</td><td>107</td></tr><tr><td>6.2.2 Classification Results</td><td>107</td></tr><tr><td>6.2.3 Fusion of Embeddings</td><td>113</td></tr><tr><td>6.2.4 Results Summary</td><td>115</td></tr><tr><td>6.3 Feature Study</td><td>115</td></tr><tr><td>6.3.1 Text Features</td><td>116</td></tr><tr><td>6.3.2 Graph Features</td><td>116</td></tr><tr><td>6.4 Conclusion</td><td>118</td></tr><tr><td><b>7 Conclusion and Perspectives</b></td><td><b>121</b></td></tr><tr><td>7.1 Conclusion</td><td>121</td></tr><tr><td>7.2 Perspectives</td><td>123</td></tr><tr><td><b>Appendices</b></td><td><b>126</b></td></tr><tr><td><b>A Text and Graph Joint Embedding</b></td><td><b>127</b></td></tr><tr><td>A.1 Flair Embedding</td><td>127</td></tr><tr><td>A.2 Proposed Architecture</td><td>127</td></tr><tr><td><b>B Datasets</b></td><td><b>129</b></td></tr><tr><td>B.1 Reddit</td><td>129</td></tr><tr><td>B.1.1 Limitations of Reddit</td><td>130</td></tr><tr><td>B.2 Wikipedia Abusive Conversations</td><td>130</td></tr><tr><td>B.2.1 Proposed Corpus</td><td>131</td></tr><tr><td>B.2.2 Limitations of WAC</td><td>133</td></tr><tr><td><b>References</b></td><td><b>135</b></td></tr></tbody></table>
INTRODUCTION

Online abusive behaviors can harm a platform or community in the long term. From targeted personal attacks to major threats toward a group of persons, these behaviors can have a devastating effect. They may have a lasting impact on the mental health, confidence, and sense of safety of the victims [1]. In extreme cases, they can even trigger legal issues in some countries. In their 2021 study, Hinduja et al. [2] stated that 45.5% of the audited US middle and high schoolers had been cyberbullied during their lifetime. Because we focus exclusively on online abuse, we use the term *abuse* to refer to *online abuse* in the rest of this thesis. We also limit our study to text documents, although online abuse can be found in other media including audio, video, or animation. With the ever-growing quantity of text messages generated on the internet each year, the monitoring and detection of abusive content online has become a task of prime importance. This is a complex task, as abusive messages often make use of innuendos, irony, implicit statements or even refer to past events shared by the persons involved in the conversation. In these conditions, it is mandatory to understand the true meaning of a message before deciding whether to sanction its author.

The monitoring of online exchanges is usually done by human moderators to ensure the quality of the moderation. However, due to the increasingly global use of the Internet, it is often difficult for human moderators to treat all abusive comments on time. At the same time, online platforms are now responsible for the content that they host in multiple countries, which means that it can trigger legal issues if they fail to correctly moderate their content. Therefore, they have a strong interest in automating this moderation process. While a fully automated system can be difficult to implement, particularly because of the risk of censorship, a semi-automatic system can be used to assist human moderators for instance by pre-processing the comments and filtering out all the correct ones.

The standard approach to automatically detect abusive messages online is to do so by analyzing their content. Some markers of abuse, including swear words, and offensive or hateful expressions can easily be detected in this way. However, one can wonder if such expressions are necessarily representative of an abusive message. For instance, does quoting a previous message containing swear words make yours abusive? Does making a lame joke to a friend make you a harasser? The answer often depends on some general information, covering a wider scope than just the message itself. This is one of the reasons why it is difficult to automatically detect abusive comments. To overcome this, depending on the framework and application, multiple el-
lements can be considered such as the shared history between users, demographic data, or the conversation preceding the problematic message. This latter point is particularly important. Tweets taken without their conversational context are 50% more likely to be labeled as abusive by human annotators than the same tweets provided in their context [3]. While effective in many cases, a limitation of methods using the content to detect abuse is their vulnerability to text-based attacks such as obfuscation [4].

The structure of a conversation can reflect the presence of an abusive author. Indeed, they tend to participate significantly more in the discussions than others and to receive more replies than regular users [5]. It can be done deliberately by adopting a troll-like behavior to draw users into pointless discussions. It can also simply result from the fact that humans tend to react more to controversial subjects. Either way, the abusive author plays a central role in the conversation, and one can assume that the changes reflected in its structure can help discover an abuse case. Previous studies [6] showed that modeling conversations under the form of conversational graphs and characterizing them through various topological measures was efficient in detecting abusive messages. These graphs represent the structure of the conversation. This structure-based approach which completely ignores the content of the messages achieves even better results than a content-based method.

Combining multiple information modalities to analyze textual documents has proved effective on multiple tasks including sentiment analysis [7], named entity recognition [8], and recommen-
dation [9]. For abuse detection, multimodal methods improve the performance of traditional text-
oriented techniques. However, they are mainly centered around the combination of content and
contextual data. The structure of the conversation is almost always overlooked in the literature. In
a previous work conducted by our research team, Papegnies et al. [6] proposed a method based
on the dynamics of conversation able to obtain strong results. The objective of this thesis is to
go further and combine message content and conversation structure to build a representation that
takes advantage of both and use this representation to improve the detection of abusive comments
in online conversations.

Such combination can be conducted in several ways, which we explore in this manuscript.
For any text classification task, the first step usually consists of transforming the raw input data into
numeric representations. From the traditional feature-based strategies [6], [10]–[13] to more recent
representation learning techniques [14]–[17], a lot of methods have been tested in the literature.
By construction, they all capture different aspects of the input data. Furthermore, their efficiency
is often closely related to the application and the data. We propose new methods and apply both
traditional feature engineering-based approaches and more recent representation learning-based
methods, in order to compare them to our abuse detection class and assess their complementarity.
1.1 Contributions

This thesis brings several contributions to the literature, the most prominent being three-fold.
The first 2 arise in the context of abuse detection, while the third is specific to graph embeddings:

*   **Combination of graph and text:** Many works in the literature combine different modalities of data to tackle the abuse detection task. It has been shown that including contextual information related to authors and conversations helps improve the classification compared to a content-only setting. The structure of the conversation, modeled by conversational graphs, is impacted by the behavior of users. This structural information on its own is able to obtain strong performance, and it has never been used in combination with other modalities. We propose multiple strategies to combine the text and the graphs to detect abusive messages in conversations.

* **Signed whole-graph embedding:** When leveraging graph-based approaches, we need to represent entire graphs. Whole-graph embedding methods are specifically designed to perform this task. As shown empirically, graph edges can include properties such as weights, directions, and signs, which are likely to improve the classification performance for abuse detection. However, all whole-graph embedding methods existing in the literature focus on unsigned graphs. Therefore, we propose 2 methods to fill this gap. The first is an adaptation of an *unsigned* whole-graph embedding approach to *signed* graphs, whereas the second is based on signed *vertex* representations, which we adapt to handle *whole* signed graphs.

*   **Comparison of feature-based and embedding methods for abuse detection:** To combine content and structure, we develop methods to treat these aspects individually before combining them. We proceed in 2 successive steps.

1. First, we study feature-based methods leveraging the content and the graphs (i.e. structure). We also perform a feature ablation study to determine the most important features.

2. Second, we use several text and graph embedding methods of different natures, in order to automate the learning of representations. We determine the most efficient for the abuse detection task.

We compare these 2 approaches in different aspects.

Besides these prominent contributions, this thesis also advances the field in 2 more minor
aspects:

*   **Network extraction:** To extract conversational graphs from conversation logs, we extend an existing network extraction method to obtain signed weighted directed graphs, as the original method is unable to produce signed graphs.
* **Data availability:** The development of abuse detection methods leveraging the structure of the conversation is limited by a lack of publicly available datasets. To tackle this issue, we made available the collection of conversational graphs extracted from our SpaceOrigin dataset and used throughout this thesis<fnref n="1" />. We also constituted the WAC dataset, that contains Wikipedia-based conversations annotated for 3 types of abuses [18]. Finally, we assembled a benchmark composed of 3 collections of signed networks annotated for diverse classification tasks.

## 1.2 Personal Bibliography

The following articles have been published in the framework of this PhD thesis:

* **International journal with peer review**

- N. Cécillon et al., "Graph embeddings for abusive language detection," *SN Computer Science*, vol. 2, no. 37, 2021. DOI: 10.1007/s42979-020-00413-7 (Chapter 6)

* **International conferences with peer review**

- N. Cécillon et al., "Abusive language detection in online conversations by combining content- and graph-based features," *Frontiers in Big Data*, vol. 2, p. 8, 2019, ISSN: 2624-909X. DOI: 10.3389/fdata.2019.00008 (Chapter 4)

- N. Cécillon et al., "WAC: A corpus of wikipedia conversations for online abuse detection," in *12th International Conference on Language Resources and Evaluation*, 2020. [Online]. Available: http://www.lrec-conf.org/proceedings/lrec2020/pdf/2020.lrec-1.173.pdf (Chapter 2)

* **National journal with peer review**

- N. Cécillon et al., "Approche multimodale par plongement de texte et de graphes pour la détection de messages abusifs," *Trajetoy Automatique des Langues*, vol. 62, no. 2, pp. 13–38, 2021. [Online]. Available: https://www.atala.org/sites/default/files/TAL_62_2_v2.pdf (Chapter 6)

* **National conference with peer review**

- N. Cécillon et al., "Tuning graph2vec with node labels for abuse detection in online conversations," in *11th MARAMI*, 2020. [Online]. Available: http://ceur-ws.org/Vol-2750/paper8.pdf (Chapter 6)

<footnote n="1">¹https://figshare.com/articles/dataset/Conversational_Networks_From_Automatic_Online_Moderation/7442273?file=24681479</footnote>
• Submitted article

– N. Cécillon et al., "Whole-graph representation learning for the classification of signed networks," *Submitted*, 2023 (Chapter 5)

1.3 Thesis Outline

The thesis is organized as follows.

* Chapter 2: We introduce the abuse detection task and review the literature associated with it.

* Chapter 3: We review the existing graph measures that can be used as classification features, to characterize the structure of a graph.

* Chapter 4: We describe our framework based on feature engineering to detect abusive messages using the textual content and the conversation structure. Using the measures previously described, we put it into practice on a conversation dataset, discuss its results, and perform a feature ablation study.

* Chapter 5: Because of the limitations detected in the previous approach, we want to use representation learning to automatically learn representations of messages and graphs. The previous chapter shows that edge attributes, including edge signs, bring useful information for the classification. As no signed whole-graph embedding methods currently exist in the literature, we propose 2 of them that we will later use to detect abusive messages. We evaluate the proposed methods on a new benchmark of 3 datasets and discuss their results.

* Chapter 6: We present our framework based on representation learning to detect abusive messages. We compare several text and graph embedding methods, including those proposed in Chapter 5, on the same conversation dataset as before. We discuss the results and perform a feature study.

* Chapter 7: We summarize our work, and identify its main perspectives.
SURVEY OF ONLINE ABUSE DETECTION

<table><tr><td>2.1 Definition of Online Abuse</td><td>18</td></tr><tr><td>2.2 Abuse Detection Methods</td><td>19</td></tr><tr><td>2.2.1 Textual Methods</td><td>19</td></tr><tr><td>2.2.2 Contextual Methods</td><td>22</td></tr><tr><td>2.3 Datasets</td><td>25</td></tr><tr><td>2.3.1 Existing Datasets</td><td>25</td></tr><tr><td>2.3.2 Datasets Related to this Thesis</td><td>27</td></tr><tr><td>2.4 Formalization and Evaluation</td><td>29</td></tr><tr><td>2.4.1 Formalization of Abuse Detection</td><td>29</td></tr><tr><td>2.4.2 Evaluation Metrics</td><td>30</td></tr><tr><td>2.5 Conclusion</td><td>31</td></tr></table>

Online abuse includes malicious behaviors that have a threatening, intimidating or harassing effect on a group or an individual target. Detecting these behaviors is thus an important task, that researchers tackle with different approaches, including a majority based on the text and some based on different aspects of the conversation. The latter includes the use of conversational graphs to represent the dynamics of the conversation, as we will see in the remainder of this thesis. A key part in the development of an abuse detection method is to obtain a suitable dataset, but this often proves to be a complex task because of multiple factors that can affect the quality of human annotations in such datasets.

The following chapter is partially based on our work published at the *International Conference on Language Resources and Evaluation (LREC 2020)* [18]. It makes the following contributions:

1. We give a definition of what constitutes an online abuse based on the literature.

2. We survey the abuse detection methods and distinguish several categories depending on the information they use.

3. We review the publicly available datasets annotated in terms of abuse. This includes datasets of individual messages and datasets of messages in a flow of conversations. We also present
the 2 datasets related to this thesis, one is an original contribution and the other was previ-
ously developed in the same research team.

4. We formalize the abuse detection problem and present the standard evaluation settings for this task.

This chapter is organized as follows. In Section 2.1, we first define the concept of an online
abuse. Second, we present and categorize the automatic abuse detection methods proposed in
the literature in Section 2.2. In Section 2.3 we present the annotated datasets for abuse detection,
including the 2 that are related to this thesis: one that we constituted and published, and the other
that was previously used in our research team. We then formalize the problem of online abuse
detection, and describe the standard evaluation methods in Section 2.4. Finally, we conclude this
chapter in Section 2.5.

## 2.1 Definition of Online Abuse

Online abuse can be defined as the use of electronic media devices to cause harm to an-
other person<fnref n="1" />. This wide concept points at a number of distinct abusive behaviors including hate
speech, cyberbullying or impersonation. Some of these terms may be used interchangeably, which
makes it difficult to have a consistent definition. To ease comparison, we curate the most accepted
definitions from the literature of the main online abusive tactics.

**Hate speech:** Offensive discourse targeting a group or an individual based on inherent char-
acteristics such as gender, religion, age, origin or sexual orientation [24], [25].

**Cyberbullying:** A repeated behavior, aimed at shaming or scaring an individual target. It includes posting embarrassing content of someone on social media and repeatedly sending hurtful remarks [26], [27].

**Impersonation:** The act of pretending to be another person on an online platform for the purpose of degrading or exploiting its public image [28].

**Defamation:** The action of posting comments with the intent to harm someone else's reputa-
tion, for instance by spreading lies [29], [30].

**Doxing:** The act of searching and publicly providing private information about a particular
individual on the internet, typically with malicious intent [31], [32].

In this thesis, we use a general definition of *abuse*. We can describe it as all behaviors that do
not respect the rules of the community in which the user is posting. Some of them can be specific
to one community, but there is almost always a common core of rules prohibiting personal attacks,
discrimination based on race, religion, or sexual orientation, as well as impersonation and doxing.

<footnote n="1">¹https://cpdonline.co.uk/knowledge-base/safeguarding/online-abuse/</footnote>
These various types of abuse are not without consequences and can have a negative impact on the people receiving these messages. Moderation is the process of monitoring user-generated content and taking actions against users who act abusively. This task is usually done by human moderators to ensure a high-level of moderation quality. Timely detection and moderation is a key factor to reduce the quantity and impact of abusive behaviors. However, due to the ever-growing quantity of content generated daily on the Internet, platforms struggle to provide adequate resources. Since this implies high human and therefore financial costs, companies have a keen interest in automating this process. Although it may seem a relatively easy task, it turns out to be quite complex. Indeed, over the years, malicious users have developed numerous techniques to bypass automated systems. In most situations, abuse comes as a text message, but it is not restricted to that. On platforms allowing to post multimedia content, abuse can come as a video, picture or audio record. However, this thesis focuses on text documents, so we will not consider such situations.

## 2.2 Abuse Detection Methods

2 main families of automatic approaches emerged in the abuse detection literature. The first and most widespread one is based on the textual content of the targeted message. Such methods can rely on a mix of standard Natural Language Processing (NLP) features, or be more machine learning-intensive with embedding-based approaches. The quality of these methods is however very often related to the training data used to learn abuse detection models. In the case of online social networks, the great variety of users, including very different language registers, spelling mistakes, as well as intentional obfuscation, makes it almost impossible to have models robust enough to be applied in all situations. Therefore, some authors consider contextual information to treat the abuse detection task. This may involve the messages occurring around the targeted message as well as information on the users themselves. Automatic abuse detection methods can be used in different settings. They can be used in a fully automated fashion, where they detect abusive instances and apply sanctions without any human intervention. The most common case, however, is a semi-automated framework where these methods are used to filter the potential abusive messages and human moderators review this small set of messages to take a decision. This pre-filter can greatly reduce the moderator's workload, and thus, the associated cost. In this section, we review the abuse detection literature, by first focusing on the textual methods (Section 2.2.1), then on the contextual methods (Section 2.2.2).

### 2.2.1 Textual Methods

The methods relying on the content of the targeted message to detect abuse or similar properties are the most widespread in the literature. We can divide them into 2 categories: standard
methods based on feature engineering, and more recent ones based on neural networks.

2.2.1.1 Feature Engineering-Based Methods

Spertus [33] was among the first to propose an automatic method for abuse detection. She
hand-crafted rules over text to generate a feature vector composed of 47 elements representing
the syntax and semantics of sentences. The rules are based on the author's observations of
abusive and non-abusive messages. Such a manual feature engineering process was later used
by Razavi et al. [10] who collected an Insulting and Abusive Language Dictionary composed of
2,700 words and expressions. Each entry is assigned a weight based on its potential abusive
impact. Other works adopted such a lexicon-based approach later on [34]–[38]. Static rules and
lexicon-based features are most of the time used as parts of systems, and combined with other
techniques such as TF-IDF [11], [39], [40] and bag-of-words [11], [41].

The manual construction of an abuse lexicon is expensive, and results in a language-dependent dictionary. Wiegand et al. [42] propose a framework to automate this process. First, they build a small lexicon of negative polar expressions annotated via crowdsourcing. Then they extract a set of hand-crafted linguistic and semantic features to train an SVM which is used to automatically expand the lexicon. Mubarak et al. [43] propose a similar idea, but to expand a vocabulary of obscene words in Arab media. They perform a log odds ratio analysis to detect the words favoring documents categorized as obscene. This approach however requires a dataset with a wide variety of abusive and obscene words.

In sentiment analysis, the main objective is to detect the polarity of a message. In the context of abuse detection, a negative polarity can be seen as a marker of abuse. On other tasks such as authorship identification, sentiment analysis helped improve classification [44]. It was therefore adapted to detect various forms of abuse like hate speech [12], [13] and sexual harassment [45]. A limitation to this approach noted in [12] is that the words' meanings can change according to the context. For instance, the expression "You are stupid" is clearly offensive, whereas "This is stupid" is not. Hence, the aforementioned frameworks usually use sentiment-based features in combination with other syntactic, linguistic and lexicon-based features.

2.2.1.2 Neural Networks-Based Methods

With the advancements in computational capabilities, researchers have rapidly introduced abuse
detection methods that rely on neural architectures. We first present those using distributed repre
sentations of messages, then those that don't but still use deep learning.
### 2.2.1.2.1 Distributed Representations

Djuric et al. [46] use the paragraph2vec [47] framework to learn low-dimensional representations of messages, and then train a logistic regression classifier to discriminate them based on this representation. With this method, they are able to outperform models trained on representations constructed from bag-of-words. An important observation of the authors is that text obfuscation in abusive comments leads to a high dimensionality and sparsity in bag-of-word representations, which has a negative impact on the classifier's performance. Nobata et al. [24] improve upon this work by training a regression model on a set of features derived from 4 different categories: word and character N-grams, linguistic features, syntactic features and distributional representations. They obtain the best results with all features combined, but note that character N-grams contribute significantly more to the performance than other features. Pavlopoulos et al. [48] and Mishra et al. [49] use 3 datasets annotated for toxicity, personal attacks and aggression to train Recurrent Neural Networks (RNN) operating on word embeddings and character N-gram features. Subsequently, numerous methods based on word embedding representations have been proposed to detect different types of abuse. This includes methods based on GloVe [50]–[54], FastText [50], [54], word2vec [52], [55], [56] and BERT [16], [17], [57]. Caselli et al. proposed HateBERT [58], a BERT model specifically designed for abusive language detection in English. To train HateBERT, they collect a dataset of approximately 1.5 million messages in English from various Reddit communities banned for being offensive, abusive, or hateful. They demonstrate better performance with HateBERT than a standard BERT model on multiple datasets. A number of studies are based on this model [59], [60].

### 2.2.1.2.2 Deep Learning

Badjatiya et al. [50] investigate different neural architectures trained for hate speech detection. They obtain their best performance with a Long-Short Term Memory (LSTM) model operating on word-level. Park et al. [61] classify sexist and racist abusive language by implementing 3 CNN-based models operating on different granularities of input features: characters, words or both. The model combining both characters and words outperforms the other models which use them separately and a logistic regression classifier based on N-grams used as a baseline. Akhter et al. [62] also show that deep learning models perform significantly better than machine learning models to detect abusive language in Urdu and Roman Urdu comments. They compare 4 architectures (Convolutional Neural Network, LSTM, Bidirectional-LSTM, and Contextual-LSTM) and obtain better results with one-layer than 2-layer architectures. The best performance being achieved by CNN. A tendency in recent studies is to develop hybrid deep learning models that combine multiple models instead of using them individually. This tendency is justified by the complexity of the task. The limitations of independent models can be complemented when used in combination with
one another, hence enhancing the overall performance of the system. We can cite CNN, LSTM, Bidirectional-LSTM and Gated Recurrent Units as some of the most widespread models in these hybrid architectures [63]–[67].

### 2.2.1.3 Discussion

There is a huge variety of methods relying on the content of the targeted message to detect abuse or related properties. Some of them use basic sets of hand-crafted rules while more sophisticated methods implement multiple deep learning architectures. While being generally more effective, the latter require large datasets for training. Since textual methods are usually language-dependent, they have to be trained on a dataset of the specific language, which can be difficult to find or constitute for low-resource languages. It is also common that a model trained on a particular type of text is not efficient on another type of text. Textual methods obtain very strong performance on multiple datasets and tasks. However, they have limitations when the abusive nature of a message is not only related to its content, but also to surrounding messages or contextual information. For instance, abuse can be spread over successive messages or can reference a shared history between users. This makes the detection more difficult. Furthermore, as noted in different studies [33], [42], they are vulnerable to text-based attacks. Abusive users can voluntarily obfuscate message content to deceive automatic methods based on text. Usual techniques include replacing letters (e.g. *f u c k*, *f-u-c-k*) and more sophisticated methods such as encoding text in binary or hexadecimal. Hosseini et al. [4] demonstrate such an attack against the Perspective API<fnref n="2" />, an API developed to mitigate toxicity online. For abusive comments, they are able to reduce the toxicity score given by the API to the level of benign phrases by slightly modifying the toxic words.

### 2.2.2 Contextual Methods

To address the aforementioned problems with the methods focusing on the content of the exchanged messages, some authors propose to consider the context of these messages. Menini et al. [3] explore the role of such context in abusive language annotation. They annotate 8,000 tweets in 2 conditions: with and without context. They find that almost half of the single tweets (i.e. tweets without context) labeled as abusive are later labeled as non-abusive when considering the context. This proves how context-dependent the offensiveness of swearing is. Yin et al. [39] also state that they often need to look at the context of a post to make a decision when manually labeling training data. In their comprehensive study of antisocial behavior in online discussion communities, Cheng et al. [5] add that instances of abusive messages generate significantly higher number of replies than regular messages. As the context can take multiple forms, we divide the context-based meth-

<footnote n="2">²https://perspectiveapi.com/</footnote>
ords for abuse detection in 2 categories: those using the text surrounding a message and those using user-based features.

### 2.2.2.1 Surrounding Text-Based Features

Based on the previous observations, we can assume that the messages surrounding an abuse case can give precious information on the nature of this targeted message. In their model, Yin et al. [39] include features derived from the sentences neighboring the targeted message to detect harassment. Their objective is to spot conversations going off-topic, and use that as an indicator. In particular, they indicate that when a first abusive post appears, it often causes other users to respond with retaliatory harassment. Anuchitanukul et al. [68] propose a context-aware model that combines a representation of context (*history representation*) and target post. They encode the context as a sequence of sentences and learn the representations with BERT [69]. The concatenated representations of context and target post are then fed to a final classifier.

Vargas et al. [70] build on the many lexicon-based methods to propose a contextual lexicon approach. This is based on an offensive lexicon enhanced with contextual labels. They obtain better results for hate speech and offensive comment detection in Portuguese when using features built from this lexicon. Karan et al. [71] develop a preemptive toxic language detection system to assess if a comment is toxic based on the preceding messages. More formally, the model treats a sequence of comments including the one to classify and all of its ancestors. They show that considering the entire thread leads to better performance, in particular in threads which already contain a toxic comment. Almerekhi et al. [72] propose a related study. They investigate the causes leading to toxic discussion threads in Reddit. They define toxicity triggers, i.e. comments that incur direct toxic responses. These triggers can be used to detect threads where abusive messages are more likely to appear. The considered context can be even broader. Gao et al. [73] rely on the title of the news article that the message was posted for. They extract character and word N-gram features as well as lexicon features from the title to detect hate speech in Fox News user comments.

### 2.2.2.2 User-Based Features

Offensive authors tend to post abusive comments in multiple conversations. This suggests that considering user-level features could improve the detection of abusive messages. Researchers have proposed to incorporate different types of user-level context. Balci et al. [74] take advantage of user features such as gender, number of in-game friends, avatars or number of daily logins, to detect abuse in the community of an online game. Such demographic signals have been successfully leveraged in several works (e.g. [26], [75], [76]). The level of activity of users is especially interesting according to multiple studies. Cheng et al. [5] indicate that abusive authors are much
more involved in the conversations they participate in than regular users, and Xiang et al. [77] state that users who spend more time online are more likely to engage in antisocial behavior. Therefore, features such as the daily activity [74], account status [76], [78], [79] or number of messages posted [79]–[81] were used to include user-related information. Chatzakou et al. [78] also consider the inter-arrival time, i.e. the time between 2 consecutive messages, to study the waiting time in user's posting activity.

The fact that social media posts are short and noisy is a problem for abuse detection approaches. Qian et al. [82] mitigate this issue by collecting and analyzing the users’ historical posts. They use the Twitter API to collect up to 400 tweets posted by each user and feed them into a pre-trained bi-LSTM to obtain an historical representation of the user, which is then used in combination with other representations based on text. Adding this historical representation of the user greatly improves the detection of abusive comments. While originally used to detect hate speech, this method could also be used to detect suspicious authors. Based on the same idea, Ziems et al. [79] estimate the historical language behavior of user based on a 4-year snapshot of its timeline. They consider that abusive comments are outside the norm. In this sense, they count the ratio of tokens in a post having zero occurrences in the timeline. According to their hypothesis, the higher this value, the greater the probability that the post is abusive.

### 2.2.2.3 Graph-Based Features

Modeling the users’ social and conversational interactions via their respective graph showed promising results. A direct manner to use such structures is to describe them via a variety of graph measures such as Jaccard’s similarity index [79], centrality scores, reciprocity or degree centrality [6], [78], [83], [84]. The latter method differs from the others in the sense that it relies exclusively on a conversational graph and ignores the content of messages, while other methods often use a mix of graph-based and linguistic features. Nonetheless, they achieve strong performance, even better than certain content-based method.

Another approach to leverage graph-based information, is to use graph embedding techniques. Mishra et al. [14] exploit community-based information from a graph representing authors of tweets to improve the detection of abusive comments. They create an undirected graph wherein vertices are authors and edges are the follower–followee relations between them. From this graph, they obtain a *user profile*, i.e. an embedding for each user, using node2vec [85]. This embedding emphasizes the structural role of the author in the community. They feed these user profiles to a gradient boosted decision tree classifier and prove that they greatly improve the system performances for detecting racist and sexist comments. In a subsequent work [86], they apply a Graph Convolutional Network (GCN) [87] to the same dataset, in order to obtain author representations. This approach allows producing input feature vectors for the author vertices which correspond to a representation of its entire set of tweets. This feature vector additionally incorporates the linguistic
behavior of authors in their learned profiles, which results in better performance. Ribeiro et al. [88] also apply a Graph Neural Network (GNN) using GraphSAGE [89], to learn user profiles. Nagar et al. [15] propose a framework that takes into account the content produced by authors and their profile information. They use a Variational Graph Auto-encoder to learn a joint representation of these 2 sources.

## 2.3 Datasets

This section is dedicated to the review of datasets for abuse detection. We only consider annotated datasets as we define our task as a supervised learning task. As mentioned previously in this chapter, abuse can take multiple forms, e.g. sexism, hate speech, racism, profanity or harassment. Here we consider abuse as a whole no matter its sub-category. Table 2.1 provides a summary of the recent datasets that are publicly available online, distinguishing between those that focus on independent messages (top part of the table) and whole conversations (bottom part). It is important to note that the majority of datasets in the literature use oversampling strategies to increase the proportion of abusive instances. Indeed, the typical prevalence of abusive tweets and personal attacks on Wikipedia talk pages is smaller than 1% [90], [91]. This oversampling can be done by considering specific sensitive topics and communities, or by using keywords related to abuse to filter messages.

This section is organized as follows. We first list and describe the existing datasets for abuse detection in Section 2.3.1. Then, we present the 2 datasets linked to this thesis in Section 2.3.2. Finally, we formalize the abuse detection problem and present how it is evaluated in Section 2.4.

### 2.3.1 Existing Datasets

Most of the datasets concern English messages, as this is the most common language on the Internet, but efforts are being made to provide datasets in other languages too. The last column of Table 2.1 highlights a recurring issue regarding the size of the datasets. Most of them consist of fewer than 10,000 messages, which is a limitation for deep learning approaches, as they often require a lot of data for training. Creating a large dataset is a long and expensive process, particularly to obtain high-quality human annotations. The challenging nature of this task is highlighted by the low inter-annotator agreement observed in the annotation process [90]. This is why some authors propose to automate the annotation of messages [18], [90] or even to automatically generate abusive instances with pre-trained language models (e.g. [94], [96]). We can distinguish 2 categories of abuse datasets: those constituted of individual messages, and those containing whole conversations.
<table><caption>Table 2.1: Summary of available abuse detection datasets.</caption><thead><tr><th>Dataset</th><th>Ref.</th><th>Description</th><th>Language</th><th>Entries</th></tr></thead><tbody><tr><td>SemEval-2023 Task 10</td><td>[92]</td><td>Class labels are - sexist, not sexist</td><td>English</td><td>20,000</td></tr><tr><td>Reddit context-aware dataset</td><td>[93]</td><td>Annotated with the parent post as context. Classes are hate, counter-hate or neutral</td><td>English</td><td>6,846</td></tr><tr><td>ToxiGen (Implicit Hate Speech)</td><td>[94]</td><td>Machine-generated dataset, labels are toxic and benign</td><td>English</td><td>274,186</td></tr><tr><td>Istanbul Convention dataset</td><td>[95]</td><td>5 classes: no hate speech, insult, exclusion, wishing harm, threatening harm. 2 datasets</td><td>Turkish</td><td>1,206 &amp; 1,278</td></tr><tr><td>DynaHate</td><td>[96]</td><td>Machine-generated dataset, labels are hate or not hate + 5 secondary labels for hate type</td><td>English</td><td>41,255</td></tr><tr><td>Abuse is Contextual tweets dataset</td><td>[3]</td><td>Tweets enriched with preceding comment. Annotated for abuse</td><td>English</td><td>8,018</td></tr><tr><td>Civil Comments in Context</td><td>[97]</td><td>Comments annotated with and without context. Labels are non-toxic, unsure, toxic, very toxic</td><td>English</td><td>10,000</td></tr><tr><td>Hate Speech and Offensive Content Identification in Indo-European Languages (HASOC)</td><td>[98]</td><td>Class labels are - Non offensive, hate and offensive, hate, offensive, profane</td><td>English<br>German<br>Hindi</td><td>5,335<br>3,425<br>4,288</td></tr><tr><td>SemEval-2019 Task 5</td><td>[99]</td><td>Class labels are - Hateful, Non-Hateful</td><td>English<br>Spanish</td><td>13,000<br>6,600</td></tr><tr><td>Wikipedia talk pages</td><td>[90]</td><td>Annotated for personal attack</td><td>English</td><td>115,737</td></tr><tr><td>Reddit Contextual Abuse Dataset</td><td>[100]</td><td>Contains conversation threads. Labels are 6 primary categories of abuse</td><td>English</td><td>27,494</td></tr><tr><td>CyberAggressionAdo</td><td>[101]</td><td>Full conversations. Collected through a role-playing game with high-schoolers</td><td>French</td><td>3,260</td></tr><tr><td>Russian</td><td>[102]</td><td>Annotation of full conversations. Real-valued scores ranging from supportive to offensive</td><td>English</td><td>6,000</td></tr><tr><td>Wikipedia Abuse Corpus</td><td>[18]</td><td>Provides conversations. Three datasets for personal attack, aggression, toxicity</td><td>English</td><td>382,665</td></tr></tbody></table>
2.3.1.1 Individual Message Datasets

The individual message datasets consider all messages independent of each other. They are
listed in the top part of Table 2.1. They are the most common, as it is much easier to extract and
annotate such individual messages (e.g. [94]–[96], [99]). We also include datasets such as [3],
[92], [97] in this category. They provide the parent post or a few preceding posts in addition to the
targeted post, but this context is too short to be considered as a real conversation. Indeed, it is
mainly used to improve the quality of labels, by providing some context to the annotators, which
has been proved beneficial.

2.3.1.2 Conversation Datasets

On the other hand, there are datasets with full conversations, such as [18], [100]–[103]. They
are listed at the bottom of Table 2.1. Some of them are fully annotated (i.e. all messages have
individual annotation) while others provide conversations in which only one message is annotated
and the rest serve as context. We discuss conversation datasets in more details because they
best suit our research needs. As mentioned in the introduction, in this thesis, we want to combine
text content and conversation structure to detect abuse. For the latter, we thus require some
conversational context in order to exploit the conversation structure. *CyberAggressionAdo* [101]
is composed of fully annotated conversations. They were collected through a role-playing game
wherein scenarios were introduced and high-school students had to play a role such as conciliator,
bystander or bully. The dataset however contains only 19 conversations of around 130 messages
each, which is too few to train a machine learning algorithm. *Ruddit* [102] and the *Reddit Contextual
Abuse Dataset* [100] both propose conversation threads from Reddit. They specifically include
subreddits which are likely to contain higher-than-average levels of abuse. They contain 6,000 and
27,494 posts, respectively. However, we cannot use these datasets for our experiments because
of the way the conversation threads work on Reddit. A thread groups comments under an initial
post, while each comment can in turn answer to a previous comment. In this manner, threads often
have a tree structure, with a large width and a small depth. As different branches of this tree are
usually unrelated and concern different users, it is not possible to correctly use the structures of
Reddit comment threads to build significant conversation graphs.

2.3.2 Datasets Related to this Thesis

We now discuss the datasets directly related to this thesis that aim at solving the issues ob-
served with the other existing datasets. The first one, SpaceOrigin [11], was constituted in the
same research team as this thesis and constitutes the main dataset for our experiments in the rest
of this thesis. The second, Wikipedia Abuse Corpus [18] is an original dataset that we constituted
and published.
The SpaceOrigin dataset [11] is a collection of annotated French messages enriched with their conversational context, i.e. the messages posted before and after in the same conversation. The messages were extracted from a database of users’ in-game interactions on the Massively Multi-player Online Role-Playing *SpaceOrigin*<fnref n="3" />. They were posted in the in-game chat used by all users to communicate, propose alliances or make strategies. The original database contains more than 4 million entries among which 655 have been flagged as being abusive by at least one user in the game, and confirmed as such by a human moderator. This ensures the high quality of annotations for the *Abuse* class. Among the messages never been flagged by a confirmed abuse report, 1,890 were chosen at random to compose the *Non Abuse* class. Each of the 2,545 messages in the constituted dataset, whatever its class, is associated to its surrounding context (i.e. messages posted in the same thread). It is composed of up to 2,000 messages on each side of the message (before and after). They are ordered from oldest to newest, usually with a gap of a few seconds between them. The annotated messages were selected in such a way that they do not appear in the context of each other. This is particularly important that no abusive message appear in the context of another message, as it could trigger reactions and bias the analysis. All the messages forming the context are unlabeled, they are only used to represent the conversation in which the labeled message was posted. To summarize, the SpaceOrigin dataset is composed of 2,545 distinct conversations, each containing one annotated message and the context before and after it. However, this dataset is based on proprietary data which means that we are not allowed to share the raw text publicly. This is the reason why it is not included in Table 2.1.

To counter this problem, we constituted the *Wikipedia Abuse Corpus (WAC)* [18], a dataset of Wikipedia comments, along with the conversation in which they were posted. The objective with WAC is to provide a large dataset of almost 400,000 messages with conversational context. Such a large dataset is non-existent in the literature, as it contains one order of magnitude more annotated messages than the second largest conversation dataset in Table 2.1. The conversations in WAC come from Wikipedia talk pages, i.e. the web pages associated to Wikipedia articles where editors can exchange. Typically, editors write a message explaining which change they made on the article and why. These comments are longer than other types of online posts such as tweets or chat messages, with an average length of more than 1,000 characters. The conversations, however, are relatively short, with a majority of them constituted of fewer than 20 messages. Abusive comments usually come from pages related to sensitive topics such as religion or politics. Abusive comments represent 13.31% of the total comments in the dataset. The conversations on Wikipedia talk pages are however particular, in the sense that the time gap between 2 consecutive comments on less-visited pages can be several years which makes them more like a succession of messages than actual conversations. To constitute this dataset, we used 2 other publicly available datasets: the Wikipedia Comment Corpus [90] containing more than 63 million individual machine-labeled

<footnote n="3">³https://www.spaceorigin.fr</footnote>
Wikipedia comments for personal attack, and WikiConv [104], a large corpus of Wikipedia conver-
sations. We combined these 2 datasets to retrieve the context of the annotated messages, and
therefore build a new conversation-based dataset.

The fact that conversations in WAC are usually very short (a few messages), and the time gap
between 2 consecutive comments make this dataset unusable for our methods in the remaining
of this thesis: first, these require longer conversations, and second, the slow evolution is likely
to exhibit very different dynamics compared to chat rooms. For this reason, the rest of the work
presented in the following focuses on the SpaceOrigin corpus. Even though we could not take
advantage of our own dataset to assess our proposed methods, it is worth stressing that it was
used by others [105]–[108].

2.4 Formalization and Evaluation

The literature does not always refer to the exact same problem when talking about abuse detec-
tion. We first formalize this task (Section 2.4.1), before presenting different metrics used to assess
the quality of abuse detection systems, including the one that we use in this thesis (Section 2.4.2).

2.4.1 Formalization of Abuse Detection

Abuse detection is usually defined as a classification task consisting in automatically determin-
ing whether a post is abusive given a set of guidelines [105]. It is almost always treated as a clas-
sification task of *individual* messages, where all messages to classify are considered independent
from each other. Still, a few works propose to directly detect abusive authors instead of messages
(e.g. [109]). For the classification, 2 approaches exist. The first one consists in treating abuse
detection as a binary task, with an *Abuse* class covering all types of abuse listed in Section 2.1,
and a *Non-Abuse* class (e.g. [11], [41], [48], [54]). Systems trained following this procedure are
easier to adapt to different frameworks, as they use a global definition of abuse. In many cases,
however, it is interesting to treat abuse detection as a multi-class problem with different types or
degree of abuse (e.g. [50], [110], [111]). This is particularly interesting for systems that have to
apply different sanctions depending on the category of abuse. In this thesis, we focus on the de-
tection of abusive comments that we consider as such if they do not meet the guidelines of the
platform they are posted on. This is therefore a binary classification task which involves classes
*Abuse* and *Non abuse*. We adopt this approach for 2 reasons. First, the SpaceOrigin dataset that
we use only provides this type of annotation and second, we want to build a general system which
could be adapted to different settings and datasets. To this end, treating abuse as a single, global
class encompassing all types of abuse seems to be the most suitable strategy.
## 2.4.2 Evaluation Metrics

To evaluate abuse detection, a number of different metrics are used in the literature. In the following, we focus on the 2 most widespread.

### 2.4.2.1 ROC-AUC

The **Receiver Operating Characteristic (ROC) curve** is another method used to evaluate abuse detection [78], [112]. Let us define true positives (TP) (resp. true negatives (TN)) as abusive (resp. non-abusive) messages that are correctly predicted as such by the system. Conversely, false positives (FP) (resp. false negatives (FN)) are non-abusive (resp. abusive) messages that are incorrectly predicted as such by the system. A false negative corresponds to an abusive message that was missed by the classifier, whereas a false positive is a message that was wrongly flagged.

The ROC curve is the plot of the true positive rate (TPR) against the false positive rate (FPR), at various threshold settings. In their most basic form, the former is defined as

$$TPR = \frac{TP}{TP + FN}, \qquad (2.1)$$

and the latter as

$$TNR = \frac{TN}{TN + FP}. \qquad (2.2)$$

In a binary classification setting, certain classifiers associate a continuous random variable $X$ to each instance. $X$ is a score representing the probability of the instance to be abusive. Given a threshold parameter $T$, the instance is abusive if $X > T$ and non-abusive otherwise. $X$ follows the probability density $f_1(x)$ if the instance is abusive and $f_0(x)$ if it is non-abusive. It is therefore possible to compute both TPR and FPR as functions of $T$. For the former we get:

$$TPR(T) = \int_{T}^{\infty} f_{1}(x) dx, \qquad (2.3)$$

and for the latter:

$$FPR(T) = \int_{T}^{\infty} f_{0}(x) dx. \qquad (2.4)$$

The ROC curve is the plot of $TPR(T)$ versus $FPR(T)$ with $T$ as the varying parameter. The performance of a classifier is usually assessed by calculating the **Area Under the Curve** (AUC) which can be seen as the probability of the classifier to correctly give a higher score to a random positive case than a random negative case. For a predictor $f$:

$$AUC(f) = \frac{\sum_{t_0 \in \mathcal{D}^0} \sum_{t_1 \in \mathcal{D}^1} \mathbf{1}[f(t_0) < f(t_1)]}{|\mathcal{D}^0| \cdot |\mathcal{D}^1|}, \qquad (2.5)$$

where $\mathbf{1}[f(t_0) < f(t_1)]$ returns 1 if $f(t_0) < f(t_1)$ and 0 otherwise, $\mathcal{D}^0$ is the set of negative examples and $\mathcal{D}^1$ is the set of positive examples.
Several studies criticize the use of the ROC curve for assessing the performance of a classification system [113]–[115]. They criticize the use of some portions of area under the curve with low sensitivity which are rarely of interest and should therefore be excluded from the AUC computation. Furthermore, another possible limitation noted by [112] is related to the low prevalence of abusive messages in abuse datasets. The author states that precision-recall curves might be more appropriate than ROC for this task.

### 2.4.2.2 F-Measure

The most commonly used metric to evaluate abuse detection is the **F-measure** (e.g. [14], [34]–[36], [38], [39]). Let us define a binary classification problem of abusive messages with *P* positive instances (Abuse class) and *N* negative instances (Non-Abuse class). The Precision (Pre) (Equation 2.6) is the proportion of actual abusive messages among all messages detected as abusive by the method:

$$Pre = \frac{TP}{TP + FP}. \qquad (2.6)$$

The Recall (Rec) is the proportion of abusive messages that are retrieved among all existing abusive messages:

$$Rec = \frac{TP}{TP + FN}. \qquad (2.7)$$

The F-measure (Equation 2.8) is the harmonic mean of the precision and recall:

$$F1 = 2 \times \frac{Pre \times Rec}{Pre + Rec}. \qquad (2.8)$$

The macro F-measure is the unweighted arithmetic mean of all the per-class F-measures. This metric handles all classes equally, even in case of unbalanced dataset. In a classification problem with *n* classes, it is defined as:

$$macro F1 = \frac{\sum_{c=1}^{n} F1_{c}}{n}. \qquad (2.9)$$

The F-measure is by far the most commonly used metric to assess abuse detection. To ease the comparison with other studies, we decide to express all our performances in terms of macro F-measure in the remaining of this thesis. We use the macro averaged variant of this metric because the SpaceOrigin dataset that we use is unbalanced with only 25% of abusive messages.

## 2.5 Conclusion

In this chapter, we first defined what constitutes an abuse and the concepts related to their detection on online platforms. We then reviewed the abuse detection methods proposed in the literature. Afterwards, we gave an overview of the existing datasets of messages annotated for abuse detection. Almost all of them focus on individual messages rather than conversations, while
the literature points out that the conversational context is important to detect abusive comments.
We presented the WAC corpus, a dataset of annotated conversations that we developed to mitigate
this issue, but that exhibits certain limitations making it unsuitable in our case, and the SpaceOrigin
corpus, which we use in the rest of the thesis. Finally, we defined the task and presented the
metrics used in the abuse detection literature including the macro F-Measure, the metric that we
use in the rest of this thesis.

As we saw in the survey of existing methods, leveraging multiple sources of information seems
important in the abuse detection task. This motivates us to propose our own approaches, based
on multiple modalities, i.e. text and graphs. As explained in Section 2.2, there are 2 main types of
methods: those relying on textual content and those using contextual information. In this thesis, we
focus on the conversational context, which we model through a graph representing the structure of
the conversation. We propose to explore both aspects of this dual information by comparing and
combining text- and graph-based methods. As a first step, we manually engineer features to train
a classifier. On the one hand, this strategy is quite standard in NLP, so we directly present the
selected text-related features when presenting our method in Chapter 4. On the other hand, using
graph features is not that common when performing graph classification, especially when applied
to abuse detection, as no method relying on conversational graphs currently exist. Hence, in the
next chapter, we perform a review of the most popular topological metrics proposed in the literature
to describe graphs, which we later leverage as classification features in Chapter 4.
# GRAPH METRICS AS GRAPH FEATURES

<table><tr><td>3.1</td><td>Definitions and Notations</td><td>34</td></tr><tr><td>3.2</td><td>Vertex-Focused Topological Measures</td><td>35</td></tr><tr><td>3.2.1</td><td>Microscopic Measures</td><td>35</td></tr><tr><td>3.2.2</td><td>Macroscopic Measures</td><td>37</td></tr><tr><td>3.2.3</td><td>Mesoscopic Measures</td><td>41</td></tr><tr><td>3.3</td><td>Graph-Focused Topological Measures</td><td>42</td></tr><tr><td>3.3.1</td><td>Microscopic Measures</td><td>42</td></tr><tr><td>3.3.2</td><td>Macroscopic Measures</td><td>43</td></tr><tr><td>3.3.3</td><td>Mesoscopic Measures</td><td>44</td></tr><tr><td>3.4</td><td>Conclusion</td><td>44</td></tr></table>

Machine learning tasks such as classification and regression require numerical inputs of fixed size. Feature engineering is the process of extracting chosen features from raw data to obtain such numerical representations. Numerous topological measures were proposed over the years to characterize the structure and nature of graphs at different scales and scopes, and can be used as features to describe them. The scale depends on the nature of the characterized entity: vertex, subgraph or graph while the scope corresponds to the information used to characterize this entity: microscopic (interconnection between a vertex and its direct neighborhood), mesoscopic (structure of a subgraph and its direct neighborhood), and macroscopic (structure of the whole graph) [116]. Throughout this thesis, we are interested in 2 types of entity: the graphs, which are the elements that we want to classify, and the vertices, including some that are particularly interesting to represent, such as the author of the message. Furthermore, it is even possible to directly construct a representation of the graph by aggregating all the representations of the graph's vertices. Therefore, we focus only on the vertex and graph measures.

This chapter makes the following contribution:

1. We review the literature of graph metrics that can be used as graph features, focusing on the scales and scopes that are relevant for our abuse detection task. This review includes vertex and graph-focused measures.
It is organized as follows. In Section 3.1, we introduce concepts and notations that are used in the rest of the manuscript. Then, we survey the vertex-focused measures in Section 3.2, and the graph-focused measures in Section 3.3. For both, we distinguish topological measures in terms of scope.

## 3.1 Definitions and Notations

We start with the definition of a simple graph, i.e. undirected, unweighted, and unsigned.

**Definition 3.1 (Simple graph).** A **simple graph** is a pair $G = (V, E)$ composed of a set of vertices $V$ and a set of edges $E \subseteq V^2$ connecting them. Each edge is a pair of vertices placed in an arbitrary but constant order (e.g. lexicographic order).

We note $n = |V|$ the number of vertices and $m = |E|$ the number of edges. It is possible to add some information over the edges to enhance the graph structure.

**Definition 3.2 (Directed graph).** A **directed graph** is a pair $G = (V, E)$ composed of a set of vertices $V$ and a set of directed edges $E \subseteq V^2$ connecting them. Unlike the undirected graph, both $(u, v)$ and $(v, u)$ can exist in such graphs.

**Definition 3.3 (Weighted graph).** A **weighted graph** is a triple $G = (V, E, w)$ composed of a set of vertices $V$, a set of edges $E \subseteq V^2$ connecting them, and a function $w: E \to \mathbb{R}$ that associates a weight to each edge.

For the sake of simplicity, we note $w_{uv}$ the weight of edge $(u, v)$. It is possible to have a graph that is both directed and weighted.

**Definition 3.4 (Signed graph).** A **signed graph** is a triple $G = (V, E, s)$ composed of a set of vertices $V$, a set of edges $E \subseteq V^2$ connecting them, and a function $s: E \to \{-, +\}$ that associates a sign to each edge. We note $E^{-} \subset E$ and $E^{+} \subset E$ the subsets of negative and positive edges, respectively. Consequently, $E = E^{-} \cup E^{+}$.

A signed graph can also be directed and/or weighted. The graphs can thus be just signed, but also signed directed, signed weighted, or signed directed weighted.

**Definition 3.5 (Adjacency matrix).** The **adjacency matrix** of a graph with vertex set $V = \{v_1, ..., v_n\}$ is a square $n \times n$ binary matrix $A$ whose elements $A_{ij}$ take the value 1 if an edge connects the vertex $v_i$ to the vertex $v_j$ and 0 otherwise.

The adjacency matrix is symmetric in undirected graphs, but not necessarily in directed graphs.

**Definition 3.6 (Neighborhood).** The **neighborhood** $N(u)$ of a vertex $u \in V$ includes all vertices attached to this vertex: $N(u) = \{v \in V : (u, v) \in E\}$.
In directed graphs, the neighborhood is split in 2: the incoming neighborhood and the outgoing neighborhood.

**Definition 3.7** (Incoming and outgoing neighborhoods). In a directed graph, the incoming $N^{in}$ and outgoing $N^{out}$ neighborhoods of a vertex $u$ are the sets of vertices connected to $u$ through incoming and outgoing edges, respectively: $N^{in}(u) = \{v \in V : (v, u) \in E\}$ and $N^{out}(u) = \{v \in V : (u, v) \in E\}$.

In undirected signed graphs, one can distinguish between 2 neighborhoods, depending on the edge signs:

**Definition 3.8** (Positive and negative neighborhoods). The positive $N^+(u)$ and negative $N^-(u)$ neighborhoods of a vertex $u \in V$ focus each on a specific edge sign: $N^+(u) = \{v \in V : (u, v) \in E^+\}$.

The unsigned neighborhood of vertex $u$ is thus defined as the union of its positive and negative neighborhoods $N(u) = N^+(u) \cup N^-(u)$. In case of directed signed graph, the neighborhood of vertex $u$ is split in 4 depending on edge sign and direction: $N(u) = N^{in+} \cup N^{in-} \cup N^{out+} \cup N^{out-}$.

**Definition 3.9** (Shortest path). In an unweighted undirected graph, the shortest path between 2 vertices is the path that connects them with the fewest edges. In a weighted graph, it is the path of minimal total weight.

**Definition 3.10** (Distance). In an undirected graph, the distance between 2 vertices is the number of edges in the shortest path between them. In a directed graph, we consider the oriented paths. We note $d(u, v)$ the distance between $u$ and $v$.

## 3.2 Vertex-Focused Topological Measures

Vertex measures are defined relatively to a single vertex of the graph. We first describe the microscopic measures that characterize a vertex depending on its direct neighborhood (Section 3.2.1). Then, we explain the macroscopic measures which operate on the entirety of the graph (Section 3.2.2). Finally, we focus on the mesoscopic measures relying on an intermediate structure to characterize vertices (Section 3.2.3).

### 3.2.1 Microscopic Measures

The Degree Centrality measures the size of the direct neighborhood of the considered vertex $v$ as:

$$k(v) = |N(v)|. \tag{3.1}$$
In directed and signed graphs, the **incoming** (Equation 3.2), **outgoing** (Equation 3.3), **positive** and **negative** (Equation 3.4) **degree centralities** of a vertex are defined as the cardinalities of the corresponding neighborhoods as:

$$k^{in}(v) = |N^{in}(v)|, \qquad (3.2)$$

$$k^{out}(v) = |N^{out}(v)|, \qquad (3.3)$$

$$k^{\pm}(v) = |N^{\pm}(v)|. \qquad (3.4)$$

The **Strength Centrality** is the generalization of the degree to weighted graphs. It is based on the sum of the weights of the edges linked to the considered vertex. The strength of vertex v is defined as:

$$Str(v) = \sum_{u \in N(v)} w_{uv}. \qquad (3.5)$$

Once again, it is possible to use the incoming (Equation 3.6) and outgoing (Equation 3.7) versions of that measure in a directed graph. Compared to the degree centrality, the strength takes into account the frequency or intensity of the interactions in the following way:

$$Str^{in}(v) = \sum_{u \in N^{in}(v)} w_{uv}, \qquad (3.6)$$

$$Str^{out}(v) = \sum_{u \in N^{out}(v)} w_{vu}. \qquad (3.7)$$

The **Local Transitivity** [117] (aka local clustering coefficient) corresponds to the proportion of the considered vertex's neighbors connected through an edge, relatively to the total number of connections possible among them. It is a score ranging from 0 (no inter-neighbor edge at all) to 1 (the vertex and its neighborhood are completely interconnected and form a clique). The measure is originally defined for unweighted undirected graphs:

$$LT(v) = \frac{2|\{(u, z) \in E : u, z \in N(v)\}|}{k(v)(k(v) - 1)}, \qquad (3.8)$$

where the degree can be reformulated as $k(v) = \sum_{u} A_{uv}$. A weighted variant based on the strength centrality was proposed [118]:

$$LTw(v) = \frac{1}{Str(v)(k(v) - 1)} \sum_{u,z} \frac{w_{uv} + w_{vz}}{2} A_{uv}A_{vz}A_{uz}. \qquad (3.9)$$
**Burt's Constraint** [119] measures how redundant the neighbors of a vertex are. Vertices with high constraint values are said to be constrained by their neighbors, i.e. they stand in a highly cohesive group of vertices. On the other hand, vertices with a low constraint value have a higher reach outside their direct neighbors pool. This measure is based on the proportion of the relations of some vertex v that are invested in connection with another vertex u, compared to the total weight that v shares with its neighbors. It is expressed as:

$$p_{vu} = \frac{\mathbf{A}_{vu} + \mathbf{A}_{uv}}{\sum_{z \in V \setminus \{v\}} (\mathbf{A}_{vz} + \mathbf{A}_{zv})} \quad (3.10)$$

Burt's constraint (Equation 3.11) is composed of 2 parts: the direct influence $p_{vu}$ and the indirect influence $\sum p_{vz}p_{zu}$ which measures the amount of weight indirectly shared by v and u through a mutual neighbor z. It is defined as:

$$BurtC(v) = \sum_{u \in V \setminus \{v\}} \left( p_{vu} + \sum_{z \in V \setminus \{u, v\}} p_{vz}p_{zu} \right)^2 \quad (3.11)$$

### 3.2.2 Macroscopic Measures

Macroscopic measures operate on the entirety of the graph structure. They allow characterizing the position of a particular vertex relatively to the whole graph. We can distinguish 3 families of macroscopic measures: the spectral measures (Section 3.2.2.1), the distance-based measures (Section 3.2.2.2) and the connectivity-based measures (Section 3.2.2.3).

#### 3.2.2.1 Spectral Measures

The spectral measures are based on the Eigenvectors or Eigenvalues of the graph adjacency matrix, or any related matrix.

The **Eigenvector Centrality** [120] is another generalization of the degree, in which instead of just counting the direct neighbors, one also takes into account their own centrality:

$$EigC(v) = \frac{1}{\lambda} \sum_{u \in N(v)} EigC(u) = \frac{1}{\lambda} \sum_{u \in V} \mathbf{A}_{vu}EigC(u), \quad (3.12)$$

where $\lambda \neq 0$ is a constant. A central neighbor contributes more to the centrality than a peripheral one. A high Eigenvector value indicates a vertex that is connected to many vertices who themselves have high values. Using matrix notation, the Eigenvector centrality can be rewritten as the Eigenvector equation:

$$\mathbf{A}x = \lambda x, \quad (3.13)$$

with $x = (EigC(v_1), ..., EigC(v_n))$, and $\lambda$ is the largest Eigenvalue of A.
The PageRank Centrality [121] can be seen as a variant of the Eigenvector centrality originally designed for directed graphs, but that can also be applied to undirected graphs. It includes an additional normalization allowing to model the dilution of the influence of a vertex through all its outgoing edges. This is done through the damping factor d, which represents the probability to jump from one vertex to another without having an explicit connection between them. In practice, it is usually set to 0.85 based on empirical results [121]. At each time step t, the computation yields:

$$ \mathbf{R}(t+1) = d\mathbf{MR}(t) + \frac{1-d}{n}\mathbf{1}, \qquad (3.14) $$

where 1 is the column vector of length n containing only ones and matrix M is defined as:

$$ \mathbf{M}_{uv} = \begin{cases} 1/N^{\text{out}}(v) & \text{if } (v, u) \in E \\ 0 & \text{otherwise.} \end{cases} \qquad (3.15) $$

This formula can be rewritten recursively as:

$$ PR(v; t+1) = \frac{1-d}{n} + d \sum_{u \in N^{\text{in}}(v)} \frac{PR(u; t)}{N^{\text{out}}(u)}, \qquad (3.16) $$

where the first term models the probability of randomly visiting a given vertex and in the second term, vertices equally dilute their influence to all their outgoing neighbors.

The Hub and Authority Scores [122] are 2 complementary measures for directed graphs, computed through the Hyperlink-Induced Topic Search (HITS) algorithm. They split the Eigenvector centrality value into 2 parts. The authority score focuses on incoming edges and the hub score on the outgoing edges. In matrix notation with constant α and β, authority and hub scores are respectively

$$ \mathbf{a} = \alpha \mathbf{A}^T \mathbf{h}, \qquad (3.17) $$

$$ \mathbf{h} = \beta \mathbf{A} \mathbf{a}. \qquad (3.18) $$

In their iterative definition, Hub(v) = Auth(v) = 1 for all vertices v ∈ V in the initial step. Then, at each iteration, the authority of all vertices is updated as the sum of the hub score of all its incoming neighbors, divided by the square root of the sum squared authority scores:

$$ \text{Auth}(v) = \frac{\sum_{u \in N^{\text{in}}(v)} \text{Hub}(u)}{\sqrt{\sum_{u \in V} \text{Auth}(u)^2}}. \qquad (3.19) $$

This normalization is needed to obtain values that converge. The hub score of all vertices is updated in the same manner, except that it is the sum of all the authority scores of outgoing
neighbors divided by the square root of the sum of the squared hub scores:

$$ Hub(v) = \frac{\sum_{u \in N^{\text{out}}(v)} \text{Auth}(u)}{\sqrt{\sum_{u \in V} Hub(u)^2}}. \qquad (3.20) $$

The **Alpha Centrality**, or Katz Centrality [123], [124], relates to the same idea, but it considers all the walks between pairs of vertices instead of only the shortest paths in directed graphs. This measure computes the relative influence of a vertex within the graph by considering its direct and indirect neighbors, but the latter are penalized by an attenuation factor $\alpha \in (0, 1)$:

$$ Alpha(v) = \sum_{\ell=1}^{\infty} \sum_{u=1}^{n} \alpha^{\ell} (\mathbf{A}^{\ell})_{uv}, \qquad (3.21) $$

wherein the power of the adjacency matrix $(\mathbf{A}^{\ell})$ denotes the presence (or absence) of a path of length $\ell$ between 2 vertices.

The **Power Centrality** [125] generalizes both the Eigenvector and Alpha Centralities in directed unweighted graphs. It is based on the notion that the power of a vertex is recursively defined by the sum of the power of its neighbors. It uses an attenuation parameter $\beta \in (-1/\lambda_{A1}; 1/\lambda_{A1})$ (the reciprocal of the largest eigenvalue of the adjacency matrix $\mathbf{A}$) which controls the influence of distant vertices and a scaling parameter $\alpha$. The power centrality is defined as follows:

$$ PC = \alpha (\mathbf{I} - \beta \mathbf{A})^{-1} \mathbf{A} \mathbf{1}, \qquad (3.22) $$

or in its iterative form:

$$ PC(v) = \sum_{u \in N(v)} (\alpha + \beta PC_u) \mathbf{A}_{vu}. \qquad (3.23) $$

The **SubGraph Centrality** [126] defines the notion of reachability based on closed walks in undirected graphs. The subgraph centrality of vertex $v$ is computed as the sum of the closed walks of all lengths starting and ending at $v$. The contribution of the closed walks decreases as their length increases, making short walks more influential on the centrality of the vertex than longer ones. It is formally defined as:

$$ SC(v) = \sum_{\ell=0}^{\infty} \frac{(\mathbf{A}^{\ell})_{vv}}{\ell!}, \qquad (3.24) $$

where the numerator is the local spectral moments, which is defined as the $v^{th}$ diagonal entry of the $\ell^{th}$ power of the adjacency matrix $\mathbf{A}$.
### 3.2.2.2 Distance-Based Measures

Another family of macroscopic measures is based on the notions of *shortest path* and *geodesic distance* between vertices.

The **Betweenness Centrality** [127] is related to the number of shortest paths going through the considered vertex. For every pair or vertices in a connected graph, there exists at least one shortest path connecting the vertices. In an undirected unweighted graph, the betweenness centrality of a vertex is the proportion of such shortest paths passing through it:

$$ \text{BetC}(v) = \sum_{u \neq v \neq z} \frac{\sigma_{uz}(v)}{\sigma_{uz}}, \qquad (3.25) $$

where $\sigma_{uz}$ is the number of shortest paths between $u$ and $z$, and $\sigma_{uz}(v)$ is the number of those passing through $v$. In directed graphs, this measure is defined as the proportion of *directed* shortest paths passing through $v$ and in weighted graphs, it considers the paths of *minimal weight*.

The **Closeness Centrality** [128] is related to the reciprocal of the total geodesic distance between the vertex of interest and the other vertices. The more central a vertex is, the higher its closeness centrality. It is generally considered that it measures the efficiency of the vertex to spread a message over the graph, and its independence from the other vertices in terms of communication. The closeness centrality was originally defined as:

$$ \text{CloseC}(v) = \frac{1}{\sum_{u} d(u, v)}, \qquad (3.26) $$

where $d(u, v)$ is the distance between $u$ and $v$. In directed and weighted graphs, this distance is the length of the shortest oriented path and the weight of the path of minimal weight, respectively. However, the closeness centrality often refers to its normalized form, where the previous formula is multiplied by the number of remaining vertices in the graph. This normalization eases the comparison of vertices in graphs of different sizes. The formula becomes:

$$ \text{CloseCNorm}(v) = \frac{n-1}{\sum_{u} d(u, v)}. \qquad (3.27) $$

This measure is generalized to directed graphs by considering the length of directed shortest paths, and to weighted graphs by considering the cost of the paths of minimal cost.

The **Eccentricity** [129] is related to the closeness centrality, but it is not a centrality measure. On the contrary, it quantifies how *peripheral* a vertex is, by considering the distance to its farthest neighbor in the graph. In directed and weighted graphs, this distance is computed on directed and weighted paths, respectively, in the following manner:

$$ \text{Ecc}(v) = \max_{u \in V} d(u, v). \qquad (3.28) $$

It is generalized to directed or weighted graphs using the same principle as for the closeness.
### 3.2.2.3 Connectivity-Based Measures

The last family of macroscopic measures is based on the notion of connectivity, i.e. whether or not a path exists between certain parts of the graph.

An **Articulation Point** is a vertex whose removal makes the graph disconnected, i.e. split into several separate components [129]. We define a binary feature indicating whether the vertex is an articulation point (1) or not (0).

### 3.2.3 Mesoscopic Measures

Mesoscopic measures rely on an intermediate structure to characterize a vertex, such as a subgraph.

The **Coreness Score** [130] is related to the *k*-core of the graph which is the maximal connected subgraph in which every vertex has at least degree *k*. The coreness score of vertex *v* is *k* if it belongs to the *k*-core but not to the (*k* + 1)-core. Ingoing cores and outgoing cores can be used to compute this score in directed graphs.

The **Within-Module Degree** (or internal intensity) and **Participation Coefficient** [131] are a pair of complementary measures defined relatively to the community structure of the graph. They aim at characterizing the position of vertices at this intermediate level. They can be computed in undirected and directed graphs by considering the oriented paths in the latter [132]. The within-module degree measures the connectivity of a given vertex to other vertices in its community. Let $k_i(v)$ be the *community degree* of *v* for the *i*-th community, i.e. the number of edges that *v* shares with vertices in this community. The within-module degree is defined as the *z*-score (or statistical standardization) of $k_i(v)$:

$$WM(v) = \frac{k_i(v) - \mu_i[k_i(v)]}{\sigma_i[k_i(v)]}, \qquad (3.29)$$

where $\mu_i[k_i(v)]$ is the average of $k_i$ over all vertices in community $C_i$, and $\sigma_i[k_i(v)]$ is its standard deviation.

The participation coefficient measures the strength of a vertex's connections within its community. It is expressed as:

$$PC(v) = 1 - \sum_{1 \le i \le K} \left( \frac{k_i(v)}{k(v)} \right)^2, \qquad (3.30)$$

where *K* is the number of communities in the graph.

A collection of 4 measures have been proposed to decompose community roles in a more precise way, and better capture the position of vertices in a modular graph [132]: **Internal Intensity**, **External Intensity**, **Diversity**, and **Heterogeneity**. They all rely on the notion of *z*-score shown in Equation 3.29 for the community degree $k_i(v)$.
The internal intensity is just another name for the within-module degree. The external intensity measures the amount of edges that a vertex have towards communities other than its own. It is based on the external degree $k_{ext}(v)$ of a vertex $v$, which corresponds to the total community degree over all communities except its own. The external intensity is the z-score of the external degree, which is obtained formally by replacing $k_i(v)$ by $k_{ext}(v)$ in Equation 3.29.

The diversity relies on the number of communities to which a vertex $v$ is connected, outside of its own. Let $\epsilon(v)$ be this number. The diversity is defined as the z-score of $\epsilon(v)$, obtained by substituting $k_i(v)$ by $\epsilon(v)$ in Equation 3.29.

The heterogeneity of vertex $v$ measures the variation of the number of edges a vertex has, from one community to another. It requires computing the standard deviation of the number of edges that $u$ has to each community, denoted by $\delta(v)$. The heterogeneity is the z-score of $\delta$, once again obtained by substituting $\delta(v)$ to $k_i(v)$ in Equation 3.29.

These measures can be extended to directed graphs by distinguishing incoming and outgoing links. This results in 2 versions of each measure, the in- and out- measures.

## 3.3 Graph-Focused Topological Measures

Though less numerous than vertex-focused measures, some measures have been specifically designed to characterize the graph structure as a whole. As for the vertex measures, one can distinguish them based on their scope.

### 3.3.1 Microscopic Measures

A number of very standard statistics exist to describe a graph using only local information. The **vertex count** or graph order, is the total number of vertices in the graph: $n = |V|$. The **edge count** or graph size is the total number of edges in the graph: $m = |E|$. In a signed graph, it can be split in a positive count ($m^+$) and a negative count ($m^-$). The **graph density** represents the ratio between the number of edges present in a graph and the maximum number of edges that this graph can contain. It is defined as:

$$D = \frac{2m}{n(n-1)}. \qquad (3.31)$$

The **Global Transitivity** [133], also known as global clustering coefficient, is the graph-focused counterpart of the local transitivity. It corresponds to the ratio of the count of triangles to connected triples (i.e. 3 vertices that are connected by either 2 or 3 edges in the graph). This measure is related to the proportion of vertices possessing a common neighbor that are directly connected.
The **Reciprocity** [134] measures the proportion of bilateral edges (i.e. edges pointing in both directions) over all pairs of vertices in a *directed* graph. Formally, the reciprocity of a graph *G* is written:

$$ Rec = \frac{\sum_{(u,v) \in G} a_{uv}a_{vu}}{|E|}. \qquad (3.32) $$

### 3.3.2 Macroscopic Measures

The **Weak Component Count** corresponds to the number of maximally connected subgraphs in an *undirected* graph. A subgraph is connected if there exists a path between any given pair of vertices. The **Strong Component Count** is its variant for directed graphs, which is based on *directed* paths. A directed graph is called *strongly connected* if there is a *directed path* in each direction between any given pair of vertices.

The **Cohesion** of a graph is the minimum number of vertices one needs to remove in order to make the graph disconnected [135]. The **Adhesion** is a similar measure, but for edges.

When describing the vertex-oriented measures, we defined an articulation point as a vertex whose removal makes the graph disconnected. The **Articulation Point Count** is the total number of articulation points in the graph:

$$ APC = \sum_{v \in V} AP(v), \qquad (3.33) $$

where $AP: V \to \{0, 1\}$ associates 1 to a vertex if it is an articulation point and 0 otherwise.

The **Diameter** is the length of the *longest shortest path* (i.e. the largest distance) over all pairs of vertices (indirectly) connected in the graph. It corresponds to the maximum eccentricity of any vertex in the graph:

$$ dia = \max_{v \in V} Ecc(v). \qquad (3.34) $$

The **Radius** is the minimum among all the maximum distances over all pairs of vertices (indirectly) connected in the graph. It corresponds to the minimal eccentricity of any vertex:

$$ rad = \min_{v \in V} Ecc(v). \qquad (3.35) $$

The **Average Distance** is the arithmetic mean of the lengths of the shortest paths processed over all pairs of (indirectly) connected vertices. Let $d(u, v)$ be the length of the shortest path
between u and v. The average distance is thus:

$$ AvgDist = \frac{\sum_{(u,v) \in V^2} d(u, v)}{\frac{n(n-1)}{2}}. \qquad (3.36) $$

### 3.3.3 Mesoscopic Measures

A clique is a subset of vertices such that every 2 distinct vertices in the clique are adjacent. In other words, a clique belonging to a graph G is a complete induced subgraph of G. The **Clique Count** is the total number of cliques in G.

The **Community Count** and the **Modularity** [136] are 2 measures related to the notion of community structure, i.e. of partition of vertex set reflecting the network mesoscopic organization. The former is the number of communities, while the latter is a measure of the quality of the community structure defined as:

$$ Q = \sum_{i} (e_{ii} - a_{i}^{2}). \qquad (3.37) $$

There are a very large number of different methods to detect such community structures, but their discussion is out of the scope of this thesis. See for instance [137] for a review.

## 3.4 Conclusion

With the graph measures presented throughout this chapter, it is possible to characterize the structure of a graph. Each one of them capture particular information and their multiplication allows to better characterize the entire graph. In the next chapter we want to use these measures in order to represent conversational graphs. This procedure known as feature engineering which has long been the standard approach allows us to obtain graph representations that have the benefit of being interpretable (i.e. based on known and identified characteristics). We can then feed them to a classifier in order to detect abusive messages in conversations, while identify the most discriminant feature in order to provide some interpretation to our results.
# FEATURE ENGINEERING FOR ABUSE DETECTION

<table><tr><td>4.1</td><td>Graph Extraction from Conversations</td><td>47</td></tr><tr><td>4.2</td><td>Proposed Representation Methods</td><td>51</td></tr><tr><td>4.2.1</td><td>Text-Based Features</td><td>51</td></tr><tr><td>4.2.2</td><td>Graph-Based Features</td><td>54</td></tr><tr><td>4.2.3</td><td>Combining the Textual and Structural Information</td><td>56</td></tr><tr><td>4.3</td><td>Experiments</td><td>58</td></tr><tr><td>4.3.1</td><td>Experimental Protocol</td><td>58</td></tr><tr><td>4.3.2</td><td>Classification Results</td><td>59</td></tr><tr><td>4.3.3</td><td>Feature Study</td><td>61</td></tr><tr><td>4.4</td><td>Analysis and Discussion</td><td>65</td></tr><tr><td>4.4.1</td><td>Temporal Aspect</td><td>65</td></tr><tr><td>4.4.2</td><td>Impact of Edge Attributes</td><td>66</td></tr><tr><td>4.5</td><td>Conclusion</td><td>67</td></tr></table>

In this chapter, we propose abuse detection methods based on text, graphs and an approach combining these 2 modalities of information. The methods using text and graphs individually through feature engineering are largely based on the work conducted in our research team by Pegnies et al. [6], [103]. The first one, called *content-based* method, relies on the content of the exchanged messages to perform abuse detection. The second one, called *graph-based* method, focuses on the interactions between participants of the conversation modeled by a conversational graph, and uses the graph measures described in Chapter 3. It significantly differs from the rest of the literature, as it completely ignores the content of the messages, and only focuses on the dynamics of the conversation.

These 2 types of approach perform reasonably well when taken separately, but given the different nature of text and graphs, one can assume that the content of the exchanged messages and the interactions between users convey different information which is at least partially complementary, hence improving the classification when combined. Mishra et al. [14] actually achieves better performances when combining these 2 modalities. To investigate this phenomenon, we propose 3 *Fusion* strategies to take advantage of both content- and graph-based methods.
To obtain numerical representations of text and graphs, both of our method use a standard approach adopted in the literature, which consists in selecting and extracting relevant measures from the raw data through a *Feature Engineering* process. For the methods based on the content of messages, this approach has been used in a number of works, e.g. [11], [33], [40]. Therefore, the content-based method uses a set of features that are quite standard in the literature of abusive language detection. On the other hand, there is no previous work that uses conversational graphs to handle this task. Hence, the adopted approach is exploratory and consists in selecting a huge range of widespread topological measures to describe the graphs. The objective is to have a large set of measures, including some that can handle edge signs, directions and weights, to increase the probability of capturing the important information carried by the graph structure. Finally, we propose to perform a feature ablation study on all the modalities and their combination to determine the best suited measures relatively to our task.

Our work differs from the original works proposed by Papegnies et al. [6], [103] on several points. First, we seek to compare the 2 sources of information and study their complementarity by combining them. Second, we extend the original graph extraction method to create signed graphs, which require us to include signed features in the graph-based method. Finally, we propose an extended analysis of our results.

This chapter is based on our work published at the *International workshop on Modeling and mining Social-Media-driven Complex Networks* [20]. The conversational graphs extracted from our proprietary dataset<fnref n="1" /> and the source code² to reproduce our experiments are available online. This chapter makes the following contributions:

1. We develop a procedure to extract directed signed weighted conversational graphs from user-generated conversations.

2. We present and compare a *Content-based* and a *Graph-based* method on an abuse detection task. We propose 3 *Fusion* strategies to combine these methods and take advantage of both sources of information.

3. We perform a feature ablation study on text and graph modalities, and their combination, to identify the most important features for our task. Furthermore, we analysis how the temporal aspect and the edge attributes can impact the graph-based method.

The rest of this chapter is organized as follows. First, we present the methods that we use to extract conversational graphs from our dataset of conversations in Section 4.1. In Section 4.2, we introduce the methods and fusion strategies used through this chapter. In Section 4.3, we present

<footnote n="1">¹https://figshare.com/articles/dataset/Conversational_Networks_From_Automatic_Online_Moderation/7442273?file=24681479

²https://github.com/CompNet/Alert</footnote>
our experimental setup and put it into practice on the SpaceOrigin dataset. We extensively interpret
the obtained results and determine the most important features on our task for each method. We
further analyze some aspects related to graphs and discuss our findings regarding the context in
Section 4.4. Finally, we review our main findings and identify some perspectives for future works
in Section 4.5.

4.1 Graph Extraction from Conversations

Graphs can be used to represent conversations under the form of so-called conversational
networks, which represent the flow of the conversation between persons. These persons are rep-
resented as vertices and the edges model the communication between them. While extracting
conversational networks from well-structured conversations is straightforward, it can be far from
trivial for unstructured conversations such as online chatrooms or IRC (Internet Relay Chat). In-
deed, these multi-participant chats often have multiple distinct conversations that overlap. There
can be a built-in mechanism to explicitly specify the recipient of a message, but it is rarely used by
users, for time and practicality reasons. In this context, Mutton [138] proposes to use the temporal
density and temporal proximity of the messages to build conversational networks. In other words,
he considers that messages posted consecutively in the chat have a higher probability of being
related than distant messages. We build an extraction framework based on this hypothesis.

In Chapter 2.3, we presented several datasets for abuse detection. For our experiments, we want to extract graphs from the selected dataset. Therefore, we require a dataset of conversations, with conversations long enough to have a variety of users and messages in each of them. The SpaceOrigin dataset is the one that best suits our requirements, so we use it in all the following experiments. As a reminder, it contains chat logs extracted from the in-game live conversation module of an online video game. It is composed of 2,545 messages labeled as *Abusive* or *Non-Abusive*, with each one being provided with its surrounding context. Since one of the methods that we use in this chapter is based on conversational graphs to model the context of conversations, we have to extract such networks from the dataset. These networks are directed signed weighted graphs to exploit all the information available. Vertices and edges represent users and their communications, respectively. The following graph extraction procedure was first proposed by Papegnies et al. [6]. Their procedure is able to extract directed weighted graphs. We propose to extend it with a sentiment analyzer to infer the polarity of the interactions between users. This allows us to add signs to interactions and thus to extract directed signed weighted networks.

The key concepts of the graph extraction framework from a conversation are illustrated in Fig-
ure 4.1, in which each vertical rectangle represents a message. The messages are ordered from
oldest to newest, and time flows from left to right in the figure. Each extracted network is defined
relatively to a *targeted message*, i.e. a labeled message of the SpaceOrigin dataset that we use
<figure><img src="image_5.png" /><figcaption>Figure 4.1: Illustration of the main concepts of our conversational network extraction process. Figure from [6].</figcaption></figure>

in our classification task. Furthermore, labeled messages were originally extracted so that they do not appear in each other's context. There are 3 steps in the extraction framework:

* First, we select a subset of messages that we use to construct the network (the context period in Figure 4.1).

* Second, we identify the subset of users that are the likely receivers of each message (represented by the sliding window in Figure 4.1).

* Third, we compute the polarity of an exchange between 2 users based on the content of the exchanged message. We also compute the strength of the interaction depending on the proximity between the exchanged messages. We add edges and revise their weights and signs accordingly.

**Context period.** Each *targeted message* in the SpaceOrigin dataset is associated with its context that can be composed of thousands of messages. Therefore, we have to determine the subset of messages to use in order to extract the network associated to this *targeted message*. To this end, we restrict the extraction process to a so-called *context period*, a sub-sequence of messages. This sequence is centered around the *targeted message* which is represented in red in Figure 4.1. The *context period* spans symmetrically *before* (left side) and *after* (right side) the *targeted message*. Each participant posting at least one message during this period is modeled by a vertex in the produced conversational network.

**Sliding window.** Our dataset is composed of a series of messages. Users can write a direct reference to another user as @user to explicitly direct a message towards him. However, most of the messages do not contain such references. Therefore, we have to infer the recipients of messages.
We do so by sliding a mobile window over the whole *context period*, one message at a time. At each step, the network is updated either by creating new edges, or by updating the weights of existing ones. The *sliding window* has a fixed length expressed in number of messages, which is derived from ergonomic constraints relative to the online conversation platform from which the dataset was extracted. At a given time, the rightmost message of the window, i.e. the oldest one posted (in blue in Figure 4.1), is called *current message* and its author *current author*. This procedure allows focusing on a smaller part of the context period. Following the hypothesis that consecutive messages have a higher probability of being related than distant messages, we assume that the *current message* is aimed at the authors of the other messages posted right before it (i.e. the messages present in the sliding window). It is also possible that the current message contains direct references to users as @user. In the case of a direct reference to one or multiple users, we consider that the referenced users are the prime targets of the message. We connect the current author to the receivers (or strengthens their weights if the edge already exists) according to the process described next

**Weight assignment.** To assign weight to a connection between users, we list and order all the users that interact with the current author, excluding the current author himself. This list first contains the users directly referenced in the message, if there are any (step a in Figure 4.2). Then, we add all the authors of messages currently present in the *sliding window* except the ones that are already among the referenced users. They are ordered by their last posted message to take chronology into account (step b in Figure 4.2). Only the edges towards users in that list receive weight. We want to favor the first authors in the list as they are more likely to be the targeted receivers of the *current message*. The weights are adjusted depending on the proximity of the concerned receivers: the higher the proximity, the stronger the interaction. For this purpose, we use a recursive scoring function to assign weights to the connections. Each receiver is assigned a score which is a decreasing function of both his rank *i* in the ordered list of receivers and of the length *N* of this list. This function is defined in Equation 4.1:

$$f(i) = \begin{cases} 0.6 \times 0.4^{i-1}, & \text{if } 1 \le i < N \\ 0.4^{i-1}, & \text{if } i = N. \end{cases} \qquad (4.1)$$

The first receiver gets 60% of the total weight, and the rest of them share the remaining 40% using the same recursive 60-40% split scheme. This approach gives more importance to temporal proximity, with scores dropping fast when the receiver is not the author of the immediately preceding message. The resulting weights are represented on the right-hand side of Figure 4.2. Papegnies et al. [6] experimented with 2 other weight assignment strategies, but they were less effective than the recursive scoring function described above, so here we focus on this last one.

**Relation polarity.** In order to obtain signed edges, we additionally leverage a state-of-the-art
<figure><img src="image_6.png" /><figcaption>Figure 4.2: Example of sliding window (left) and computation of the corresponding receivers’ weights (right). Each color represents a specific user. On the left, each message in the window is filled with the color of its author, whereas the small squares represent direct references to users. On the right, the *a* and *b* columns represent the different steps of the computation. See main text for details.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 4.3: Update of the edges and weights of the conversational graph corresponding to the example in Figure 4.2. We consider that the sentiment analyzer determined a negative polarity for the current message. All the weights added at this step are therefore negative. The first graph displays the state before the update, and each remaining one corresponds to one rank in the receiver list.</figcaption></figure>

BERT-like sentiment analyzer<fnref n="3" /> to determine the polarity of the users’ interactions, based on their exchanged textual content. More specifically, the analyzer is applied to the *current message*. The polarity thus computed can be either negative (hostile interaction) or positive (friendly) and is used as the sign of the weight computed at the current step. Figure 4.3 illustrates this weight update following the weights computed in Figure 4.2. In this illustration, we consider a negative polarity for the current message. The total weight of an edge is obtained by summing all its interactions over the whole context period, and can thus be negative or positive. The sign of this summed weight is used as the sign of the edge. This last part is an original proposition compared to the extraction process proposed by [6].

<footnote n="3">³https://github.com/TheophileBlard/french-sentiment-analysis-with-bert</footnote>
Once this iterative framework has been applied over the whole *context period*, we obtain the *Full* network associated to one labeled message of the original dataset. We repeat this operation for each of the 2,545 labeled messages. Besides the *Full* network extracted over the whole context period, we additionally extract 2 smaller networks. We split the *context period* in 2, right in the middle, with only the *targeted message* included in both parts. We extract the *Before* network from the messages posted in the first half and the *After* network from the messages posted in the second half. In a live classification setting where only past information is available, one would only be able to use the *Before* network. However, in a more general setting we can use all 3 networks (*Full*, *Before*, *After*). Figure 4.4 shows an example of such networks obtained for a message of the corpus. The disconnected vertices in the *Before* and *After* networks correspond to users present in the context period, but active only before or after the *targeted message*.

<figure><img src="image_8.png" /><figcaption>Figure 4.4: Example of the 3 types of conversational networks extracted for a given context period: *Before* (left), *After* (center), and *Full* (right). The author of the targeted message is represented in red.</figcaption></figure>

## 4.2 Proposed Representation Methods

In this section, we describe the feature engineering approaches that we use to tackle the problem of detecting abusive messages in conversations. We first summarize the text- (Section 4.2.1) and graph-based (Section 4.2.2) approaches. We then describe the fusion methods that we propose, aiming at taking advantage of both sources of information (Section 4.2.3). Figure 4.5 shows the whole process discussed through this section.

### 4.2.1 Text-Based Features

One way of representing a word is to characterize it with appropriate measures selected through a *Feature engineering* process. This procedure is heavily task- and context-dependent, and must
therefore be performed specifically for each application. For instance, one can assume that the
ratio of capital letters must be a key element to detect spam, while the presence of smileys is more
important in sentiment analysis. With a carefully designed set of measures, it is possible to obtain
representations of text that are suitable for downstream tasks such as text classification [139],
keyword extraction [140] or text categorization [141]. There exist a huge range of features that can
be used to characterize a word. Some of them are based on the morphology of words and some are
based on the language. We use a selection of text-based features oriented for the representation
of abusive messages, previously used in the literature [11], [142], [143]. We describe them in the
remaining of this section.

4.2.1.1 Morphological Features

Morphological features are characteristics related to the shape of the message.

**Message length:** The length of the message expressed in number of characters. The intuition is that abusive messages are often either very short or very long which might be symptomatic of a massive copy/paste.

**Word length:** The average and maximum word length in the message expressed in number of characters.

**Characters count:** The number of characters in the message. We distinguish 5 classes of characters (letters, digits, punctuation, spaces, and others) and compute 2 features for each one: the number of occurrences and the proportion of that class of characters in the message.

**Unique characters:** The number of unique characters in the message. In conjunction with the previous features, it can allow to detect spam messages with a single character overly emphasized (e.g. "fuuuuuuuuuuuuuuuuuuuuuuuuuuuuck").

**Capital letters:** The number and ratio of capital letters in the message. Abusive users tend to use a lot of capital letters to emphasize their messages.

**Compression ratio:** Abusive messages often contain a lot of copy/paste. To deal with such redundancy, we apply the Lempel-Ziv-Welch (LZW) compression algorithm [144] to the message and take the ratio of its raw to compress lengths, expressed in characters. This feature highlights users that tend to repeat exactly and multiple times the same text.

** collapsed characters:** Abusive messages also often contain extra-long words, which can be identified by collapsing the message, i.e. extra occurrences of letters repeated more than 2 times consecutively are removed. For instance, loooooool would be collapsed to lool. We compute the difference between the raw and collapsed message lengths.
### 4.2.1.2 Language Features

Language features are associated to a higher granularity of text than morphological features. They are related to words in the message.

**Number of words:** Intuitively, a message with more words and diverse ones is more likely to be constructive. People that verbally abuse other users rarely take the time to elaborate. We compute the total number of words and the number of unique words in the message.

**Bad words:** Even though there are obfuscations techniques to hide abusive words, many abusive words can still be detected with a simple predefined list of insults and symbols considered as abusive. We count the number of occurrences in the message. We also count them in the collapsed version of the message. In this application, we use a list of French and English bad words as our dataset is in French. We created this list from dictionaries of insults and swear words.

**Bag-of-Words (BoW):** BoW is a model that uses the frequency of words in a corpus to convert a piece of text into fixed-length vectors. As the name suggests, it puts words in a "bag" and compute the frequency of every word. Put differently, a textual document is represented by all the words contained in it together with the frequency of each word. Each dimension of the vector corresponds to a word from the corpus, and the associated value is the number of times this word appears in the document. This means that the dimension of the vectors depends on the size of the vocabulary. This causes the same scalability issues as with the one-hot encoding. The frequency count of words used in this model helps compare and contrast documents. However, with such a "bag" representation, any information about the order of words in the original text is lost. Hence, the sentences "I love cats and hate dogs" and "I love dogs and hate cats" obtain similar BoW representations.

We lower-case the text and strip punctuation, in order to represent the message as a basic BoW. We then train a Naive Bayes classifier to detect abuse using this sparse binary vector (as represented in the very bottom part of Figure 4.5). The output of this simple classifier, in the form of a score, is then used as an input feature for the SVM classifier.

**TF-IDF scores:** Term Frequency-Inverse Document Frequency determines how relevant a word is to a document in a corpus. It adjusts for the fact that some words appear more frequently in general by applying a scaling factor to the term frequency. The TF-IDF value increases proportionally to the number of times a word appears in a document, and is offset by the number of documents in the corpus that contain that word. Formally, this approach comprises 2 metrics, Term Frequency (TF) and Inverse Document Frequency (IDF). TF is the ratio of the number of occurrences of a word in a document to the total number of words in that document. It is formalized as

$$TF(t, d) = \frac{f_{t,d}}{\sum_{t' \in d} f_{t',d}}, \qquad (4.2)$$
where $f_{t,d}$ is the count of a term $t$ in document $d$, and the denominator is the total number of terms in $d$.

The IDF score measures the rarity of words in the text. It is the log ratio of the number of documents in the corpus $N$ to the number of documents with the term in them $D$:

$$ IDF(t, D) = \log \frac{N}{D}. \qquad (4.3) $$

The TF-IDF score of a document is the product of the 2 previous metrics (Equation 4.4). This method does not provide direct representations of words, but rather a score that indicates how important a term is in a document. This score can then be used among other measures in a feature engineering process to represent a word. It is defined as:

$$ TF-IDF(t, d, D) = TF(t, d) \times IDF(t, D). \qquad (4.4) $$

We compute 2 overall TF-IDF scores corresponding to the sums of the standard TF-IDF scores of each individual word in the message. One is processed relatively to the *Abuse* class, and the other to the *Non-abuse* class. We proceed similarly with the collapsed message.

### 4.2.2 Graph-Based Features

To characterize the extracted conversational graphs, we use the measures formally defined in Section 3. We use the (un)weighted, (un)directed, (un)signed versions of all these measures when possible. Table 4.1 gives an overview of all the measures and their variants that we use. In this section, we give an interpretation of these measures in the context of abuse detection to understand why they can be useful for this task.

#### 4.2.2.1 Vertex-Focused Topological Measures

We compute the vertex-focused measures for the vertex corresponding to the author of the targeted message (represented in red in Figure 4.4). The intuition is that measures related exclusively to this vertex could bring information that is not altered by other vertices. Hence, they could capture more precise information on the behavior of this particular author in the conversation.

**Microscopic measures:** In our application, microscopic measures are used to characterize the position of some user depending on its direct interlocutors. The **degree centrality** directly depicts the number of users that have exchanged (undirected version), received or sent (directed version) messages to the author. The **strength centrality** is the generalization of the degree to weighted graphs, which allows taking into account the frequency of the interactions. This is particularly important to describe authors with few interlocutors but strong interactions with them. Some users play a more central role than others in a community. As abusive users often operate on a short period of time, they are usually not very well embedded in the community. **Burt's**
**constraint** relates to this. The **local transitivity** gives information about the connections between the neighbors of the considered vertex. In our context, a high transitivity denotes that the author is implied in a single large conversation in which most users interact with each other. On the other hand, a low transitivity indicates that the user participates in several distinct conversations or that some of its interlocutors ignore each other.

**Macroscopic measures** allow characterizing the position of the targeted author relatively to the whole context period when dealing with the *Full* graph, or to one of its halves with the *Before* and *After* graphs. The **eigenvector centrality** helps to detect central vertices, which can be symptomatic of an abusive author. An important authority score can characterize a user which receives much attention, while a very important hub score can rather represent someone harassing others. In our conversational graph, we expect that a user participating a lot in the conversation will be central, and thus have a high **subgraph centrality**. The **betweenness centrality** can be interpreted as the level of control that the user has over information transmission. The goal of abusive authors is usually to reach as many people as possible with their messages. The **closeness centrality** precisely measures the efficiency of a given vertex to spread a message over the graph. A high closeness indicates an author that plays an important role in the discussion. The **eccentricity** also indicates how involved the considered user is in the conversation. The **articulation point** binary feature help detect users that play the role of a bridge between 2 separate groups of users in the conversation.

**Mesoscopic measures** rely on a subgraph that is likely to represent a conversation. The **coreness score** is related to the number of participants of the largest conversation in which the author of interest is involved. It can be seen as the potential targets of an abusive message. The **within-module degree** relates to how involved the user is in his current conversation, and the **participation coefficient** indicates if the user holds a mediation position in the conversation.

### 4.2.2.2 Graph-Focused Topological Measures

Although we suppose that the vertex corresponding to the author of the targeted message is the one with most important information for our task, it is still possible that other vertices bring additional information. A solution to obtain measures describing the entirety of the graph is to compute a vertex-focused measure over the whole vertex set, and average them. We apply this methodology with all the vertex features described in Section 4.2.2.1. In addition to these artificial aggregated features, we also leverage measures that are specifically defined at the graph scale.

We assume that in a standard conversation, all interactions tend to be bilateral, which is a property captured by the **reciprocity** measure. The **degree assortativity** measures the tendency for vertices to be connected with other similar vertices, and thus can differentiate groups of users based on their behaviors. Many users leave a conversation when an abusive author is active in it. Thus, users in healthy conversations interact with more people than users in conversations
containing abusive comments. The **weak component count** captures this phenomenon. The **cohesion** and **adhesion** denote the presence of several distinct conversations in the network, with users interacting in many of them. To compute the **community count** and the **modularity**, we extract the community structure through the InfoMap algorithm [145].

### 4.2.3 Combining the Textual and Structural Information

In the previous sections, we defined a set of text and graph features. We now propose a method seeking to take advantage of both to study the complementary nature of these 2 sources of information. Indeed, they are based on 2 completely distinct ways of representing messages in a conversation, i.e. the message itself and the conversational graphs. To check this complementarity, we propose and experiment with 3 different fusion strategies to combine the features extracted by both feature-based methods. Figure 4.5 shows the whole pipeline.

<figure><img src="image_9.png" /><figcaption>Figure 4.5: Representation of our processing pipeline. The top part (red) represent the graph-based method, the bottom part (green) represent the content-based method and the fusion strategies appear on the right side.</figcaption></figure>

The left part represents the conversation in which the message to classify (in orange) was posted. This whole conversation is used by the graph-based method (top part, in red) to extract a conversational graph. Then, we compute all the topological measures described previously to represent this graph. Finally, this vector of features is fed to the graph-based SVM to obtain a predicted class. The bottom part (in green) represents the content-based method. The top part illustrates the extraction of text-based features directly from the message. In the bottom part, we first represent the message as a BoW, and train a Naive Bayes classifier to detect abuse using this sparse binary vector. The output of this classifier is added to the other features to form the message's representation which is then fed to the content-based SVM. We then use the features and scores produced by these 2 methods in our 3 fusion methods. We describe them as:
<table><caption>Table 4.1: Summary of the graph measures used in the graph-based method. The letters in the *Weight*, *Direction* and *Sign* columns stand for: *Unweighted*, *Undirected* or *Unsigned* (U), *Weighted* (W), *Directed* (D), *Incoming* (I), *Outgoing* (O) and *Signed* (S).</caption><thead><tr><th>Scale</th><th>Scope</th><th>Name</th><th>Weight</th><th>Direction</th><th>Sign</th></tr></thead><tbody><tr><td rowspan="12">Vertex</td><td rowspan="4">Microscopic</td><td>Degree Centrality</td><td>U</td><td>U/I/O</td><td>U/S</td></tr><tr><td>Strength Centrality</td><td>W</td><td>U/I/O</td><td>-</td></tr><tr><td>Local Transitivity</td><td>U/W</td><td>U</td><td>-</td></tr><tr><td>Burt's Constraint</td><td>U/W</td><td>-</td><td>-</td></tr><tr><td rowspan="10">Macroscopic</td><td>Eigenvector Centrality</td><td>U/W</td><td>U/D</td><td>-</td></tr><tr><td>PageRank Centrality</td><td>U/W</td><td>U/D</td><td>-</td></tr><tr><td>Hub / Authority scores</td><td>U/W</td><td>D</td><td>-</td></tr><tr><td>Alpha Centrality</td><td>U/W</td><td>D</td><td>-</td></tr><tr><td>Power Centrality</td><td>U</td><td>D</td><td>-</td></tr><tr><td>SubGraph Centrality</td><td>U</td><td>U</td><td>-</td></tr><tr><td>Betweenness Centrality</td><td>U/W</td><td>U/D</td><td>-</td></tr><tr><td>Closeness Centrality</td><td>U/W</td><td>U/I/O</td><td>-</td></tr><tr><td>Eccentricity</td><td>U</td><td>U/I/O</td><td>-</td></tr><tr><td>Articulation point</td><td>-</td><td>U</td><td>-</td></tr><tr><td rowspan="6">Mesoscopic</td><td>Coreness Score</td><td>-</td><td>U/I/O</td><td>-</td></tr><tr><td>Within-module Degree</td><td>U</td><td>U/I/O</td><td>-</td></tr><tr><td>Participation Coefficient</td><td>U</td><td>U/I/O</td><td>-</td></tr><tr><td>External Intensity</td><td>U</td><td>U/I/O</td><td>-</td></tr><tr><td>Diversity</td><td>U</td><td>U/I/O</td><td>-</td></tr><tr><td>Heterogeneity</td><td>U</td><td>U/I/O</td><td>-</td></tr><tr><td rowspan="12">Graph</td><td rowspan="5">Microscopic</td><td>Vertex count</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Edge count</td><td>-</td><td>-</td><td>U/S</td></tr><tr><td>Density</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Global Transitivity</td><td>U</td><td>U</td><td>-</td></tr><tr><td>Reciprocity</td><td>-</td><td>D</td><td>-</td></tr><tr><td rowspan="5">Macroscopic</td><td>Degree Assortativity</td><td>-</td><td>U/D</td><td>-</td></tr><tr><td>Weak Components Count</td><td>-</td><td>U</td><td>-</td></tr><tr><td>Strong Components Count</td><td>-</td><td>D</td><td>-</td></tr><tr><td>Adhesion/Cohesion</td><td>-</td><td>D</td><td>-</td></tr><tr><td>Articulation Points</td><td>-</td><td>U</td><td>-</td></tr><tr><td rowspan="4">Macroscopic</td><td>Diameter</td><td>U/W</td><td>U/D</td><td>-</td></tr><tr><td>Radius</td><td>U</td><td>U/I/O</td><td>-</td></tr><tr><td>Average Distance</td><td>U</td><td>U/D</td><td>-</td></tr><tr><td>Mesoscopic</td><td>Clique Count</td><td>-</td><td>-</td><td>-</td></tr><tr><td rowspan="2">Microscopic</td><td>Communities</td><td>U</td><td>D</td><td>-</td></tr><tr><td>Modularity</td><td>U/W</td><td>U</td><td>-</td></tr></tbody></table>

**Early Fusion:** The first strategy consists in constituting a global feature set containing all content- and graph-based features from Sections 4.2.1 and 4.2.2 respectively, then training an
SVM classifier directly using these features. This is illustrated in the top-right corner of Figure 4.5. The rationale with this method is that the classifier has access to the whole set of features, independently of its source (text or graph). Thus, it can determine which ones are the most relevant for the classification task and put the focus on them to improve the performance.

**Late fusion:** The second strategy is processed in 2 steps. First, we apply separately both text and graph methods. We feed the respective features of each method to an SVM that outputs a score corresponding to the probability of each message to be abusive given by the content- and graph-based methods, respectively. Then, we fetch these 2 scores to a new classifier trained to determine if a message is abusive or not. This third classifier thus only takes 2 input variables and outputs the final predicted class of the message. This is illustrated in the middle-right part of Figure 4.5. This approach relies on the assumption that the 2 initial classifiers could act as an extreme dimensionality reduction system which compact the important information into a single score. Hence, these scores contain all the information that the final classifier needs, and not the noise present in the raw features.

**Hybrid fusion:** Finally, the third fusion strategy seeks to combine both previous proposed ones. We create a feature set containing features from both sources, like with *Early Fusion*, but also both scores used in *Late Fusion*. This whole set is used to train a new classifier. It corresponds to the bottom-right corner of Figure 4.5. The idea with this strategy is to check if the scores convey additional information compared to the raw features, in which case combining scores and features should lead to better results.

## 4.3 Experiments

In the previous section, we described the various text and graph features that we extract, and the approaches proposed to combine them. We now assess the performances of these methods. We first describe the experimental protocol followed in our experiments regarding the automatic detection of abusive messages in conversations (Section 4.3.1). Then, we present and discuss our results, in terms of classification performance (Section 4.3.2). Finally, we perform an in-depth analysis of our features to determine the most important ones for the classification and gain a better comprehension of our dataset and task (Section 4.3.3).

### 4.3.1 Experimental Protocol

We conduct our experiments on the SpaceOrigin dataset previously described in Section 2.3 composed of 2,545 annotated messages. We are in a posterior classification setup which implies that we have access to the context before and after the annotated messages. To handle all classes equally in this unbalanced setting, we express the performance in terms of macro F-measure, as defined in Section 2.4.
For the graph-based method, we extract conversational networks following the methodology described in Section 4.1. There are 2 important parameters for this extraction process, the *context period* size and the *sliding window* length. We use the values matching best performances on the test set, obtained during the greedy search of the parameter space performed in [6]. We fix the length of the sliding window to 8 messages and the size of the context period to 1,600 messages. Half of which were posted before the annotated message and the other half after. Implementation-wise, we use the iGraph library [146] to extract the conversational networks and process the corresponding features. We use the Sklearn toolkit [147] to get the text-based features.

We use an SVM for the classification, as it is well-suited for small datasets such as ours. We also experimented with other standard classifiers, but that did not change the order in which the methods are ranked. Therefore, we use an SVM as our classification system in the rest of this thesis. For the same reason of dataset dimension, we set up our experiments with a 10-fold cross-validation. We use a 70%-train / 30%-test split, which means that for each run of the cross-validation, 7 folds are used for the train and the remaining 3 compose the test set.

### 4.3.2 Classification Results

Table 4.2 presents the macro F-measure scores obtained for the independent text and graph-based methods, and all 3 fusion strategies described previously (*Early Fusion*, *Late Fusion*, *Hybrid Fusion*). It also shows the number of features used to perform the classification. Note that *Late Fusion* has only 2 direct inputs (the scores generated by content- and graph-based SVMs), but these in turn have their own inputs, which explains the values displayed in the table.

<table><caption>Table 4.2: Comparison of the performances obtained with the methods *Content-based*, *Graph-based*, and the 3 *Fusion* strategies. The total runtime is expressed as *h:min:s*.</caption><thead><tr><td>Method</td><td>Number of features</td><td>Total runtime</td><td>F-measure</td></tr></thead><tbody><tr><td>Content-Based</td><td>29</td><td>0:41</td><td>75.21</td></tr><tr><td>Graph-Based</td><td>477</td><td>3:51:25</td><td>83.40</td></tr><tr><td>Early Fusion</td><td>506</td><td>3:55:17</td><td>84.51</td></tr><tr><td>Late Fusion</td><td>506 (2)</td><td>3:54:57</td><td>84.17</td></tr><tr><td>Hybrid Fusion</td><td>508</td><td>3:57:44</td><td>84.97</td></tr></tbody></table>

The first interesting result is that the graph-based method clearly outperforms the content-based one. Intuitively, one could think that the content of a message is the main factor to determine its degree ofabusiveness. However, this result shows otherwise. Relying on the interactions between users on a short period of time before and after a particular message is posted, seems
to be much more efficient for this task. Though surprising at first sigh, this result is in line with
previous studies [6], [11]. We suppose that when an abusive message is posted in a conversation,
it tends to change the way users interact with each other. It can be either by generating a massive
spike in reactions toward the author of that message, or by *killing* the conversation with people not
wanting to interact with the abusive author and ultimately leaving the discussion. Thus, the abusive
author plays a central role in the conversational graph that can be captured by our features. On
the other hand, non-abusive messages usually go unnoticed and are mixed in with all the others
messages, therefore not playing such a central role in the graph.

This result also emphasizes the importance of using conversational context to correctly detect abuse. Indeed, the content-based method might easily be tricked by spelling mistakes (intentional or not) or by obfuscation techniques (e.g. "f..k 0ff"). This can lead to abusive messages not being detected when using the content, while the graph-based method is unaffected by such techniques. The modeling of conversations and interactions can also reduce the false positive rate. For instance, in the case of a borderline message which some would consider abusive, knowing that the 2 authors share a long history drastically reduces the likelihood that the message is truly abusive. It might be more of a joke between friends.

Although showing many benefits, the graph-based method is computationally very expensive
due to the high number of computed features and the complex nature of some of them. It took
almost 4 hours to compute the graph-based features for the full dataset, while it took less than a
minute on the same machine for the content-based approach. This difference is also due to the
number of features for each method: only 29 for the text and 477 for the graphs. One could argue
that the performance gap between these 2 approaches is mainly caused by this major difference
in the size of the features set. We address this question in the next section and show that this is
not the case. The content-based method also suffers from the fact that there is no clear standard
in the features used to describe a message. On the other hand, there are many well established
topological measures to capture various properties of graphs.

With the fusion methods, we try to further improve the classification performance by combining
the 2 modalities. Our first observation is that we get higher *F*-measure values compared to both
individual methods when performing the fusion, no matter the fusion strategy. This confirms what
we expected, i.e. both sources are at least partly complementary, since the performance increases
when merging them. The content can bring useful information for the messages that are clearly
abusive in their form, while the conversational graphs can bring information based on the context.

Next, when comparing the fusion strategies, it appears that *Hybrid Fusion* performs better than
the others, with an *F*-measure of 84.97%. This is what we were expecting, since this strategy
is the combination of the other 2, benefiting from both. The *Late Fusion* is the least efficient
fusion strategy but by just a few tenths of a point. This method only gets 2 features, which are
themselves the outputs of 2 other classifiers. This means that these classifiers do a good work in
summarizing their inputs, without losing much of the information necessary to efficiently perform
the classification task. We could see these intermediate classifiers as a pre-processing step, which
reduces the dimensionality of data. The *Early Fusion* produces better results than the *Late Fusion*
with its combination of all the available features. Regarding runtime, the fusion methods are a few
minutes longer than graph-based method since these approaches require computing both content-
and graph-based features.

4.3.3 Feature Study

We developed our content- and graph-based methods based on an exploratory approach which
consists in selecting a very wide range of widespread features in the literature. We adopted this
methodology because we had no idea of the features that were important for this specific task.
The goal with such an exploratory approach was not to miss any important features. This resulted
in large sets of 29 content features and 477 graph features that are computationally expensive to
calculate, especially the latter. Furthermore, we assume that some of them are useless for the
classification, i.e. they do not bring any additional information compared to the rest of the features.

In this section, we try to estimate the discriminative power of our features with regard to our
classification task. The objective is to identify the best features for all our methods and fusion
strategies. In order to do so, we apply an iterative approach based on the *Sklearn* toolkit, which
allows us to fit a linear kernel SVM to the dataset and provide a ranking of the input features
reflecting their importance in the classification process. Using this ranking, we identify the least
discriminant feature, remove it from the dataset, and train a new model with the remaining features.
The impact of this deletion is measured by the performance loss, in terms of *F*-measure. We
reiterate this process until only one feature remains. We call *Best Features* (BF) the minimal subset
of features allowing to reach 97% of the original performance (when considering the complete
feature set). This threshold was chosen arbitrarily to have a limited number of BF, while preserving
good performance.

We apply this process to our content- and graph-based methods and all 3 fusion strategies.
We then repeat the classification process using only their respective BF. The results are shown in
Table 4.3 with a comparison to the original results obtained on the complete feature sets. Note
that the *Late Fusion BF* performance is obtained using the scores produced by the SVMs trained
on *Content-based BF* and *Graph-based BF*. These are also used as features when computing the
BF for *Hybrid Fusion BF* (together with the raw content- and graph-based features). In terms of
classification performance, by construction, the methods are ranked exactly like when considering
all available features.

The BF obtained for each method are listed in Table 4.4. The last 4 columns indicate which
variants of the graph-based features are concerned. Indeed, as explained in Section 4.2.2, most
of these topological measures can handle/ignore edge weights and/or edge directions, can be
<table><caption>Table 4.3: Comparison of the performances obtained with the methods (*Content-based*, *Graph-based*, *Fusion*) and their subsets of *Best Features* (BF). The total runtime is expressed as *h:min:s*.</caption><thead><tr><th>Method</th><th>Number of features</th><th>Total Runtime</th><th>F-measure</th></tr></thead><tbody><tr><td>Content-Based</td><td>29</td><td>0:41</td><td>75.21</td></tr><tr><td>Content-Based BF</td><td>3</td><td>0:27</td><td>73.17</td></tr><tr><td>Graph-Based</td><td>477</td><td>3:51:25</td><td>83.40</td></tr><tr><td>Graph-Based BF</td><td>10</td><td>7:59</td><td>81.08</td></tr><tr><td>Early Fusion</td><td>506</td><td>3:55:17</td><td>84.51</td></tr><tr><td>Early Fusion BF</td><td>4</td><td>9:49</td><td>82.29</td></tr><tr><td>Late Fusion</td><td>506 (2)</td><td>3:54:57</td><td>84.17</td></tr><tr><td>Late Fusion BF</td><td>13</td><td>9:31</td><td>81.89</td></tr><tr><td>Hybrid Fusion</td><td>508</td><td>3:57:44</td><td><strong>84.97</strong></td></tr><tr><td>Hybrid Fusion BF</td><td>4</td><td>10:29</td><td>82.66</td></tr></tbody></table>

vertex- or graph-focused, and can be computed for each of the 3 types of networks (*Before*, *After* and *Full*).

There are 3 *Content-Based BF*. The first is the *Naive Bayes* prediction, which is not surprising as it comes from a fully fledged classifier processing BoW. This system on its own could be used as the main abuse detection method in some scenarios. In our application context, the naive Bayes classifier alone obtains a *F*-measure score of 62.01. The second BF is the *TF-IDF score* computed over the *Abuse* class, which shows that considering term frequencies indeed improve the classification performance. The fact that this is the score computed over the *Abuse* class is particularly interesting because it suggests that there are words or family of words which are characteristic of abusive messages. Of course, we can think of insults and swear words. This information should be captured by our *Bad words* feature, but since it is not among the BF, we can assume that its information is redundant with the *TF-IDF score*. The third BF is the *Capital Ratio* (proportion of capital letters in the comment), which is likely to be caused by abusive messages tending to be shouted, and therefore written in capitals.

We obtain 10 features for the *Graph-Based BF*. Among them, 4 are computed at the vertex-scale (i.e. only for the targeted vertex) and 6 are computed over the whole graph. Most of these features seem to confirm our previous assumption that abusive messages tend to generate more reactions than non-abusive messages. The *Coreness* score, which is closely related to the number of users interacting with the author of a message, is the best topological measure for this task. We find 2 variants of this measure in the BF, one computed over the *Full* graph and the other over the *Before* graph. The presence of the *Authority* score among BF can be explained by the same
<table><caption>Table 4.4: Best features obtained for our 5 methods. The letters in the *Graph* column stand for *Before* (B), *After* (A) and *Full* (F). Those in the *Weights* and *Directions* columns stand for: *Unweighted* or *Undirected* (U), *Weighted* (W), *Directed* (D), *Incoming* (I) and *Outgoing* (O). Those in the *Signs* column mean *Unsigned* (U) or *Signed* (S). Those in the *Scale* column stand for *Graph-scale* (G) or *Vertex-scale* (N).</caption><thead><tr><th>Method</th><th>Best Features (BF)</th><th>Graph</th><th>Weights</th><th>Directions</th><th>Signs</th><th>Scale</th></tr></thead><tbody><tr><td rowspan="3">Content-Based</td><td>Naive Bayes</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>TF-IDF Abuse Score</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Character Capital Ratio</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td rowspan="10">Graph-Based</td><td>Coreness Score</td><td>F</td><td>-</td><td>I</td><td>-</td><td>G</td></tr><tr><td>Authority Score</td><td>B</td><td>W</td><td>D</td><td>-</td><td>G</td></tr><tr><td>Closeness Centrality</td><td>B</td><td>W</td><td>O</td><td>-</td><td>G</td></tr><tr><td>PageRank Centrality</td><td>A</td><td>U</td><td>D</td><td>-</td><td>N</td></tr><tr><td>Closeness Centrality</td><td>B</td><td>W</td><td>O</td><td>-</td><td>N</td></tr><tr><td>Coreness Score</td><td>B</td><td>-</td><td>I</td><td>-</td><td>G</td></tr><tr><td>Degree Centrality</td><td>F</td><td>U</td><td>O</td><td>U</td><td>N</td></tr><tr><td>Vertex Count</td><td>F</td><td>-</td><td>-</td><td>-</td><td>G</td></tr><tr><td>Reciprocity</td><td>A</td><td>-</td><td>D</td><td>-</td><td>G</td></tr><tr><td>Closeness Centrality</td><td>A</td><td>W</td><td>U</td><td>-</td><td>N</td></tr><tr><td rowspan="4">Early Fusion</td><td>Coreness Score</td><td>A</td><td>-</td><td>O</td><td>-</td><td>G</td></tr><tr><td>Strength Centrality</td><td>B</td><td>W</td><td>O</td><td>-</td><td>N</td></tr><tr><td>Naive Bayes</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Eccentricity</td><td>B</td><td>-</td><td>I</td><td>-</td><td>G</td></tr><tr><td rowspan="2">Late Fusion</td><td>Content-Based BF ∪ Graph-Based BF</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Hybrid Fusion</td><td>Graph-based output</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td rowspan="3">Hybrid Fusion</td><td>Coreness Score</td><td>B</td><td>-</td><td>I</td><td>-</td><td>G</td></tr><tr><td>Content-based output</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Hub Score</td><td>B</td><td>U</td><td>D</td><td>-</td><td>N</td></tr></tbody></table>

reasons as it also relates to how central a vertex is in the graph. There are 3 variants of the *Closeness centrality* in the BF subset. 2 of them focus on the targeted vertex while the third is averaged over all vertices to represent the graph scale. This measure is considered as the efficiency of the vertex to spread a message over the graph. Once again, this directly relates to the tendency of abusive message to spread wider and faster than other messages. The *PageRank* captures how influential a vertex is in the graph and the *Degree centrality* can be interpreted as
the number of users that have exchanged with the author. All these features can be interpreted
as different measures of our assumption. However, they all capture different information since
removing any of the BF has a noticeable negative impact on the classification performance. The
last 2 BF are the *Reciprocity*, which captures the tendency of certain users to respond or not to
others. Finally, the *Vertex count* is the number of users participating in the conversation. The fact
that an abusive author interact in the discussion can affect one way or the other the number of
active users in the discussion.

There are 4 features for *Early Fusion BF*. One is the *Naive Bayes* feature (content-based), and the other 3 are topological measures (graph-based features). The *Coreness* score, though with different variants, was also among the graph-based BF. The *Strength* centrality is a generalization of the degree centrality, which was also among them. The *Eccentricity* of the graph reflects important changes in the interactions between users. It is likely caused by angry users piling up on the abusive user after he has posted some inflammatory remark. Note that eccentricity is related to the closeness centrality. Hence, the 4 *Early Fusion BF* are either directly among the BF of one of our 2 methods or, related to a feature that is part of them.

For *Hybrid Fusion BF*, we also get 4 features but those include both scores produced by the classifiers from the content- and graph-based methods. Those are completed by 2 graph-based features, the *Coreness* score (also found in the *Early Fusion BF*) and Hub score. It is interesting to note that the *Hybrid Fusion BF* and *Early Fusion BF* are a mix of features based on text and graphs. The complementary nature of these 2 methods was already proved by the results in Table 4.2, but this also demonstrates that both methods provide some measures that cannot be replaced by features of the other type.

This in-depth study of our features gives us a better understanding of our dataset and classifica-
tion process. We now know which text and graph measures are the most important to characterize
abusive messages of our dataset. In addition, we demonstrated that a small subset of features
can be enough to train a classifier almost as good as the original classifier trained on the complete
set of features. We can retain 97% of the performance while using only 3 out of the 29 features
(10.34%) based on the content. This effect is even stronger with graphs, as only 10 out of 477
(2.10%) features are needed to retain this degree of performance. This is a very interesting result,
since the feature computation is by far the most computationally expensive step of the framework.
Computing only a handful of features instead of hundreds allows drastically decreasing the com-
putational cost of the classification. This is true for all methods. For instance, a classifier trained
with the *Graph-Based BF*, only requires 3.5% of the total *Graph-Based* runtime.
## 4.4 Analysis and Discussion

We now discuss the results of the feature engineering methods aiming to detect abusive messages. Our 2 points concern the graph-based system. First, we explore its temporal aspect (Section 4.4.1). Second, we investigate how considering the edge weights, directions and signs in graphs impact the classification performance (Section 4.4.2).

### 4.4.1 Temporal Aspect

As explained in the graph extraction process (Section 4.1), there are actually 3 networks extracted for each message to classify: the *Full*, *Before* and *After* networks. The graph-based results shown until now are all obtained using the *All* feature set, i.e. the features resulting from the calculation of all topological measure variants for all 3 individual graphs (*Full*, *Before* and *After*).

However, the *After* network is only available in a post-classification context where users have had time to respond to the message of interest. This is the case in our work, and more generally with most of the research work. However, real life applications often require taking a decision as soon as the message is posted. For instance, to block it before it is published if there is a suspected abuse. In this case, the detection method can only rely on the context posted *Before* the message. In this section, we study the performance of our framework in a real-time classification context. For the sake of completeness, we also consider the opposite case, where only the context *After* the message is available. This could correspond to an application which logs messages only after one of them has been reported.

To obtain a better understanding of the role of each part of the context, we train and test a classifier on each of the 3 feature sets (*Full*, *Before* and *After*). Each feature set is composed of the graph-based features extracted from the corresponding graph. Table 4.5 shows the classification performance obtained. As a comparison, we also include the *All* set, which is the combination of the other 3. This is the set of features that was used in all the previous experiments. Aside from the input graphs, the experimental protocol is exactly the same as in the previous section.

<table><caption>Table 4.5: Comparison of the performances obtained with the feature sets *Before*, *After*, *Full* and *All*. The latter is the combination of the first 3.</caption><thead><tr><td>Temporality</td><td>Number of features</td><td>F-measure</td></tr></thead><tbody><tr><td>Before</td><td>159</td><td>79.08</td></tr><tr><td>After</td><td>159</td><td>78.97</td></tr><tr><td>Full</td><td>159</td><td>82.89</td></tr><tr><td>All</td><td>477</td><td>83.40</td></tr></tbody></table>
The performance of the *Before* and *After* feature sets are almost on par. They obtain acceptable performance level considering that they have access to only half of the *Full* context. This shows that the context before is as important as the context after to detect an abusive message. This is surprising, as one could think that the reactions after a message give more information about its nature than its predecessors.

For the context *After*, we already mentioned the fact that abusive messages tend to modify the way authors interact with each other and thus change the structure of the graph. Regarding the context *Before* the message, we can assume that it is possible to predict an abusive message before it is even posted thanks to the build-up leading to that message. The abusive author starts to stand out from the other users and draws attention before posting its abusive comment. This result is very promising as it shows that building a real-time classifier using only the past messages is possible and can give decent performance. This is the type of application that could typically be used on online forums or social networks.

The *Full* feature set logically obtains a better *F*-measure as it covers the same context period as the previous 2 combined. It is worth noting that this feature set obtain noticeably higher performance than the *Before* and *After* sets, which means that there is information allowing to discriminate abusive messages in both sets and that their information do no completely overlap. As expected, the *All* feature set performs best overall, as it is the union of all the other considered feature sets. However, it is only slightly better than *Full*. This shows that the *Full* feature set already conveys almost all the information. This is interesting as using the *Full* set instead of *All* means computing only one third of the features and thus greatly decreases the runtime without impacting heavily the classification performance. Furthermore, the *All* set requires extracting 3 graphs, while the *Full* set only requires one. The time saving is negligible compared to the previous point, but it is still important as it could have a bigger impact for very large graphs. These 2 options are worth exploring in a future work, and especially in combination with the best features.

### 4.4.2 Impact of Edge Attributes

Edge directions and weights are graph-specific information that cannot be found in the content-based method. The weight represents the intensity of an interaction between 2 users, the direction its reciprocity (unilateral or bilateral). On the other hand, the edge sign, which represents its polarity (hostile or friendly), is obtained through a sentiment analysis of the text, and is therefore directly related to it. Some of the measures used to represent graphs are able to deal with these properties, while others ignore them. To investigate in more details how using or not these properties affects the classification performance, we set up the following experiments. We define 8 variants of our conversational graphs, all the possible combinations of (*Un*)*weighted-(*Un*)*directed-(*Un*)*signed graphs. Note that the *Weighted-Directed-Signed* graph is the standard configuration used in all our previous experiments. We then compute our graph-based features for each graph and compare
their respective classification performance. The results are shown in Table 4.6.

<table><caption>Table 4.6: Comparison of the F-measure obtained when considering the 8 different types of graphs. Bottom right is the standard configuration used in the rest of this section.</caption><thead><tr><th>Graph type</th><th></th><th>Unsigned</th><th>Signed</th></tr></thead><tbody><tr><td rowspan="2">Unweighted</td><td>Undirected</td><td>72.26</td><td>72.39</td></tr><tr><td>Directed</td><td>72.51</td><td>72.60</td></tr><tr><td rowspan="2">Weighted</td><td>Undirected</td><td>74.94</td><td>74.92</td></tr><tr><td>Directed</td><td>75.18</td><td><strong>75.21</strong></td></tr></tbody></table>

It appears that all weighted methods obtain better performance than their unweighted counterparts. This indicates that edge weights help the classifier to identify abusive messages. If we think of abusive authors as persons who draw a lot of attention because of their behavior, this is reflected in the edge weights that are higher than other users overall. As a reminder, most of the weights in our graphs are computed based on an assumption that consecutive messages respond to each other. While generally true, this assumption can lead to incorrect weight assignation in some cases. Consequently, we think that weights can have an even stronger impact in applications where they are perfectly computed.

The directions also bring a slight improvement, but very limited compared to the weights. We can think of some cases where edge weights used in conjunction with directions can highlight an abusive behavior. For instance, a very strong unilateral link between 2 users can be symptomatic of harassment.

Edge signs appear to have a small impact on the performance. This impact is probably limited due to the very small number of signed features. Edge signs are particularly well suited for conversational graphs as they can model friendships and enmities, so we think that in other configurations, it could have a lot more impact. Nonetheless, the best overall performance is reached with the *Weighted - Directed - Signed* graphs showing that this is worth including measures that account for these graph-specific properties.

## 4.5 Conclusion

In this chapter, we have presented several approaches to automatically detect online abusive messages using feature engineering from different sources of information. We extended this framework by applying 2 methods: the first one based on the content and using NLP features. The second, a *graph-based* approach, integrates all the contextual aspects of conversions through conversational graphs. We manually constituted a set of 29 textual features to create a representation of the message in the *content-based* method, and a set of 477 topological measures to character-
ize the graph in the *graph-based* approach. We applied these methods to the dataset extracted
from the in-game chat of SpaceOrigin, an online video game from Chapter 2.3.2. Our experiments
showed that the method relying exclusively on feature engineering from graphs to model the inter-
actions between users (i.e. the context in which a message is posted), obtain better classification
performance than the method relying on the content and ignoring context of the targeted message.
This highlights how important the context is when dealing with abuse detection.

We also proposed 3 fusion strategies to combine the 2 proposed methods and showed that their combination improve the performance, suggesting that text and graphs are 2 complementary sources of information for this task. Then, we studied in details the features of all our methods and identified the ones that are the most important in the classification process. We showed that using only a very small subset of so-called *best features* was enough to obtain 97% of the original performance. Furthermore, we explored the temporal aspects of our *graph-based* method. Though it is better to use all the context available around the message to classify, we showed that using only the context *before* or *after* the message still leads to satisfying performance. Finally, we demonstrated how using the edge directions, edge signs and most importantly the edge weight improve the performance.

We believe that this work can be extended in several ways. First, one important limitation of our methodology based on feature engineering is the high computational time required to extract the graph features. However, we show that using a small subset of relevant features can dramatically reduce the processing time (by more than 96%) while keeping more than 97% of the original performance. Second, our graph-based method currently uses all the context available. An extension could be to adapt it to a real-time classification setting by considering only the messages which were posted before the message to process. Third, we showed that edge weights, directions and signs were important parameters which improve the classification performance of the graph-based method. They provide additional information regarding the nature and the intensity of the interactions between users. Finally, one main finding of this chapter is that combining content and graphs works fine, but it is difficult and computationally expensive in a feature engineering framework. It is also possible to miss some important features with this approach. Therefore, in the rest of this manuscript, we propose to use representation learning to automatically learn representations of messages and graphs. For text, we focus on existing methods [148]–[154] in Chapter 6. There are also many graph representation learning techniques, however they do not cover the full range of attributes available in our conversational networks. In the next chapter, we review the graph representation learning literature, and propose methods to fill this methodological gap.
SIGNED WHOLE-GRAPH EMBEDDING

<table><tr><td>5.1 Definitions and Notations</td><td>71</td></tr><tr><td>5.2 Graph Representation Learning</td><td>72</td></tr><tr><td>5.2.1 Vertex Embedding</td><td>73</td></tr><tr><td>5.2.2 Whole-Graph Embedding</td><td>76</td></tr><tr><td>5.2.3 Signed Graph Embedding</td><td>78</td></tr><tr><td>5.3 Datasets</td><td>80</td></tr><tr><td>5.3.1 Correlation Clustering Instances</td><td>81</td></tr><tr><td>5.3.2 European Parliament Roll-Calls</td><td>81</td></tr><tr><td>5.3.3 Brief Comparison</td><td>82</td></tr><tr><td>5.4 Proposed Methods</td><td>83</td></tr><tr><td>5.4.1 Signed Network Embedding</td><td>83</td></tr><tr><td>5.4.2 Signed Graph2vec</td><td>84</td></tr><tr><td>5.4.3 Signed Graph Convolutional Networks</td><td>85</td></tr><tr><td>5.5 Experiments</td><td>86</td></tr><tr><td>5.5.1 Results</td><td>87</td></tr><tr><td>5.5.2 Comparison</td><td>92</td></tr><tr><td>5.6 Conclusion</td><td>93</td></tr></table>

In Chapter 4, we experimentally showed that edge directions, weights and signs help improve the detection of abusive messages when using feature-based approaches. Because of the important computational cost of feature engineering methods for graphs, and the complexity for a human to create a set of discriminant features, we propose to use representation learning as a solution to automatically learn graph representations. It is even possible that such representations also improve the classification performance because they are dense representations automatically learned without having to redefine them. Graph representation learning methods can operate at different granularity levels, such as vertex and whole graph. Vertex embedding is the task consisting in learning a representation for each vertex of the graph, while whole-graph embedding seeks to learn a single representation of the graph as a whole. In our context, the abuse detection task consists in classifying graphs, therefore we would like to learn representations of whole
graph, while taking into account edge attributes. On the one hand, a number of graph embedding
approaches allow, or can easily be tweaked, to take weights and directions into account (e.g. [85],
[155]–[157]). There are weighted and/or directed methods that are designed for vertex and for
whole-graph embedding. On the other hand, signs are much more complicated to incorporate in
a graph embedding pipeline, as the duality between positive and negative edges involves complex
concepts. Therefore, several recent methods only handle vertex representations in signed graphs
(e.g. [158]–[160]), and the literature offers no method for signed whole-graph representations.

In this chapter, we first review the literature of graph representation learning. Then, we pro-
pose 2 original approaches to learn whole-graph representations of signed graphs. The first is a
generalization of the unsigned whole-graph embedding method Graph2vec [161] to signed whole
graphs. The second one is a generalization of the signed vertex embedding method Signed Graph
Convolutional Networks (SGCN) [160] to signed whole graphs. We propose several variants of
these models and assess them experimentally. The SpaceOrigin dataset that we used in the pre-
vious chapter is relatively small, so we constitute a benchmark composed of 3 distinct collections
of graphs, including SpaceOrigin for the experimental evaluation of our methods. This benchmark
also allows us to improve the diversity of graphs, both in terms of structure and properties.

The following chapter is based on our work [23]. Our source code is publicly available online<fnref n="1" />.
It makes the following contribution:

1. We review the graph representation learning literature, focusing on the vertex- and graph-level methods.

2. We propose 2 adaptations of existing methods to learn whole-graph representations of signed graphs, for which we define several variants.

3. We constitute and share a benchmark annotated for signed graph classification, and composed of 3 distinct collections.

4. We present extensive computational experiments established for the proposed methods, on our benchmark.

The rest of this chapter is organized as follows. In Section 5.1 we introduce the main concepts and notations used later in the chapter. Next, we survey graph embedding techniques in Section 5.2. Then, we present our signed graph classification benchmark in Section 5.3, and we describe the methods that we propose to handle signed whole-graph representation learning in Section 5.4. We present and discuss our results in Section 5.5. Finally, we review our main findings and describe how our work can be extended in Section 5.6.

<footnote n="1">¹https://github.com/CompNet/SWGE</footnote>
## 5.1 Definitions and Notations

The presence of signs associated to edges allows defining the notion of path sign:

**Definition 5.1 (Sign of a path).** The **sign of a path** or cycle corresponds to the product of its constituting edge signs. Consequently, this sign is negative if the path or cycle contains an odd number of negative edges, and positive otherwise.

Edge signs can also be used to define additional properties, in particular the reachable set, which we use later:

**Definition 5.2 (Reachable set of a vertex).** The positive (resp. negative) **reachable set** of a vertex $u \in V$ is the subset of vertices that are connected to $u$ through positive (resp. negative) shortest paths.

Structural Balance (SB) is a fundamental property of signed graphs [162], [163], stating that the graph can be partitioned in 2 clusters such that all positive edges are internal, i.e. they connect vertices from the same cluster, whereas all negative edges are external, i.e. they lie in-between both clusters.

**Definition 5.3 (Structural balance (SB)).** A graph $G = (V, E, s)$ is said to be **structurally balanced** if it is possible to find a bisection $C = \{C_1, C_2\}$ of $V$ such that $E[C_1, C_2] = E^-$ and $E[C_1] \cup E[C_2] = E^+$, where $E[X]$ denotes the edges connecting 2 vertices from $X \in V$, and $E[X, Y]$ denotes the edges connecting 2 vertices from $X$ and $Y \in V$.

This definition is the strict version proposed by Cartwright et al. [164], and illustrated in Figure 5.1.a). Equivalently, all the cycles of a structurally balanced graph are positive.

In real-world networks, though, graphs are rarely perfectly balanced, and no bisection exists that respects the SB definition. In this case, one may want to measure the amount of imbalance of the graph, through the notion of *Frustration*. The positive edges located in-between the clusters and the negative edges located inside them are said to be *frustrated*, as they do not respect SB. The Frustration (aka *Line Index* or *Imbalance*) of this bisection is the number of such edges.

**Definition 5.4 (Frustration of a bisection).** For a graph $G = (V, G, s)$, let $C = \{C_1, C_2\}$ be an arbitrary bisection of $V$. The **frustration** of this bisection is the total number of external positive edges and internal negative edges: $F(G, C) = |E^+[C_1, C_2]| + |E^-[C_1]| + |E^-[C_2]|$.

The Frustration of a graph corresponds to the minimal Frustration over all possible bisections of the graph.

**Definition 5.5 (Frustration of a graph).** The **frustration** of a graph $G = (V, G, s)$ is the minimal frustration over all possible bisections: $F(G) = \min_{C \in \mathcal{C}} F(G, C)$, where $\mathcal{C}$ is the set of all possible bisections of $V$.
<figure><img src="image_10.png" /><figcaption>Figure 5.1: Examples of balanced graphs according to a) Structural Balance (SB); and b) Generalized Balance (GB) ($k = 3$).</figcaption></figure>

Put differently, the Frustration is the minimal number of edges whose sign must be switched to reach perfect structural balance. Computing the frustration requires solving a combinatorial optimization problem which was proposed by Doreian et al. [165], and later called the Correlation Clustering (CC) problem [166]. One of the datasets presented in Section 5.3 is directly related to this CC problem.

SB was later generalized to allow partitions constituted of more than 2 antagonistic clusters [167], i.e. clusters where all positive edges are internal, and all negative edges are external. A graph which can be split into $k$ antagonistic clusters is said to be $k$-balanced.

**Definition 5.6 (Generalized balance (GB))**. A graph $G = (V, E, s)$ is said to enforce the general balance property if it is possible to find a partition $C = \{C_1, ..., C_k\}$ of $V$ such that $\bigcup_{1 \le i < j \le k} E[C_i, C_j] = E^-$ and $\bigcup_{1 \le i \le k} E[C_i] = E^+$.

Equivalently, a graph respecting the generalized balance has no cycle with exactly one negative edge. Figure 5.1.b) illustrates the notion of GB. Note that the Frustration remains a valid imbalance measure for this generalization of the SB.

## 5.2 Graph Representation Learning

Graph representation learning methods have to learn representations of graphs that preserve at least some part of their topological properties [168]. 2 graphs with similar properties must sit close in the embedding space [169]. Graph embedding is a very popular research topic, and the literature provides numerous methods allowing to automatically train models into representing various types of graphs (directed, weighted, signed, multiplex, etc.), and various parts of graphs (vertices,
edges, subgraphs, whole graphs, etc.). Each category better fits the needs of different applications and problems. In this thesis, we are interested in abuse detection, which we formulated as a graph classification task. Therefore, this chapter mainly describes whole-graph representation methods. However, as shown in Chapter 4, it is alternatively possible to agglomerate vertex representations to create graph representations. For this reason, we also include vertex-level methods in our review. Furthermore, representation learning provides representations which can be used for various tasks. We explore this possibility with a benchmark constituted of 3 tasks, including abuse detection, later in this chapter. We first summarize the main approaches for representing the vertices of graphs (Section 5.2.1), then we review the methods that directly handle graphs as a whole (Section 5.2.2). Finally, edge signs are difficult to integrate in an embedding framework due to their nature. We dedicate the last section of this review to the main approaches designed to deal with signed graphs, which all handle only vertex representation, and not whole graphs (Section 5.2.3).

### 5.2.1 Vertex Embedding

Vertex embedding methods take a graph as an input and output a fixed-length vector representation for each of its vertices. It is the most common form of graph embedding in the literature. Following the taxonomy proposed in [170], we distinguish 3 categories of methods depending on the general approach used to perform the transformation: Matrix Factorization (Section 5.2.1.1), Random Walks (Section 5.2.1.2) and Graph Neural Networks (GNNs) (Section 5.2.1.3). Note that random walks also use neural networks but leverage a different strategy to sample the graph.

#### 5.2.1.1 Matrix Factorization

There are various ways to represent a graph in a matrix form, such as the adjacency, Laplacian or transition matrices. The pioneering studies on vertex embedding propose to map them into low-dimensional vectors by decomposing such matrices into products of smaller matrices of the desired dimension, a process called *Matrix Factorization* (MF). Depending on the matrix properties, there are multiple approaches to decompose it.

The most straightforward approach is to leverage existing dimensionality reduction techniques, originally designed for tabular data, and apply them to a graph matrix. Doing so with the **Lowly Linear Embedding** method proposed by Roweis et al. [171] amounts to considering that the representation of each vertex in the graph is a weighted linear combination of its neighbors'. The method first estimates weights that best reconstruct the original characteristics of a vertex from its neighbors, and then uses these weights to generate vector representations. This method has been used in the literature to perform face recognition [169]. Belkin et al. propose **Laplacian Eigenmaps** [156], a method aiming at keeping strongly connected vertices close in the representation space. Representations are obtained by computing the Eigenvectors of the graph Laplacian.
Typical applications for this method include vertex classification and link prediction [156], [170]. Both these approaches preserve the first order proximity, i.e. vertices which are directly connected have close representations. A major drawback of these 2 methods is that their time complexity is in $O(|E|d^2)$ with $d$ being the number dimensions in the learned representation. This makes them poorly scalable and impossible to use on very large real-world graphs.

**Graph Factorization** [157] proposed by Ahmed et al. is much more time efficient and can handle graphs with several hundred million vertices. It uses stochastic gradient descent to optimize the matrix factorization. To improve its scalability, this approach uses some approximation strategies, which can introduce noise in the generated representations. Furthermore, the authors focus on preserving only the first-order proximity. Hence, the global graph structure is not necessarily well-preserved by this method. Ahmed et al. use this method to partition graphs and to predict the volume of e-mail exchanges between pairs of users [157].

Ou et al. introduce a matrix factorization method called **High-Order Proximity preserved Embedding (HOPE)** [155]. The similarity matrix is obtained using centrality measures like Rooted PageRank, Katz measure and Adamic-Adar score. HOPE is specifically designed to preserve asymmetric transitivity in directed graphs. To this end, 2 vector representations are learned for each vertex to capture asymmetric edges, a *source* vector and a *target* vector. Applications of this method include link prediction, proximity approximation and vertex recommendation [172]. However, once again the time complexity of this factorization method is high and does not allow the processing of very large graphs.

Li et al. present **BoostNE** [173]. This multi-level graph embedding framework learns multiple graph representations at different granularity levels. Inspired from boosting, it is built on the assumption that multiple weak embeddings can lead to a stronger and more effective one. It applies an iterative process to a closed form vertex connectivity matrix. This process successively factorizes the residual obtained from the previous factorization, to generate increasingly finer representations. The sequence of representations produced is then assembled to create the final embedding. Li et al. apply their method to a multi-label vertex classification task.

Matrix factorization was the first strategy developed to learn representations of vertices. However, it has a major limitation. Their time complexity is very high and depends on the number of edges in the graph. Hence, it makes them unusable on large real-world graphs. To prevent this issue, authors proposed a more efficient strategy to model the structure of the graphs: random walks.

### 5.2.1.2 Random Walks

Random walks have first been adopted by graph embedding approaches trying to mimic word-embedding methods such as *word2vec* [174]. Since vertices in graphs have no natural ordering,
random-walks allow representing the graph structure under a sequential form, analogous to sentences in a text. They are used to sample the graph, and can be seen as a proxy allowing to obtain a partial representation of its structure. They also have the advantage of being able to deal with graphs too large to be explored in their entirety. Given a starting vertex, random-walk-based methods generate vertex sequences by selecting a neighbor and repeating this procedure until the sequence reaches a certain length. Different strategies can generate random walks that sample the graph in completely distinct ways, allowing to capture various properties.

Perozzi et al. propose **DeepWalk** [175]. It is among the first vertex embedding methods based on random-walks. First, DeepWalk samples vertex sequences using uniform random walks and then applies the standard *SkipGram* model [174] to generate the representations. This model takes a vertex as input and aims at predicting its context, i.e. the vertices in its neighborhood. With this method, vertices with similar contexts share similar representations. Typical applications of this approach include vertex classification [176], [177] and link prediction [155]. However, a limitation is that 2 vertices can be structurally similar (i.e. they play the same role in the graph) but be distant in the graph, hence, not share any common neighbors. Their representations might thus be completely different.

The **Node2vec** [85] method proposed by Grover *et al.* was developed following the idea of *DeepWalk*. The main difference is that *Node2vec* uses *biased random-walks* to provide a more flexible notion of a vertex's neighborhood and better integrate the notion of structural equivalence. More specifically, it uses 2 parameters to bias the transition probabilities between vertices. The *return parameter* controls the likelihood of immediately revisiting a vertex in the random walk. The *in-out parameter* can restrict the walks to a local neighborhood or conversely, increase the probability of visiting vertices which are further away from the current one. Node2vec has been used to predict links in a biomedical context [172], and to classify vertices [176]. However, the model randomly initializes the embeddings, which can result in being stuck in a local optima during the computation of embeddings. Chen *et al.* propose an improved weight initialization strategy to avoid such problems in their **Hierarchical Representation Learning** method [178]. In **Walklets** [179], Perozzi *et al.* introduce a new random walk strategy. Traditional random-walk methods select the next vertex from the current vertex's neighbors. Instead, **Walklets** proposes to skip over vertices to obtain sequences which are not constituted of direct neighbors. This strategy allows modeling and preserving higher order relationships between vertices and can be used in multi-label classification problems [179].

5.2.1.3 Graph Neural Networks

Modern neural approaches have been successfully adapted to many fields including graph rep-
resentation learning. The proposed methods were first direct adaptation of standard neural network
approaches to graphs, before developing a new family of neural networks that directly operates on
graph data: Graph Neural Networks (GNNs).

Wang et al. propose the **Structural Deep Network Embedding** (SDNE) framework [177]. This method learns representations based on first and second order proximities in the graph. These 2 properties are jointly optimized using a deep autoencoder and a variation of Laplacian Eigenmaps, applying a penalty when similar vertices are mapped far from each other in the embedding space. This allows a good representation of both the local and global structure of the graph. This method has been used on vertex classification and link prediction tasks [170], [177].

**Generative Adversarial Networks (GANs)** have also been adapted to vertex embedding.
Wang et al. [180] propose **GraphGAN**, which works through 2 models. First, a generator $G(v|v_c)$ tries to approximate the true connectivity between vertices $v$ and $v_c$ and selects the most likely connected vertices to $v_c$. Second, a discriminator $D(v, v_c)$ computes the probability of an edge to exist between $v$ and $v_c$. The generator tries to fit the distribution of vertices as much as possible to generate the most indistinguishable fake pairs of connected vertices. The discriminator tries to distinguish between ground truth and the fake pairs created by the generator. This method is however only able to capture the local structure. Wang et al. apply GraphGAN to vertex classification, link prediction and movie recommendation tasks.

**Graph Convolutional Networks (GCNs)** [87] are a family of neural networks adapting traditional Convolutional Neural Networks (CNNs) so that they can process graph data instead of standard tabular data [181]. Shallow embedding methods such as Graph2vec may miss complex patterns in the graphs, and deep learning methods like CNNs are likely to solve this limitation [182]. GCNs generalize the convolution operation by considering graph neighborhood instead of linear or grid neighborhoods, as in standard CNN used in NLP and image processing. Kipf et al. leverage their method to perform document and entity classification.

**GraphSAGE** [89] aggregates feature information from the local neighborhood of a vertex. At each iteration, it samples a neighborhood of fixed size for each vertex and aggregate them through an aggregator function. Thus, vertices aggregate information from their local neighbors at each iteration and propagate it through the following layers of the network. By this way, vertex representations incrementally gain more and more information from further neighbors as the process iterates.

### 5.2.2 Whole-Graph Embedding

As mentioned before, vertex embedding methods are the most widespread in the literature. But some tasks require information at a higher granularity, in which case one would turn to whole-graph embedding. These methods allow representing a whole graph as a single vector of fixed length. They take a collection of graphs, and output a representation for each of them. Some strategies
used for vertex embedding can be transposed to whole-graph embedding matrix factorization and
random-walks.

Lara et al. [183] propose the **Simple and Fast** algorithm based on the spectral factorization of the graph Laplacian. It computes the *k* smallest positive Eigenvalues of normalized Laplacian of the input graph in ascending order, to form the representation of the whole graph. Lara et al. use their approach to predict the properties of chemical compounds [183].

Mousavi et al. [184] introduce a whole-graph embedding hierarchical framework called **Pyramidal Graph Embedding**, based on some ideas originating from image processing algorithms. Important global information from images can be extracted by recursively analyzing local information. In the context of graphs, this means that the overall graph structure can be modeled by analyzing substructures at different scales. To this end, a graph pyramid is formed with subgraphs of different scales. Every graph is embedded into vector representations, which are all concatenated to form the global graph embedding. The representations are obtained by factorizing an affinity matrix. This pyramidal approach is especially designed for large graphs, since they potentially contain more different scales. Mousavi et al. used it for graph classification tasks.

Verma et al. propose a **Family of Graph Spectral Distances** [185] to represent a whole-graph. This method is built on the assumption that the graph atomic structure is encoded in the multiset of all vertex pairwise distances. It computes the Moore-Penrose Pseudoinverse spectrum of the graph Laplacian. A vector representation of the whole graph is constructed from the histogram of this spectrum. Typical tasks include graph classification in various fields such as bioinformatics and social networks [185], [186].

Tsitsulin et al. introduce **NetLSD** [186], a permutation- and size-invariant, scale-adaptive embedding method. Like the aforementioned vertex embedding method Laplacian Eigenmaps [156], NetLSD operates on the Laplacian matrix of the graph. It relies on a physical analogy consisting in simulating a heat diffusion process on the graph to preserve its structure. The method processes the amount of heat transferred between vertices at different times scales. These heat traces at different time scales are then used to compute the heat trace signature of the graph, i.e. the vector representation of the graph. Tsitsulin et al. use NetLSD for graph classification and for community detection.

Another popular approach involves leveraging models from the field of NLP, such as in **Graph2vec** [161] and **Graph Classification via Graph Structure Learning (GC-GSL)** [187]. Both are based on an analogy with the Doc2vec approach defined for text [47]. Graph2vec, one of the earliest methods for whole-graph representation learning, is an unsupervised and task-agnostic approach designed to learn whole-graph representations. Its principle is to consider graphs (documents, in the analogy) as collections of subgraphs (words that compose the document). The procedure enumerates rooted subgraphs around all vertices of the considered graphs. Each one represents the neighbor-
hood of a vertex (the so-called root) at a certain order.

Another family of approaches relies on graph autoencoders to learn the representation in an unsupervised way, e.g. **Permutation-Invariant Graph-level Autoencoder (PIGAE)** [188], or the **Denoising Autoencoder (DAE-based)** method from [189]. Such neural networks are constituted of 2 parts. First, the encoder receives a raw representation of the graph, which is compressed in order to remove redundant information and superfluous variability, and get a fixed-sized and compact representation. Second, the decoder is in charge of reconstructing the original input based on the compressed representation. The autoencoder is trained by minimizing the reconstruction error.

**Deep Divergence Graph Kernels (DDGK)** [190] is an unsupervised method that adopts a different approach based on attention. It relies on an encoder to learn a first compact representation of the graphs. Pairs of graphs are then fed to a cross-graph attention network, using this representation. This attention network is trained into reconstructing one representation based on the other. Based on the latter, DDGK is able to compute a divergence measure between the input graphs, which is then used to build the embedding space.

The literature contains another family of approaches, which adapts CNNs from the field of image processing to handle graphs, resulting in supervised methods able to learn whole-graph representations for specific classification tasks, e.g. **Patchy-San Convolutional Network (PSCN)** [191] and **NgramCNN** [192]. PSCN adapts the notion of convolution to the context of graphs, which allows applying the same principle as for image processing. The graph is represented by a collection of subgraphs, on which PSCN performs convolutions. These are then aggregated to create higher-level representations of the graph. NgramCNN operates in a similar fashion, but it first decomposes the graph into a sequence of n-gram blocks connected through overlapping regions, before applying convolutions on them.

Finally, another strategy is to modify vertex-oriented Graph Neural Networks (GNNs) in order to produce whole-graph representations, e.g. **Message Passing Neural Network (MPNN)** [193] or **Virtual Column Network (VCN)** [194]. This is conducted by the addition of a so-called master node, which is connected to all the other vertices. At the end of the training, the vector associated to this master node can be used as a representation of the graph.

### 5.2.3 Signed Graph Embedding

Signed graphs are commonly used in social sciences to represent friendly relations and enmity between individuals (modeled by vertices). It is much more difficult to handle signs than other attributes such as weights and directions in embedding methods, because of the complex relationships induced by the positive and negative edges. Although less common than for unsigned graphs, a number of graph embedding methods have been developed for signed graphs. However, they are all designed to operate at vertex-level and no signed whole-graph embedding method ex-