Shortest-Path Graph Kernels for Document Similarity

Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 1890–1900 Copenhagen, Denmark, September 7–11, 2017. c⃝2017 Association for Computational Linguistics Shortest-Path Graph Kernels for Document Similarity Giannis Nikolentzos ´Ecole Polytechnique and AUEB nikolentzos@aueb.gr Polykarpos Meladianos ´Ecole Polytechnique and AUEB pmeladianos@aueb.gr Franc¸ois Rousseau ´Ecole Polytechnique rousseau@lix.polytechnique.fr Michalis Vazirgiannis ´Ecole Polytechnique and AUEB mvazirg@aueb.gr Yannis Stavrakas IMIS / RC ATHENA yannis@imis.athena-innovation.gr Abstract In this paper, we present a novel docu- ment similarity measure based on the def- inition of a graph kernel between pairs of documents. The proposed measure takes into account both the terms contained in the documents and the relationships be- tween them. By representing each doc- ument as a graph-of-words, we are able to model these relationships and then de- termine how similar two documents are by using a modified shortest-path graph kernel. We evaluate our approach on two tasks and compare it against several baseline approaches using various perfor- mance metrics such as DET curves and macro-average F1-score. Experimental re- sults on a range of datasets showed that our proposed approach outperforms tradi- tional techniques and is capable of mea- suring more accurately the similarity be- tween two documents. 1 Introduction In recent years, we have witnessed a tremendous growth in the volume of textual documents avail- able on the Web. With this rapid increase in the number of available content, new opportunities for knowledge extraction have arisen. Many text min- ing tasks such as information retrieval, text catego- rization and document clustering involve the direct comparison of two documents. It is thus crucial to be able to determine accurately how similar two documents are by defining a document similarity measure. Generally speaking, a similarity measure is a real-valued function that quantifies the common information shared by two objects (in our case documents). Determining the similarity between two documents is not a trivial task. Whether two documents are similar or different is not always clear and may vary from application to applica- tion. Similarity measures that make use of the vector- space model (Salton et al., 1975) treat words in a document as if they were independent of one an- other, which is not realistic. In fact, words relate to one another to form meaningful phrases and to develop ideas. It is known that the human brain utilizes these relations between words to facilitate understanding (Altmann and Steedman, 1988). In general, we assume that two terms are related if they co-occur together in a small context, typi- cally a phrase or a window of specific size, which resulted in n-gram features in many text mining tasks (an n-gram is a sequence of n terms in this paper). But n-grams correspond to sequences of words and thus fail to capture word inversion and subset matching (e. g., “article about news” vs. “news article”). To take into account these statis- tical relations, we propose to represent each doc- ument as a graph-of-words instead. And then, in order to measure the similarity between two doc- uments, we …

Content truncated to 500 words