Exploring graph representation strategies for text classification

ABSTRACT

Since 2005, the deep learning community has had access to input graphs to their models. So, the natural language processing (NLP) community started using this technique to process text. However, a challenge that the graph neural networks (GNN) may encounter is the sensibility to representation format. Since different graphs can represent the same text, the model’s performance may change depending on the representation used. Even though many practitioners have this intuition, only some works touch on this aspect of GNN. Therefore, we explore twelve different text representation strategies that build graphs from text and apply them to the same GNN to investigate how different graphs may affect the results. We divide these strategies into four groups: reading order, dependency-based, binary tree, and graph of words. From these groups, we created the binary tree group for this paper. Nevertheless, in our tests, we observed that the dependency-based representations tend to achieve better performance: The dependency-based methods allow us to stay competitive in five relevant datasets and beat the state-of-the-art in another dataset. These results suggest that performing representation tuning can be a valuable technique to improve a deep learning model.

KEYWORDS:

• Graph neural networks
• text classification
• natural language processing
• information representation

1. Introduction

The introduction of graph neural networks (GNN) in 2005 (Gori et al., 2005) allowed the deep learning community to expand by allowing deep learning in problems that could only be represented as graphs. The natural language processing (NLP) community saw this new technique as an opportunity to represent text using graphs in 2013 (Rousseau & Vazirgiannis, 2013). While the community experimented with this new approach, GNNs replaced more state-of-art results. Even though the GNNs are promising, the same deep learning model can process different types of graph representations and data domains because a graph is an abstract concept that allows this diversity. This characteristic of graphs imposes a limitation that may impact the discoverability of promising deep learning models because the chosen representation may need to be revised to the proposed task. However, the deep learning community has no culture of representation tuning when practitioners create a new deep learning model.

Because we observed that few works deal with the impact of text representation on GNNs, we experiment with it. Thus, this work may sensitise practitioners to think about the representation used with a deep learning model. In this regard, we present experiments that show the importance of thinking on the input of a deep learning model. Our experiments reveal noticeable performance differences, only changing the graph input to a deep learning model. In a dataset, we even beat the state-of-the-art without losing competitiveness in other datasets. Therefore, using representation tuning, a deep learning development team may improve the performance of a GNN model and the efficiency of its team while creating a novel GNN model. The improvement in team efficiency comes because we may have a single model that may be trained multiple times with different graph representations. Since the GNNs tend to require fewer computational resources than a language model for NLP tasks, we may train identical GNNs multiple times, even at the same time, to choose the best result. As a result, this team should be able to use the best version of its model and representation sooner, possibly reducing some costs associated with building a deep learning model.

Since we intend to investigate representation tuning for a GNN model from an NLP perspective, we chose a trendy natural language processing task: text classification. We can generalise this task to a graph classification problem and use a verified model that classifies graphs. Because we transformed the problem into a graph classification problem, the natural language used to write the texts should not matter for the classifier. Thus, we should not need to build new deep learning models for each language. We only need to train them again with graphs built from the new language. This paper investigated this property by experimenting with three natural languages: English, Portuguese, and German.

Therefore, we present three contributions: 1) We present that the GNN development can benefit from a representation tuning step; 2) We present some novel representation based on binary trees; 3) As a result of our study, we achieve the state-of-the-art in a competition dataset only by changing the representation used to represent the text.

This text starts presenting the literature about text representation, the theme of this work, regardless of whether it is a graph representation strategy. Because of that, we identified three kinds of main approaches that represent text, and we present them in Section 2. Regarding the representation strategies studied in this paper, there are three sources: the literature, intuitive representation strategies, and novel representation strategies we created. In total, we tested twelve representation strategies, which can be divided into four categories, as we will present in Section 3.

We present two types of experiments in Section 4: The first investigates the accuracy of each representation strategy in popular and novel datasets that cover three distinct natural languages; The second type of experiment simulates two competitions in German regarding social media text classification. Section 5 finishes the paper with a discussion of the work presented.

2. Related works

In the search for solutions for better text representation approaches, researchers and practitioners explored a wide variety of techniques. This Section presents three types of methodologies to represent text that are prevalent in state-of-the-art: the traditional feature engineering method, presented in Section 2.1, deep learning-based approaches, presented in Section 2.2, and graph-based approaches, presented in Section 2.3. Because our approach is graph-based, we explored more works using this representation type.

2.1. Traditional feature engineering method

One of the first methods of representing text is the Bag of Words (BoW) (Harris, 1954; Joachims, 1998). The BoW consists of a word list that contains how many occurrences of each word a document contains. Using the BoW technique, a matrix can be constructed where the rows represent documents, and the columns represent words. This way, in each cell of this matrix, we can place the word count from each document. Machine learning techniques, such as SVM (Joachims, 1998), receive text represented as a BoW.

Another usual way to represent text is by using n-grams. An n-gram uses a sliding window with size n. All the n words that appear in the window are the n-gram. Take, for example, the sentence “I parked my car in your garage”. The 2-gram (also known as bigram) representation is [I parked]; [parked my]; [my car]; [car in]; [in your]; [your garage]. One of the early usages of this technique applied to natural language processing appeared in Broder et al. (1997) ‘s work. They used the n-gram to analyse the text from the web and search for plagiarism. In another work, the n-grams were used to classify Arabic text (Ayed et al., 2017).

Regarding word representation in a collection of documents, we can use a method called Term Frequency-Inverse Document Frequency (TF-IDF). This model generates a number that indicates the importance of a document’s word concerning the collection of documents. The TF-IDF is given by Equation 1(1) $\text{TF - ID}{\text{F}}_{\text{i}}\text{ = t}{\text{f}}_{\text{i}}\times \mathrm{l}\mathrm{o}\mathrm{g}\left(\frac{\text{N}}{\text{d}{\text{f}}_{\text{i}}}\right)$(1) (Salton, 1989). (1) $\text{TF - ID}{\text{F}}_{\text{i}}\text{ = t}{\text{f}}_{\text{i}}\times \mathrm{l}\mathrm{o}\mathrm{g}\left(\frac{\text{N}}{\text{d}{\text{f}}_{\text{i}}}\right)$(1) In Equation 1(1) $\text{TF - ID}{\text{F}}_{\text{i}}\text{ = t}{\text{f}}_{\text{i}}\times \mathrm{l}\mathrm{o}\mathrm{g}\left(\frac{\text{N}}{\text{d}{\text{f}}_{\text{i}}}\right)$(1) , the tf_i is the frequency of the ith term, N is the total number of documents, and df_i is the number of documents that contain the ith term.

2.2. Deep learning-based method

Mikolov et al. (2013) explored another approach to represent text. They created one of the first word vectors, the word2vec. This technique uses machine learning to build a vector representation that considers each word’s syntactical and semantical information. This idea spread and inspired the creation of GloVe (Pennington et al., 2014), fastText (Joulin et al., 2016), A La Carte Embedding (Khodak et al., 2018), and another word embedding technique based on n-grams (Gupta et al., 2019).

