Towards Generative Graph Matching for Graph Edit Distance Computation

Graph Edit Distance (GED), which aims to find an edit path with minimum number of edit operations to transform one graph into another, is a fundamental NP-hard problem and a widely used graph similarity measure. Recent matching-based hybrid approaches have demonstrated better scalability than A* search-based hybrids by reformulating GED as a graph matching problem. In these methods, a neural network predicts a single deterministic node matching matrix, from which top-$k$ node mappings are extracted iteratively to derive candidate edit paths. However, these methods often suffer from highly correlated candidates that easily lead to suboptimal solutions, while the iterative extraction becomes inefficient for large $k$. In this paper, we propose DiffGED, the first generative approach for GED computation. Specifically, we formulate the graph matching problem as a generative task, and employ a diffusion-based model to generate multiple diverse node matching matrices simultaneously, from which diverse node mappings can be efficiently extracted. The generative diversity introduced by the diffusion process enables DiffGED to avoid suboptimal solutions and achieve superior solution quality close to the exact solution. Experiments on real-world datasets show that DiffGED generates multiple diverse edit paths with accuracy comparable to exact solutions, while running faster than existing hybrid approaches.

Graph Edit Distance (GED) is a way to measure how different two graphs are by finding the minimum number of edit operations needed to transform one graph into another. It is widely used in applications such as pattern recognition and graph similarity search, but it is also computationally very difficult to solve exactly. Existing learning-based methods approximate GED by predicting a single distribution and then extracting multiple candidate edit paths from it to find the one with the minimum number of edit operations. However, this is essentially a “putting all eggs in one bucket” strategy. What if the single predicted distribution fails? The candidate edit paths derived from it may all suffer from poor quality, making it difficult to discover a good solution. In this paper, we propose DiffGED, a new generative approach for GED computation. Instead of relying on a single predicted distribution, DiffGED generates multiple diverse distributions using a diffusion-based generative model. This allows candidate edit paths to be extracted from different distributions, increasing the chance of obtaining high-quality edit paths even when some predicted distributions are inaccurate. Experiments on real-world datasets show that DiffGED produces high-quality solutions that are close to exact results, while being faster than existing methods.