Abstract
Many tasks in natural language processing, ranging from machine translation to question answering, can be reduced to the problem of matching two sentences or more generally two short texts. We propose a new approach to the problem, called Deep Match Tree (DeepMatch$_{tree}$), under a general setting. The approach consists of two components: 1) a mining algorithm to discover patterns for matching two short-texts, defined in the product space of dependency trees, and 2) a deep neural network for matching short texts using the mined patterns, as well as a learning algorithm to build the network having a sparse structure. We test our algorithm on the problem of matching a tweet and a response in social media, a hard matching problem, and show that DeepMatch$_{tree}$ can outperform a number of competitor models including one without using dependency trees and one based on word-embedding, all with large margins.
Introduction
Matching short texts—such as determining if a response is appropriate for a tweet or if two sentences are paraphrases—is a fundamental challenge in Natural Language Processing (NLP). Unlike long documents, short texts provide very little context, making them susceptible to noise and ambiguity.
Existing "embedding-based" methods, which represent words as dense vectors, often struggle with the structural subtleties of language. For example, to match the utterance "I have to work during the weekend!" with the response "You should rest more," a model must understand the semantic link between the structural core of "working" and the necessity of "rest." Standard models often rely on simple word co-occurrence or local proximity, which can be easily fooled by "distractor" words that appear in both sentences but are grammatically unrelated. To address this, we introduce DeepMatch$_{tree}$, a framework that leverages dependency syntax to capture long-distance relationships.
The DeepMatch$_{tree}$ Framework
The proposed framework follows a multi-stage pipeline designed to transform raw text into a structured matching degree. As shown in Figure 1, the process begins with dependency parsing, followed by the construction of a joint structural space, feature abstraction, and finally, classification via a deep neural network.
Structural Representation: Product of Graphs (PoG)
Instead of analyzing sentences in isolation, DeepMatch$_{tree}$ represents each sentence as a dependency tree. To find matches between two trees, the model constructs a Direct Product of Graphs (PoG). This creates a massive graph where each node represents a pair of words (one from each sentence) and edges represent shared structural relations between those pairs. This product space allows the model to identify sub-graphs that represent complex, multi-word matching patterns.
Abstraction and Discriminative Mining
To ensure the model generalizes beyond specific vocabulary, two types of abstraction are introduced:
- Same Entity: Specific names (e.g., "Beijing") are replaced with a generic
SAMEENTITYtag if they appear in both texts. - Similar Word: Words are clustered using
word2vecso that semantically related terms (e.g., "sunny" and "cloudy") are treated as the same feature.
A discriminative mining algorithm then identifies the most "useful" sub-graphs (patterns) that appear frequently in positive matching pairs but rarely in mismatched ones. These mined patterns are converted into a sparse binary vector for the neural network.
Deep Neural Network Architecture
The resulting feature space can contain millions of patterns. To handle this, the model employs a deep neural network (DNN) with a specialized sparse structure. Using a "NodeDensity" strategy, the network ensures that each input node connects to only a balanced subset of hidden units. This preserves the structural information of the mined patterns while keeping the model computationally tractable. The final output is a "matching degree" representing the likelihood that the two texts are a valid pair.
Experimental Evaluation
The model was evaluated on two large-scale datasets from Weibo (a Chinese microblogging service):
- DataOriginal: 4.8 million (tweet, response) pairs used for training.
- DataLabeled: A high-quality benchmark of 422 tweets with human-labeled responses.
Key Results
DeepMatch$_{tree}$ significantly outperformed all competitors, including Convolutional Neural Networks (CNNs) and word-embedding MLPs:
- 1-vs-9 Task: DeepMatch$_{tree}$ achieved a Precision@1 of 0.708, compared to 0.496 for the CNN-based model and 0.370 for the word-embedding model.
- Conversation Retrieval: On human-labeled data, it achieved a P@1 of 0.608, outperforming the baseline (0.574).
- Ablation Study: Removing "deep" patterns (those involving multiple levels of the dependency tree) led to a significant drop in performance, proving that the model relies on structural depth rather than simple keyword matching.
Conclusion
DeepMatch$_{tree}$ demonstrates that long-distance grammatical relationships captured by dependency trees are more reliable for short-text matching than local word proximity. By combining graph-based structural mining with deep learning, the model effectively bridges the gap between syntactic precision and neural predictive power. Future work will focus on reducing the preprocessing burden of dependency parsing and exploring the model's effectiveness across different languages.
Summary updated