Another initiative to represent text is by creating language models. These models build probability distributions over a sequence of words and their contexts. Three popular language models are ELMo (Peters et al., 2018), BERT (Devlin et al., 2019) and GPT-3 (Brown et al., 2020). These language models can perform multiple NLP tasks, such as text question answering, abstract summarising, and sentiment classification. They require a first training that needs a state-of-the-art machine to perform. When someone needs to use it to perform some task, the user has to perform a fine-tuning, which adjusts the model’s parameters to the specific task.

ELMo, short for Embedding from Language Models, is one of the pioneering language models (Peters et al., 2018) that offers deep contextualised word representations. Its primary objectives are to mitigate two core challenges: 1) to address the intricate characteristics of word usage, including syntax and semantics; 2) to capture the varying word meanings across diverse linguistic contexts, commonly referred to as polysemy. To deal with these challenges, the authors proposed a method for generating highly contextualised word representations employing bi-directional language models, known as biLMs. A biLM comprises both forward and backward language models constructed using BiLSTM. By joining the representations from each layer of the biLM, ELMo enables the delivery of specific word embeddings for the same word within disparate sentences.

In contrast, BERT (Devlin et al., 2019) builds a language model based on three distinct types of embeddings, each corresponding to a dedicated lookup table: token embeddings, segment embeddings, and position embedding. The token embeddings contain lookup words, ensuring that even rare words may be embedded (Shukri, 2019). Segment embeddings accommodate multiple inputs by assigning a numerical tag (0, 1, 2, … , n) to each input. Position embeddings encode the position of each token. Thus, BERT calculates the element-wise sum of the three types of embeddings to generate the final token embedding. Then, BERT undergoes pre-training for two primary tasks: the Masked Language Model (MLM) and Next Sentence Prediction (NSP).

BERT’s groundbreaking achievements and its open-source availability by Google have motivated numerous practitioners to employ and train the model with texts in languages other than English. For instance, Souza et al. (2020) applied BERT to Portuguese, Chan et al. (2020) to German, and Cañete et al. (2020) to Spanish.

Furthermore, BERT’s development has inspired other researchers to construct their language models based on BERT’s foundation. Examples include roBERTa (Liu et al., 2019), ERNIE (Sun et al., 2019), SpanBERT (Joshi et al., 2020), and ALBERT (Lan et al., 2019).

Researchers also investigated more techniques to improve BERT’s performance. According to Xu et al. (2023), BERT representation power can be further improved by applying a technique called “Contrastive Learning”. In contrastive learning, a model learns the similarities and differences between examples in a self-supervised learning environment. This technique helps BERT to reduce a problem called “anisotropy”, where the embeddings are not well distributed into the vector space, which can generate bias in the semantic similarity. Xu et al. (2023)’s work is one of the most recent works that survey the use of contrastive learning with BERT.

Another popular language model, GPT-3 Brown et al. (2020), is an autoregressive language model with 175 billion parameters. It uses transformers to simulate how humans perform tasks by receiving a few examples or simple instructions.

2.3. Graph-based method

The evolution of computer hardware has created the possibility to apply the successful methods of deep neural networks to process data in the non-Euclidean domain, such as graphs (Cao et al., 2020). These new models allowed the study of distinct ways of representing text in the non-Euclidean domain.

Rousseau and Vazirgiannis (2013) created one of the first graph representation approaches for text classification. Their technique transforms each text document into a graph, the Graph of Words (GoW). The resulting graph represents words as their vertices. A sliding window captures the co-occurrence of words and builds the edges of the graph between these co-occurring words. In the presentation of the method, Rousseau and Vazirgiannis (2013) defined weights for each edge using a function called Term Weights - Inverse Document Frequency. However, according to Rousseau and Vazirgiannis (2013), the GoW also works without the edges’ weight.

Malliaros and Skianis (2015) used the graph structure created by Rousseau and Vazirgiannis (2013) and changed the function that calculates the edges’ weight.

Yao et al. (2019) create their graph by considering all documents and words of the corpus. Then an edge is created between the vertex representing the document and a word from this document. Next, they add an edge for all words that co-occur. They also add a self-loop edge, a edge that links a vertex to itself, to use their representation with the GCN model (Kipf & Welling, 2017). Finally, they add the edge weight based on the type of vertices it connects.

L. Huang et al. (2019) represents text using a method similar to a Graph of Words (Rousseau & Vazirgiannis, 2013). They consider each word a node and link each word to adjacent words. The edge set E is defined as follows: E = e_ij | i ∈ [1, l]; j ∈ [i−p, i + p ]. In this definition, l is the number of words in the text, and p denotes the number of adjacent words connected to each word in the graph. Therefore, they can choose how many words connects to each word by defining different values of p.

Zhang et al. (2020) also uses the Graph of Words proposed by Rousseau and Vazirgiannis (2013). The resulting graphs are undirected graphs built of a sliding window with size 3.

Ding et al. (2020) created a framework that supports hypergraphs. A hypergraph is a graph that, instead of edges, has hyperedges. These hyperedges are edges that connect to more than two other vertices. Ding et al.’s framework supports multiple hyperedges, where each hyperedge of a node has a different semantic. Their initial study considered Sequential hyperedges, based on sliding windows of size 3, and Semantic hyperedges, which uses the Latent Dirichlet Allocation (LDA), a generative probabilistic model for collections of discrete data (Blei et al., 2003), to construct them.

Yang and Cui (2021) use a multi-representation approach. They use word embeddings in a GoW representation. They also extract features by using BERT. The combination of BERT and the GoW is aggregated in a co-attention layer and classified by a fully connected network. Lin et al. (2021), inspired from the TextGCN proposed by Yao et al. (2019), developed the BertGCN. This model creates representations of the documents using a BERT-style model (Devlin et al., 2019). Then they create a graph following the Yao et al. (2019) methodology to serve as input to a GCN (Kipf & Welling, 2017) model.

Mei et al. (2021) goal is to create a graph representation for each document, where each node n is a word of the document. Thus, in the pre-processing of each document, the TF-IDF of each word is calculated. This value is used as the weight w of the word. Then, the words are sorted descending by their weight. Now that an ordered list of words is available, one of the two following methods can be applied in this step.

In Method A, the node with the highest weight receives the degree n − 1, and the node with the lowest weight receives the degree 1. From this two nodes a line equation (y = kx + b) is created by considering the following points: (w_max, n − 1) and (w_min, 1), where w_max is the highest weight and w_min is the lowest weight. All the other degrees are calculated by using the line equation generated.

In Method B, the degree is calculated by Equation 2(2) $deg\left(n_i\right)=\lfloor \frac{w_{n_i}\times (n-1)}{w_{sum}}\rfloor +1$(2) . In this Equation, w_sum is the sum of all weights, and w_ni is the weight of node n_i. After calculating all degrees, the nodes are sorted descending by their degree. (2) $deg\left(n_i\right)=\lfloor \frac{w_{n_i}\times (n-1)}{w_{sum}}\rfloor +1$(2) This ordered list of nodes is used to construct the graph using an idea similar to the Havel- Hakimi algorithm (Hakimi, 1962; Havel, 1955). We connect the first node (the one with the highest degree) to all nodes. The nodes that were connected have their degree reduced by one. If one node gets its degree reduced to zero, it is removed from the list. The process continues until all nodes are removed from the set.

