Abstract
Named Entity Disambiguation (NED) is a critical task in natural language processing, yet state-of-the-art neural models often fail in low-resource domains where annotated data and detailed entity descriptions are scarce. We present GST-NED, an unsupervised approach that frames NED as a Group Steiner Tree (GST) problem. By identifying the most cohesive set of entities within a knowledge graph, GST-NED achieves significant performance gains over existing unsupervised methods without requiring any training data.
Introduction
Named Entity Disambiguation (NED) involves mapping entity mentions in text to their corresponding entries in a knowledge base (KB). While modern models like BLINK or GENRE excel in general domains like Wikipedia, they are notoriously "data-hungry," requiring vast amounts of annotated training data and rich entity descriptions. In "low-resource" contexts—such as digital humanities, legal archives, or specialized museum collections—these resources are often unavailable. GST-NED addresses this gap by leveraging the structural properties of knowledge graphs (KGs) to perform collective disambiguation.
Methodology: The Group Steiner Tree Approach
GST-NED operates in two primary phases: candidate generation and candidate ranking.
- Candidate Generation: For each mention in a document, the system identifies potential matches in the KG using fuzzy text search.
- Candidate Ranking via GST: Rather than disambiguating mentions in isolation, GST-NED treats the document as a collective unit. It constructs a subgraph of the KG containing all potential candidates for all mentions. The problem is then modeled as finding a Group Steiner Tree (GST).
In graph theory, a Steiner Tree is the minimum-cost tree connecting a specific set of nodes. In the Group Steiner Tree variant, nodes are organized into groups (one group per mention), and the goal is to find the minimum-cost tree that includes at least one node from every group. This approach is rooted in the "cohesion hypothesis": correct entities in a document are contextually related and thus likely to be proximal within the knowledge graph.
Datasets and Evaluation
The efficacy of GST-NED was evaluated across four distinct low-resource domains: WWO (Women Writers Online), 1641 (17th-century Irish Rebellion legal statements), Artifact (Getty Arts and Architecture Thesaurus), and Chemical (biomedical annotations). These datasets feature domain-specific KGs with sparse entity descriptions, making them challenging for traditional neural models.
Key Results
GST-NED consistently outperformed both simple baselines and sophisticated unsupervised models like WalkingNED and Eigenthemes.
As shown in the results table, GST-NED achieved a Precision@1 of 0.57 on the WWO dataset, a substantial improvement over the 0.35 achieved by the next best baseline. Across all datasets, the method demonstrated an average performance increase of approximately 40%. Notably, the fine-tuned neural model (BLINK*) performed poorly, underscoring the limitations of supervised models in niche, data-scarce environments.
Discussion and Insights
The success of GST-NED highlights several key insights:
- Collective Disambiguation: The identity of one mention provides vital context for others. By resolving all mentions simultaneously, the system uses the graph's structure to filter out noise.
- Ranking Robustness: The authors found that ranking candidates based on their frequency in the top k least-cost trees (GST count) was more effective than simply using the single minimum-cost tree.
- Neural Fragility: The failure of heavyweight neural models in these domains suggests that structural graph-based methods remain essential for specialized applications.
Limitations and Future Work
Despite its strengths, GST-NED faces challenges regarding entity density; the cohesion logic is less effective in documents with very few mentions. Additionally, the computational complexity of finding Steiner Trees (an NP-complete problem) can lead to longer processing times for large graphs. Future research will focus on scaling these graph algorithms and addressing rare cases of polysemy within a single document.
Summary updated