# SMARAGD: Learning SMatch for Accurate and Rapid Approximate Graph Distance

arXiv: https://arxiv.org/abs/2203.13226 · HTML: https://mlsanity.com/paper/2203.13226/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 39 references that are in the map.
- First posted on arXiv 24 Mar 2022.

## Builds on (most cited first, 23 of 23)

- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Compressive Transformers for Long-Range Sequence Modelling](https://mlsanity.com/paper/1911.05507/) (2019)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Deep Learning for Symbolic Mathematics](https://mlsanity.com/paper/1912.01412/) (2019)
- [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016)
- [Learning Compositional Rules via Neural Program Synthesis](https://mlsanity.com/paper/2003.05562/) (2020)
- [AMR Parsing as Graph Prediction with Latent Alignment](https://mlsanity.com/paper/1805.05286/) (2018)
- [Latent Execution for Neural Program Synthesis](https://mlsanity.com/paper/2107.00101/) (2021)
- [Neural Programmer: Inducing Latent Programs with Gradient Descent](https://mlsanity.com/paper/1511.04834/) (2015)
- [Rewarding Smatch: Transition-Based AMR Parsing with Reinforcement Learning](https://mlsanity.com/paper/1905.13370/) (2019)
- [Towards a Decomposable Metric for Explainable Evaluation of Text Generation from AMR](https://mlsanity.com/paper/2008.08896/) (2020)
- [AMR Similarity Metrics from Principles](https://mlsanity.com/paper/2001.10929/) (2020)
- [Weisfeiler-Leman in the BAMBOO: Novel AMR Graph Metrics and a Benchmark for AMR Graph Similarity](https://mlsanity.com/paper/2108.11949/) (2021)
- [Translate, then Parse! A strong baseline for Cross-Lingual AMR Parsing](https://mlsanity.com/paper/2106.04565/) (2021)
- [Ensembling Graph Predictions for AMR Parsing](https://mlsanity.com/paper/2110.09131/) (2021)
- [SemBleu: A Robust Metric for AMR Parsing Evaluation](https://mlsanity.com/paper/1905.10726/) (2019)
- [Evaluating Scoped Meaning Representations](https://mlsanity.com/paper/1802.08599/) (2018)
- [AMR Quality Rating with a Lightweight CNN](https://mlsanity.com/paper/2005.12187/) (2020)
- [Automatic Accuracy Prediction for AMR Parsing](https://mlsanity.com/paper/1904.08301/) (2019)

## Abstract (arXiv)

The similarity of graph structures, such as Meaning Representations (MRs), is often assessed via structural matching algorithms, such as Smatch (Cai and 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.