Utilizing Graph Measure to Deduce Omitted Entities in Paragraphs

Eun-kyung Kim, Kijong Han, Jiho Kim, Key-Sun ChoiCOLING 2018

TL;DR

This paper tackles the challenge of extracting relationships between entities when those entities are not explicitly mentioned in the same sentence, a common issue in natural language processing. They propose a novel method using graph-based "salience" measures to identify key entities within a paragraph, which then helps deduce missing arguments for relation extraction, thereby improving overall accuracy.

What Problem Does This Paper Address?

Extracting structured relationships (like "person X works for company Y") from unstructured text is a fundamental task in NLP. Traditional methods often rely on distant supervision, where sentences containing mentions of two entities are assumed to express a relationship. However, this approach struggles when entities and their relationships span across multiple sentences, a frequent occurrence in natural language, especially in sources like Wikipedia where content is often focused on a single entity. This "omitted entity" problem leads to incomplete or inaccurate relation extraction. Furthermore, existing solutions often depend on complex parsers or pipelined approaches that can propagate errors.

Methods

The core of this paper's contribution lies in its approach to identifying "salient entities" within a paragraph. Instead of relying on syntactic parsing, they construct a graph where nodes represent entities and edges represent relationships (even if implicit). They then use standard graph measures to rank entities based on their "salience," defined as their impact on the paragraph's cohesion. This salience score is then used to infer missing entities. The process involves:

  1. Graph Construction: Building a graph from entities and relationships within a paragraph, without full syntactic parsing.
  2. Salient Entity Identification: Ranking entities using graph measures to determine which ones are most central to the paragraph's theme.
  3. Omitted Entity Deduction: Using the identified salient entities to infer missing arguments for relation extraction.

This method aims to overcome the limitations of sentence-level analysis and complex NLP pipelines by leveraging paragraph-level context and graph-based centrality.

Datasets

The experiments were conducted using the Korean Wikipedia corpus (dumps on July 2017) and the Korean DBpedia Knowledge Base. The authors transformed Wikipedia links into entity annotations and used a multi-class logistic regression classifier for relation classification. For evaluation, they created a "gold standard" by having ten college students judge the correctness of noisy data generated by the distant supervision assumption to mitigate false negatives.

Key Insights and Ideas

  • Paragraph-level context is crucial: Focusing solely on individual sentences is insufficient for accurate relation extraction when entities are omitted.
  • Graph-based salience is effective: Measuring entity importance through graph centrality provides a robust way to identify key players in a narrative, even without deep linguistic analysis.
  • Deducing omitted entities improves accuracy: By inferring missing arguments based on salient entities, the system can capture more relationships than traditional methods.
  • Bridging the gap for low-resource languages: The approach is particularly promising for languages that lack advanced NLP tools, as it relies less on complex parsing.

Key Results

The paper demonstrates that their proposed sentence augmentation method, which adds deduced omitted entities, leads to higher performance compared to the conventional distant supervision paradigm. Table 1 shows that their "Centrality" based method achieved the highest F1-score (0.52) among the evaluated baselines, outperforming methods relying on title mentions, maximum frequency, or first sentence mentions. This indicates that their graph-based salience detection is effective in improving relation extraction.

Limitations and Future Work

The authors acknowledge that while their method improves upon existing approaches, incorrectly augmented sentences can still negatively impact relation extraction performance, as seen in the comparative performance between "A (Title)" and "Standard." They suggest that their approach has promising potential for languages lacking advanced NLP tools, implying future work could focus on expanding this to more languages and exploring further applications. The paper also mentions the challenge of data sparseness in relation extraction and how their method alleviates this by reducing reliance on distant supervision assumptions.

Summary updated

BibTeX
@inproceedings{kim2018utilizing,
  author = {Eun-kyung Kim and Kijong Han and Jiho Kim and Key-Sun Choi},
  title = {{Utilizing Graph Measure to Deduce Omitted Entities in Paragraphs}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2018},
}
Figure