Abstract
In this work, we propose a novel segmental hypergraph representation to model overlapping entity mentions that are prevalent in many practical datasets. We show that our model built on top of such a new representation is able to capture features and interactions that cannot be captured by previous models while maintaining a low time complexity for inference. We also present a theoretical analysis to formally assess how our representation is better than alternative representations reported in the literature in terms of representational power. Coupled with neural networks for feature learning, our model achieves the state-of-the-art performance in three benchmark datasets annotated with overlapping mentions.
Introduction: The Challenge of Overlapping Mentions
Traditional Named Entity Recognition (NER) systems typically treat the task as a sequence labeling problem, assuming that entity mentions are non-overlapping "flat" spans. However, in many real-world scenarios—particularly in the biomedical and news domains—mentions are often nested or overlapping.
As shown in the examples above, a single phrase like "the Seattle zoo" can contain a Geo-political entity ("Seattle") nested within a Facility ("the Seattle zoo"). Standard sequence labeling models struggle here because they cannot assign multiple tags to the same token. While previous graph-based solutions attempted to solve this, they often suffered from structural ambiguity, where a single graph structure could represent multiple conflicting sets of mentions, leading to errors during inference.
Methodology: Segmental Hypergraphs
To address these limitations, we propose a Segmental Hypergraph representation. A hypergraph generalizes a standard graph by allowing edges (hyperedges) to connect any number of nodes.
Our model utilizes specific nodes to track the start, duration, and end of mentions. We introduce "I-nodes" ($I^k_{i,j}$) that represent a mention of type $k$ starting at word $i$ and continuing through word $j$. This structure allows the model to "remember" the boundaries of a mention as it traverses the sentence, effectively eliminating the ambiguity found in earlier work.
For feature learning, the model employs two layers of Bidirectional LSTMs:
- Word-level: Captures the context of individual words.
- Span-level: Aggregates word-level features into representations of entire segments (spans).
Inference is performed using a generalized "inside-outside" message-passing algorithm. This approach finds the most likely set of mentions with a time complexity of $O(cmn)$, where $n$ is sentence length, $m$ is the number of entity types, and $c$ is the maximum mention length. This is significantly more efficient than the $O(n^3)$ complexity required by traditional parsing-based approaches for nested NER.
Theoretical Comparison and Efficiency
A key contribution of this work is the formal proof that our hypergraph maintains a one-to-one correspondence between paths in the graph and valid mention combinations. This solves the "spurious structure" and "structural ambiguity" issues that plagued previous segmental models.
As summarized in the table above, our model is the first to simultaneously eliminate structural ambiguity and spurious structures while maintaining linear time complexity relative to sentence length (when $c$ is constant).
Experimental Results
We evaluated the model on three standard benchmarks known for overlapping mentions: ACE-2004, ACE-2005, and GENIA.
- State-of-the-Art Performance: The model outperformed all previous methods across these datasets. On ACE-2005, it achieved an F1-score of 74.5, a significant improvement over previous hypergraph and sequence labeling models.
- Robustness: Even on "flat" datasets like CoNLL-2003, the model remained competitive with specialized NER systems, proving that the ability to handle overlaps does not come at the cost of standard performance.
- Ablation Studies: The inclusion of character-level embeddings and a "softmax-margin" loss (which penalizes false negatives more heavily) were critical for achieving high recall in complex, nested sentences.
Conclusion
Neural Segmental Hypergraphs provide a robust and efficient framework for recognizing overlapping entity mentions. By eliminating structural ambiguity and maintaining low time complexity, this approach offers a scalable solution for complex information extraction tasks in specialized domains like medicine and law. Future work will explore extending this framework to handle discontinuous mentions, such as "muscle and joint pains."
Summary updated