Abstract
Paraphrases are important linguistic resources for a wide variety of NLP applications. Many techniques for automatic paraphrase mining from general corpora have been proposed. While these techniques are successful at discovering generic paraphrases, they often fail to identify domain-specific paraphrases (e.g., {staff, concierge} in the hospitality domain). This is because current techniques are often based on statistical methods, while domain-specific corpora are too small to fit statistical methods. In this paper, we present an unsupervised graph-based technique to mine paraphrases from a small set of sentences that roughly share the same topic or intent. Our system, Essentia, relies on word-alignment techniques to create a word-alignment graph that merges and organizes tokens from input sentences. The resulting graph is then used to generate candidate paraphrases. We demonstrate that our system obtains high-quality paraphrases, as evaluated by crowd workers. We further show that the majority of the identified paraphrases are domain-specific and thus complement existing paraphrase databases.
Introduction
Paraphrases—alternative ways of expressing the same meaning—are critical for Natural Language Processing (NLP) tasks such as machine translation, question-answering, and conversational AI. While large-scale resources like the Paraphrase Database (PPDB) provide extensive coverage for general language, they frequently lack domain-specific nuances. For instance, in a hospitality context, "staff" and "concierge" might function as paraphrases, yet general-purpose models often fail to capture this relationship.
The primary obstacle is that domain-specific data is typically "low-resource." Traditional statistical mining techniques require massive corpora to identify patterns, making them unsuitable for small datasets like help-desk logs or niche application queries. Essentia addresses this gap by extracting high-quality paraphrases from small clusters of sentences sharing a common intent.
Methodology: The Word-Alignment Graph
Essentia employs a three-stage unsupervised pipeline to process related sentences:
- Word Aligner: The system utilizes a monolingual aligner to map similar words and phrases across sentence pairs based on syntactic and semantic similarity. Pre-processing steps replace numbers and named entities with generic tags (e.g.,
NUM,ORG) to generalize patterns. - Word-Alignment Graph Generator: This core component merges alignments into a compact Directed Acyclic Graph (DAG). To maintain logical structure, the system enforces constraints of injectivity (one-to-one mapping), monotonicity (preserving word order), and transitivity.
- Paraphrase Generator: The system identifies "bubbles"—parallel paths within the graph that originate and terminate at the same nodes. These paths represent candidate paraphrases.
The graph structure also allows for identifying the "essence" of a sentence by detecting optional phrases (nodes with direct bypass edges). By traversing different valid paths, the system can even generate novel sentences not present in the original input.
Experimental Evaluation
The system was evaluated on two specialized datasets: Snips (smart assistant queries across 10 intents) and HotelQA (guest questions regarding hotel amenities). These datasets are notably small, averaging only 32 to 54 sentences per intent.
Essentia was compared against a syntax-based Finite-State Automata (FSA) baseline. Key findings include:
- Increased Recall: Essentia generated 263% more paraphrases than the baseline. Specifically, it improved recall by 460% on Snips and 247% on HotelQA.
- Domain Specificity: Human evaluators confirmed the high quality of the extracted pairs. Notably, only 4% of the paraphrases discovered by Essentia were found in the general-purpose PPDB, highlighting its ability to capture niche linguistic variations.
Discussion and Future Work
A significant insight from this research is the value of contextual interchangeability. Phrases do not need to be dictionary synonyms to be paraphrases; if they share an aligned context within a specific domain, they are likely interchangeable.
However, some limitations remain. The current filtering logic is optimized for verb phrases, leading to noise when processing noun phrases (e.g., confusing specific locations with general ones). Additionally, the $O(n^2)$ complexity relative to the number of sentences necessitates pre-clustering for larger datasets. Future work will focus on expanding the range of syntactic units mined and identifying "phatic" expressions to further refine the extraction of a sentence's core meaning.
Summary updated