INEXACT GRAPH MATCHING THROUGH GRAPH COVERAGE

Lorenzo Livi, Guido Del Vescovo, Antonello Rizzi

2012

Abstract

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.

Paper Citation

in Harvard Style

Livi L., Del Vescovo G. and Rizzi A. (2012). INEXACT GRAPH MATCHING THROUGH GRAPH COVERAGE . In Proceedings of the 1st International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM, ISBN 978-989-8425-98-0, pages 269-272. DOI: 10.5220/0003732802690272

in Bibtex Style

@conference{icpram12,
author={Lorenzo Livi and Guido Del Vescovo and Antonello Rizzi},
title={INEXACT GRAPH MATCHING THROUGH GRAPH COVERAGE},
booktitle={Proceedings of the 1st International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM,},
year={2012},
pages={269-272},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003732802690272},
isbn={978-989-8425-98-0},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 1st International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM,
TI - INEXACT GRAPH MATCHING THROUGH GRAPH COVERAGE
SN - 978-989-8425-98-0
AU - Livi L.
AU - Del Vescovo G.
AU - Rizzi A.
PY - 2012
SP - 269
EP - 272
DO - 10.5220/0003732802690272