Graph Centrality for Entity Disambiguation and Ranking

24 concepts18 papers1 proposal

When a natural language processing system encounters an ambiguous name like "Washington," local context clues (such as nearby verbs or adjectives) can only go so far. If the text is brief, noisy, or cross-lingual, local context often dries up entirely. Humans resolve this ambiguity effortlessly because we maintain a global mental model of how entities relate to one another. If a document mentions "Washington," "Seattle," and "Starbucks," we instantly know "Washington" refers to the state, not the president or the capital city.

To replicate this intuition computationally, researchers map text onto structural networks—either by building document-specific entity graphs or by projecting mentions directly onto massive, pre-existing Knowledge Graphs (KGs) like Wikipedia or DBpedia. By analyzing the topology of these graphs, systems can leverage structural properties like centrality, reachability, and link density to rank candidates, resolve ambiguities, and extract the most salient information.

Global Popularity Priors and Structural Prominence

Before considering the specific context of a document, some entities are simply more prominent in human discourse than others. In a graph representation of a knowledge base, this prominence manifests directly as structural connectivity.

As Dredze et al. (2010) demonstrated, global importance metrics derived from a knowledge graph's link structure—such as PageRank or simple in-degree and out-degree statistics—provide an incredibly robust prior probability. When local context is insufficient to distinguish between two entities with the same name, defaulting to the node with the higher structural prominence significantly boosts accuracy.

This structural property is equally powerful in question-answering and conversational systems. For instance, Li et al. (2018) found that knowledge graph entities with a higher out-degree are statistically far more likely to be the subject of natural language queries. Intuitively, a node with many outgoing edges represents a topic with a wealth of facts connected to it, making it a natural "magnet" for user curiosity.

Expanding on this idea for multi-turn dialogues, Lan et al. (2021) utilized out-degree connectivity to predict how conversational focus shifts over time. Their work demonstrates that highly connected entities serve as reliable anchors for predicting the next logical question in a sequence, as users naturally traverse the existing edges of the knowledge topology.

Semantic Triangulation and Random Walks

While global priors help establish a baseline, resolving a document's true meaning requires enforcing global coherence across all mentions simultaneously. If a text contains multiple ambiguous names, choosing the correct entity for one should automatically clarify the others. This process is often described as "semantic triangulation."

Liu et al. (2011) pioneered this by constructing a graph of all candidate entities mentioned in a document and measuring their connectivity via Wikipedia's internal hyperlink structure. High link density or in-degree among a cluster of candidates signals that they belong to the same semantic context. To formalize this mathematically, researchers widely adopt the Personalized PageRank (PPR) algorithm.

In a standard PageRank setup, a random walker traverses the graph uniformly. In Personalized PageRank, however, the walker is periodically "teleported" back to a specific set of seed nodes—in this case, the nodes corresponding to the observed mentions in the text. As shown by Gurevych et al. (2012) and Liu et al. (2017), this mechanism calculates a "semantic signature" for the entire document. The candidates that receive the highest visit frequency from the random walker are those that are most structurally reachable from all other mentions combined.

By treating the knowledge base as a unified network, Barrena et al. (2015) demonstrated that this link-analysis approach enforces global coherence so effectively that it can outperform heavily supervised models without requiring any hand-labeled training data. The network structure itself filters out the noise: incorrect candidates remain isolated or poorly connected to the rest of the document's theme, causing the random walker to quickly abandon them.

Identifying Core Salience and Summarization

The utility of graph centrality extends beyond resolving ambiguity; it is also a powerful tool for distillation. When extracting information or summarizing a massive knowledge graph, systems must distinguish between core subjects and peripheral noise.

In information extraction tasks like template filling, Jean‐Louis et al. (2011) and Besançon et al. (2012) modeled extracted entity relationships as a document graph. By applying centrality algorithms like PageRank to this topology, the systems could identify which entity was truly central to the discourse, allowing them to accurately fill specific template slots. Similarly, Stewart et al. (2019) applied betweenness and degree centrality to extracted knowledge triples to automatically isolate significant "anchor entities," effectively filtering out peripheral details for cleaner data visualization.

This topological intuition also underpins how we evaluate document relevance and summarize knowledge graphs. Zhang et al. (2014) proposed that the importance of a topic within a document can be measured by the size of the largest connected component containing its representative entity within a document-specific subgraph. If an entity is part of a massive, interconnected component, it is structurally integrated into the document's core narrative. Conversely, isolated nodes represent passing mentions.

This structural filtering is vital for extractive knowledge graph summarization, where, as surveyed by Wang et al. (2024) and detailed by Liu et al. (2019), topology-driven centrality metrics are used to compress billions of triples into concise, human-readable subgraphs that preserve the core identity of the underlying data.

Even in noisy, multimodal settings, Zhang et al. (2022) showed that PageRank-based algorithms can successfully filter out social media stream noise to identify the most central, representative prototype data points for knowledge learning. Finally, Nanni et al. (2016) demonstrated that analyzing the hyperlink symmetry and frequency between a central event page and potential entity pages allows researchers to quantify entity relatedness for retrospective analyses of complex historical events.

Key Foundational Work

Entity Disambiguation for Knowledge Base Population (2010) — contributed 2 concept elements to this direction.
Text Segmentation and Graph-based Method for Template Filling in Information Extraction (2011) — contributed 1 concept elements to this direction.
HIT Approaches to Entity Linking at TAC 2011 (2011) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

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

This exact version (version 1, frozen text):

@misc{lacuna_graph_based_entity_ranking_1bc912f2_v1,
  title = {graph-based entity ranking},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-entity-ranking/rdr_1bc912f2eb9e4aa38b0ebeb7a1defee6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake