Inexact Graph Matching: A Case of Study

Ivan Olmos, Jesus A. Gonzalez, Mauricio Osorio

Inexact graph matching has become an important research area because it is used to find similarities among objects in several real domains such as chemical and biological compounds. Let G and G' be input labeled graphs, we present an algorithm capable to find a graph S of G, where S is isomorphic to G' and the corresponding labels between the vertices and edges of S and G' are not the same (inexact matching). We use a list-code based representation without candidate generation, where a step by step expansion is implemented. The proposed approach is suitable to work with directed and undirected graphs. We conducted a set of experiments in a genome database in order to show the effectiveness of our algorithm. Our experiments show a promissing method to be used with scalable graph matching tools that can be applied to areas such as Machine Learning (ML) and Data Mining (DM).

Subjects: 12. Machine Learning and Discovery; 11. Knowledge Representation

Submitted: Feb 13, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.