Graph-based Ranking

A direct adaptation of PageRank for natural language processing. TextRank constructs a co-occurrence graph where vertices represent words or sentences, and edges are weighted by their co-occurrence within a sliding window. The algorithm runs the PageRank formula iteratively until convergence, and the final score of each vertex represents its salience. Unlike supervised methods, TextRank requires no labeled training data, making it domain-independent and highly portable for both keyword extraction and extractive summarization.

The original graph-based ranking algorithm developed by Larry Page and Sergey Brin at Stanford. PageRank models a random surfer who traverses a directed graph by either following an outgoing edge or randomly jumping to any vertex. The stationary probability distribution of this random walk defines the authority score of each node. The core recursive formula is:

• PR(V_i) = (1-d) + d * Σ(PR(V_j) / Out(V_j)) where d is the damping factor, typically set to 0.85. This mechanism elegantly captures the principle that a node is important if it is linked to by other important nodes.

An extension of TextRank that incorporates edge weighting based on the number of co-occurrences between two words within a document. While TextRank typically uses unweighted edges, SingleRank assigns a weight w_ij equal to the co-occurrence frequency of words i and j. This modification allows the algorithm to distinguish between weak and strong lexical associations, often yielding higher precision in keyphrase extraction by prioritizing terms that consistently appear together in the same context windows.

A biased PageRank variant that injects a positional prior into the random walk. PositionRank observes that important keyphrases tend to cluster at the beginning of academic documents. It modifies the restart probability of the random surfer to favor words occurring in the first few sentences of a document. The bias vector is computed using the inverse of a word's first occurrence position. This simple heuristic dramatically improves performance on scientific article keyphrase extraction, often outperforming standard TextRank on benchmarks like Inspec and SemEval.

A graph-based model that shifts the unit of ranking from individual words to multi-word topics. TopicRank first clusters candidate keyphrases into cohesive topics using hierarchical agglomerative clustering based on stemmed forms and surface string overlap. It then constructs a complete graph where vertices are topics and edges are weighted by the normalized co-occurrence distance between their constituent phrases. PageRank is applied to this topic graph, and the top-ranked phrase from each high-scoring topic is selected. This approach reduces redundancy in the final keyphrase set.

An advanced graph-based method that constructs a multipartite graph with distinct layers for topics and candidate keyphrases. Unlike TopicRank's two-step process, MultipartiteRank models the relationships between topics and phrases simultaneously in a single heterogeneous network. Edges connect topics to their constituent phrases, and the ranking algorithm propagates scores across layers. This joint inference allows the model to select keyphrases that are both centrally located within their topic cluster and globally salient to the document, achieving state-of-the-art unsupervised performance.