Speeding up Graph Matching by Means of Systematic Graph Reductions Using Centrality Measures

Gillioz, Anthony; Riesen, Kaspar (2022). Speeding up Graph Matching by Means of Systematic Graph Reductions Using Centrality Measures. In: 2022 12th International Conference on Pattern Recognition Systems (ICPRS). IEEE 10.1109/ICPRS54038.2022.9854062

Text Speeding_up_Graph_Matching_by_Means_of_Systematic_Graph_Reductions_Using_Centrality_Measures.pdf - Published Version Restricted to registered users only Available under License Publisher holds Copyright. Download (1MB)

Comparing large graphs using graph edit distance is a time-consuming or even intractable problem. This is mainly due to the exponential time complexity of graph edit distance w.r.t. to the size of the underlying graphs. Nevertheless, considering its great adaptability, graph edit distance is a popular metric in structural pattern recognition and has found widespread applications. Main contribution of the present paper is to substantially speed up the computation of graph edit distance by initially reducing the graphs to the most important substructures. The graph downsizing is based on centrality measures - e.g. Page Rank -. That is, we systematically delete nodes including their edges from our graphs that offer the least level of influence to the overall graph structure. We empirically validate the benefit of our reduction method by classifying reduced graphs from a broad range of applications with a distance-based classifier. The main finding is that we can reduce the computation time by a wide margin while maintaining satisfying classification accuracy.

Interest & Impact

Downloads

1 since deposited on 29 Feb 2024
1 in the past 12 months

Citations

5 Citations in Web of Science ®
6 Citations in Scopus

Search

in Google Scholar™

Services

Actions (login required)

Edit item

Actions (login required)

Edit item