Using Graph Edit Distance for Noisy Subgraph Matching of Semantic Property Graphs

Abstract

The subgraph matching problem is a fundamental problem in graph theory that is known to be NP-complete. In this study, performers were asked to develop algorithms to search for semantic property graphs that were subgraphs of a large knowledge graph. The templates provided contained structural information about the subgraphs and some attributes for each node and edge. There also exists a similarity measure between a set of attribute values that occurs on every node and edge. Algorithms performed well in the case where an exact match existed, but performers were also provided templates that had noise added such that there existed no match in the knowledge graph. Performers were asked to find the closest matches to those noisy subgraphs. To evaluate performance on this task, we developed a version of the graph edit distance algorithm to measure the cost of editing the template graph so that it is isomorphic in structure and attributes to the performer submission.