Essentia: Mining Domain-Specific Paraphrases with Word-Alignment Graphs

Danni Ma, Chen Chen, Behzad Golshan, Wang-Chiew Tan

TL;DR

Essentia is an unsupervised, graph-based system designed to mine domain-specific paraphrases from small, specialized datasets where traditional statistical methods fail. By constructing "word-alignment graphs," the system identifies interchangeable phrases that share the same linguistic context, successfully capturing niche mappings—like "log onto" and "connect to" in a hotel Wi-Fi context—that are largely absent from massive general-purpose databases.

What Problem Does This Paper Address?

Paraphrase mining is a cornerstone of NLP, essential for tasks like machine translation and question answering. However, most existing tools are built on massive general-purpose corpora and statistical methods. These "one-size-fits-all" approaches struggle with domain-specific language for two reasons:

  1. Data Scarcity: Specialized domains (like hospitality or medical tech) often lack the millions of parallel sentences required for statistical models.
  2. Contextual Meaning: Words that aren't synonyms in a general sense often become interchangeable within a specific domain. For example, in a hotel setting, "reservation" and "stay" might be used interchangeably in the context of extending a booking, but a general-purpose model wouldn't recognize them as paraphrases.

The authors introduce ESSENTIA to bridge this gap by mining high-quality paraphrases from small sets of sentences sharing the same intent.

Methods

The ESSENTIA pipeline consists of three main stages:

  1. Word Aligner: The system uses a state-of-the-art monolingual word aligner to map similar words between pairs of sentences based on syntactic and semantic similarity.
  2. Word-Alignment Graph Generator: This is the core innovation. It merges all sentence alignments into a single Directed Acyclic Graph (DAG). To keep the graph compact and cycle-free, the authors enforce three constraints: Injectivity (one-to-one mapping), Monotonicity (preserving word order), and Transitivity (consistent mapping across three or more sentences).
  3. Paraphrase Generator: The system identifies "candidate paraphrases" by looking for different paths in the graph that share the same start and end nodes. To reduce noise, a rule-based filter currently focuses on verb phrases with three or fewer tokens.
Figure 1: An instance of a word-alignment graph.

Datasets

The authors evaluated ESSENTIA on two distinct datasets:

  • Snips: A public collection of queries for smart speakers (e.g., "Get Weather," "Get Directions"), averaging 32 sentences per intent.
  • HotelQA: A proprietary industry dataset consisting of questions from hotel guests regarding amenities like "Check-out" or "Wi-Fi," averaging 54 sentences per category.

Key Insights and Ideas

  • Structural Equivalence: The key insight is that if two different phrases are surrounded by the same aligned words (the "context"), they are likely domain-specific paraphrases.
  • Beyond Synonyms: ESSENTIA identifies functional paraphrases rather than just lexical ones. In the "Hotel Wi-Fi" domain, it correctly identifies "log onto" and "connect to" as equivalents, even though they aren't strict synonyms in a general dictionary.
  • Sentence "Cleaning": The graph structure naturally identifies "optional" phrases—words that can be removed without changing the core meaning (e.g., "already" or "completely" at the end of a sentence). This allows the system to distill a sentence down to its "essence."
  • Generative Potential: Because the graph represents a union of many sentences, one can traverse new paths to generate valid sentences that were never actually present in the original input data.

Key Results

ESSENTIA was compared against a syntax-based baseline (FSA). While the baseline had higher precision due to a very conservative alignment strategy, ESSENTIA vastly outperformed it in terms of the volume of useful data discovered.

  • Higher Recall: ESSENTIA generated 263% more paraphrases than the baseline across both datasets. Specifically, it improved recall by 460% on the Snips dataset and 247% on HotelQA.
  • Novelty: Perhaps the most striking result is that 96% of the paraphrases discovered by ESSENTIA were missing from PPDB (the Paraphrase Database), the most extensive resource in the community. This highlights the critical need for domain-specific mining.
Comparison table showing ESSENTIA's significantly higher volume of extracted pairs compared to the FSA baseline.

Limitations and Future Work

The authors acknowledge two primary types of errors:

  1. Alternative Options: The system sometimes flags different options as paraphrases (e.g., "avoiding the highway" vs. "avoiding toll road").
  2. Intent Shifts: It may extract phrases that share a topic but have slightly different goals (e.g., "tell me the password" vs. "how to connect").

Future work aims to expand the filtering logic beyond short verb phrases to include noun phrases and other syntactic units, as well as improving the underlying word aligner to handle prepositions more accurately.

Examples of high-quality domain-specific paraphrases found by ESSENTIA across various intents.

Summary updated

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.
BibTeX
@misc{ma2019essentia,
  author = {Danni Ma and Chen Chen and Behzad Golshan and Wang-Chiew Tan},
  title = {{Essentia: Mining Domain-Specific Paraphrases with Word-Alignment Graphs}},
  year = {2019},
  eprint = {1910.00637},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1910.00637},
}
Figure