Huang et al. (2022) constructs their graph by tokenising the words into sub-words. Then, they connect the sub-words that occur in a fixed sliding window. Then the edge’s weight is calculated based on the point-wise mutual information (PMI). After building the graph, a context enrichment step occurs. This step is responsible for creating the node features for each sub-word.

Wang et al. (2023) build their graphs by considering each word a vertex, and the edges come from four distinct sources: The first is the co-occurrence of words within a fixed-size sliding window of length 3. The second is syntactic dependency. The third is self-loops. The last type is the fusion of edges that start and finish in the same vertices. Thus the resulting graph is not a multigraph.

Wang et al. (2023) create a novel graph convolution model called LDGCN that uses the same graph representation used in TextGCN (Yao et al., 2019). Wang et al. (2023) also uses the same GCN model with a difference, a discriminative regular term module. This module aims to group the texts that belong to the same scene class, which may reduce the cross-entropy loss.

Bugueño and de Melo (2023) investigate the intuitive graphs based on sliding windows, similar to the Reading order and Graph of words strategies we present in the following Section. In their work, they define the following types of graphs. The simplest method considers each word a node and builds an edge between two nodes if two words are consecutive terms in the text. The extended version of the former method is the same, but instead of only building edges between consecutive terms, it also builds edges in a window size of three terms. Two sequence-based methods build directed arcs between the nodes. In a simplified approach, there are no weights; in the sequence-weighted approach, the weight is the number of times the arc appears. The last graph-based representation follows the same approach Huang et al. (2019) did.

Then Bugueño and de Melo (2023) compare these five graph-based representations against a pre-trained version of BERT and a fine-tuned version of BERT in some tasks. The authors conclude that graph-based approaches are promising but also sensitive to the lexical features of the documents. Their advantages against BERT are their simplicity, both for creation and processing, and they tend to converge earlier in datasets containing shorter documents.

Wang et al. (2023) used a psychological study to build embeddings that try to mitigate the polysemy of words. Later, they use these embeddings to represent the words that compose a graph. These graphs use the same shape Zhang et al. (2020) used. Then, the graphs are passed to a Dual BiGRU-CNN model to classify the sentiment of the text.

3. Explored representations

In this part, we describe the representations strategies studied. We explored four groups of representation strategies: Reading order, Binary tree, Dependency tree, and Graph of words. As a subsequent Subsection will present, each group strategy may have more than one variation.

All strategies build directed graphs G = (V, E), where V is the set of vertices, and E is the set of arcs. Each vertex is the word embedding of a token of the document. A token is a word or a non-word sequence (i.e. punctuation mark, numbers). The word embedding used is the pre-trained fastText (Joulin et al., 2016) for the language processed (English, Portuguese or German). We choose fastText because it has many languages pre-trained, and it can build embeddings for rare words, improving the final result and enabling other practitioners to reproduce this research with other natural languages. The resulting graph G is the representation of one document.

We do not perform any pre-processing besides choosing the correct language for the word embeddings and tagging (POS tagging and dependency tagging). Therefore, if the document has punctuation marks or emojis, they will be represented in the final graph. We summarise the graph creation process overview in Figure 1.

Figure 1. Overview of the text-to-graph conversion. The white boxes are the steps used to transform the text dataset into a graph dataset. The black boxes are the representation strategies options used. There are 12 strategies: 2 for Reading order, 3 for Binary tree, 6 for Dependency tree, and 1 for Graph of words.

A Python library called spaCy (Honnibal et al., 2020) does all tokenization and dependency parsing when needed. The source code we developed to build all representations is available at https://github.com/HenriqueVarellaEhrenfried/Text_Representation.

3.1. Reading order

The reading order strategy is based on how humans read text. Therefore, an arc starts in the first word and ends in the second word. Another arc starts in the second word, ends in the third word, and so forth until the last arc ends in the last word. This description defines the reading order only (ROO). The difference between the ROO approach and a GoW with sliding window 1 is that the ROO considers each word independently. Thus, if the same word appears in two or more parts of the text, they are represented multiple times, while the GoW only represents it once.

There is another strategy based on the reading order. It is called reading order circular (ROC). Its difference with the ROO is that the last word connects to the first word with an arc that starts on the last word and ends on the first word. Figure 2 shows these two strategies. We present an example of creating the ROO and ROC representations in Algorithm 1. In this Algorithm, we omit the step that adds the word embeddings to improve readability.

Figure 2. Graphical representation of the Reading order text strategies. The solid arcs appear in both representation strategies, ROC and ROO. The dashed arc only appears on the ROC representation strategy.

3.2. Binary trees

The binary tree idea was motivated by the observation that a word in an utterance has two functions: A morphological (POS) function, where the word by itself has its semantic, and a syntactical (DEP) function, where a word influences other words in the utterance to build the meaning intended by the utterance’s creator. Thus, if we combine this information into a single data, we could use it to represent an utterance better.

Then, we developed a way to unite this information. We wanted to represent an entire sentence using this novel technique, so we immediately thought of binary trees because they would group words with similar properties in different branches. Once the original binary tree provided interesting results, from a representation perspective, we experimented with variations of it, the Red-Black tree and the AVL tree.

Thus, the Binary tree group contains three representation strategies. To the best of our knowledge, all of them are novel representation strategies that we created, which we present in the following paragraphs. The idea is to use well-known data structures (binary tree, AVL tree, and Red-Black tree) to represent text.

