To pick the most important sentences from a large pile of news articles, one common approach builds a graph. Sentences link to the words and named entities they contain, and articles link to their sentences. A random-walk score such as PageRank then ranks the sentences. This breaks down at two points that are usually treated separately. On a single large event cluster, the walk is pulled toward generic entities like "United States" or "police," which connect the real story to the roughly 18% of unrelated articles that web-crawled clusters contain (WCEP). On a graph spanning millions of articles and split across machines, those same high-degree nodes cross every partition and dominate network traffic. Graph systems handle hubs by cutting them: RWDISK turns hubs into "sinks" (nodes where random walks stop) and gets faster and more accurate (Fast Nearest-Neighbor Search in Disk-Resident Graphs). Text models instead treat hubs as the bridges that carry meaning between sentences (HeterSumGraph). Both views are partly right, because there are two kinds of hubs.
We propose to tell them apart by cohesion rather than by degree. A hub whose sentences all fall inside one densely connected region of the graph is a topical anchor and should stay active. A hub whose sentences scatter across many unrelated dense regions is generic glue and should become a sink. One rule then does two jobs. It removes noise from centrality ranking within an event, and it removes most cross-machine messages in a distributed graph, because the cut hubs are the ones that span partitions.
Core Claim
Our hypothesis is a single criterion for each hub. The criterion is how many distinct cohesive regions its neighbors spread over, with regions computed by degeneracy (the k-core decomposition, which repeatedly peels off weakly connected nodes until a dense nucleus remains). Sinking hubs that score high on this criterion should give two results at once. First, it should rank sentences in large noisy clusters better than keeping all hubs, sinking by degree, or down-weighting by inverse document frequency. Second, it should cut the communication cost of distributed personalized PageRank on a corpus-wide graph by close to the share of cross-partition edges those hubs carry, while recovering event articles at least as well as unpruned walks. The method is new in using degeneracy structure to decide which hubs to sink. Degree-based sinking ignores semantics. Neural pooling ignores scale. Corpus-frequency weighting ignores local context.
Positioning Against Prior Work
Three lines of work supply the ingredients.
The first is degeneracy-based text ranking. A Graph Degeneracy-based Approach to Keyword Extraction shows that k-core and k-truss selection (dens, inf, CoreRank) beats TextRank by over 5.5 absolute F1 on short and medium documents, because PageRank favors hubs that span topics. We reuse its premise that cohesion beats popularity. We move it from single-document word graphs to typed graphs of words, entities, sentences, and documents, and use it to gate walks rather than to select keywords directly.
The second is hub handling for scale. RWDISK motivates the sinking operation and reports a 3× speedup, about 4× better link prediction, and 2–4 GB of RAM where METIS needed 80 GB on LiveJournal. Its sinking is purely by degree on homogeneous graphs, and that is exactly what we test against.
The third is heterogeneous centrality. Efficient Betweenness Centrality Computation over Large Heterogeneous Information Networks computes meta-path betweenness on structured networks such as DBLP and IMDb, with compression that cut DBLP runtime from 20.45 to about 0.5 hours. It runs on one machine, and it has not been tried on document hierarchies. Betweenness is also costly and the wrong signal here: generic hubs have high betweenness by construction. We therefore use it as a contrast, not as the scoring function.
On the text side, HGSUM (Compressed Heterogeneous Graph for Abstractive Multi-Document Summarization) builds a three-level word–sentence–document graph and selects sentences with learned attention pooling in GPU memory. It reaches 50.64 ROUGE-1 on Multi-News, but it is limited to small clusters or the WCEP-100 subset. CFGNN also splits graphs into hub "cores" and "fringes" via hub labeling for scalable message passing. However, its cores are hubs chosen for shortest-path coverage, so they are kept by design, and it has only been run on molecular and synthetic graphs.
On the systems side, PEGASUS gives the MapReduce PageRank template, Partout motivates partitioning by access pattern, and GraphMineSuite gives parallel set-algebra degeneracy ordering, which it speeds up by more than 2×. We use these as building blocks rather than contributions.
Research Program
Graph and regions. We build a typed graph. Article nodes link to their sentences. Sentence nodes link to content words and to named-entity strings, the latter from a lightweight tagger only, to avoid the heavy parsing pipelines criticized in Two-phase Multi-document Event Summarization. There are no direct sentence–sentence edges, following HeterSumGraph. Hub candidates are word or entity nodes above a degree threshold $\tau$. We temporarily remove these candidates and run a parallel k-core decomposition on the remaining graph. Connected pieces of the high-core subgraph serve as cohesive regions $g$.
Dispersion score and sinking rule. For each candidate hub $h$, let $p_g(h)$ be the fraction of its sentence neighbors that lie in region $g$. Its dispersion is
$$D(h) = -\sum_g p_g(h)\log p_g(h),$$
so $e^{D(h)}$ is the effective number of regions the hub touches. A hub with $D(h)$ above a threshold $\delta$ becomes a sink: it absorbs walk probability and emits none. Hubs below $\delta$ are reinserted as active routers. One optional refinement pass recomputes the regions with the kept hubs included.
Ranking. Sentence ranking is personalized PageRank on the gated graph. In a given cluster it is seeded uniformly. Over the whole corpus it is seeded from one seed article. We also try a CoreRank-style variant that sums the core numbers of a sentence's word neighbors.
Distribution. In the distributed setting, partitions follow the cohesive regions. Each sunk hub is copied locally into every partition as a sink, so it generates no messages. Kept hubs are replicated with normal message exchange. Per-iteration communication is then roughly the number of cross-partition edges incident to kept nodes. That is the source of the predicted reduction: it equals the share of cut edges that touch sunk hubs, which we measure directly.
Analysis. We will characterize which hubs get sunk and which get kept, for example broad national entities versus event-specific people and places. We will also check whether high-$D$ hubs are the ones linking event articles to noise articles.
Baselines
Do nothing. The naive reference is a fine-tuned PRIMERA generator (PRIMER) fed the cluster's articles concatenated and truncated to its 4,096-token window. This is what practitioners do by default. PRIMERA is reported at 46.1 ROUGE-1 on WCEP, the bar a selector-plus-PRIMERA pipeline must clear. We will rerun it on the same split, since the reported cluster version may differ from our full-cluster setting.
Shared protocol. Every selector runs with the same frozen PRIMERA checkpoint and the same token budget, so differences come only from which sentences are chosen. Each graph method gets the same hyperparameter search budget on the validation split, over the restart probability and over $\tau$ and $\delta$ or their analogues.
Homogeneous PageRank. The sentence-similarity PageRank filter used in DALE is the strongest cheap graph competitor. It is trivially distributable as repeated sparse matrix–vector products in the PEGASUS style. Beating it shows the typed graph and the gating add value beyond centrality alone.
Unpruned heterogeneous PageRank. The same typed graph with no sinking isolates whether gating matters at all.
Degree-based sinking. Sinking the top hubs by degree, as in RWDISK, with the number of sunk hubs matched to ours. This ablation isolates the key ingredient: if it matches us, cohesion adds nothing over degree.
Inverse-document-frequency weighting. Edges down-weighted by corpus-level and by cluster-level inverse document frequency, again budget-matched.
Embedding-centroid selection. Sentences ranked by similarity to the cluster mean of sentence embeddings.
Neural graph selection. HGSUM is the strongest neural graph method. It reports 50.64 ROUGE-1 on Multi-News, against PRIMERA's 49.9. On WCEP-100, no reported result was found on Lacuna for HGSUM. We will run it at increasing cluster sizes on one GPU and report both its scores and the cluster size at which it runs out of memory.
Reference points. The WCEP oracle (0.558 ROUGE-1) and the best supervised extractive system TSR (0.353) bound the range.
Beating the field means a statistically significant ROUGE-1 and ROUGE-2 gain over the best of degree-sinking, inverse-document-frequency weighting, and centroid selection on full WCEP clusters, with no loss on Multi-News.
Why not just…?
Why not just down-weight frequent words by inverse document frequency? This is the most serious threat, because it is the classic fix for generic terms. The difference is a testable claim. Corpus frequency penalizes an entity that is common across the whole corpus even when it anchors this particular event. Cluster-level frequency penalizes the event's own protagonist, who appears in every article. Dispersion asks a different question: whether the hub's sentences form one cohesive region or many. We run both frequency variants with the same number of affected hubs. If either matches dispersion on WCEP selection and on cluster recovery, we will report the contribution as a systems-only result about partitioning.
Why not just rank sentences by closeness to an embedding centroid? It is cheap, parallel, and strong on clean clusters. With about 18% noise and several sub-events per cluster, however, the centroid drifts toward whatever dominates by volume. We test this directly on clusters stratified by noise rate, and on sub-sampled clusters where we inject extra noise articles. Our hypothesis is that centroid selection degrades with noise faster than gated walks do. If it does not, the graph is unnecessary for selection.
Why not just run homogeneous TextRank, which already distributes easily? Tixier et al. show that PageRank is biased toward topic-spanning hubs, and EoG (Connecting the Dots) shows that typed graphs reach links between sentences that flat graphs miss: inter-sentence F1 rose from 11.7% to 50.9%. That evidence comes from other tasks, though. The DALE-style baseline under identical budgets settles it here.
Why not just use a longer-context model? At 235 articles per cluster, no 4,096-token model sees the input; the selection problem remains. HGSUM's gains over PRIMERA on Multi-News suggest that structure helps even when the input fits.
Proposed Experiments
Selection on full WCEP clusters. Using full clusters of about 235 articles, we report ROUGE-1, ROUGE-2, and ROUGE-L of PRIMERA outputs, plus the oracle ROUGE of the selected sentences. We also report the noise share among selected sentences. As a proxy for noise labels, we treat articles cited directly by the portal as on-topic and crawled additions as candidates, and we verify the proxy on a manually labeled sample.
Corpus-wide distributed ranking. We build one typed graph over all 2.39 million WCEP articles, partitioned across a commodity cluster. Seeded from a single article per event, personalized PageRank must recover that event's articles. We measure recall at the cluster size, along with bytes communicated per iteration, wall-clock time, and peak memory per machine, under each sinking policy. The decisive check is joint. Cohesion sinking should cut communication by roughly the measured share of cut edges on sunk hubs, while matching or exceeding the unpruned walk's recall. Degree sinking should save similar traffic but lose recall.
Sanity checks. On Multi-News, where clusters are small, we expect parity with the unpruned graph, compared against the reported HGSUM and PRIMERA numbers. On Hulth2003, Marujo2012, and SemEval keyword extraction, we confirm that sinking does not harm CoreRank.
Sensitivity. We sweep $\tau$ and $\delta$ to show whether a single setting transfers across both regimes. If it does not, that is a real limitation of the method.
References
- A Large-Scale Multi-Document Summarization Dataset from the Wikipedia Current Events Portal
- Fast nearest-neighbor search in disk-resident graphs
- Heterogeneous Graph Neural Networks for Extractive Document Summarization
- A Graph Degeneracy-based Approach to Keyword Extraction
- Efficient Betweenness Centrality Computation over Large Heterogeneous Information Networks
- Compressed Heterogeneous Graph for Abstractive Multi-Document Summarization
- Bridging Indexing Structure and Graph Learning: Expressive and Scalable Graph Neural Network via Core-Fringe
- Mining Billion-Node Graphs: Patterns, Generators and Tools
- Partout: a distributed engine for efficient RDF processing
- GraphMineSuite: Enabling High-Performance and Programmable Graph Mining Algorithms with Set Algebra
- Two-phase Multi-document Event Summarization on Core Event Graphs
- PRIMER: Pyramid-based Masked Sentence Pre-training for Multi-document Summarization
- DALE: Generative Data Augmentation for Low-Resource Legal NLP
- Connecting the Dots: Document-level Neural Relation Extraction with Edge-oriented Graphs