Error-tolerant geometric graph similarity

Abstract

Graph matching is the task of computing the similarity between two graphs. Error-tolerant graph matching is a type of graph matching, in which a similarity between two graphs is computed based on some tolerance value whereas within exact graph matching a strict one-to-one correspondence is required between two graphs. In this paper, we present an approach to error-tolerant graph similarity using geometric graphs. We define the vertex distance (dissimilarity) and edge distance between two graphs and combine them to compute graph distance. © Springer Nature Switzerland AG 2018.