Inexact graph matching through graph coverage

In this paper we propose a novel inexact graph matching procedure called graph coverage, to be used in supervised and unsupervised data driven modeling systems. It relies on tensor product between graphs, since the resulting product graph is known to be able to encode the similarity of the two input graphs. The graph coverage is defined on the basis of the concept of graph weight, computed on the weighted adjacency matrix of the tensor product graph. We report the experimental results concerning two distinct performance evaluations. Since for practical applications the computing time of any inexact graph matching procedure should be feasible, the first tests have been conceived to measure the average computing time when increasing the average size of a random sample of fully-labeled graphs. The second one aims to evaluating the accuracy of the proposed dissimilarity measure when used as the core of a classification system based on the k-NN rule. Overall the graph coverage shows encouraging results as a dissimilarity measure.