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:
- 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)
- PDF:
- https://preview.aclanthology.org/ml4al-ingestion/2023.iwcs-1.28.pdf