DiffGED: Computing Graph Edit Distance via Diffusion-based Graph Matching

Wei Huang, Hanchen Wang, Dong Wen, Wenjie Zhang, Ying Zhang, Xuemin Lin · 2025

Read DiffGED: Computing Graph Edit Distance via Diffusion-based Graph Matching by Wei Huang, Hanchen Wang, Dong Wen, Wenjie Zhang, Ying Zhang, Xuemin Lin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-18245.txt.

Introduction

Wei Huang and co-authors compute the edit distance between graphs with a diffusion model, in a 2025 paper. The distance counts the fewest changes turning one graph into another, a basic measure for chemistry, networks, and pattern matching. Exact solvers crawl on large graphs, while neural shortcuts give a number but not the actual edit path users want.

DiffGED generates many candidate node matchings in parallel, letting a diffusion model dream up diverse pairings. Each pairing converts directly into an edit path, and the best wins. Variety keeps the search out of poor local traps. The authors report stronger solutions than hybrid rivals. The method restores the path, not just the price.

Catalog record

CREATORWei Huang, Hanchen Wang, Dong Wen, Wenjie Zhang, Ying Zhang, Xuemin Lin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-18245

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

DiffGED: Computing Graph Edit Distance via Diffusion-based Graph Matching Wei Huang, Hanchen Wang, Dong Wen, Wenjie Zhang, Ying Zhang, Xuemin Lin Abstract . The Graph Edit Distance (GED) problem, which aims to compute the minimum number of edit operations required to transform one graph into another, is a fundamental challenge in graph analysis with wide-ranging applications. However, due to its NP-hard nature, traditional A* approaches often suffer from scalability issue, making them computationally intractable for large graphs. Many recent deep learning frameworks address GED by formulating it as a regression task, which, while efficient, fails to recover the edit path—a central interest in GED. Furthermore, recent hybrid approaches that combine deep learning with traditional methods to recover the edit path often yield poor solution quality. These methods also struggle to generate candidate solutions in parallel, resulting in increased running times. In this paper, we present a novel approach, DiffGED, that leverages generative diffusion model to solve GED and recover the corresponding edit path. Specifically, we first generate multiple diverse node matching matrices in parallel through a diffusion-based graph matching model. Next, node mappings are extracted from each generated matching matrices in parallel, and each extracted node mapping can be simply transformed into an edit path. Benefiting from the generative diversity provided by the diffusion model, DiffGED is less likely to fall into local sub-optimal solutions, thereby achieving superior overall solution quality close to the exact solution. Experimental results on real-world datasets demonstrate that DiffGED can generate multiple diverse edit paths with exceptionally high accuracy comparable to exact solutions while maintaining a running time shorter than most of hybrid approaches. DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Mathematics of computing Graph algorithms CCS: Mathematics of computing Combinatorial optimization CCS: Computing methodologies Machine learning 1. Introduction Graph edit distance (GED) computation is a fundamental NP-hard problem in graph theory ( Bunke, 1997 ) , and GED is also one of the most popular similarity measurements for graphs ( Gouda and Arafa, 2015 ; Liang and Zhao, 2017 ) , with broad applications in computer vision and pattern recognition, such as scene graph edition ( Chen et al., 2020 ) , image matching ( Cho et al., 2013 ) , and signature verification ( Maergner et al., 2019 ) . It aims to determine the minimum number of edit operations required to transform one graph into another as illustrated in Figure 1 . Traditional solvers are mostly designed to find the solution based on A* search ( Neuhaus et al., 2006 ; Blumenthal and Gamper, 2020 ; Chang et al., 2020 ) . However, these solvers often fail to scale to graphs with more than 16 nodes within reasonable time since the search space grows exponentially with the number of nodes ( Blumenthal and Gamper, 2020 ) . Figure 1 . The optimal edit paths for transforming G to G^{\prime} . GED (G,G^{\prime})=4 . In recent years, there has been increasing attention on adopting Graph Neural Networks (GNNs) for GED estimation ( Bai et al., 2019 ; Bai and Zhao, 2021 ; Zhuo and Tan, 2022 ; Ling et al., 2021 ; Bai et al., 2020 ; Zhang et al., 2021 ; Qin et al., 2021 ) . These approaches typically take a pair of graphs as input and directly estimate GED in one shot through neural networks with extremely short running time. However, the estimated GED might be smaller than the exact GED, which means there is no actual edit path for the estimated GED. What is worse, these approaches are not designed to recover the edit path for the estimated GED, where the edit path is often the central interest of many applications ( Wang et al., 2021 ) . To overcome these limitations, many hybrid approaches ( Wang et al., 2021 ; Yang and Zou, 2021 ) proposed to guide the A* search with an effective and efficient heuristic learned by GNNs. Unfortunately, these A*-based approaches still suffer from exponential time costs. The state-of-the-art approach GEDGNN ( Piao et al., 2023 ) proposed to predict a node matching matrix across two graphs by GNNs, then top- k node mappings with maximum weights are extracted from the predicted node matching matrix to derive the candidate edit paths. However, the extracted top- k node mappings depend solely on a single node matching matrix and are highly correlated, thus the following limitations could arise: (1) The extracted top- k node mappings might fall into the local sub-optimal if the predicted node matching matrix is biased; (2) Highly correlated node mappings limit the diversity of found edit paths, as multiple diverse edit paths could exist with multimodal distribution for an optimal GED; (3) The extraction of top- k node mappings cannot be parallelized to reduce the running time. In this work, we propose DiffGED, a novel method that utilizes a diffusion-based graph matching model to compute GED with extremely high accuracy and recover its corresponding edit path. Specifically, DiffGED first generates k diverse node matching matrices in parallel by our diffusion-based graph matching model DiffMatch. Next, k edit paths can be derived by extracting one node mapping from each node matching matrix in parallel using a greedy algorithm, the derived edit path with the minimum number of edit operations will be selected as our solution. Therefore, our proposed DiffGED reduces the correlation between each extracted node mapping, which not only enhances overall accuracy and decreases the likelihood of the extracted candidate solutions being locally sub-optimal, but also improves the diversity of the found edit paths. More importantly, these top- k mapping computations could be parallelized to reduce the running time. Our main contributions can be summarized as follows: • We propose a novel deep learning framework, DiffGED, that computes the edit path for GED by generating multiple node matching matrices and extracting multiple node mappings in parallel. • To the best of our knowledge, this is the first work that proposes a generative diffusion model for graph matching, namely DiffMatch. DiffMatch can generate diverse and high-quality node matching matrices and enable the parallelization of top- k node mappings computation. • Extensive experiments on real-world datasets demonstrate that our proposed DiffGED (1) has exceptionally high accuracy (around 95\% on all datasets) which outperforms the baseline methods by a great margin, (2) has great interpretability by generating diverse edit paths, and (3) has a shorter running time compared to other deep learning-based approaches. 2. Related Work 2.1. Traditional Approaches for GED Traditional exact approaches are often based on A* search ( Blumenthal and Gamper, 2020 ; Chang et al., 2020 ) guided with designed heuristics to prune unpromising search space. Unfortunately, these exact solvers are usually intractable for large graphs due to the NP-hard nature of GED computation. To enhance the scalability, traditional approximation approaches focus on constructing a node edition cost matrix, then model GED as a bipartite node matching problem and solve by either Hungarian ( Riesen and Bunke, 2009 ) or Volgenant-Jonker ( Bunke et al., 2011 ) algorithm in polynomial time. Another type of approximation method simplifies and accelerates A* search, such as A*-beam search

Read the complete text