An Efficient Screening Algorithm for Inexact Sub-graph Isomorphism
Yi-Yang Chiang, Wenlin Huang, Shun‐Fa Hwang, Shinn‐Ying Ho · 2005
Inexact sub-graph matching of attributed relational graphs is a hard combinatorial optimization problem with the constraint of structure consistence. This paper proposes an efficient screening algorithm to solve the inexact sub-graph isomorphism problems by incrementally reducing the infeasible search space such that the search for near optimal solutions can be confined in a relatively small feasible space. The screening algorithm mainly consists of three stages: construction, pruning and evaluation. The aim of the construction stage is to efficiently identify initial candidates for individual vertices and edges from each label mapping between two graphs by using a given geometric tolerances of attribute values. As for the pruning stage, it iteratively eliminates most of these vertex and edge candidates which lead to infeasible combinations by considering the whole topological graph structure. Consequently, at the evaluation stage, the desired near optimal solutions can be obtained from evaluating all mappings of the remaining candidates based on an objective function measure. This screening algorithm can also work efficiently using a zero tolerance for exact sub-graph isomorphism. Simulation results indicated that near optimal solutions can be obtained by using few pruning iterations and a small number of objective function evaluations even though the tolerance is up to 50% of the maximal edge attribute value by using an existing graph benchmark database.