FAST-GED: GPU-Accelerated Graph Edit Distance (Best Paper Award)
The International Conference on Computational Science (ICCS) 2026 was held in Hamburg, Germany, from 29th June to 1st July 2026. We presented our paper, Efficient Accelerated Graph Edit Distance Computation on GPU, which received the Best Paper Award.
Graph Edit Distance (GED) measures the cost of transforming one graph into another — a key operation in bioinformatics, pattern recognition, and machine learning. However, computing GED is NP-hard, and existing methods are either too slow or too inaccurate for large graphs.
We propose FAST-GED, an open-source GPU-accelerated framework that makes GED computation both fast and accurate. It uses a BFS-style K-Best search mapped entirely onto the GPU: each GPU block expands one search node, each thread evaluates one edit operation, and a two-phase ranking selects the top-K candidates without full sorting — all without any host-device data transfer.
On NVIDIA A100 GPUs (JUWELS Booster), FAST-GED reaches optimal GED in over 90% of cases with 26–55× speedup over NetworkX, outperforms Beam Search and DFS methods on real-world datasets, and scales to graphs with 1000 vertices in under one second. We also demonstrate two applications: graph classification with KNN achieving accuracy comparable to Graph Neural Networks, and a 1000× speedup for GED-based Neural Architecture Search.
The source code and datasets are available on GitLab. Check out the paper and preprint for full details.