A Semantics-aware Approach for Graph Edit Distance Estimation over Knowledge Graphs

Graph Edit Distance (GED) is a key metric for measuring the similarity between two Knowledge Graphs (KGs), defined as the minimum number of atomic operations required to transform one KG into another. It has broad applications in fields such as pattern recognition, biological analysis, and graph databases. The state-of-the-art approaches adopt Graph Neural Networks (GNNs) to predict GED, but they are limited to simple graphs and cannot be directly applied to the KGs, as they fail to capture the rich semantics and complex relationships present in KGs. To design a KG-native solution, in this paper, we propose a semantics-aware GNN model, SEABED, to capture local semantic dependencies and global semantic consistency between two KGs. Extensive experiments on four real-world KGs demonstrate that our proposed algorithm outperforms the state-of-the-art methods on all datasets. In particular, the mean absolute error is reduced by up to 66.7%, while the accuracy is improved by up to 70.5%, without increasing the computation time.