HGED: A Hybrid Search Algorithm for Efficient Parallel Graph Edit Distance Computation

• Published in: IEEE access 2020, Vol.8, p.175776-175787
• Main Author: Kim, Jongik
• Format: Article
• Language: English
• Subjects: Algorithms; Computational efficiency; Computing costs; dynamic load balancing; Dynamic loads; graph edit distance; Graph similarity; Heuristic algorithms; hybrid search; Instruction sets; Load management; parallel computation; Search algorithms; Search problems; Synchronism; Synchronization; Transforms; Upper bound; Upper bounds
• ISSN: 2169-3536; 2169-3536
• DOI: 10.1109/ACCESS.2020.3026648

Graph edit distance (GED) is a measure for quantifying the similarity between two graphs. Because of its flexibility and versatility, GED is widely used in many real applications. However, the main disadvantage of GED is its high computational cost. Many solutions have been proposed to speed up GED computation, but most of them focus on developing serial algorithms and only very few solutions consider parallel computing. In this paper, we study a parallel GED computation to elaborate a fast and precise algorithm. Unlike existing solutions that utilize either a depth-first or a best-first search, we propose a hybrid approach that combines depth-first and best-first search paradigms. Our approach can quickly find tighter GED upper bounds, and effectively prune the search space using the upper bounds. Based on the approach, we develop an efficient parallel GED computation algorithm named {\sf HGED} . To maximize thread utility, {\sf HGED} is also equipped with a novel dynamic load balancing scheme whose main focus is on reducing the overhead of thread synchronization. Experimental results on widely used real datasets show that, on average, {\sf HGED} outperforms the state-of-the art serial algorithm {\sf AStar}^{+} - {\sf LSa} by 6 times and the state-of-the parallel algorithm {\sf PGED} by 4 times.