TextRank, LexRank and their descendants decide which words or sentences in a document matter by building a graph, linking two words when they appear near each other, and then scoring nodes by how connected they are. The weak point is the edge. Two words that merely co-occur often are linked strongly even when one is a generic filler, such as "said", "year" or "government", that appears alongside everything. Prestige-style rankings then reward exactly these hubs. We propose a different edge: link two words only if one still predicts the other after every other word in the sentence is taken into account. Graph centrality then runs on that conditional dependency graph. A filler word that co-occurs with everything carries no information that the specific words around it do not already carry, so its edges largely disappear.
Estimating such a graph exactly would mean fitting a Markov random field, a probability model over many interacting binary variables whose normalizing constant sums over exponentially many configurations. Pseudo-likelihood avoids that constant by fitting one sparse logistic regression per word, predicting the word's presence in a sentence from the presence of all other words. It is cheap, it runs per document, and it produces signed couplings: positive couplings mean "these words go together beyond what everything else explains," and negative couplings mean "these words tend to substitute for one another." The proposal is to test whether centrality computed on this learned graph selects better content than centrality on co-occurrence graphs. The prediction is that the gain comes from conditioning specifically, and that it should grow with the number of sentences available for estimation.
Core Claim
For a document or document cluster with $n$ sentences and a candidate vocabulary of $p$ words, let $x_{s} \in \{0,1\}^p$ record which words appear in sentence $s$. For each word $j$ we fit
$$\hat\theta_j = \arg\min_{\theta_j} \; -\sum_{s=1}^{n} \log P\big(x_{sj} \mid x_{s,-j};\, \theta_j\big) + \lambda \|\theta_j\|_1,$$
where $P$ is a logistic model whose weights $\theta_{jk}$ are the coupling from word $k$ to word $j$, $x_{s,-j}$ is the sentence's presence vector without word $j$, and $\lambda$ controls sparsity. We symmetrize the couplings into a matrix $W$ with $W_{jk} = \tfrac12(\hat\theta_{jk}+\hat\theta_{kj})$. Word salience is the PageRank or eigenvector centrality of the positive part of $W$, and sentences are scored by the salience of the words they contain. The claim has three parts. First, this ranking beats the same pipeline run on a raw or PMI-weighted co-occurrence graph built from the same sentences. Second, the advantage disappears on short texts, where $n$ is too small to estimate conditional structure. Third, the negative part of $W$ identifies substitutable terms, and penalizing coverage of both members of a substitute pair reduces redundancy in the selected sentences.
Relation to Prior Work
The ranking side supplies the target problem and its known failure. TextRank runs PageRank on sliding-window co-occurrence graphs for keywords and on word-overlap graphs for sentences. LexRank runs eigenvector centrality on thresholded idf-weighted cosine graphs and reports that the choice of threshold matters, with the lowest threshold of 0.1 performing best. Both build their edges from marginal statistics and never estimate them. GoWvis and a study on graph degeneracy argue that PageRank is fooled by generic hub words and replace it with $k$-core decomposition, which keeps only the densely interconnected core of the graph. That work motivates ours: we accept the diagnosis but locate the problem in how edges are built, not in which centrality is computed. Our design therefore lets us run both PageRank and $k$-core on both kinds of graph and separate the two effects. The stronger multi-document systems, SummPip with spectral clustering and sentence compression, and MRGSEM-Sum with multi-relational discourse edges and structural-entropy clustering, handle redundancy through clustering stages added after the graph is built. We do not try to replace their pipelines. We test whether a better word graph helps underneath them.
The estimation side supplies the method. Admixture of Poisson MRFs fits sparse word-dependency networks within topics, observes hub words such as "temperature" and learned negative dependencies, but never ranks nodes or selects content. We take its observation as evidence that learned dependency graphs have meaningful hubs, and we move from corpus-level topics to per-document estimation. Optimization Methods for Sparse Pseudo-Likelihood Graphical Model Selection provides fast proximal solvers (CONCORD-ISTA/FISTA) for a Gaussian-free pseudo-likelihood. We use it as an alternative estimator, so the comparison asks whether the binary Ising form matters or only conditioning does. Piecewise pseudolikelihood constrains our design. On NER, full Markov-blanket pseudo-likelihood reached 85.1 F1 against 90.3 for the piecewise variant, which warns that conditioning on everything can overfit when data are sparse. That is exactly our regime, and it is why we fit with strong $\ell_1$ sparsity, restrict the candidate vocabulary, and include a restricted-neighborhood variant that conditions only on words within the same window. Regression from Dependent Observations shows that pseudo-likelihood stays consistent from a single dependent network sample under weak coupling. Sentences in one document are not independent draws, and this result is the reason to expect per-document estimation to be meaningful rather than hopeless. Its conditions, a known topology and bounded dependence, do not hold here, so we treat it as motivation, not a guarantee. Finally, Dependence-Aware Label Aggregation for LLM-as-a-Judge via Ising Models shows that modeling correlations by pseudo-likelihood beats independence assumptions when units share failure modes. It uses ten judges as nodes, not text units, and does no ranking. It is the closest use of the same estimator, but on a different object.
Research Program
We will build a per-document estimator. It filters candidate words to nouns and adjectives, as TextRank does, caps $p$ at a few hundred by document frequency, fits the neighborhood regressions with the stability of each edge checked by bootstrap over sentences, and outputs a signed $W$. On top of it we run PageRank and $k$-core on $W^+$. Sentences are ranked by summed word salience, and greedy selection under a length budget includes an optional penalty when a candidate sentence covers a word negatively coupled to a word already selected. We will analyze how edge stability and ranking quality depend on $n$ and $\lambda$, and how hub words change rank when we move from the marginal graph to the conditional one. That last analysis is the mechanism check and is reported separately from ROUGE. A natural extension, left for later, is to replace sentence-level binary presence with the attention-derived fine layer used by RAGP for prompt compression.
Baselines
The naive reference points are lead-$k$ selection and TF-IDF sentence scoring. They tell us whether any graph is needed at all. Lead selection is strong on news, which is why both are run under the identical word budget.
The main competitor is LexRank. It is the most widely reproduced graph-centrality summarizer, and SummPip reports LexRank at ROUGE-1 38.27 on Multi-News. We rerun LexRank ourselves with the same sentence segmentation, POS filtering, length budget and a tuning budget matched to ours: twenty configurations of threshold, against twenty configurations of $\lambda$ and vocabulary cap for our method, all selected on the same development split. Beating it means a ROUGE-1 and ROUGE-2 gain whose paired bootstrap confidence interval excludes zero on the test split, not a gain over the published 38.27, which comes from a different setup. TextRank is run the same way for keywords and sentences, with its window size tuned. On Inspec, its reported keyphrase F-measure is 36.2 with window 2.
The strongest existing unsupervised systems in the file are SummPip, reported at ROUGE-1 42.32 on Multi-News and 36.30 on DUC-2004, and MRGSEM-Sum, reported at ROUGE-1 49.23 on DUC-2004. We do not expect a word-graph change inside a simple extractive selector to match MRGSEM-Sum, which adds discourse edges and sentence compression. The fair test is a substitution: reimplement SummPip's word-graph and clustering stages, swap in our conditional graph in place of its similarity-derived word graph, and hold everything else fixed. Beating SummPip means the swapped pipeline improves on our reproduction of SummPip. MRGSEM-Sum is reported as a ceiling reference only.
Three ablations isolate the key ingredient, conditioning. The first replaces $W$ with a PMI-weighted co-occurrence matrix computed from the same sentence-presence data, which keeps the same information but removes conditioning. The second replaces $W$ with partial correlations from CONCORD, which keeps conditioning but drops the binary model. The third fits the model on sentence-presence matrices whose columns are independently permuted, preserving word frequencies while destroying dependence. Under that null, centrality should collapse toward frequency ranking.
Why not just…?
Why not just reweight co-occurrence edges by PMI or idf to suppress hubs? This is the most serious threat. PMI already penalizes words that co-occur with everything, so it might capture most of the benefit without any model fitting. The PMI ablation is built to settle this: it uses the same data and the same centrality, differing only in marginal versus conditional edges. If PMI matches the conditional graph, the honest conclusion is that hub suppression, not pseudo-likelihood, is what matters, and we will report it that way. We expect a difference when two specific words are each tied to a third: PMI keeps all three pairwise edges, while conditioning removes the indirect one.
Why not just use $k$-core degeneracy, which GoWvis already uses against hub noise? GoWvis addresses hubs by changing the centrality while keeping window-based edges. Because we run $k$-core on both graph types, the experiment shows whether conditional edges add anything beyond degeneracy, and whether the PageRank-versus-$k$-core disagreement in the literature shrinks once edges are conditional.
Why not just add Maximal Marginal Relevance on top of LexRank for redundancy? This greedy penalty on similarity to already-chosen sentences is the standard fix and is likely competitive. Our negative-coupling penalty must beat LexRank with that redundancy penalty, tuned under the same budget. If it does not, we keep only the centrality claim and drop the redundancy claim.
Why not just prompt a large language model? MRGSEM-Sum reports that its graph method outperformed GPT-4-32k and GPT-3.5-turbo on Multi-News and had fewer hallucinations. This proposal, however, asks about graph construction, not about the best summarizer. An LLM is outside its scope except as context, and we do not claim to beat one.
Proposed Experiments
The main experiment covers DUC-2004 and Multi-News. It compares the baselines and ablations above with ROUGE-1, ROUGE-2 and ROUGE-L under fixed length budgets, using a development split of Multi-News for all tuning and reporting paired bootstrap intervals. The decisive check is a dose-response curve. We bin documents by sentence count, and for long documents we subsample sentences to create shorter versions. If conditioning is the cause, the gap between the conditional graph and the PMI graph should be near zero at small $n$ and should widen as $n$ grows, while the permutation null should stay flat. Inspec abstracts, at roughly ten sentences, serve as a negative control: we expect no gain over TextRank's 36.2 there, and a gain would indicate the effect comes from something other than estimation. The mechanism check measures how far the most frequent generic words fall in centrality rank between graphs, and whether the words that rise are those appearing in reference summaries. For redundancy, we measure pairwise overlap among selected sentences at matched ROUGE, comparing the negative-coupling penalty against the MMR variant of LexRank. All estimation runs per document on a CPU, and we report wall-clock time against LexRank, because a large cost gap would weaken the practical case even if quality improves.
References
- TextRank: Bringing Order into Text
- LexRank: Graph-based Lexical Centrality as Salience in Text Summarization
- GoWvis: A Web Application for Graph-of-Words-based Text Visualization and Summarization
- A Graph Degeneracy-based Approach to Keyword Extraction
- SummPip: Unsupervised Multi-Document Summarization with Sentence Graph Compression
- MRGSEM-Sum: An Unsupervised Multi-document Summarization Framework based on Multi-Relational Graphs and Structural Entropy Minimization
- Admixture of Poisson MRFs: A Topic Model with Word Dependencies
- Optimization Methods for Sparse Pseudo-Likelihood Graphical Model Selection
- Piecewise pseudolikelihood for efficient training of conditional random fields
- Regression from dependent observations
- Dependence-Aware Label Aggregation for LLM-as-a-Judge via Ising Models
- Mapping Text to Multiplex Graph: Prompt Compression as Lévy Walk-guided Graph Pruning