Efficient Accelerated Graph Edit Distance Computation on GPU

Dabah, Adel; Herten, Andreas

doi:10.1007/978-3-032-29921-5_2

Contribution to a conference proceedings/Contribution to a book

FZJ-2026-03305

Efficient Accelerated Graph Edit Distance Computation on GPU

Dabah, A. (Corresponding author)FZJ* ; Herten, A.FZJ*

2026
Springer Cham
ISBN: 978-3-032-29920-8 (print), 978-3-032-29921-5 (electronic)

Computational Science – ICCS 2026
26th International Conference on Computational Science, ICCS 2026, Hamburg, Germany, 29 Jun 2026 - 1 Jul 2026 Cham : Springer, Lecture Notes in Computer Science 16783, : 26, 17-31 (2026) [10.1007/978-3-032-29921-5_2]

This record in other databases:

Please use a persistent id in citations: doi:10.1007/978-3-032-29921-5_2 doi:10.1007/978-3-032-29921-5

Abstract: Graph representation is a powerful abstraction of real-world objects and relations. Computing the Graph Edit Distance (GED) between graphs is critical in domains such as bioinformatics, machine learning, and pattern recognition. GED measures the minimum number of edit operations required to transform one graph into another. However, the high computational complexity of optimal and near-optimal methods limits their applicability to large-scale graphs, making high-performance parallel GED computation essential. To address this, we propose FAST-GED, a fast and scalable open-source framework for GED computation on GPUs. FAST-GED overcomes existing limitations by combining high accuracy with fast execution through GPU-friendly algorithmic design and efficient mapping to GPU hardware, minimizing host-device communication. The implementation is optimized and tested across multiple GPU architectures. We validate FAST-GED on real and synthetic datasets with diverse graph sizes and densities. It achieves speedups of several orders of magnitude over the Python NetworkX library while reaching optimal solutions in most cases. Moreover, it outperforms state-of-the-art approximate methods in both accuracy and scalability. We show that FAST-GED enables broader adoption of GED-based solutions in real-world applications. Keywords: Graph Edit Distance · GPU Computing · Parallel Algorithms · Graph Matching · High-Performance Computing

Contributing Institute(s):