SMARAGD: Learning SMatch for Accurate and Rapid Approximate Graph Distance

Juri Opitz, Philipp Meier, Anette Frank

[How to correct problems with metadata yourself]

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.
Anthology ID:
2023.iwcs-1.28
Volume:
Proceedings of the 15th International Conference on Computational Semantics
Month:
June
Year:
2023
Address:
Nancy, France
Editors:
Maxime Amblard, Ellen Breitholtz
Venue:
IWCS
SIG:
SIGSEM
Publisher:
Association for Computational Linguistics
Note:
Pages:
267–274
Language:
URL:
https://aclanthology.org/2023.iwcs-1.28
DOI:
Bibkey:
Cite (ACL):
Juri Opitz, Philipp Meier, and Anette Frank. 2023. SMARAGD: Learning SMatch for Accurate and Rapid Approximate Graph Distance. In Proceedings of the 15th International Conference on Computational Semantics, pages 267–274, Nancy, France. Association for Computational Linguistics.
Cite (Informal):
SMARAGD: Learning SMatch for Accurate and Rapid Approximate Graph Distance (Opitz et al., IWCS 2023)
Copy Citation:
PDF:
https://preview.aclanthology.org/teach-a-man-to-fish/2023.iwcs-1.28.pdf
PDF Search