The base for this representation strategy is three different binary trees structures: the Binary tree (Windley, 1960), the AVL tree (Adel'son-Velskii & Landis, 1962), and the Red-Black tree (Bayer, 1972). The Binary tree is a method developed to minimise the storage needed by rearranging data. The AVL tree and the Red-Black tree are self-balancing binary trees. Natural numbers are the input of the three trees. Therefore, we had to create a procedure to transform the text from the documents into natural numbers. Hence, we created a function that converts a word into two natural numbers and maps them to a single natural number.

These two numbers are the position, in two different lists, of the part-of-speech (POS) and the dependency (DEP) information of the word. These lists come from a Python library called spaCy (Honnibal et al., 2020) in alphabetical order. Since each language has its particularities, these lists are language dependent.

The formal concepts of part-of-speech (POS) and dependency (DEP) are the following. A part-of-speech is a category assigned to a word under its syntactic functions. In English, some of the main parts-of-speech are nouns, verbs, pronouns, and adjectives. Regarding dependency, one of the first linguists to formalise the concept of dependency was Tesnière (1959). He believed a sentence is an organised set of words containing connections the human mind perceives. The connection between these words is called “dependency”.

Thus, our procedure begins with creating these lists by acquiring the information from the spaCy library and storing them in lists. Let us call the part-of-speech list $\mathcal{P}$ and the dependency list $\mathcal{D}$.

Then, we build the domain set of our function by creating a Cartesian plane that begins with two points: O = (0, 0) and P = (| $\mathcal{D}$ | + 1, | $\mathcal{P}$ | + 1). We next consider every possible natural number in the interval [ 0, | $\mathcal{D}$ | ] for the X-axis, and [ 0, | $\mathcal{P}$ | ] for the Y-axis. For each combination of these intervals, we calculate the Euclidean distance from this generated point Q to point O; let us call it the distance x. Afterwards, we calculate the Euclidean distance from point Q to point P; let us call it the distance y. The resulting distance x and y are subtracted and inserted into the $\mathcal{R}$ list.

We order the list $\mathcal{R}$ when we finish building it. Now, for each word of a document, we get the part-of-speech and the dependency tag of the word, search the lists $\mathcal{P}$, $\mathcal{D}$ to gather their indexes, calculate the distances x and y, and calculate the number k as being k = x − y. Finally, we look for k in the $\mathcal{R}$ list and return the found index. We insert this index into one of the binary trees. The new node receives the embedding of the word provided by fastText (Joulin et al., 2016). When we insert all words from the document, the tree is ready.

Observe that the insertion follows the order in which the words appear in the document. Figure 3 illustrates a sentence represented with each binary tree. In this text, we refer to the binary tree as BT, the AVL tree as AT, and Red-Black Tree as RBT. To illustrate the procedure that creates the binary trees, we present Algorithm 2. In this Algorithm, we omit the step that adds the word embeddings to improve readability.

Figure 3. Resulting trees after all insertions. The numbering inside the vertices corresponds to the order in which the word appears in the text. This number is also presented in the first line of numbers at the image’s bottom. The numbers outside the vertices are the keys returned by the function. They are also presented in the last line of numbers at the image’s bottom.

Intuitively, these trees separate the words depending on their POS and DEP values. Since we use the $\mathcal{D}$ and $\mathcal{P}$ lists we got from spaCy in alphabetical order, we usually start inserting a word around the middle of the domain interval. Thus, the following words are inserted in a binary tree that reasonably splits the word classes, as Figure 3 shows. Notice that although we build all possible combinations of POS and dependency, some may never happen (i.e. PUNCT with VB will never happen since a verb is never a punctuation mark).

3.3. Dependency trees

The third method also uses the library spaCy (Honnibal et al., 2020). However, this time we construct the dependency tree using the dependency information provided by spaCy. We defined six strategies to build the dependency tree: 1) Only; that is, only the dependency tree. We call it DTOY; 2) Order; we add the reading order to the DTOY. We call it DTOR; 3) Order Multigraph; we build the same tree from DTOR, but instead of omitting repeating arcs, we represent them again. We call it DTORM; 4) Only Self is the same tree from DTOY, but we add a self-loop arc for each vertex. We call it DTOYS; 5) Order Self is the same tree from DTOR, but we add a self-loop arc for each vertex. We call it DTORS; 6) Order Self Multigraph is the same tree from DTORM, but we add a self-loop arc for each vertex. We call it DTORMS. We illustrate these variations in Figure 4. Algorithm 3 presents the creation procedure. In this Algorithm, we omit the step that adds the word embeddings to improve readability.

Figure 4. Graph representation using the Dependency tree approach. The solid lines define the Dependency tree. Dotted lines (self-loops) represent the Self Component. Long dashed lines represent the Multigraph component. Dashed lines represent the Order component. The components may be added to the dependency tree, creating a graph that contains all solid arcs and the arcs of the component chosen.

3.4. Graph of words

The fourth method used is the Graph of words, as idealised by Rousseau and Vazirgiannis (2013). In this representation strategy, the idea is to link all words that appear in a predefined window size. So if the window size is four, the first word of the sentence link itself to the following four words, then the window shifts for the next word, and the second word links itself to the following four words. This process continues until the sliding window exceeds the number of words left. We reduce the window size in this case, and the process continues. If the window size becomes zero, the graph is ready.

If, during the process, two words have the exact spelling, their representation is a single node. However, the words become distinct nodes if there is at least one different character (i.e. sand, Sand, SAnd, SAND).

To build our graphs using this representation strategy, we followed the procedure proposed by Rousseau and Vazirgiannis (2013), including the recommended parameters: a sliding window of size 4 builds unweighted directed graphs. We refer to this representation strategy as GOW. Figure 5 shows an example of a sentence represented with GOW. We illustrate the process of creating a graph-of-word in Algorithm 4. In this Algorithm, we omit the step that adds the word embeddings to improve readability.

Figure 5. Graph representation using the Graph of Words with sliding window of maximum size 4.

From what we presented, we show in Table 1, the statistics of the generated graph for each representation strategy. Observe, as we previously presented, that the number of nodes is the number of tokens in a document. A token in this context can be a word, a number, a punctuation mark, or even an emoji. Table 1 presents the number of arcs, in the worst case, as a function of the number of nodes. Only the GOW representation depends on an additional parameter, the sliding window, denoted as s. Note that the sliding window can not exceed the number of nodes, thus 0 ≤ s ≤ n − 1.

Table 1. Statistics of the graphs created in each representation strategy. In this Table, n denotes the number of tokens, and s is the sliding window size.

Strategy	# Nodes	# Arcs
ROO	n	n − 1
ROC	n	n
BT	n	n − 1
AT	n	n − 1
RBT	n	n − 1
DTOY	n	n
DTOR	n	2n
DTORM	n	2n
DTOYS	n	2n
DTORS	n	3n
DTORMS	n	3n
GOW	n	(n * s) − (s^2 + s)/2

3.5. Deep learning model

This work used the UGformerV1 (Nguyen et al., 2022), an open-source model that uses Transformers to classify graphs. Its use was motivated because the UGformer is a generic graph classification model.

We chose to use the UGformerV1 instead of the UGformerV2 because the authors Nguyen et al. (2022) stated that the first variant should be used for larger graphs, while the second variant should be used for small and medium graphs. Since they do not provide metrics to qualify a graph as small, medium or large, and we do not know the graph size that will be processed, we always use the variant that can handle larger graphs. We also performed a non-rigorous test regarding both variants. The first variant could achieve better accuracy scores under similar parameters, which made us suspect that the graphs we process are large.

UGformerV1’s implementation is available at the authors’ Github.¹ Since this work aims to study text representations and their efficiency, we will briefly present the UGformer in the following paragraphs. If more details about this model are needed, please refer to (Nguyen et al., 2022).

UGformer’s objective is to learn a plausible embedding o_Gm for each graph G_m to predict its label y_m. Therefore, it is given a set of M graphs $\{{\mathrm{G}}_{\mathrm{m}}{\}}_{\mathrm{m}=1}^{\mathrm{M}}$ and their corresponding class labels $\{{\mathrm{y}}_{\mathrm{m}}{\}}_{\mathrm{m}=1}^{\mathrm{M}}$

