Computing Graph Edit Distance via Neural Graph Matching

Download PDF

Abstract

Graph edit distance (GED) computation is a fundamental NP-hard problem in graph theory. Given a graph pair (𝐺1,𝐺2), GED is defined as the minimum number of primitive operations converting 𝐺1 to 𝐺2. Early studies focus on search-based inexact algorithms such as A*-beam search, and greedy algorithms using bipartite matching due to its NP-hardness. They can obtain a sub-optimal solution by constructing an edit path (the sequence of operations that converts 𝐺1 to 𝐺2). Recent studies convert the GED between a given graph pair (𝐺1,𝐺2) into a similarity score in the range (0, 1) by a well designed function. Then machine learning models (mostly based on graph neural networks) are applied to predict the similarity score. They achieve a much higher numerical precision than the sub-optimal solutions found by classical algorithms. However, a major limitation is that these machine learning models cannot generate an edit path. They treat the GED computation as a pure regression task to bypass its intrinsic complexity, but ignore the essential task of converting 𝐺1 to 𝐺2. This severely limits the interpretability and usability of the solution. In this paper, we propose a novel deep learning framework that solves the GED problem in a two-step manner: 1) The proposed graph neural network GEDGNN is in charge of predicting the GED value and a matching matrix; and 2) A post-processing algorithm based on 𝑘-best matching is used to derive 𝑘 possible node matchings from the matching matrix generated by GEDGNN. The best matching will finally lead to a high-quality edit path. Extensive experiments are conducted on three real graph data sets and synthetic power-law graphs to demonstrate the effectiveness of our framework. Compared to the best result of existing GNN-based models, the mean absolute error (MAE) on GED value prediction decreases by 4.9% ∼ 74.3%. Compared to the state-of-the-art searching algorithm Noah, the MAE on GED value based on edit path reduces by 53.6% ∼ 88.1%.