Joint Extraction and Labeling via Graph Propagation for Dictionary Construction

Doo Soon Kim, Kunal Verma, Peter Z. YehAAAI 2013 · DOI

Introduction

Dictionary construction—the process of identifying and categorizing entities like company names or medical supplies—is a foundational task in Information Extraction (IE). Traditionally, this follows a linear "extract then label" pipeline. First, an extractor identifies candidate token boundaries; then, a labeler assigns categories to these tokens.

However, this pipeline suffers from "aggressive commitment." If an extractor incorrectly identifies "teething" as a complete entity when the source text contains "teething blanket," the labeler is forced to categorize a fragment. Once a boundary decision is made, it cannot be corrected. This is particularly problematic in unstructured or "noisy" domains, such as informal advertisements or semi-structured medical documents, where standard parsers often fail.

Methodology: Joint Inference with ME Edges

To address these limitations, this research proposes a joint extraction and labeling framework based on semi-supervised graph propagation. In a standard graph propagation model, nodes represent tokens and edges represent similarities. Labels flow from a small set of "seed" nodes to unlabeled ones.

The authors extend this framework with Mutually Exclusive (ME) edges. When two candidate tokens overlap in the same text span (e.g., "teething" vs. "teething blanket"), they are connected by an ME edge. This allows the graph to maintain ambiguity rather than forcing a premature choice.

Illustration of Mutually Exclusive (ME) edges between overlapping candidate tokens.

During label propagation, if a node receives a high-confidence label, it sends a signal across its ME edges to push competitor nodes toward a "null" label ($\phi$). This mechanism allows labeling evidence to effectively "de-select" incorrect token boundaries. For example, if "teething blanket" is strongly identified as an infant product, its overlapping fragments ("teething" and "blanket") are suppressed.

Experimental Setup

The system was evaluated on two challenging datasets:

  1. Medical Tenders: 2,200 documents containing bid requests for medical supplies (e.g., "Sodium Chloride").
  2. Infant Product Ads: 10,500 informal Craigslist-style advertisements (e.g., "child rocking chair").

The proposed model, OURJOINT, was compared against several pipeline baselines and a BASEJOINT model that lacked the specific ME edge suppression logic.

Key Results

The experimental results confirm that joint learning systems significantly outperform pipeline-based approaches. As shown in the F1-score analysis, both joint models maintained a substantial lead over the baselines across varying seed ratios.

F1-score performance comparison across Medical Tenders and Infant Product Ads datasets.

The inclusion of ME edges specifically boosted precision. By treating token competition as a soft constraint, the system avoids the pitfalls of early commitment, allowing the iterative propagation process to accumulate evidence before finalizing boundaries.

Conclusion

This work demonstrates that the category of a word provides vital evidence for its boundaries. By breaking the traditional pipeline and allowing labeling confidence to correct extraction errors, the joint graph propagation framework achieves higher accuracy in messy, real-world data. Future work will focus on scaling these algorithms to handle larger datasets and incorporating more complex structural features from documents.

Summary updated

BibTeX
@inproceedings{kim2013joint,
  author = {Doo Soon Kim and Kunal Verma and Peter Z. Yeh},
  title = {{Joint Extraction and Labeling via Graph Propagation for Dictionary Construction}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8597},
}
Figure