Graph matching : filtering databases of graphs using machine learning techniques
Christophe Irniger · 2005
Graphs are a powerful concept useful for various tasks in science and engineering. In applications such as pattern recognition and information retrieval, object similarity is an important issue. If graphs are used for object representation, then the problem of determining the similarity of objects turns into the problem of graph matching. Some of the most common graph matching paradigms include graph and subgraph isomorphism detection, maximum common subgraph extraction and error-tolerant graph matching. A number of solutions for all of these tasks have been proposed in the literature, but they all suffer from the high computational complexity inherent to graph matching. An additional problem arises in applications where an input graph is to be matched not only to another single graph, but to an entire database of graphs under a given matching paradigm. If the database is large, sequential comparison of the input graph with each graph from the database using conventional