mlsanityData to 14 Oct 2026

SMARAGD: Learning SMatch for Accurate and Rapid Approximate Graph Distance

arXiv 2203.13226 ↗First posted 24 Mar 2022cs.CLcited by 0

Not on the map. Why?

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.

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

23 of 39 references.

References · 23

  1. 2019Sentence-BERT: Sentence Embeddings using Siamese BERT-Networkscited by 9,170
  2. 2020Longformer: The Long-Document Transformercited by 3,413
  3. 2020Rethinking Attention with Performerscited by 1,601
  4. 2019Compressive Transformers for Long-Range Sequence Modellingcited by 726
  5. 2020Long Range Arena: A Benchmark for Efficient Transformerscited by 700
  6. 2014Neural Turing Machinescited by 644
  7. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  8. 2019Deep Learning for Symbolic Mathematicscited by 270
  9. 2016DeepCoder: Learning to Write Programscited by 149
  10. 2020Learning Compositional Rules via Neural Program Synthesiscited by 74
  11. 2018AMR Parsing as Graph Prediction with Latent Alignmentcited by 36
  12. 2021Latent Execution for Neural Program Synthesiscited by 35
11 more
  1. 2015Neural Programmer: Inducing Latent Programs with Gradient Descentcited by 34
  2. 2019Rewarding Smatch: Transition-Based AMR Parsing with Reinforcement Learningcited by 25
  3. 2020Towards a Decomposable Metric for Explainable Evaluation of Text Generation from AMRcited by 25
  4. 2020AMR Similarity Metrics from Principlescited by 22
  5. 2021Weisfeiler-Leman in the BAMBOO: Novel AMR Graph Metrics and a Benchmark for AMR Graph Similaritycited by 16
  6. 2021Translate, then Parse! A strong baseline for Cross-Lingual AMR Parsingcited by 15
  7. 2021Ensembling Graph Predictions for AMR Parsingcited by 15
  8. 2019SemBleu: A Robust Metric for AMR Parsing Evaluationcited by 12
  9. 2018Evaluating Scoped Meaning Representationscited by 11
  10. 2020AMR Quality Rating with a Lightweight CNNcited by 4
  11. 2019Automatic Accuracy Prediction for AMR Parsingcited by 3

Built on by

Not cited yet.