SMARAGD: Learning SMatch for Accurate and Rapid Approximate Graph Distance
This addresses the scalability issue for graph clustering or search applications, offering a faster alternative to exact Smatch, though it is incremental as it builds on existing Smatch methods.
The paper tackled the NP-complete problem of computing Smatch scores for graph similarity by learning SMARAGD, a neural network-based approximation, achieving linear or constant time complexity and substantially reducing approximation error through data augmentation and graph anonymization.
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.