Proceedings

Graph Edit Distance Learning via Modeling Optimum Matchings with Constraints

Yun Peng, Byron Choi, Jianliang Xu

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 1534-1540.

https://doi.org/10.24963/ijcai.2021/212

Keywords

  • Data Mining: Big Data, Large-Scale Systems
  • Data Mining: Intelligent Database Systems

Abstract

Graph edit distance (GED) is a fundamental measure for graph similarity analysis in many real applications. GED computation has known to be NP-hard and many heuristic methods are proposed. GED has two inherent characteristics: multiple optimum node matchings and one-to-one node matching constraints. However, these two characteristics have not been well considered in the existing learning-based methods, which leads to suboptimal models. In this paper, we propose a novel GED-specific loss function that simultaneously encodes the two characteristics. First, we propose an optimal partial node matching-based regularizer to encode multiple optimum node matchings. Second, we propose a plane intersection-based regularizer to impose the one-to-one constraints for the encoded node matchings. We use the graph neural network on the association graph of the two input graphs to learn the cross-graph representation. Our experiments show that our method is 4.2x-103.8x more accurate than the state-of-the-art methods on real-world benchmark graphs.

Yun Peng, Byron Choi, and Jianliang Xu. 2021. Graph Edit Distance Learning via Modeling Optimum Matchings with Constraints. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 1534–1540. https://doi.org/10.24963/ijcai.2021/212
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards