Semantic WordRank: Generating Finer Single-Document Summarizations

We present Semantic WordRank (SWR), an unsupervised method for generating an extractive summary of a single document. Built on a weighted word graph with semantic and co-occurrence edges, SWR scores sentences using an article-structure-biased PageRank algorithm with a Softplus function adjustment, and promotes topic diversity using spectral subtopic clustering under the Word-Movers-Distance metric. We evaluate SWR on the DUC-02 and SummBank datasets and show that SWR produces better summaries than the state-of-the-art algorithms over DUC-02 under common ROUGE measures. We then show that, under the same measures over SummBank, SWR outperforms each of the three human annotators (aka. judges) and compares favorably with the combined performance of all judges.


Introduction
An extractive summarization algorithm of a single document aims to produce a much shorter text file to cover all the main points of the document without redundancy. Such an algorithm, unsupervised or supervised, extracts a few critical sentences from the document to form a summary.
An unsupervised method typically solves an optimization problem of selecting sentences subject to the underlying length constraint of a summary through sentence scoring and topic diversity. Unsupervised methods have three advantages: (1) They do not need training data; (2) they are in general independent of the underlying languages; and (3) they are much more efficient. Most unsupervised methods use easy-to-compute counting features, such as term frequencyinverse document frequency (TF-IDF) and co-occurrences of words, discarding semantic information. Some methods do incorporate semantic features including Semantic Role Labeling, WordNet, and Named-Entity Recognition when selecting sentences. These methods rely on specific language features which can be a potential problem when adapting across languages.
Supervised methods, on the other hand, may either require handcrafted features or learn feature representations automatically with a deep neural network model trained on a significant amount of data and is often time-consuming.
These considerations motivate us to investigate unsupervised summarization algorithms using semantic features that can be computed readily for any language.
Word embedding representation maps a word into a high-dimensional vector representing continuous relations with other words, which is easy to obtain and does not rely on specific language features. A good pre-trained word embedding representation can help capture both useful semantic and syntactic information [15]. Word Mover's Distance (WMD) [12] utilizes this property to measure the distance between two documents, which brings semantics to sentence similarity. Our method, called Semantic WordRank (SWR), is an unsupervised graph-based algorithm with semantic features for generating extractive singledocument summaries. It adds word-embedding representations as semantic relations to a graph with word co-occurrence relations. It then uses an articlestructure-biased PageRank algorithm to compute a score for each word and a score for each sentence after an adjustment using the Softplus function. To facilitate coverage diversity, our approach uses a spectral subtopic clustering method to group subtopics under the WMD. Finally, it selects sentences with the highest scores over subtopic clusters in a round-robin fashion until the length constraint of the summary size fails.
The rest of the paper is organized as follows: We present in Section 2 a brief overview of related work on single-document extractive summarizations. Section 3 provide a detailed description of SWR. We describe in Section 4 our evaluation datasets, experiment settings, and comparison results under ROUGE measures on DUC-02 and SummBank datasets. We conclude the paper in Section 5.

