HGED: A Hybrid Search Algorithm for Efficient Parallel Graph Edit Distance Computation
Author:
Open Access
- 25 September 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 8, 175776-175787
Abstract
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 HGED. To maximize thread utility, 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, HGED outperforms the state-of-the art serial algorithm AStar + -LSa by 6 times and the state-of-the parallel algorithm PGED by 4 times.Keywords
Funding Information
- Research Funds of Jeonbuk National University, in 2020
- Basic Science Research Program through the National Research Foundation of Korea
- Korea government (2019R1F1A1059795)
This publication has 18 references indexed in Scilit:
- Exact Graph Edit Distance Computation Using a Binary Linear Program2016
- An Exact Graph Edit Distance Algorithm for Solving Pattern Recognition Problems2015
- A partition-based approach to structure similarity searchProceedings of the VLDB Endowment, 2013
- Efficient processing of graph similarity queries with edit distance constraintsThe VLDB Journal, 2013
- TreeSpan2012
- Efficient Graph Similarity Joins with Edit Distance Constraints2012
- SAPPERProceedings of the VLDB Endowment, 2010
- Comparing starsProceedings of the VLDB Endowment, 2009
- SAGA: a subgraph matching tool for biological graphsBioinformatics, 2006
- A graph distance metric based on the maximal common subgraphPattern Recognition Letters, 1998