Text Categorization as a Graph Classification Problem

Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 1702–1712, Beijing, China, July 26-31, 2015. c⃝2015 Association for Computational Linguistics Text Categorization as a Graph Classification Problem François Rousseau Emmanouil Kiagias LIX, École Polytechnique, France Michalis Vazirgiannis Abstract In this paper, we consider the task of text categorization as a graph classifica- tion problem. By representing textual doc- uments as graph-of-words instead of his- torical n-gram bag-of-words, we extract more discriminative features that corre- spond to long-distance n-grams through frequent subgraph mining. Moreover, by capitalizing on the concept of k-core, we reduce the graph representation to its dens- est part – its main core – speeding up the feature extraction step for little to no cost in prediction performances. Experiments on four standard text classification datasets show statistically significant higher accu- racy and macro-averaged F1-score com- pared to baseline approaches. 1 Introduction The task of text categorization finds applications in a wide variety of domains, from news filter- ing and document organization to opinion mining and spam detection. With the ever-growing quan- tity of information available online nowadays, it is crucial to provide effective systems capable of classifying text in a timely fashion. Compared to other application domains of classification, its specificity lies in its high number of features, its sparse feature vectors and its skewed multiclass scenario. For instance, when dealing with thou- sands of news articles, it is not uncommon to have millions of n-gram features, only a few hundreds actually present in each document and tens of class labels – some of them with thousands of articles and some others will only a few hundreds. These particularities have to be taken into account when envisaging a different representation for a docu- ment and in our case when considering the task as a graph classification problem. Graphs are powerful data structures that are used to represent complex information about en- tities and interaction between them and we think text makes no exception. Historically, following the traditional bag-of-words representation, uni- grams have been considered as the natural features and later extended to n-grams to capture some word dependency and word order. However, n- grams correspond to sequences of words and thus fail to capture word inversion and subset match- ing (e. g., “article about news” vs. “news article”). We believe graphs can help solve these issues like they did for instance with chemical compounds where repeating substructure patterns are good in- dicators of belonging to one particular class, e. g., predicting carcinogenicity in molecules (Helma et al., 2001). Graph classification has received a lot of attention this past decade and various tech- niques have been developed to deal with the task but rarely applied on textual data and at its scale. In our work, we explored a graph representation of text, namely graph-of-words, to challenge the traditional bag-of-words representation and help better classify textual documents into categories. We first trained a classifier using frequent sub- …

Content truncated to 500 words