Related Work
Unsupervised methods. Relations between words play a central role in unsupervised extractive methods, with the underlying idea that related words "promote" each other. In particular, TextRank [14] and LexRank [6] model a document as a sentence graph, and use the PageRank algorithm to rank sentences. TextRank offers robust performance over the DUC-02 dataset. These methods extract sentences based only on sentence scores, without considering topic diversity.
UniformLink [23] builds a sentence graph on a set of similar documents, where a sentence's score is computed based on both with-in document score and cross-document score. URank [22] uses a unified graph-based framework to study both single-document and multi-document summarizations.
E coh [19], as well as T coh [18], use a bipartite graph to represent a document and a different algorithm, Hyperlink-Induced Topic Search (HITS) [11], is used to score sentences. They both treat the summarization problem as an ILP problem, which maximizes the sentence importance, non-redundancy, and coherence at the same time. However, since ILP is an NP-hard problem, obtaining an exact solution to an ILP problem is intractable.
Submodularity optimization [13] and Latent Semantic Analysis [8] are two other widely used unsupervised techniques for extractive summarizations.
Supervised methods. Traditional supervised machine learning methods often need handcrafted features. These methods include Support Vector Machine and Naive Bayesian Classifier [24]. CP3 [17], which has the same underlying idea as E coh and T coh , mines coherence patterns in a corpus of abstracts, and extracts sentences by solving an ILP problem.
Deep learning methods, able to learn sentence or document representations automatically, have recently been used to score sentences. For example, R2N2 [4] uses a recursive neural network for both word level and sentence level scoring, followed by an ILP optimization strategy for selecting sentences. CNN-W2V [25] is another example, which modifies a convolutional-neural-network (CNN) model of sentence classification [9] to rank sentences. SummaRuNNer [16], on the other hand, treats summarizations as sequence classifications and uses a two-layer bidirectional recurrent neural network (RNN) model to extract sentences, where the first layer RNN is for words and the second layer is for sentences. Unlike unsupervised methods, the state-of-the-art deep learning approaches require a larger dataset and a significantly longer time to train a model, yet with a much lower ROUGE-1 score when evaluating on DUC dataset.

Semantic WordRank
We model a single-document extractive summarization problem as a 0-1 multiobjective knapsack problem. Let D be a document consisting of n sentences indexed as S 1 , S 2 , . . . , S n in the order they appear, each with a length l i and a score s i , along with a maximum length capacity L, where l i is the number of characters contained in S i . Let F d (D) denote a diversity coverage measure and x i a 0-1 variable such that x i = 1 if sentence S i is selected, and 0 otherwise. We model the summarization problem as the following multi-objective optimization problem: In this section, we describe Semantic WordRank in details. In particular, we first describe how we score sentences, followed by a spectral subtopic clustering method to facilitate diversity. Finally, instead of solving the 0-1 knapsack problem to obtain an optimal solution, which is NP-hard, we use a greedy strategy to obtain an approximation.

Semantic Word Graphs
Let G = (V, E) denote a weighted, undirected multiple-edge graph to represent a document D, where V is a subset of words contained in D that pass a part-ofspeech filter, a stop-word filter, and a stemmer for reducing inflected words to the word stem. Two nodes in G are connected if they co-occur within a window of N successive words in the document, or the cosine similarity of their wordembedding representations exceeds a threshold value ∆. Let u and v be two adjacent nodes. Initially, they may have two types of connections, one for cooccurrence and one for semantic similarity. We assign the co-occurrence count of u and v as the initial weight to the co-occurrence connection, and the cosine similarity value as the initial weight to the semantic connection. Let w c u,v and w s u,v denote, respectively, the normalized weight for the co-occurrence connection and the semantic connection of u and v. Finally, we assign as the weight to the incident edge of u and v.
Note that the original TextRank algorithm [14] only considers co-occurrence between words. We add semantic similarity to represent that a pair of words express the same or similar meanings.
On a separate note, adding semantic similarity is vital for processing analytic languages, such as Chinese, which seldom use inflections. When stemming is not applicable, semantic similarity serves as an alternative to represent the relations between words with similar meanings, allowing them to share the importance when computing the PageRank scores for these nodes.