Each graph G is defined as G = (V, E, X), where V is a set of vertices, E is a set of edges, and X ∈ $\mathbb{R}$ ^{||V|| ×d} represents feature vectors of vertices, which are the fastText (Joulin et al., 2016) embeddings in this work. These graphs are fed into a Transformer network to learn a vertex embedding o_v for each vertex v ∈ V. Later, all vertex embeddings are summed to obtain the o_G.

To learn the vertex embeddings o_v, a set of neighbours N_v of each vertex v ∈ V is sampled and inputted with the origin vertex to the UGformer learning.

The vertices N_v ∪ {v} are transformed into a sequence of feature vectors. These vectors are iteratively refined by a Transformer encoder followed by a feed-forward network and layer normalisation.

After T steps the output representation ${\text{h}}_{\text{T,V}}^{\text{(k)}}$ is fed to the next (k + 1)-th layer. Therefore, multiple layers are stacked on top of each other to capture k-hops neighbours in the UGformer. In the end, all output representations of all K layers are concatenated to infer the vertex. embedding o_v. The graph embedding o_G is the sum of all vertices embeddings o_v ∀ v ∈ V. The model parameters are learned by minimising a cross-entropy loss function.

3.6. Summary

In this Section, we presented twelve types of text representation strategies using graphs: Read- ing Order Only (ROO), Reading Order Circular (ROC), Binary Tree (BT), AVL Tree (AT), Red-Black Tree (RBT), Dependency Tree Only (DTOY), Dependency Tree Order (DTOR), Dependency Tree Order Multigraph (DTORM), Dependency Tree Only Self (DTOYS), Dependency Tree Order Self (DTORS), Dependency Tree Order Multigraph Self (DTORMS), and Graph of Words (GOW). We also presented the deep learning model used in our experiments. The following Section will use these strategies to represent distinct classification datasets.

4. Experiments

This part presents the experiments conducted. We present the datasets used, followed by our methodology, results, and results analysis.

4.1. Datasets used

This work used four datasets - MR, Ohsumed, B2W-Rating-Balanced, and 10kGNAD to evaluate the language independence of the graph classification. They came from a different source: the MR and Ohsumed datasets were extracted from the TextGCN project (Yao et al., 2019). While the B2W-Rating-Balanced² and 10kGNAD³ were extracted from GitHub. We will refer to these four datasets as the LI datasets in this text.

The MR⁴ dataset is a movie review dataset for binary sentiment classification, in which each review only contains one sentence (Pang & Lee, 2005). The corpus has 5,331 positive and 5,331 negative reviews.

The Ohsumed corpus⁵ (Moschitti & Basili, 2004) is from the MEDLINE database, a bibliographic database of crucial medical literature maintained by the National Library of Medicine. In this work, we used the 13,929 unique cardiovascular diseases abstracts in the first 20,000 abstracts of 1991. Each document in the set has one or more associated categories from the 23 disease categories. As we focus on single-label text classification, the documents belonging to multiple categories are excluded. Thus only 7,400 documents belonging to only one category remain.

The B2W-Rating-Balanced is a balanced dataset (Ehrenfried et al., 2022) composed of 41,945 reviews written in Portuguese. These classes are the review score given by the review’s author. This score is an integer number between 1 and 5, where one is the lowest and five is the highest.

The 10kGNAD consists of 10,273 news articles in German from an Austrian online newspaper categorised into nine topics (Web, Panorama, International, Wirtschaft, Sport, Inland, Etat, Wissenschaft, Kultur). It is important to note that the 10kGNAD is an unbalanced dataset. The goal of this dataset is to categorise each document into one topic. Table 2 presents a summary of the content of each dataset.

Table 2. LI datasets used in the experiments. The number after the ± sign is the standard deviation.

	MR	B2W-Rating	Ohsumed	10kGNAD
Language	English	Portuguese	English	German
Docs	10,662	41,945	7,400	10,273
Classes	2	5	23	9
Mean tokens	21.04 ± 9.42	26.36 ± 25.77	193.74 ± 76.36	345.85 ± 257.61
Max tokens	60	796	615	4,804
Min tokens	1	1	30	3

We also experimented with these twelve representation strategies in two German competitions, the GermEval 2018 (Wiegand et al., 2018) and the GermEval 2021 (Risch et al., 2021). These competitions collected text from social media and proposed different classification tasks. Because the text came from social media, it may contain emojis, mentions to other users (that the competition committee anonymised, but the mentions remain in the text), and slang. An overview of the datasets, with information about the number of documents and statistics about the tokens is available in Table 3.

Table 3. Statistics of GermEval Datasets. The number after the ± sign is the standard deviation.

	GermEval 2018	GermEval 2021
Language	German	German
Docs	5,009	4,188
Mean tokens	19.94 ± 9.85	28.88 ± 37.69
Max tokens	74	759
Min tokens	5	1

The GermEval 2018 Shared Task comprises two tasks of identification of offensive language with 8,541 comments collected from Twitter. From these comments, 5,009 composes the training set, and 3,532 composes the test set.

In the first task, the classification task is a coarse-grained binary classification. The second task is a fine-grained multi-class classification. The first task contained the text classified with either OTHER or OFFENSE. The OFFENSE class comprises texts with abusive language, insults or profane statements. The OTHER class contains all text that is not in the OFFENSE class.

The second task contains four classes, a category for texts that are not offensive called OTHER, and the three subcategories from the OFFENSE class from task one. They are PROFANITY, INSULT, and ABUSE. More information about class distribution is in Table 4a. The GermEval 2021 competition aimed to identify toxic, engaging, and fact-clamming comments. The corpus came from 4,188 comments from a German political talk show page on Facebook. From these 4,188 comments, 3,244 are training data, and 944 are test data.

Table 4. Composition of GermEval datasets.

		Training Set		Test Set
Task	Label	Freq	%	Freq	%
Coarse	OFFENSE	1,688	33.7	1,202	34
	OTHER	3,321	66.3	2,330	66
Fine	ABUSE	1,022	20.4	773	21.9
	INSULT	595	11.9	381	10.8
	PROFANITY	71	1.4	48	1.4
	OTHER	3,321	66.3	2,330	66
	TOTAL	5,009	100	3,532	100
(a) Composition of the GermEval 2018 dataset
		Training Set		Test Set
Task	Label	Freq	%	Freq	%
Toxic	toxic	1,122	34.6	350	37.1
	not toxic	2,122	65.4	594	62.9
Engaging	engaging	865	26.6	253	26.8
	not engaging	2,379	73.3	691	73.2
Fact Clamming	fact-clamming	1,103	34.0	314	33.3
	not fact-clamming	2,141	66.0	630	66.7
	TOTAL	3,244	100	944	100
(b) Composition of the GermEval 2021 dataset

In this competition, there are three tasks of binary identification, one for toxic text, another for engaging text, and another for fact-clamming text. More information about class distribution is in Table 4b.

