Vertex Similarity - A Basic Framework for Matching Geometric Graphs
Ayser Armiti, Michael Gertz · 2014
Abstract. Solutions to the graph matching problem play an impor-tant role in many application domains, such as chemistry, proteomics, or image processing. Especially in these domains, graphs have geometric properties that describe the positions of the vertices in some 2- or 3-dimensional space. Several exact and approximate approaches have been proposed to address the problem of matching graphs, which is known to be NP-hard in general. For this, most approaches depend on the concept of vertex similarity to iteratively increase the matching quality. In this paper, we study the vertex similarity problem for geometric graphs. We formally define such a problem and prove that its complex-ity is NP-hard. For geometric graphs in 2D, we propose an approximate solution with polynomial runtime. For this, we utilize techniques under-lying attributed cyclic string matching and customized edit operations that consider spatial properties and labeling information. In our evalua-tions, we show that our approach outperforms existing vertex similarity approaches in terms of classification accuracy and matching quality. 1