Article-Structure-Biased PageRank
Article structures define the order how to present information. For example, the typical structure of news articles is an inverted pyramid, presenting critical information at the beginning, followed by additional information with less important details. In academic writing, the structure would look like an hourglass, which includes an additional conclusion piece at the end of the article. To include article structures in our model, we use a position-biased PageRank algorithm [7].
Let G denote the word graph constructed in the previous section. The original TextRank algorithm computes score W (v i ) of a node v i by iterating the following PageRank equation until converging, where A(v i ) denotes the set of nodes adjacent to v i : where α ∈ (0, 1) is a damping factor, often set to 0.85 [3], and w ji is the weight of the edge between node j and node i. The intuition behind this equation is that the importance of a node v i is related to the scores of its adjacent nodes and the probability β = 1 − α of jumping from a random node to node v i . In unbiased PageRank, each word is treated equally likely. In article-structurebiased PageRank, each word v i is biased with a probability P (v i ) according to the underlying article structure. For example, in the inverted pyramid structure, we assign a higher probability to a word that appears closer to the beginning of the article. We rank the importance of sentences from the most important to the least important based on the underlying article structure. In the inverted pyramid structure, we assign score s i to sentence S i using the reciprocal of indexing (or negative indexing). The probability for node v i can now be computed as follows: Note that the above computation is at the sentence level, which can be easily adapted to the word level by ranking words instead of sentences. We compute the revised TextRank score W ′ (v i ) for node v i as follows: We first assign an arbitrary value to each node and iterate the computation until it converges. The score associated with each node represents the word importance, and we refer it to as salient score.

Sentence Scoring with Softplus Adjustment
We use W ′ (v i ) to compute a salient score for each sentence, where v i is a node in the word graph. At the first glance, one would sum up W ′ (v i ) for words contained in sentence S to be the salient score of S. This method has the following drawback. Suppose that two sentences S 1 and S 2 have similar salient scores with different W ′ score distributions, where S 1 has a bipolar word score distribution where several keywords have very high scores and the rest have very low scores, while S 2 has roughly a uniform word score distribution. In this case, we would consider S 1 more critical than S 2 , but using this method to compute a salient score of a sentence, we may end up with an opposite result.
To overcome this drawback, we use a Softplus Adjustment. The Softplus function sp = ln(1 + e x ), commonly used as an activation function in neural networks, offers a significant enhancement when the input x is a small positive number. When x is large, we have sp(x) ≈ x. We apply the Softplus Adjustment to each keyword, and then sum them up to get a salient score by

Spectral Clustering for Topic Diversity
Spectral clustering [21] uses eigenvalues of an affinity matrix to reduce dimensions before clustering. This model offers better performance over K-means with fewer requirements. The affinity matrix is an n × n square matrix, where each element corresponds to a similarity between two sentences. Since we use WMD metric, where smaller value between two sentences means more similar and larger value means less similar, we can use a RBF kernel to transfer WMD scores to similarity as follows: sim(S i , S j ) = e −γ * W MD(Si,Sj ) 2 , where γ can be set to 1. Note that the time complexity for computing WMD is cubical in terms of the number of unique words in the sentences, making it difficult to scale. Linear-Complexity Relaxed WMD [1] provides a faster approximation to WMD and we will use it to reduce time complexity.
We set the number of clusters c num based on the number of sentences n. According to our experiments, we find that 30% of the original text size would be the best size for a summary to contain almost all significant points. To ensure 30% summary size with no redundancy, we set c num = min{⌊0.3n⌋, 8}.

Greedy Sentence Selections
Each sentence S i now associates with four values: (1) sentence index i, (2) salient score s i , (3) sentence length l i , and (4) cluster index c j it belongs to. We select sentences in a round robin fashion as follows: 1. For each sentence S i , compute the value per unit length using s ′ i = s i /l i . 2. For each cluster, sort the sentences contained in it by their unit scores s ′ i . 3. Group sentences with the highest unit scores, one for each cluster, to form a sentence sequence S c = S x , S y , . . . , S cnum . Select one sentence at a time from S c to the summary. Repeat this step while the size of the summary is less than L.