These datasets were selected because they can represent the main challenges found in text classification within them. The mentioned challenges are language ambiguity, language variation, and the use of complex language features such as irony and metaphors. In addition, they present different scenarios where we can apply representation tuning: a data analysis environment and a competitive environment.

4.1.1. Baselines

In this part, we report the baselines for each dataset experimented. We compare our approaches to other graph-based approaches whenever it is possible. Since we did not find experimentation of the German datasets (10kGNAD, GermEval 2018, and GermEval 2021) with graphs, we report the results found. We also report the only result we found on the Portuguese dataset (B2W-Rating). Table 5 presents the results concerning the English datasets. Table 6a presents the top five results of GermEval 2018 in each task, while Table 6b presents the top five results of GermEval 2021 in each task.

Table 5. Baseline for the English datasets (MR and Ohsumed). The bold results are the highest.

Work	Citation	MR	Ohsumed
BertGCN	(Lin et al., 2021)	0.8600	0.7280
RoBERTaGCN	(Lin et al., 2021)	0.8970	0.7280
BertGAT	(Lin et al., 2021)	0.8650	0.7120
RoBERTaGAT	(Lin et al., 2021)	0.8920	0.7120
TextGCN	(Yao et al., 2019)	0.7674 ± 0.0020	0.6836 ± 0.0056
Text Level Graph Neural Network for Text Classification	(Huang et al., 2019)	0.7547	0.6940
SCG	(Wu et al., 2019)	0.759 ± 0.3	0.6850 ± 0.3
SSGC	(Zhu & Koniusz, 2021)	0.7670 ± 0.0	0.6850 ± 0.1
GraphStar	(Haonan et al., 2019)	0.7660 ± 0.004	0.642 ± 0.006
ConTextING-BERT	(Huang et al., 2022)	0.8601	0.7128
ConTextING-Graph Attention Network - BERT	(Huang et al., 2022)	0.8616	0.7151
ConTextING-RoBERTa	(Huang et al., 2022)	0.8943	0.7253
ConTextING-Graph Attention Network - RoBERTa	(Huang et al., 2022)	0.8924	0.7206
TextING	(Zhang et al., 2020)	0.7982	0.7042
HyperGAT	(Ding et al., 2020)	0.7832 ± 0.0027	0.6990 ± 0.0034
VGCN-BERT	(Lu et al., 2020)	0.8593	0.7019
Text-FCG	(Wang et al., 2023)	0.8078 ± 0.22	0.7165 ± 0.36
Text-FCG + BERT	(Wang et al., 2023)	0.8689 ± 0.18	0.7384 ± 0.31
LDGCN	(Wang et al., 2023)	0.7825 ± 0.11	0.7085 ± 0.18

Table 6. Baselines, in terms of F1-Score, for the GermEval datasets. These baselines come from the results of the competitions (Risch et al., 2021; Wiegand et al., 2018).

Position	Coarse	Fine
1	76.77	52.71
2	75.52	51.42
3	75.22	48.44
4	75.18	43.04
5	74.64	41.77
(a) GermEval 2018 baseline
Position	Toxic	Engaging	Fact-Clamming
1	71.75	69.98	76.26
2	71.61	69.91	76.02
3	71.27	69.69	75.79
4	70.73	69.47	75.43
5	69.14	69.34	74.82
(b) GermEval 2021 baseline

We begin reporting the baselines we just find one result. The 10kGNAD, regarding text classification, has a baseline in accuracy of 90.5%. This result came from the BERT for German (Chan et al., 2020).

The Portuguese dataset (B2W-Rating) is a new dataset. Therefore the only baseline found comes from the creator of the dataset (Ehrenfried et al., 2022), which scored an accuracy of 60.4% by using a TextGCN.

4.2. Methodology

For each dataset from the LI datasets presented in Table 2, we transformed each document into a graph using the methods explained in Section 3. Therefore, we generate one file with all graphs for each representation strategy. Since twelve representations exist for each of the four datasets, we built 48 files. Each of these 48 files takes approximately 1 h to be built using the desktop machine described in the following paragraphs.

Then, we run the UGFormerV1 model for each of these files. We use the 10-fold strategy. Therefore, 10% of the dataset is the test set, and the other 90% is the training set.

For the GermEval datasets, we experimented with a simulated competition environment. So, we ran each representation strategy once, following the division of train and test data provided by the competition’s committee.

We modified the original model UGformerV1 (Nguyen et al., 2022) to allow each vertex to contain the node features referenced in Section 3. Thus, the code mentioned in the previous paragraph adds the word embeddings of each word as the node feature. The modified code is available at our Github.⁶

All experiments were conducted using the Pytorch version of the UGformerV1 (Nguyen et al., 2022) supervised model briefly explained in Section 3.5. We used as a base most of the default parameters suggested by the authors of UGformerV1 (Nguyen et al., 2022), so most of the experiments may run using a GPU with 8 Gb of VRAM. The parameters used are:

num_timesteps = 1; num_neighbors = 4; sampled_num = 512; dropout = 0.5; learning_rate = 0.0001;

ff_hidden_size = 1024; num_hidden_layers = 2; num_epochs = 30; batch_size = 4;

Regarding the parameters of the UGFormer for the GermEval datasets, we only increased the number of epochs from 30 to 70, so we could analyse the effects of more epochs. The five experiments report the test metrics in the last epoch since the UGFormer does not implement early stopping.

For all experiments, we did not perform parameter tuning in any experiment. That is because the work aims to evaluate how different representation strategies behave. Performing parameter tuning would move the reader’s attention from the representation’s impact to the model’s performance, which is not intended in this work. Thus, we standardised the parameter as previously described.

To run the experiments from Table 2, we used a desktop machine equipped with an Intel i9 10900KF, 32 GB RAM, and an RTX 3080 12 GB. The operating system is Ubuntu Server 22.04 without any graphical interface. This machine took approximately 120 h to train and infer each LI dataset 10 times each, totalling approximately 480 h to train and infer all representation strategies for all LI datasets. Plus 48 h to build the 48 representations, totalling 528 h to execute the complete experiment.

To run the GermEval experiments, we had access to a cluster equipped with an Intel Xeon CPU E5-2683 v4, two Tesla P100 16GB, and 512 GB RAM. However, the experiments used only one Tesla P100 and 8 CPU cores. Regarding the time needed to train and infer, for the GermEval 2018, each of the 24 experiments took approximately 40 min. For the GermEval 2021, each of the 36 experiments took approximately 34 min. We spent 16 h in the GermEval 2018 and 20 h and 24 min in the GermEval 2021.

Regarding metrics, the evaluation of the four datasets presented in Table 2 uses accuracy, as the literature does. At the same time, the GermEval experiments use F1-Score, as the competition’s committee expected.

4.3. Results

