HFMRE: Constructing Huffman Tree in Bags to Find Excellent Instances for Distantly Supervised Relation Extraction

Min Li, Cong Shao, Gang Li, Mingle Zhou

Introduction

Relation Extraction (RE) is a fundamental task in natural language processing, aimed at identifying semantic relationships between entities in text. For instance, recognizing that "Steve Jobs co-founded Apple" implies a founder relationship. While effective, supervised RE requires vast amounts of manually labeled data. To address this, Distant Supervision (DS) automatically generates labels by aligning text with knowledge graphs.

However, DS introduces significant noise. A sentence like "I spent my summer vacation in Paris, France" might be incorrectly labeled with a capital_of relation simply because a knowledge graph contains that fact, even if the sentence doesn't express it. Current Multi-Instance Learning (MIL) strategies, such as averaging (AVG), attention (ATT), or selecting the single best sentence (ONE), often fail because they treat sentences as independent entities, ignoring the intrinsic associations within a "bag" of sentences.

Methods: The HFMRE Framework

The proposed HFMRE (Huffman Tree for Relation Extraction) framework shifts from simple aggregation to an iterative denoising process that leverages sentence consensus.

Sentence Encoding and Circular Cosine Similarity (CCS)

Sentences are first transformed into high-dimensional vectors using a Pre-trained Language Model (PLM) like BERT. The core innovation is Circular Cosine Similarity (CCS). Unlike standard attention mechanisms that compare sentences to an external query, CCS calculates the similarity of each sentence to every other sentence in the bag. Sentences that are similar to many others are considered more likely to express the true relation, while outliers are treated as noise.

Huffman Tree Construction and Denoising

HFMRE treats sentences as leaf nodes in a Huffman tree, with their CCS scores serving as weights. The algorithm iteratively merges the two nodes with the lowest weights—the most probable noise. During merging, a reduction factor ($\alpha$) is applied to the lower-weight node to dampen its influence. This process continues until a single root node, the "excellent instance," is formed, representing the distilled features of the entire bag.

The HFMRE architecture: from sentence encoding via BERT to CCS calculation, Huffman tree construction, and final relation classification.

Experimental Results

The model was evaluated on three major benchmarks: NYT10d, NYT10m, and Wiki20m.

Performance Metrics

HFMRE achieved state-of-the-art results on the NYT10d dataset, reaching an Area Under the Curve (AUC) of 54.0, a 3.2-point improvement over the previous best model (CIL). It also demonstrated high reliability with a Precision at M (P@M) score of 86.4.

Precision-Recall curves on the NYT10d dataset, showing HFMRE outperforming various baseline models across most recall levels.

Ablation Studies

Ablation tests confirmed the importance of the Huffman tree structure. Removing this component led to a significant performance drop (e.g., 12.2 points in AUC on NYT10m), indicating that the tree-based denoising is the primary driver of the model's success, rather than the choice of encoder alone.

Conclusion and Future Work

HFMRE provides a robust method for denoising distantly supervised data by identifying "excellent instances" through consensus. While the current implementation faces some computational overhead for very large bags, it offers a general-purpose improvement for MIL tasks. Future research may explore multilingual applications and the simultaneous construction of positive and negative trees to further enhance discriminative power.

Summary updated

Abstract

Since the introduction of distantly supervised relation extraction methods, numerous approaches have been developed, the most representative of which is multi-instance learning (MIL). To find reliable features that are most representative of multi-instance bags, aggregation strategies such as AVG (average), ONE (at least one), and ATT (sentence-level attention) are commonly used. These strategies tend to train third-party vectors to select sentence-level features, leaving it to the third party to decide/identify what is noise, ignoring the intrinsic associations that naturally exist from sentence to sentence. In this paper, we propose the concept of circular cosine similarity, which is used to explicitly show the intrinsic associations between sentences within a bag. We also consider the previous methods to be a crude denoising process as they are interrupted and do not have a continuous noise detection procedure. Following this consideration, we implement a relation extraction framework (HFMRE) that relies on the Huffman tree, where sentences are considered as leaf nodes and circular cosine similarity are considered as node weights. HFMRE can continuously and iteratively discriminate noise and aggregated features during the construction of the Huffman tree, eventually finding an excellent instance that is representative of a bag-level feature. The experiments demonstrate the remarkable effectiveness of our method, outperforming previously advanced baselines on the popular DSRE datasets.
BibTeX
@inproceedings{li2023hfmre,
  author = {Min Li and Cong Shao and Gang Li and Mingle Zhou},
  title = {{HFMRE: Constructing Huffman Tree in Bags to Find Excellent Instances for Distantly Supervised Relation Extraction}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2023},
  doi = {10.18653/v1/2023.findings-emnlp.854},
}
Figure