@inproceedings{opitz-etal-2023-smaragd,
    title = "{SMARAGD}: Learning {SM}atch for Accurate and Rapid Approximate Graph Distance",
    author = "Opitz, Juri  and
      Meier, Philipp  and
      Frank, Anette",
    editor = "Amblard, Maxime  and
      Breitholtz, Ellen",
    booktitle = "Proceedings of the 15th International Conference on Computational Semantics",
    month = jun,
    year = "2023",
    address = "Nancy, France",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/jlcl-multiple-ingestion/2023.iwcs-1.28/",
    pages = "267--274",
    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."
}