Experiments
The DUC-02 [5] dataset contains a total of 567 news articles with an average of 25 sentences per document. Each article has at least two abstractive summaries written by human evaluators, where each summary is at most 100 words long. It has been a standard practice to use the DUC-02 benchmarks to evaluate the effect of summarization algorithms, including extractive summaries, even though DUC-02 benchmarks are abstractive summaries. The SummBank [20] dataset is a better dataset for evaluations, for it provides extractive summary benchmarks produced by human evaluators. SummBank offers, for each article, four extractive summaries, with a wide range of summary length from 5% up to 90% of, respectively, words and sentences. Three human judges annotate 200 news articles with an average of 20 sentences per document. In particular, given a document, each judge assigns an importance score to each sentence, resulting in, for a given length constraint, three extractive summaries, one for each judge, by selecting sentences with scores as high as possible and as relevant as possible. Moreover, summing up the three judges' scores for each sentence, we get a combined score and new summaries based on the new scores. We refer to the new summaries as a combined performance of all judges.
ROUGE is the most used metric to evaluate the effect of summarizations. ROUGE-n is an n-gram recall between the automatic summary and a set of references, where ROUGE-SU4 evaluates an automatic summarization using skip-bigram and unigram co-occurrence statistics, allowing at most four intervening unigrams when forming skip-bigram.

Setup
We use a pre-trained word embedding representations with subword information [2] which can help solve the out-of-vocabulary problem and generate better word embedding for rare words. We run SWR (Semantic WordRank) to evaluate 30 articles selected uniformly at random from the DUC-01 dataset, and use the similarity value denoted by ∆ that maximizes the ROUGE-1 score as the threshold value for evaluations on DUC-02 and SumBank. We set N = 2 as the window size for co-occurrences. Since both datasets contain only short news articles, it is reasonable to use inverted pyramid as the article structure.

Evaluations
On the DUC-02 dataset, we use SWR to extract sentences with a length of 100 words and use ROUGE to evaluate the results against the benchmarks. We can see from Table 1 that SWR outperforms the state-of-the-art algorithms under ROUGE-1 (R-1), ROUGE-2 (R-2), and ROUGE-SU4 (R-SU4), where UA means that the value is unavailable in the corresponding publications.  We can see that SWR produces better R-1 and R-SU4 scores over those of CP3 and produces the same R-2 score as that of CP3. But more importantly, SWR offers higher adaptability across languages and lower time complexity. CP3 is a supervised method that requires annotated data to train coherence patterns, where entity recognition and co-reference resolution are needed. Moreover, CP3 generates summarization by solving a time-consuming ILP problem. On the contrary, SWR is an unsupervised model using only word embedding features that can be obtained easily for any language.
Comparisons with individual judges on SumBank To compare with each judge's summaries, for each judge i (i = 1, 2, 3), we use the other two judges' summaries as golden standards. Comparison with each judge are given in Figure  1, where the words limitation or sentences limitation is from 5% to 90%.    Table 3 depicts the evaluation results on 10%, 40%, and 70% sentence constraints, where SWR NSE, SWR NAS, SWR NSC, and SWR NSP denote, respectively, SWR using no semantic edges, no article-structure information, no subtopic clustering, and no softplus adjustment. TextRank is added as a baseline model. We can see that when we remove a feature, the ROUGE scores drop, indicating that each part is essential. The numbers in bold are the biggest drops. We also see that when the summaries are short, removing article structure results in much larger drops, indicating that article structures are a more significant feature than the other two features. As summaries become longer, including semantic edges would become increasingly more critical. Our results indicate that using the Softplus function adjustment does improve the ROUGE scores, but not as significant as using the other three features.

Conclusion and Future Work
We present Semantic WordRank (SWR), an unsupervised method for generating an extractive summary of a single document. SWR incorporates semantic similarity to summarization while maintaining a high adaptability across languages. In particular, SWR generates an extractive summary using word embedding, Softplus function adjustment, article-structure-biased PageRank, and WMD spectral subtopic clustering. We evaluate SWR on DUC-02 and Summ-Bank under three common ROUGE measures. Our experimental results show that, on DUC-02, our approach produces better results than the state-of-the-art methods under ROUGE-1, ROUGE-2, and ROUGE-SU4. We then show that, under the same ROUGE measures over SummBank, SWR outperforms each of the three individual human judges and compares favorably with the combined performance of all judges.
For a future project, we plan to adopt this approach to multi-document summarizations. We would also like to explore unsupervised sentence representations such as skip-thought vectors [10] for summarization.