A network based approach to exact and inexact graph matching

In this paper a new approach to exact and inexact graph matching is introduced. We propose a compact network representation for graphs, which is capable of sharing identical subgraphs of one or several model graphs. The new matching algorithm NA works on the network and uses its compactness in order to speed up the detection process. Next, the problem of inexact graph matching is described and a distance measure based on basic graph edit operations and subgraph isomorphism is defined. We propose an inexact network algorithm INA which determines the optimal distance between an input graph and a set of model graphs along with the corresponding subgraph isomorphism. In addition to INA, a new lookahead procedure is proposed. The lookahead procedure works simultaneously over a set of model graphs and efficiently limits the size of the search space. The advantages of the new methods are studied in a theoretical complexity analysis. Finally, some experimental results with randomly generated graphs and a traditional graph matching algorithm for comparision confirm the superiority of the new methods in practice. CR Categories and Subject Descriptor: F.2 Analysis of Algorithms and Problem Complexity; I.2.4 [Artificial Intelligence]: Knowledge representation formalisms and methods; I.2.8 [Artificial Intelligence]: Problem solving, Control Methods and Search; I.5 [Artificial Intelligence]: Pattern Recognition General Terms: Algorithms Additional Keywords: Graphs, subgraph isomorphism, RETE