REMATCH : Robust and Efficient Matching of Local Knowledge Graphs to Improve Structural and Semantic Similarity (2024)

Abstract: Knowledge graphs play a pivotal role in various applications, such as question-answering and fact-checking. Abstract Meaning Representation (AMR) represents text as knowledge graphs. Evaluating the quality of these graphs involves matching them structurally to each other and semantically to the source text. Existing AMR metrics are inefficient and struggle to capture semantic similarity. We also lack a systematic evaluation benchmark for assessing structural similarity between AMR graphs. To overcome these limitations, we introduce a novel AMR similarity metric, rematch, alongside a new evaluation for structural similarity called RARE. Among state-of-the-art metrics, rematch ranks second in structural similarity; and first in semantic similarity by 1–5 percentage points on the STS-B and SICK-R benchmarks. Rematch is also five times faster than the next most efficient metric.

## introduction knowledge graphs provide a powerful framework for multi-hop reasoning tasks, such as question answering and fact-checking @xcite . even for closeddomain tasks like long-form question answering and multi-document summarization, knowledge graphs derived from individual documents -referred to as local knowledge graphs -exhibit superior performance compared to plain text @xcite . this highlights the significance of automatically parsed knowledge graphs in both large-scale and fine-grained structured reasoning applications. the abstract meaning representation (amr) framework leverages acyclic, directed, labeled graphs to represent semantic meaning (knowledge) extracted from text @xcite . as illustrated in the example of fig. 1 , amrs capture the relationships between concepts and their roles in a sentence. they have been applied to a variety of natural language processing tasks, including summarization and question answering @xcite @xcite . recent work has also shown that amrs can reduce hallucinations and improve performance in factual summarization and text classification tasks @xcite . however, evaluating the quality of knowledge graphs like amrs hinges critically on the ability to accurately measure similarity. this assessment must consider a dual perspective. firstly, the similarity between two amrs should reflect structural consistency, guaranteeing that the similarity between two amrs aligns with the similarity of their structural connections. secondly, amrs should exhibit semantic consistency, ensuring that the similarity between two amrs aligns with the similarity of the texts from which they are derived. therefore, an effective amr similarity metric must successfully account for both structural and semantic similarity, all while overcoming the resource-intensive nature of matching labeled graphs. current amr similarity metrics fall short in sev-eral key areas. firstly, their computational efficiency hinders the comparison of large amrs extracted from documents @xcite . secondly, these metrics struggle to accurately capture the semantic similarity of the underlying text from which amrs are derived @xcite . additionally, while recent efforts like bamboo @xcite have evaluated metrics on amr transformations, we still lack a large-scale benchmark to systematically evaluate the ability of amr metrics to capture structural similarity. our work introduces a structural amr benchmark called randomized amrs with rewired edges (rare) and proposes rematch, a novel and efficient amr similarity metric that captures both structural and semantic similarity. compared to the state of the art, rematch trails the best similarity metric on rare by 1 percentage point and ranks first on the sts-b @xcite and sick-r @xcite benchmarks by 1-5 percentage points. additionally, rematch is five times faster than the next most efficient metric. ## methods in this work, we propose rematch, an amr similarity metric that aims to capture both the structural and semantic overlap between two amrs. a straightforward approach to match two labeled graphs involves identifying the alignment between node labels. however, labeled graphs often contain duplicate labels, necessitating an exhaustive exploration of all one-to-one combinations among nodes within the same label group to determine the optimal match. the resulting matching complexity hinges on the size of node groups with shared labels. this is why algorithms like smatch and s2match do not scale well to large amrs, where these node groups can be large. graph features constructed using an ordered concatenation of edge-node bi-grams are utilized in both isomorphism tests like the cisc and kernels like weisfeiler-leman @xcite . this approach is effective: it consistently produces smaller node groups compared to those based solely on node labels. matching between two graphs is significantly accelerated as a result. inspired by this idea of exploiting graph features for efficiency, rematch computes the similarity between two amrs by analyzing the overlap of semantically rich features, which we call motifs. unlike the ordered graph partitions used by cisc and weisfeiler-leman kernel, which rely on node and edge labels, amr motifs are unordered graph partitions that leverage amr instances, attributes, and relations. this approach allows rematch to capture meaning across three semantic levels: specific facts (attributes), main concepts (instances), and the relationships among concepts (relations). fig. 2 illustrates rematch through an example. next, we delve into the three orders of semantic motifs that we use for rematch. we extract these motifs using the python package penman (goodman, 2020). ## evaluation we evaluate the effectiveness of rematch on three types of similarity: structural similarity, semantic similarity, and bamboo @xcite , a hybrid benchmark that modifies amr semantics through structural transformations. additionally, we assess the efficiency of rematch. ## conclusion this paper introduces rematch, a novel and efficient metric for amr similarity. rematch leverages semantic amr motifs to outperform existing metrics in both semantic consistency and computational efficiency. additionally, we present rare, a new benchmark designed to evaluate the struc-tural consistency of amr metrics. using rare, we demonstrate the strong sensitivity of rematch to structural changes in amrs. amr matching was originally introduced to evaluate and enhance amr parsers. through improved matching, metrics like rematch improve parsing, which indirectly benefits downstream uses of amrs. but rematch shows that amrs encode richer semantics than previously assumed. thus, improved amr matching also directly benefits downstream applications, like semantic textual similarity. future research should explore the full potential of amrs for natural language understanding. natural language inference (nli) is a prime example, where amr-based systems have already shown promise @xcite ). an even more intriguing direction would be to develop methods that perform nli solely through amr matching, capitalizing on the rich structure and semantics encoded within amrs.