Semantic Sentence Matching via Interacting Syntax Graphs (2022)

Abstract: Studies have shown that the sentence’s syntactic structures are important for semantic sentence matching. A typical approach is encoding each sentence’s syntactic structure into an embedding vector, which can be combined with other features to predict the final matching scores. Though successes have been observed, embedding the whole syntactic structures as one vector inevitably overlooks the fine-grained syntax matching patterns, e.g. the alignment of specific term dependencies relations in the two inputted sentences. In this paper, we formalize the task of semantic sentence matching as a problem of graph matching in which each sentence is represented as a directed graph according to its syntactic structures. The syntax matching patterns (i.e. similar syntactic structures) between two sentences, therefore, can be extracted as the sub-graph structure alignments. The proposed method, referred to as Interacted Syntax Graphs (ISG), represents two sentences’ syntactic alignments as well as their semantic matching signals into one association graph. After that, the neural quadratic assignment programming (QAP) is adapted to extract syntactic matching patterns from the association graph. In this way, the syntactic structures fully interact in a fine granularity during the matching process. Experimental results on three public datasets demonstrated that ISG can outperform the state-of-the-art baselines effectively and efficiently. The empirical analysis also showed that ISG can match sentences in an interpretable way.

## introduction matching two natural language sentences has become a fundamental technique in information retrieval (ir) and natural language processing (nlp). extensive research efforts have been devoted to the task @xcite . recently, researchers found that the sentences' rich syntactic information helps match. some studies utilize the implicit syntax-encoding methods to learn the sentence embedding based on its syntactic strictures @xcite . other studies directly utilize the different syntactic tags as syntactic features and fuse them with word features @xcite @xcite . all these approaches separately represent the syntactic information of the two input sentences as two coarse-grained embedding vectors, ignoring the fine-grained matching patterns between the syntactic structures. in sentence matching, the fine-grained syntax structures are lost during the process of representing the syntactic information as a vector. studies in @xcite also verified that representationbased methods will lose the fine-grained matching signals. figure 1 illustrates two semantically similar sentences from the snli dataset where sentences @xmath0, @xmath1. the parsed syntactic structures (the pos tags and syntactic dependencies) are represented as nodes and edges in two graphs, respectively. we can see that though the overall syntactic struc-tures of the two sentences are very different, they still contains matched sub-graphs: "men(nns) nsubj ← ---playing(vbg) obj -→sport(nn)" from x and "game(nn) obj ←-playing(vbg) nsubj ---→males(nns)" from y . the matched sub-graphs provide a crucial syntactic matching signal for downstream models to make high-precision matching decisions. existing approaches, however, inevitably overlook the fine-grained sub-graph matching signal because the sub-graph details are lost during the embedding of the whole syntax graphs. specifically, the subgraph details denote the combination of first-order (e.g. part-of-speech) and second-order (e.g. word dependency) syntactic information. in this paper, we propose to formalize the task of sentence matching as matching two directed graphs where each graph corresponds to one sentence, and its edges and nodes correspond to the word-word syntactic dependencies and the words' syntax and semantic information, respectively. the sentence matching, therefore, becomes a process of first extracting the sub-graph structure alignmentsand then summarizing them into the final matching score. a neural model called interacted syntax graphs (isg) is developed for conducting the matching. specifically, given two sentences, isg employs a pre-trained language model (plm) and a syntactic parser to get the word embeddings and the syntactic structures as the initialization features. then, isg fuses these semantic and syntactic features into an associate graph. sub-graph matching patterns can be extracted based on the associate graph, by using lawler's quadratic assignment programming (qap) @xcite . finally, a matching classifier is used to merge the matching patterns and semantic vectors outputted from the plm, resulting in the final matching score. isg offers several advantages, including accurate extraction and fusion of the syntactic graph matching signals, ease in interpretation, and high matching accuracy. the contributions of this paper can be summarized as follows: (1) we highlight the importance of the fine-grained matching patterns from syntax graphs in semantic sentence matching. a novel matching model called isg is proposed; ## related work machine learning models have been widely used for matching natural language sentences @xcite . among them, the representative methods include dssm @xcite and its extensions @xcite @xcite . representative interaction-based models include arc-ii @xcite , matchpyramid @xcite , etc. recently, the pre-trained language model has been adapted to conducting matching @xcite . these models always focused on superficial matching signals and ignore explicit nlp knowledge. recently, there is a trend to utilize explicit nlp knowledge to improve sentence representation. for example, him @xcite used the syntactic dependencies to enhance the sentence representations, see also @xcite @xcite . the nlp knowledge-enhanced matching models have also adapted to the interaction-based models. for example, mix @xcite utilizes pos and named-entity tags as prior features. recently, @xcite @xcite found that syntax can help plm capture more information and achieve impressive results for nlp tasks. however, these models overlook the fine-grained syntactic matching patterns. graph matching problem (gm) has also been adopted for discovering the patterns between different graphs @xcite . the key is to learn a practical affinity function with given two structures. in early work, most on seeking approximate affinity function and euclid distance together with the gaussian kernel is applied @xcite . recently, quadratic assignment programming (qap) @xcite has a wide application in graph matching (gm) because of its great performance. the affinity function in qap can be learned with the manners of unsupervised @xcite , semi-supervised @xcite , or supervised @xcite . recently, deep graph matching has been applied for gm on images @xcite and the matching accuracy has been achieved. moreover, graph-based models have also been used for sentence matching @xcite @xcite . mary nn nsubj obj compound nsubj obj likes vb food nn flour nn mary nn loves vb noodles nn sim(nn,nn)+sim(mary,mary) (mary, mary) (a) sentence matching (c) association graph 𝓖𝓖 (likes, loves) (mary, loves) (likes, mary) (likes noodles) (food mary) (mary, noodles) (flour, mary) (flour, loves) (flour, noodles) (food likes) (food noodles) sentence x sentence y (b) affinity matrix 𝑲𝑲 (𝒙𝒙 𝟏𝟏 ) (𝒙𝒙 𝟐𝟐 ) (𝒙𝒙 𝟑𝟑 ) (𝒙𝒙 𝟒𝟒 ) (𝒚𝒚 𝟏𝟏 ) (𝒚𝒚 𝟐𝟐 ) (𝒚𝒚 𝟑𝟑 ) sim(nsubj, nsubj) 3 problem formulation ## proposed model: isg in this section, we present an efficient implementation of interacting syntax graphs (isg) with quadratic assignment programming (qap) @xcite . figure 3 illustrates the model architecture, which can be divided into sentence characteristic initialization, qap component, and matching classifier. ## experiments we conducted experiments to verify the effectiveness of the proposed approach. the source code and experiments are available at the link. foot_0 ## conclusion this presents a novel sentence matching model which formulates sentence matching as a problem of syntax graph matching, referred to as isg. based on the constructed association graph, isg explicitly aligns the syntactic sub-graphs as fine-grained matching signals. neural qap is adopted to learn the rich matching patterns from the training data. isg offers several advantages: explicitly interacting with the syntactic structures in fine granularity, high matching accuracy, and the ability to interpret. experiments on three publicly available benchmarks verified the effectiveness, robustness, and interpretability of isg.