A Graph Degeneracy-based Approach to Keyword Extraction

Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 1860–1870, Austin, Texas, November 1-5, 2016. c⃝2016 Association for Computational Linguistics A Graph Degeneracy-based Approach to Keyword Extraction ∗ Antoine J.-P. Tixier1, Fragkiskos D. Malliaros1,2, Michalis Vazirgiannis1 1Computer Science Laboratory, ´Ecole Polytechnique, Palaiseau, France 2Department of Computer Science and Engineering, UC San Diego, La Jolla, CA, USA � anti5662,fmalliaros,mvazirg � @lix.polytechnique.fr Abstract We operate a change of paradigm and hy- pothesize that keywords are more likely to be found among influential nodes of a graph-of- words rather than among its nodes high on eigenvector-related centrality measures. To test this hypothesis, we introduce unsuper- vised techniques that capitalize on graph de- generacy. Our methods strongly and sig- nificantly outperform all baselines on two datasets (short and medium size documents), and reach best performance on the third one (long documents). 1 Introduction Keyword extraction is a central task in NLP. It finds applications from information retrieval (notably web search) to text classification, summarization, and vi- sualization. In this study, we focus on the task of unsupervised single-document keyword extraction. Following (Mihalcea and Tarau, 2004), we concen- trate on keywords only, letting the task of keyphrase reconstruction as a post-processing step. More precisely, while we capitalize on a graph representation of text like several previous ap- proaches, we deviate from them by making the as- sumption that keywords are not found among pres- tigious nodes (or more generally, nodes high on eigenvector-related centrality metrics), but rather among influential nodes. Those nodes may not have many important connections (like their prestigious counterparts), but they are ideally placed at the core ∗This research is supported in part by the OpenPaaS::NG project. of the network. In other words, this switches the objective from capturing the quality and quantity of single node connections, to taking into account the density and cohesiveness of groups of nodes. To op- erate this change of paradigm, we propose several algorithms that leverage the concept of graph degen- eracy (Malliaros et al., 2016a). Our contributions are threefold: (1) we propose new unsupervised keyword extraction techniques that reach state-of-the art performance, (2) we ap- ply the K-truss algorithm to the task of keyword ex- traction for the first time, and (3) we report new in- sights on the interplay between window size, graph- of-words structure, and performance. 2 Graph-of-Words Representation Many ways of encoding text as a graph have been explored in order to escape the very limiting term- independence assumption made by the traditional vector space model. In this study, we adopt the sem- inal Graph-of-Words representation (GoW) of (Mi- halcea and Tarau, 2004), for its simplicity, high his- torical success, and above all because it was recently used in several approaches that reached very good performance on various tasks such as information retrieval (Rousseau and Vazirgiannis, 2013), doc- ument classification (Malliaros and Skianis, 2015; Rousseau et al., 2015), event detection (Meladianos et al., 2015), and keyword extraction (Rousseau and Vazirgiannis, 2015). While sophisticated variants of the GoW model …

Content truncated to 500 words