Accelerating Graph Similarity Calculations with FAS-GED
Poster in institute repository: https://doi.org/10.34734/FZJ-2024-06811
Graphs are powerful tools for representing real-world objects and relations in numerous domains, such as bioinformatics, pattern recognition, and computer vision. However, quantifying their similarity or difference is crucial despite the computationally expensive execution. The Graph Edit Distance (GED) is a popular metric that measures the cost of transforming one graph into another using operations such as node/edge insertion, deletion, or substitution. It can be applied in K-Nearest Neighbor classifiers, image matching, or to compare molecular structures.
While of significant algorithmic importance, the computational complexity of GED grows exponentially with graph size, making it impractical for large-scale tasks. To address this challenge, we present the FAS-GED framework, which leverages GPUs to provide a fast, accurate, and scalable solution for GED computation.
Traditional GED computation methods struggle with efficiency, particularly for large graphs or dense datasets. But FAS-GED is from the ground up designed for efficient scaling by exploiting GPU parallelism. It is an approximation method, but still maintains high accuracy. In our tests, it can scale up to large graphs (1000 vertices), balancing accuracy and computational complexity.
FAS-GED follows a BFS-style search, but retains only the top K candidates at each level. It uses a three-phase GPU pipeline for efficient GED computation, in which each GPU thread executes edit operations, ranking nodes directly on the GPU, and discarding sub-threshold candidates.
Compared to the popular NetworkX library, FAS-GED reaches a 55× speedup for small graphs and scales efficiently to larger datasets. It retains over 95% accuracy, with deviations under 0.5% compared to optimal methods. It outperforms traditional methods like Beam Search (BS) or Depth-First Search (DFS).
Check out the poster about FAS-GED below, which we presented at SC24 in Atlanta!