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.
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.
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