We present the accuracy results in Table 7 and Table 8. The values reported in Table 7 average ten executions. The results in Table 8 are the result of a single execution, as discussed previously. Bold values present the best result from each type of graph (Reading order, Binary tree, Dependency tree, and GOW). Underlined values represent the best accuracy result of the dataset. The number after the ± sign is the standard deviation.

Table 7. Accuracy of each dataset for each graph strategy. The bold values are the highest values of their category (Reading order, Binary tree, Dependency tree, and Graph of words). The underlined values are the best results for the dataset.

Strategy	MR	Ohsumed	B2W-Rating	10KGNAD
ROO	79.35 ± 0.93	67.18 ± 2.78	53.97 ± 0.86	81.01 ± 2.41
ROC	79.68 ± 1.51	66.69 ± 1.84	54.23 ± 0.78	80.44 ± 1.98
BT	77.73 ± 1.81	67.57 ± 1.85	53.30 ± 1.49	80.91 ± 1.66
AT	78.06 ± 1.93	68.57 ± 2.69	53.18 ± 1.09	80.13 ± 2.05
RBT	77.72 ± 1.82	68.27 ± 1.24	53.51 ± 0.51	80.31 ± 2.45
DTOY	79.56 ± 0.92	66.59 ± 2.30	54.70 ± 0.59	77.88 ± 3.73
DTOR	79.20 ± 1.90	66.38 ± 2.23	54.15 ± 0.47	79.67 ± 2.89
DTORM	79.20 ± 1.30	66.25 ± 1.61	54.24 ± 0.68	79.41 ± 3.14
DTOYS	78.93 ± 1.45	69.12 ± 2.00	54.30 ± 1.11	79.76 ± 2.95
DTORS	79.54 ± 1.37	68.08 ± 1.45	53.80 ± 0.83	80.74 ± 1.62
DTORMS	79.01 ± 1.92	67.70 ± 2.10	53.92 ± 0.77	81.60 ± 1.62
GOW	78.33 ± 1.65	60.11 ± 1.53	54.06 ± 0.68	73.89 ± 3.65

Table 8. Accuracy and F1-Score for each task of GermEval 2018 and GermEval2021 competition with each representation strategy presented. The bold values are the highest values of their category (Reading order, Binary tree, Dependency tree, and Graph of words). The underlined values are the best results for the dataset. Observe that the competition uses the F1-Score to rank the participants.

	GermEval2018						GermEval2021
	Coarse		Fine		Engaging		Fact Clamming		Toxic
Strategy	Acc	F1	Acc	F1	Acc	F1	Acc	F1	Acc	F1
ROO	71.84	60.60	68.45	42.63	73.41	35.14	73.73	55.56	66.95	76.04
ROC	74.31	53.79	67.83	44.21	75.00	38.54	74.68	53.41	67.16	48.84
BT	72.37	53.17	68.10	39.45	77.54	44.21	74.47	52.09	66.21	74.50
AT	73.13	54.24	68.13	39.60	72.03	78.78	71.61	55.92	66.95	40.23
RBT	71.42	54.94	68.01	40.02	76.59	85.49	73.52	52.83	66.31	44.01
DTOY	70.39	57.01	63.18	41.04	74.47	83.75	74.89	82.38	65.78	76.98
DTOR	73.25	58.28	65.54	43.56	77.22	84.89	75.21	53.20	63.35	54.23
DTORM	73.60	57.63	64.95	45.19	75.53	84.91	75.32	61.23	67.16	75.00
DTOYS	68.89	59.55	69.46	42.71	74.47	82.34	73.94	52.51	66.21	73.74
DTORS	71.19	60.28	67.69	45.35	75.42	53.97	72.14	47.29	67.69	76.08
DTORMS	71.22	58.10	64.54	43.08	78.50	86.20	73.73	48.55	65.36	47.17
GOW	71.51	54.89	69.25	41.37	74.68	83.93	72.56	51.04	67.90	42.50

We calculated the p-values for all experiments in Table 7, and we report them on our GitHub page⁷ because the resulting tables may consume much space.

4.4. Results analysis

We consider the baselines presented in Section 4.1.1 to analyse our results. When we consider the results of Table 7, we observe that we do not surpass any state-of-the-art result regardless of the representation strategy used. Nevertheless, our investigation performs better than some graph-based approaches, such as GraphStar (Haonan et al., 2019) and TextGCN (Yao et al., 2019).

We also observe that the representation strategy can improve the accuracy of the results in the same dataset up to 2.8% if it has an average of 30 tokens and up to 14.9% if the dataset has more than 150 tokens, as shown in Table 9.

Table 9. Improvement observed in accuracy by changing the representation strategy.

Dataset	Worst Result	Best Result	Improvement	Worst strategy	Best strategy
MR	77.72	79.68	2.5%	RBT	ROC
Ohsumed	60.11	69.12	14.9%	GOW	DTOYS
B2W-Rating	53.18	54.70	2.8%	AT	DTOY
10kGNAD	73.89	81.60	10.4%	GOW	DTORMS

We also observe that the dependency-based trees perform well under any size of tokens, being the best representation strategy for three datasets. Even in the MR dataset, where the dependency-based trees are not the best, they perform similarly to the best representation strategy. The GOW strategy performs the worst when the text contains more than 150 tokens, probably because it loses semantic information, similar to the BoW approach.

To compare dependency-based approaches with and without the reading order module. We divide the comparison into two groups: the group with self-loop edges and the group without self-loop edges. When the group without self-loop edges is observed, we notice that, except for the 10KGNAD dataset, all datasets performed better without the reader order module.

In the group that has self-loop edges, the result was mixed. MR and 10KGNAD perform better with the reading order module, and Ohsumed and B2W perform better without the reading order module.

When a similar comparison regarding the use of self-loop edges is drawn, using the same base structure (DTOY vs DTOYS; DTOR vs DTORS; DTORM vs DTORMS), adding a self-loop edge improves the performance of the model when assessing the datasets with larger sentences (Ohsumed and 10KGNAD). However, in a smaller dataset, we did not observe any pattern. The MR dataset had mixed results, and the B2W dataset performed the best without self-loop edges.

We present more detailed metrics of the best and worst results in Table 10 and Table 11, respectively. Observe that these metrics follow the same pattern observed with the accuracy results.

Table 10. Metrics observed in the best results of each of the four datasets: MR - ROC, B2W - DTOY, Ohsumed - DTOYS, and 10KGNAD - DTORMS. These metrics are the average of 10 executions.

Metric	MR	B2W	Ohsumed	10KGNAD
ACC	79.68 ± 1.51	54.70 ± 0.59	69.12 ± 2.00	81.60 ± 1.62
F1	79.06 ± 1.96	53.79 ± 0.93	61.37 ± 2.41	80.91 ± 1.37
Precision	81.11 ± 3.42	54.41 ± 0.9	65.77 ± 2.6	82.76 ± 0.90
Recall	77.70 ± 6.43	54.63 ± 0.82	60.71 ± 2.39	80.26 ± 1.74
AUROC	79.54 ± 1.14	71.65 ± 0.51	79.62 ± 1.21	88.94 ± 0.96

