LexRank

LexRank models a document as a similarity graph where vertices represent sentences and edges are weighted by TF-IDF cosine similarity. It then applies eigenvector centrality—the same mathematical principle behind PageRank—to compute a stationary distribution over sentences. A sentence is deemed salient not merely by its own content, but by the number and importance of other sentences that are similar to it. This captures the intuition that a central, representative sentence will be heavily connected within the graph. The algorithm computes the principal eigenvector of the sentence adjacency matrix, yielding a probability distribution where higher scores indicate greater centrality to the document's core themes.

To prevent the summary from being dominated by a single highly-connected cluster of near-duplicate sentences, LexRank incorporates a stochastic selection process. After computing the stationary distribution, sentences are selected using a greedy algorithm with a cosine similarity threshold. Once a sentence is chosen for the summary, all sentences too similar to it are temporarily suppressed. This threshold is applied stochastically, meaning the algorithm can produce different summaries on different runs, introducing controlled diversity. This mechanism directly addresses the Maximum Marginal Relevance (MMR) trade-off between centrality and redundancy without requiring an explicit query.

The original LexRank paper by Erkan and Radev (2004) defines a simpler variant called Degree Centrality LexRank. Instead of computing the principal eigenvector, this baseline simply counts the number of sentences that exceed a similarity threshold for each candidate. The sentence with the highest degree—the most neighbors in the similarity graph—is selected first. While computationally cheaper, this method lacks the recursive reinforcement of eigenvector centrality, where a sentence gains importance from being similar to other important sentences. The full eigenvector method consistently outperforms degree centrality on ROUGE evaluation benchmarks.

LexRank naturally extends to multi-document summarization by constructing a unified similarity graph across all sentences from all source documents. In this cross-document graph, sentences from different documents that discuss the same event or fact will cluster together. The eigenvector centrality computation then identifies sentences that are representative of the entire document set, not just a single document. This makes LexRank particularly effective for tasks like timeline generation from news articles or multi-case legal synthesis, where the goal is to identify the most central facts across a corpus of related legal opinions or filings.

In legal text summarization, LexRank excels at identifying ratio decidendi—the binding legal reasoning—by surfacing sentences that are structurally central to the opinion's argument graph. Legal documents exhibit high lexical repetition and formal citation structures that create dense similarity clusters around core holdings. LexRank's graph-based approach naturally identifies these clusters. However, it is limited to extractive output only; it cannot paraphrase or synthesize novel legal conclusions. For this reason, modern legal AI pipelines often use LexRank as a pre-processing step to identify salient passages before passing them to an abstractive model for final summary generation.

LexRank and TextRank are both graph-based extractive summarization algorithms inspired by PageRank, but they differ in key details. TextRank uses a weighted, undirected graph with edge weights based on lexical overlap and applies a modified PageRank formula with a damping factor. LexRank uses a cosine similarity matrix with a threshold to binarize edges and computes the stationary distribution via eigenvector decomposition. LexRank's stochastic thresholding step explicitly addresses redundancy, while TextRank relies on the graph structure alone. Empirically, LexRank tends to produce more diverse summaries, while TextRank is often more computationally efficient for very large document sets.

The original LexRank paper introduces a threshold parameter that converts the fully-connected similarity graph into a sparse graph by removing edges below a cosine similarity cutoff. This has profound algorithmic implications:

• Computational Efficiency: Sparse matrices enable faster eigenvector computation via power iteration
• Topic Segmentation: The graph may naturally partition into connected components representing distinct subtopics
• Robustness to Noise: Low-similarity edges that introduce noise into centrality scores are eliminated In legal documents with clear section boundaries, thresholding can produce implicit segmentation where each component represents a distinct legal issue. The threshold value is a critical hyperparameter requiring domain-specific tuning.