Textstar: a Fast and Lightweight Graph-Based Algorithm for Extractive Summarization and Keyphrase Extraction (2022)

Abstract: We introduce Textstar, a graph-based summarization and keyphrase extraction system that builds a document graph using only lemmatization and POS tagging. The document graph aggregates connections between lemma and sentence identifier nodes. Consecutive lemmas in each sentence, as well as consecutive sentences themselves, are connected in rings to form a ring of rings representing the document. We iteratively apply a centrality algorithm of our choice to the document graph and trim the lowest ranked nodes at each step. After the desired number of remaining sentences and lemmas is reached, we extract the sentences as the summary, and the remaining lemmas are aggregated into keyphrases using their context. Our algorithm is efficient enough to one-shot process large document graphs without any training, and empirical evaluation on several benchmarks indicates that our performance is higher than most other graph based algorithms.

## introduction contemporary natural language processing is mostly done through neural networks. however, this is resource intensive and requires large amounts of data. this can be a problem for languages that are not widely spoken, due to insufficient data for training these models. even for tasks where neural network based models excel, they are often an overkill. state of the art transformer-based tools such as bert @xcite , gpt-3 @xcite , and even longformer @xcite have size limits and require hierarchical approaches to long documents. however, graph-based approaches are one-shot algorithms that do not require expensive computational resources to train. the need for a fast graph-based summarizer is also justified as a preprocessor to assist these neural models by enabling them to work on salient smaller subsets of a large document. to address this insufficiency, we propose textstar, a lightweight graph-based summarization and keyphrase extraction algorithm that outperforms most other graph-based methods. our model is language-independent, making it suitable for application to languages with insufficient training data. additionally, it simultaneously supports keyphrase extraction and summarization. this flexibility, along with its short runtime, opens up possibilities for many applications. we will start with an overview of our system, as presented in figure 1 . after a document is uploaded, it is pre-processed. then, each sentence is converted into a connected ring of nodes (figure 2 ). additionally, the sentence ids are also connected into a ring of nodes. afterwards, the graph is fed to the textstar algorithm, which gradually trims out word nodes and sentence id nodes that have low ranking values. when the graph contains only the desired number of sentence id nodes or keyword nodes, we feed this information to the postprocessing component. the postprocessing component then converts certain keywords into keyphrases and combines the sentences represented by the sentence id nodes into a summary. our contribution is as follows: the rest of the paper is organized as follows: section 2 overviews related work. section 3 describes the algorithm and implementation. section 4 provides empirical analysis. section 5 analyzes the results and discusses the limitations. section 6 concludes the paper. ## related work graph-based approaches to text summarization and keyphrase extraction are well-established. textrank @xcite and its derivatives are popular unsupervised approaches to text summarization and keyphrase extraction. they utilize graph-based centrality algorithms to score sentences or words with the assumption that sentences or words with the highest centrality scores are expected to have the highest importance in a document. textrank, in particular, uses the pagerank algorithm @xcite as its scoring mechanism. several methods have been proposed that improve the base textrank algorithm by changing the scoring metric @xcite or by changing the construction of the textgraph using salient information about the text or by use of word embeddings. @xcite discover and categorize candidate keyphrases to topics by applying the hierarchical agglomerative clustering algorithm. then, a weighted complete and undirected graph is generated where nodes represent the topics and weighted edges show the semantic relations of the topics. keyphrases that best represent each topic are chosen with three criteria: appearing first in the document, appearing most frequently in the document, and being the most similar to other keyphrases in the topic. then, each topic is ranked by the textrank algorithm. choosing the topics with the n highest scores and selecting the most significant keyphrase per topic generates the final set of keyphrases. @xcite retrieve nouns and adjectives and construct an undirected word graph in which each node is a unique word and the weight of an edge is calculated from the number of bigram co-occurrences in the document. the biased pagerank score of each word is counted by considering both its position and its frequency. the sum of scores of words in each keyphrase generates the keyphrase's score. @xcite selects keyphrase candidates and classifies word stems to topics in a manner similar to @xcite . then, a complete directed k-partite graph is constructed where each node is a keyphrase, an edge connects 2 different topics, the weight of an edge shows a distance between 2 nodes in the document, and k is the number of topics. in addition, the incoming weight of the first node of each topic is adjusted. then the textrank algorithm gives the score for each node, and the n top scoring keyphrases are extracted. lexrank @xcite showcases improved summarization by introducing the idea of computed eigenvector centrality. this method constructs a weighted undirected cosine similarity graph cluster from the given multiple documents, where nodes denote sentences and a weighted edge signifies the idf-modified-cosine of 2 nodes. then, the graph is transferred to an undirected graph which focuses on the salient similar sentences by setting a threshold. the lexrank score of each node is calculated based on eigenvector centrality. the summary is n top scoring sentences. most graph-based methods perform either extractive text summarization or automatic keyphrase extraction, but not both. neural methods have recently been shown to be effective at multi-task natural language processing. however, like graph-based methods, there is little work on neural methods that perform both extractive summarization and keyphrase extraction. our approach implements a multi-task approach to summarization and keyphrase extraction by creating a textgraph sharing both sentences and word nodes. we also introduce a different topology for building a textgraph using a ring-ofrings construction for connecting both words in a sentence and sentences among them. at the same time, a new method is used to compute rankings by successive trimming of unimportant nodes until the required number of sentences and keyphrases is reached. ## method our overall method is shown in figure 1 . the first step of processing a document is to remove words and sentences that are unlikely to contain relevant information. a text graph with a ring-of-rings structure is then constructed using the remaining words and sentences. using the graph, the core document preprocessing construct graph ranking trimming postprocessing summary keywords if s_done and w_done textstar algorithm works by repeatedly computing a centrality metric and then removing low ranked nodes. this process continues until the desired number of summary sentences and key words is reached. finally, the word and sentence nodes left in the graph are post-processed to create the final summary and keyphrases. ## evaluation we have used the degree centrality ranking algorithm, with the summary size and keyphrase size as 6 and the trim percentage set to 80%. we compare textstar against well-known extractive graphical algorithms: lsa @xcite , sumbasic @xcite , and lexrank @xcite . we use the results of these algorithms found in @xcite . each piece consists of an abstract, a title, and keyphrases. @xcite . our model is evaluated by f-mesure on the top k keypharses (f1@k). textstar is compared against the following graph-based keyphrase extraction algorithms: textrank @xcite , singlerank @xcite , topicrank @xcite , positionrank @xcite , and multipartiterank @xcite . the results of inspec and semeval2010 for the baseline algorithms are obtained from @xcite . textstar is also comparable to copyrnn @xcite and outperforms rnn @xcite deep learning model on both the inspec and semeval dataset. these results are gained from @xcite to evaluate these algorithms, we use a python implementation of the rouge @xcite ) metric 2 . our tests show that we outperform other graphbased algorithms for text summarization on arxiv, and are competitive to lexrank on the pubmed dataset. for keyphrase extraction, we outperform all other graph-based algorithms on all datasets with the exception of the inspec dataset. ## discussion the experiments show that the algorithm is competitive on benchmarks of both extractive summarization and automatic keyphrase extraction. whereas separate sentence and word text graphs lose information from the original text, reducing the effectiveness of either task, our multi-task approach takes advantage of the synergies between summarization and keyphrase extraction, allowing 2 https://github.com/diego999/py-rouge for better results than either individually. the important words in a document are strongly correlated to the important sentences. we make use of the relationship between the words and the structure of the document explicitly. ## conclusions we introduced textstar, a multi-task graphbased extractive text summarization and automatic keyphrase extraction algorithm. by iteratively simplifying the text graph while eliminating the lowest ranked scores as determined by a centrality algorithm, we efficiently determine the most salient sentences and keyphrases. moreover, by building the textgraphs from both sentence and word nodes, we extract in one pass both summaries and keyphrases. by aggregating information about word subsequences occurring in a sentence and sentence subsequences occurring in a document, we show that we outperform most other graph-based methods. while