Personalized Page Rank for Named Entity Disambiguation

Maria Pershina, Yifan He, Ralph GrishmanNAACL 2015

TL;DR

This paper introduces a novel graph-based approach for Named Entity Disambiguation (NED) that leverages Personalized PageRank (PPR) to effectively combine local entity similarity with global document coherence. By carefully constraining the random walk process, their method significantly outperforms existing state-of-the-art NED systems, achieving impressive accuracy on a large-scale dataset.

What Problem Does This Paper Address?

Named Entity Disambiguation (NED) is the crucial task of linking mentions of entities in text (like "Apple") to their correct entries in a knowledge base (like Apple Inc. vs. the fruit). While knowledge bases like Wikipedia have grown immensely, accurately mapping these mentions remains challenging. Existing NED systems often rely on two types of information: local similarity (how well a mention's context matches an entity's description) and global coherence (how well entities within a document relate to each other). However, local features can miss broader context, and global features can be noisy if not properly integrated. This paper aims to bridge this gap by developing a method that effectively combines both local and global evidence, while mitigating the noise introduced by incorrect candidate entities.

Methods

The core of this paper's contribution lies in its novel graph-based approach using Personalized PageRank (PPR). Here's a breakdown:

  • Graph Construction: They build a graph where each node represents a potential link between an entity mention in the document and a candidate entity from a knowledge base (e.g., Wikipedia). Edges connect candidate entities if their corresponding Wikipedia pages link to each other.
  • Personalized PageRank (PPR): Instead of a standard PageRank, they use PPR. The key innovation here is how they "personalize" the walk. They constrain the random walk to start only from the most promising candidate for each entity mention. This is a clever way to filter out noise from incorrect candidates early in the process.
  • Coherence and Constraints: They define a "coherence" score for a candidate entity, measuring how well it fits into the document's graph. Crucially, they introduce two constraints to refine this coherence:
  • (c1) Ignore competing candidates: Candidates for the same entity mention should not contribute to each other's coherence, as only one can be correct.
  • (c2) Select highest contribution: For different entities, only the single most contributing candidate should influence coherence. This prevents a cascade of weak signals.
  • Combining Scores: The final score for a candidate is a combination of its initial similarity to the mention and its calculated coherence, weighted by an average PPR value across the graph. This ensures both local relevance and global context are considered.

Datasets

  • AIDA: The primary dataset used for evaluation is AIDA, which contains 34,965 annotated mentions across 1393 documents. Only mentions with a valid entry in Wikipedia are used, resulting in 27,816 mentions.
  • Wikipedia: A Wikipedia dump from June 14, 2014, serves as the reference knowledge base.

Key Insights and Ideas

  • Strategic PPR Personalization: The idea of starting the PPR random walk only from the most promising candidate for each mention is a brilliant way to prune the search space and reduce noise from incorrect candidates. It's a form of "intelligent filtering" before the main computation.
  • Pairwise Constraints for Coherence: The explicit constraints (c1 and c2) for calculating coherence are vital. They acknowledge that entities in a document aren't just loosely related; there's a strong assumption that only one entity can represent a given mention. These constraints enforce this, preventing noisy signals from propagating.
  • Balancing Local and Global: The paper demonstrates that a simple combination of initial similarity and a carefully computed coherence score (derived from PPR) is more effective than relying on either in isolation or using less constrained global methods.

Key Results

The proposed PPRSim method achieves state-of-the-art performance on the AIDA dataset:

  • Microaccuracy: 91.7%
  • Macroaccuracy: 89.89%

This significantly outperforms previous methods, including strong baselines like iSim (62.61% microaccuracy) and PPR (85.56% microaccuracy without constraints or initial similarity). The paper also shows that the combination of constraints (c1) and (c2) is more effective than either constraint alone.

Limitations and Future Work

  • Limitations: The paper acknowledges that the graph construction relies on Wikipedia links, and the performance might be affected by the quality and completeness of these links. While they use a large dataset, the performance on domains with sparser Wikipedia coverage is not explicitly discussed.
  • Future Work: The authors plan to explore other strategies and constraints for further noise reduction in the document graph. They also suggest investigating other ways to leverage pairwise information in NED.

Summary updated

BibTeX
@inproceedings{pershina2015personalized,
  author = {Maria Pershina and Yifan He and Ralph Grishman},
  title = {{Personalized Page Rank for Named Entity Disambiguation}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2015},
}
Figure