Table 11. Metrics observed in the worst results of each of the four datasets: MR - RBT, B2W - AT, Ohsumed - GOW, and 10KGNAD - GOW. These metrics are the average of 10 executions.

	MR	B2W	Ohsumed	10KGNAD
ACC	77.72 ± 1.82	53.18 ± 1.09	60.11 ± 1.53	73.89 ± 3.65
F1	76.69 ± 3.00	51.64 ± 1.76	58.76 ± 1.74	79.67 ± 1.87
Precision	80.23 ± 2.40	52.70 ± 1.53	63.36 ± 2.63	82.13 ± 2.18
Recall	73.95 ± 6.93	53.18 ± 1.04	58.97 ± 2.05	79.13 ± 1.41
AUROC	77.72 ± 1.73	70.74 ± 0.65	78.69 ± 1.05	88.31 ± 0.80

However, if we analyse the AUROC (Area under the ROC curve) following the same methodology used in Hosmer et al. (2013), the results show that all experiments have at least an acceptable classification, with results from 10KGNAD achieving an excellent classification.

When we look at the competition datasets, we can observe that when the German text is relatively smaller, in the GermEval 2018 dataset, the methods based on reading order are enough to deliver the best performance, while the Binary tree is always the worst strategy. Regardless of the method, we could not beat the state-of-the-art, but we could achieve the top 4 results in the fine-grained task.

However, the best results come from the GermEval 2021. We beat the state-of-the-art in all tasks with an average increase of 1.12x the result achieved by the best team for each competition task. Once again, the Dependency-based methods performed the best, leading us to suspect that perhaps the most reliable representation method to start using when developing a deep learning model should be based on dependency trees.

Table 12 reports the maximum improvement observed in each task of the two GermEval competitions in F1-Score.

Table 12. Improvement observed in F1-Score by changing the representation strategy.

Task	Worst Result	Best Result	Improvement	Worst strategy	Best strategy
Coarse	53.17	60.60	13.9%	BT	ROO
Fine	39.45	44.21	12%	BT	ROC
Engaging	35.14	86.20	145.3%	ROO	DTORMS
Fact Clamming	47.29	82.38	74.2%	DTORS	DTOY
Toxic	40.23	76.98	91.3%	AT	DTOY

We observed in GermEval 2018 and GermEval 2021 that in the dependency trees that do not use self-loops, the majority of the results were better when the reading order module was enabled. The only exceptions were the F1-Score from GermEval 2021 in the tasks Fact Clamming and Toxic. These results might happened because the dataset division is more balanced when compared to the Engaging task.

The self-loop edges versions also performed better when the reading order module was enabled. The exceptions are the Fact Clamming and the Fine, which had results that favoured the version without the reading order module. We also attribute these results to the dataset division.

When we look closer at these dependency-based approaches and compare the same base representation with and without the self-loop edges, we observe the following: In the GermEval 2018 Coarse task, the accuracy is always better without self-loop edges, and the F1-Score is always better with self-loop edges. These results indicate that even though the model could more accurately classify the graphs without the self-loop edge, it wrongly classifies false positives and false negatives more often. However, the Fine task of GermEval 2018 followed this pattern in only one case: when the graph is a multigraph, the best performance in accuracy and F1-Score comes from the variant without self-loop edges.

Regarding GermEval 2021, in the Engaging task, the multigraph approach did not follow the pattern. It performed best with self-loop edges. The others performed better without self-loops. In the Fact Clamming, the three approaches performed best without self-loops. Nonetheless, in the Toxic task, the dependency tree without any modules had its best accuracy with self-loops but its best F1-Score is without self-loops. These results suggest that the version without self-loops classifies false positives and false negatives more accurately. The representation version that added the reading order performed best with self-loop edges, and the multigraph version performed the best without self-loop edges.

Regarding all results presented, we hypothesise that the dependency-based strategies performed well in most cases because they can better capture valuable relations to define the semantics. At the same time, the binary trees divide the words by their function in the text, and the other two strategies, reading order and graph of words, capture the sequence in which words appear in a text.

Thus, we identified that no representation model is the best in all scenarios because each classification dataset and task needs the assessment of different text fragments to be classified accurately. This phenomenon happens because language is applied differently in each dataset - each sentence author builds different representations in their mind to communicate. In addition, the classification labels we create can be subjective, making even humans debate the categorisation of some sentences.

Regardless, if we needed to point to the most reliable representation strategy family, our results suggest that it would be the dependency tree family. When the dependency-based representations are regarded, adding and removing edges in the representation model can help the deep learning model understand the importance of different text fragments in the desired classification task, improving the final result.

5. Discussion and further work

This work presented an exploration of representation strategies for text using graphs. We explored twelve different graph formats divided into four groups, Reading order, Binary tree, Dependency tree, and Graph of words. We applied them to four classification datasets, covering three distinct languages and two competitions in German.

We showed that the representation strategy used can affect the performance of a deep learning model. In our tests, we observed that the best type of text representations as a graph are the dependency-based representations, which achieved up to 145% improvement over the worst strategy used. These results may motivate other researchers and practitioners to consider representation tuning as another technique to improve machine learning algorithms.

The exploration performed regarding text representation beat the current state-of-the-art in the GermEval 2021 tasks, and they remained competitive in other datasets.

Further work may investigate if the same improvements occur in other deep learning models or if it is a characteristic of UGFormerV1. Further work may also explore a collaboration with linguists to develop a novel text representation tuned to deep learning processing. The motivation comes from our results with the dependency-based strategies, which were some of the best performers of the studied strategies. In future work, parameter tuning could be applied to improve the results we achieved even further.

In addition, a similar methodology could be used to test other datasets and other NLP tasks to verify if other scenarios also benefit from representation tuning, as our results suggest.

Acknowledgements

Research financed with funds from the National Development Fund (FNDE, in Portuguese) and the Ministry of Education (MEC, in Portuguese) of the Federal Government of Brazil, carried out by the Center for Scientific Computing and Free Software (C3SL, in Portuguese) of the Federal University of Paraná (UFPR, in Portuguese). We also want to thank the Coordination for the Improvement of Higher Education Personnel (CAPES) - Program of Academic Excellence (PROEX) (Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) - Programa de Excelência Acadêmica (PROEX) in Portuguese).

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 https://github.com/daiquocnguyen/Graph-Transformer - Last access on March 07th, 2023

2 https://github.com/HenriqueVarellaEhrenfried/B2W-Datasets - Last access on March 07th, 2023

3 https://tblock.github.io/10kGNAD/ - Last access on March 07th, 2023

4 http://www.cs.cornell.edu/people/pabo/movie-review-data/ - Last access on March 07th, 2023

5 http://disi.unitn.it/moschitti/corpora.htm - Last access on March 07th, 2023

6 https://github.com/HenriqueVarellaEhrenfried/Graph-Transformer

7 https://github.com/HenriqueVarellaEhrenfried/Graph-Transformer/blob/master/experiments.md