Graph Centrality for Salient Content Selection

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2463 papers610 conceptsfrozen 2026-10-04

When we read a long document, we don't treat every sentence with equal weight. We instinctively look for the "anchor" ideas—the central arguments that support everything else. In natural language processing, identifying these anchors is the core challenge of summarization and information retrieval. While modern Large Language Models (LLMs) often treat text as a linear sequence of tokens, a long-standing and powerful research direction treats text as a graph, using network topology to mathematically pinpoint the most important information.

By representing linguistic units (words, sentences, or concepts) as nodes and their relationships as edges, researchers apply graph centrality algorithms—like PageRank—to discover the "structural skeleton" of a document.

The Intuition: Importance as Connectivity

The fundamental hypothesis of this field is that salience is a function of connectivity. In a semantic graph, a node is considered important if it is related to many other nodes, or if it is related to other important nodes.

This approach, often referred to as graph-based ranking, allows models to move beyond simple frequency counts. As Vincent Ng 0001 notes in his survey of abstractive summarization, these methods identify the most "salient information paths" by maximizing information density within a fixed length.

Early work by Jure Leskovec, Natasa Milic-Frayling, and Marko Grobelnik in Impact of Linguistic Analysis on the Semantic Graph Coverage and Learning of Document Extracts demonstrated that even simple linguistic features, when mapped to a graph, allow Support Vector Machines to identify "summary-worthy" nodes. They found that topological attributes—like a node's degree or its position in the network—quantify importance more effectively than traditional keyword metrics.

From PageRank to TextRank

The most influential mechanism in this space is the adaptation of Google’s PageRank algorithm to text, often called TextRank. Instead of ranking web pages, the algorithm ranks words or sentences.

  1. Node Creation: Text is broken into units. These can be words (Weiming Liang et al., Extracting Keyphrases from Chinese News Articles Using TextRank and Query Log Knowledge), sentences (Arman Cohan, Scientific document summarization via citation contextualization and scientific discourse), or even abstract semantic representations (Jun Suzuki et al., Neural Headline Generation on Abstract Meaning Representation).
  2. Edge Weighting: Edges are drawn based on co-occurrence, semantic similarity (using embeddings), or grammatical dependencies (Vivi Nastase, Topic-Driven Multi-Document Summarization with Encyclopedic Knowledge and Spreading Activation).
  3. Convergence: A random walk is performed across the graph. Nodes that are frequently visited are deemed "central."

This mechanism is particularly robust against noise. Jung-Tae Lee and colleagues in Bridging Lexical Gaps between Queries and Questions on Large Online Q&A Collections with Compact Translation Models showed that graph-based ranking outperforms frequency-based metrics when filtering "noisy" datasets, as it prioritizes terms that share relationships with multiple other concepts rather than just appearing often.

Scaling to Long Contexts and GraphRAG

As the field has moved toward Large Language Models, graph centrality has found a new role: managing the "lost in the middle" problem of long-context windows. When a document is too long for an LLM to process, we must choose which parts to keep.

Recent work like Mixture-of-PageRanks (MixPR) by Nicholas Alonso (Mixture-of-PageRanks: Replacing Long-Context with Real-Time, Sparse GraphRAG) uses centrality to identify structurally significant information across million-token contexts. By treating similarities between text chunks as edges, the system can retrieve disparate facts that are connected through the document's internal network—something standard keyword search often misses.

Similarly, Yijing Liu and Yi Yang introduced G2ConS (Graph-Guided Concept Selection for Efficient Retrieval-Augmented Generation), which uses PageRank on a "Concept Graph" to slash the costs of building Retrieval-Augmented Generation (RAG) systems. They found that removing highly connected concepts from a retrieval pool causes a much sharper decline in model performance than removing peripheral ones, proving that structural importance is a reliable proxy for utility.

Beyond Simple Centrality: Hierarchy and Cohesion

Researchers have also explored more nuanced graph structures to capture the "flow" of information:

Why It Works

The enduring success of graph centrality in NLP stems from its ability to bridge the gap between local semantics (what a sentence says) and global structure (how a sentence fits into the whole).

Whether it is Ioana Hulpuş using betweenness centrality to find hidden topics in DBpedia (Kanopy: Analysing the Semantic Network around Document Topics) or Jiaxin Ju summarizing scientific papers (SciSummPip), the core intuition remains the same: the most important ideas are the ones that serve as the conceptual bridges of the text. By finding these bridges, we can condense massive amounts of information without losing the narrative thread.

Papers in this version

Showing 60 of 463 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 396 papers
  2. Version 1 · 2026-10-04 · 463 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_graph_based_centrality_ranking_e2973a81,
  title = {graph-based centrality ranking},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-centrality-ranking/rdr_e2973a819390434e859c96e6007e0095},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_graph_centrality_for_salient_content_sel_e2973a81_v1,
  title = {Graph Centrality for Salient Content Selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-centrality-for-salient-content-selection/rdr_e2973a819390434e859c96e6007e0095/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}