SMARAGD : Learning SM atch for Accurate and Rapid Approximate Graph Distance (2023)

Abstract: The similarity of graph structures, such as Meaning Representations (MRs), is often assessed via structural matching algorithms, such as Smatch (Cai & Knight 2013). However, Smatch involves a combinatorial problem that suffers from NP-completeness, making large-scale applications, e.g., graph clustering or search, infeasible. To alleviate this issue, we learn SMARAGD: Semantic Match for Accurate and Rapid Approximate Graph Distance. We show the potential of neural networks to approximate Smatch scores, i) in linear time using a machine translation framework to predict alignments, or ii) in constant time using a Siamese CNN to directly predict Smatch scores. We show that the approximation error can be substantially reduced through data augmentation and graph anonymization.

## introduction semantic graphs such as meaning representation (amr) are directed, rooted and acyclic, and labeled. for instance, in amr @xcite labels indicate the events and entities of a sentence, and structures capture semantic roles and other key semantics such as coreference. often, pairs of mrs need to be studied, using mr metrics. classically, mrs are compared to assess inter annotator agreement in sembanking or for the purpose of parser evaluation, typically using the structural smatch metric @xcite . going beyond these applications, researchers have leveraged smatchbased mr metrics for nlg evaluation @xcite , for re-inforcing amr parsers @xcite , as a basis for a covid-19 semantics-based search engine @xcite , comparison of crosslingual amr @xcite , and fine-grained argument similarity assessment @xcite . many of these extended scenarios greatly profit from a quick similarity computation. also, additional future applications can be anticipated that require fast metric inference: e.g., corpus linguists who want to find instantiations of abstract semantic patterns in a large corpus. but graph metrics typically suffer from a high time complexity: computation of smatch is nphard @xcite , and it can take more than a minute to compare some 1,000 amr pairs @xcite . to understand that this can become problematic in many setups, consider a hypothetical user who desires exploring a (small) amr-parsed corpus with only @xmath0, 000 instances via clustering. the (symmetric) smatch needs to be executed over (n 2 -n)/2 = 499, 500 pairs, resulting in a total time of more than 6 hours. this high time complexity is a well-known bottleneck and negatively impacts amr evaluation time (song and gildea, 2019), as well as parsing efficency of approaches involving re-inforcement learning @xcite or graph ensembling @xcite , where the smatch metric is executed with high frequency. furthermore, given recent interest into larger meaning representations that cover multiple sentences, such as multi-sentence amr (o'gorman et al., 2018), dialogue amr @xcite or discourse representation structures @xcite , we anticipate that this problem will become more pressing in the future. testing ways to mitigate these issues, we propose a method that learns to match semantic graphs from a teacher smatch, and show that this can reduce amr clustering time from hours to seconds, with only little expected loss in accuracy. our contributions are: our code is available at: https://github.com/ phmeier/smaragd/ . ## related work other metrics for mr similarity recently, researchers have proposed amr metrics beyond smatch. we can distinguish two lines of work: i) metrics aiming at extreme efficiency by skipping the alignment and extracting graph parts via breadth-first traversal @xcite . ii) weisfeiler-leman graph metrics that aim to reflect human similarity ratings @xcite . @xcite make an argument for the importance of graph alignment. algorithm synthesis neural networks have been studied for solving other problems efficiently. examples range from sorting numbers @xcite to solving elaborated tasks such as symbolic integration @xcite , the famous traveling salesman problem @xcite @xcite , and computer programs @xcite @xcite . the 'long-range arena' benchmark @xcite includes algorithm synthesizing tasks, such as 'listops' (learning to calculate), or xpath (tracing a squiggly line), which prove challenging even for sota architectures. since structural graph matching with smatch constitutes a very hard combinatorial problem, investigating efficient neural approximations seems an interesting challenge in general -beyond the usecase of rapid graph distance calculation. ## learning np-hard graph alignment the smatch metric measures the structural overlap of two graphs. we i) compute an alignment between variable nodes of graphs and ii) assess triple matches based on the provided alignment. formally, we start with two graphs a and b with variable nodes @xmath1, ...x n ) and @xmath2...y m ). the goal is then to find an optimal alignment ## conclusion we tested methods for learning to solve the hard structural graph matching problem that is key to many applications where we compare meaning representations. to this aim, we explored different neural architectures, and data augmentation strategies that help models to generalize. our best models increase metric calculation speed by a large factor while incurring only small losses in accuracy that can be tolerated in many use cases. our work paves the way to emergent use-cases of meaning representation that involve pair-wise analysis: e.g., semantic clustering or semantic pattern-based search for corpus linguistic studies.