---
title: "Graph Edit Distance Learning via Modeling Optimum Matchings with Constraints"
authors:
  - "Yun Peng"
  - "Byron Choi"
  - "Jianliang Xu"
doi: "10.24963/ijcai.2021/212"
url: "https://ijcai.org/proceedings/2021/212"
pdf: "https://ijcai.org/proceedings/2021/0212.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "1534-1540"
track: "Main Track"
keywords:
  - "Data Mining: Big Data, Large-Scale Systems"
  - "Data Mining: Intelligent Database Systems"
---

# Graph Edit Distance Learning via Modeling Optimum Matchings with Constraints

Yun Peng, Byron Choi, Jianliang Xu

*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 1534-1540. DOI: [10.24963/ijcai.2021/212](https://doi.org/10.24963/ijcai.2021/212)

## 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.