Graph Edit Distance Learning via Modeling Optimum Matchings with Constraints

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

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.

Original languageEnglish
Title of host publicationProceedings of the 30th International Joint Conference on Artificial Intelligence, IJCAI 2021
EditorsZhi-Hua Zhou
PublisherInternational Joint Conferences on Artificial Intelligence
Pages1534-1540
Number of pages7
ISBN (Electronic)9780999241196
DOIs
Publication statusPublished - Aug 2021
Event30th International Joint Conference on Artificial Intelligence, IJCAI 2021 - Virtual, Online, Canada
Duration: 19 Aug 202127 Aug 2021
https://ijcai-21.org/#
https://www.ijcai.org/proceedings/2021/

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
ISSN (Print)1045-0823

Conference

Conference30th International Joint Conference on Artificial Intelligence, IJCAI 2021
Country/TerritoryCanada
CityVirtual, Online
Period19/08/2127/08/21
Internet address

Scopus Subject Areas

  • Artificial Intelligence

User-Defined Keywords

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

Fingerprint

Dive into the research topics of 'Graph Edit Distance Learning via Modeling Optimum Matchings with Constraints'. Together they form a unique fingerprint.

Cite this