SMATCH ++: Standardized and Extended Evaluation of Semantic Graphs (2023)

Abstract: The Smatch metric is a popular method for evaluating graph distances, as is necessary, for instance, to assess the performance of semantic graph parsing systems. However, we observe some issues in the metric that jeopardize meaningful evaluation. E.g., opaque pre-processing choices can affect results, and current graph-alignment solvers do not provide us with upper-bounds. Without upper-bounds, however, fair evaluation is not guaranteed. Furthermore, adaptions of Smatch for extended tasks (e.g., fine-grained semantic similarity) are spread out, and lack a unifying framework. For better inspection, we divide the metric into three modules: pre-processing, alignment, and scoring. Examining each module, we specify its goals and diagnose potential issues, for which we discuss and test mitigation strategies. For pre-processing, we show how to fully conform to annotation guidelines that allow structurally deviating but valid graphs. For safer and enhanced alignment, we show the feasibility of optimal alignment in a standard evaluation setup, and develop a lossless graph compression method that shrinks the search space and significantly increases efficiency. For improved scoring, we propose standardized and extended metric calculation of fine-grained sub-graph meaning aspects. Our code is available at https://github.com/flipz357/smatchpp

## introduction semantic graphs such as meaning representations (mrs) aim at capturing the meaning of a text. typically, these graphs are rooted, directed, acyclic, and labeled. vertices denote semantic entities, and edges represent semantic relations (e.g., instrument, cause, etc.). a prominent mr framework is abstract meaning representation (amr), proposed by @xcite , which anchors in a propositional knowledge base @xcite . using a metric such as smatch @xcite , we can measure a distance (or similarity) between graphs, by aligning nodes, and counting matching graph triples. in fact, smatch measurement has various applications. it is used for selecting parsing systems that project amr structures @xcite @xcite @xcite and various other semantic graphs @xcite @xcite @xcite , for mr-based evaluation and diagnostics of text generation systems @xcite @xcite , as backbone in an ensemble parsing algorithm @xcite , and for studying cross-lingual phenomena @xcite . through smatch measured on sub-graphs, we can assess similarity of linguistic phenomena such as semantic roles, negation, or coreference @xcite , a property that can be leveraged in neural text embeddings @xcite . however, smatch measurement is non-trivial and lacks specification. for instance, smatch involves an np-hard optimization problem of structural graph alignment, which distinguishes it from most metrics used in other evaluation tasks. in practice, a solution of this problem is found by employing a hill-climber. however, a hill-climber terminates at local optima, and it cannot inform us about a score upper-bound. in the end, this means that we lack information about the quality of the returned solution, potentially lowering our trust in the final evaluation. to mitigate this issue, we would like to study the possibility of optimal solution, or solution with a tight upper-bound. there are also other issues, on which we lack understanding. e.g., we do not know to what extent different pre-processing choices may affect the evaluation results, and we miss specification of smatch's popular fine grained sub-graph metrics @xcite , where it is unclear how sub-graphs should be best extracted and compared. paper structure and contributions first, we describe and generalize the smatch metric ( §3), and summarize recent smatch variants in one framework. then we break the metric down into three modules ( §4), which ĺets us better distribute our attention over its key components. for each module, we discuss specification of goals and mitigation of issues. in the pre-processing module ( §5), we motivate graph standardization to allow safer matching of equivalent mr graphs with different structural choices. in the optimization module ( §6), we test strategies for solving the alignment problem with optimality guarantees. in the scoring module ( §7), we discuss standardized and extended scoring of fine-grained semantic aspects, such as causality, tense, and location. ## related work metric standardization an inspiration for us is the work of @xcite , who propose the popular sacrebleu framework for fairer comparison of machine translation systems with a standardized bleu metric @xcite . specifically, sacrebleu ships bleu together with a specified tokenizer -prior to this, bleu differences between systems could depend on different tokenization protocols. facing the challenging problem of graph evaluation, a main contribution of our work is that we i) analyze weak spots in the current evaluation setup and ii) discuss ways of mitigating these issues, aiming at best evaluation practices. @xcite introduce a variant of smatch @xcite that penalizes dissimilar structures if they are situated in proximity of the graph root, motivated by their assumption that 'core-semantics' are located near the root of mr graphs. furthermore, @xcite introduce a smatch variant that performs a graded match of semantic concepts (e.g., cat vs. kitten), aiming at extended use-cases beyond parsing evaluation, where mrs of different sentences need to be compared. similarly, wein and schneider (2022) adapt an embedding-based variant of smatch for cross-lingual mr comparison. we show that the different smatch adaptions can be viewed through the same lens with a generalized notion of triple match. furthermore, @xcite propose fine-grained smatch that measure mr agreement in different aspects, such as semantic roles, coreference or polarity. we diagnose and mitigate issues in the aspectual assessment, and show how to extend the measured aspects. ## smatch: overview and generalization we introduce smatch and define a generalized smatch, so that we can summarize recent smatch variants in one framework. ## a modular view on smatch to set the stage for inspection, we break smatch down into three modules. i) preprocessing, ii) alignment, and iii) scoring. in particular, i) preprocessing discusses any graph reading and processing in advance of the alignment. ii) alignment revolves around the search mechanism used for finding an optimal mapping map ⋆ . iii) scoring involves calculating final scores and statistics that are returned to a user. for each module, we will specify its goals, assess potential weak spots and discuss mitigation. ## module ii: alignment the goal of this module is solving eq. 2, finding a map ⋆ for optimal matching score. smatch uses a hill-climber for solving eq. 2. an issue with this is that such a heuristic terminates at local optima and cannot provide us with any upper-bounds. upper-bounds, however, can inform users about the quality of the outputted solution and thus increase the trustworthiness of the final score (and any parser comparison that is based thereupon). therefore, we can conclude that using a hill-climber seems practical but may not be optimal, especially when considering cases where fair comparison needs to be guaranteed. instead, we would like to use an integer linear program (ilp) to obtain the (optimal) solution. alternatively, at least, we would like to know a tight upper-bound to inform ourselves about the trustworthiness of 8 i.e., since reification can potentially be used to model n-ary relations, only in the case where @xmath0, we find the effects of either choice to be negligible. the final score. but ilp is np hard, and therefore it seems optimal but possibly not practical, a conception that might favor the usage of a hillclimber. triggered by these considerations, we review the hill-climber and the ilp and assess their effects on mr evaluation, with two desiderata in mind: evaluation quality and efficiency. additionally, we propose a strategy for loss-less mr compression that can improve efficiency of any solver. in practice, we can resort to multiple random restarts, to find better optima. however, this hardly addresses the underlying issue: we lack any information on upper-bounds, which may decrease trustworthiness of results, especially when facing larger graphs with lots of local optima. we would like to use integer linear programming (ilp) for optimal solution of the graph alignment. problem statement assume two graphs g, g ′ with node sets v, v ′ . let u(i, j) denote the amount of unary triple matches, given we align i from v to j from v ′ , counting matches of triples that involve one mr variable. on the other hand, b(i, j, k, l) will denote the amount of structural binary triple matches, given we align i from v to j from v ′ and k from v to l from v ′ . here, we count matching binary triples that involve two mr variables. usually, these data are pre-computed. let x indicate our current map, i.e., if x @xmath1. we find our solution at the constraint ensures that every node from one graph is aligned, at maximum, to one node from the other graph. by linearization, and introducing structural variables y, we obtain the equivalent ilp: ## conclusion smatch++ is the first specification of a standardized, extended, and extensible smatch metric. we aim at i) standardized and transparent comparison of graph parsing systems, and ii) improved extensibility for custom applications. 18 the applications can include finer parser diagnostics and measuring semantic sub-graph similarities such as quantification, cause, or tense with our fine-grained metrics.