Finding Friends and Flipping Frenemies: Automatic Paraphrase Dataset Augmentation Using Graph Theory

Hannah Chen, Yangfeng Ji, David Evans

Abstract

Supervised NLP models are fundamentally constrained by the quality and scale of human-labeled datasets. This paper introduces a graph-theoretic framework to automatically expand and refine paraphrase datasets. By representing sentences as nodes and relationships as signed edges, we leverage transitivity to infer missing labels and structural balance theory to identify and correct labeling errors. Applied to the Quora Question Pairs (QQP) dataset, our method increases training data by over 60% and corrects critical mislabelings, resulting in a fine-tuned BERT model that achieves superior accuracy and generalization.

Introduction

Paraphrase identification—determining if two sentences share the same meaning—is a cornerstone of natural language understanding. However, the datasets used to train these models are often "noisy" and incomplete. Human annotators frequently disagree on semantic equivalence, and the sheer number of possible sentence pairs makes exhaustive manual labeling impossible. This research proposes a systematic way to mathematically infer relationships and "clean" existing data without additional human intervention.

Methodology: The Paraphrase Graph

The core innovation lies in treating a paraphrase dataset as a signed graph where nodes represent sentences and edges represent labels: positive (+) for paraphrases and negative (-) for non-paraphrases.

Finding Friends: Transitive Inference

Since paraphrasing is an equivalence relation, it must satisfy transitivity. If Sentence A is a paraphrase of B, and B is a paraphrase of C, then A and C must also be paraphrases. This logic extends to negative relationships: if A is a paraphrase of B, but B is not a paraphrase of D, then A cannot be a paraphrase of D.

The process of converting sentence pairs into a graph and inferring new relationships through transitivity.

By applying transitive closure across the entire graph, we can "fill in the blanks" for pairs that were never manually compared. In our experiments, this process expanded the QQP training set by 60.7%, adding over 250,000 new labeled pairs.

Flipping Frenemies: Structural Balance Theory

To address human error, we employ Structural Balance Theory. In a consistent semantic graph, certain configurations of relationships are stable, while others are "imbalanced" and suggest a labeling conflict.

Structural balance in triads: (a) and (b) are balanced, while (c) and (d) represent imbalanced configurations likely containing errors.

For example, a triad where A=B and B=C but A≠C (Figure 1d) is imbalanced. In such cases, the negative edge is often a human error. Our algorithm identifies these "frenemies"—negative edges that contradict a chain of positive evidence—and flips their labels to positive to restore balance. This targeted correction helps remove "noise" that can confuse machine learning models during training.

Experimental Results

We evaluated our approach by fine-tuning a BERT-base model on the original QQP dataset versus our "Augmented-Flipped" version.

  • Error Detection: The method successfully identified 90 mislabeled pairs in QQP, such as nearly identical questions that had been incorrectly marked as non-paraphrases.
  • Model Improvement: The model trained on the enhanced data outperformed the baseline across all test sets.
  • Generalization: When tested on the augmented test set, the error rate dropped from 10% to under 6%. This suggests that the augmented data helps the model better internalize the transitive nature of semantic equivalence.

Conclusion

By viewing NLP datasets through the lens of graph theory, we can move beyond the limitations of manual labeling. Our methods for "finding friends" and "flipping frenemies" provide a scalable, automated way to improve data quality and model robustness, turning noisy human labels into a mathematically consistent semantic network.

Summary updated

Abstract

Most NLP datasets are manually labeled, so suffer from inconsistent labeling or limited size. We propose methods for automatically improving datasets by viewing them as graphs with expected semantic properties. We construct a paraphrase graph from the provided sentence pair labels, and create an augmented dataset by directly inferring labels from the original sentence pairs using a transitivity property. We use structural balance theory to identify likely mislabelings in the graph, and flip their labels. We evaluate our methods on paraphrase models trained using these datasets starting from a pretrained BERT model, and find that the automatically-enhanced training sets result in more accurate models.
BibTeX
@inproceedings{chen2020finding,
  author = {Hannah Chen and Yangfeng Ji and David Evans},
  title = {{Finding Friends and Flipping Frenemies: Automatic Paraphrase Dataset Augmentation Using Graph Theory}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2020},
  doi = {10.18653/v1/2020.findings-emnlp.426},
}
Figure