Poster (After Call)

FZJ-2024-06811

http://join2-wiki.gsi.de/foswiki/pub/Main/Artwork/join2_logo100x88.png FAS-GED: GPU-Accelerated Graph Edit Distance Computation

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

2024

This record in other databases:

Please use a persistent id in citations: doi:10.34734/FZJ-2024-06811

Abstract: Graph Edit Distance (GED) is a fundamental metric for assessing graph similarity with critical applications across various domains, including bioinformatics, classification, and pattern recognition. However, the exponential computational complexity of GED has hindered its adoption for large-scale graph analysis. This poster presents FAS-GED, a GPU framework for fast and accurate GED computation. FAS-GED achieves significant performance gains by optimizing memory accesses and minimizing data transfer while maintaining high accuracy. FAS-GED shows up to a 300x speedup over its CPU-based implementations on 48-CPU AMD EPYC. Our approach surpasses existing methods in speed and precision, demonstrating up to a 55x speedup over the NetworkX library for small graphs and reaching optimal solutions in 94% of cases. FAS-GED is a step toward unlocking the potential of GED for large-scale graph analysis in real-world applications.

---

Contributing Institute(s):

1. Jülich Supercomputing Center (JSC)

Research Program(s):

1. 899 - ohne Topic (POF4-899) (POF4-899)
2. 5112 - Cross-Domain Algorithms, Tools, Methods Labs (ATMLs) and Research Groups (POF4-511) (POF4-511)
3. 5122 - Future Computing & Big Data Systems (POF4-512) (POF4-512)
4. ATML-X-DEV - ATML Accelerating Devices (ATML-X-DEV) (ATML-X-DEV)

Appears in the scientific report 2024

---

Database coverage:

---