Constraint Rules And Branch Learning For Subgraph Isomorphism Problem

The subgraph isomorphism(SI)is to determine whether subgraph occurs inside target graph is isomorphic to the given pattern graph.SI problem is one of the classic NP-complete problems with wide applications in social networks,integrated circuits,information retrieval,bioinformatics and other fields.The exact algorithm for SI needs to traverse the computationally exponential search space.As the graph size increases,the solution time exponentially explodes.How to find the solution quickly on the sparse large graphs transformed from real problems is the direction that researchers have been working on.The algorithm of SI solving is divided into complete algorithm and incomplete algorithm.Nowadays,the mainstream algorithm is Branch-and-Bound(Bn B)which belongs to completeness algorithm.To address the problems that the branching strategy of SI algorithm relies on the static properties of the graph,lacks information for dynamic search,and the selected branching points in backtracking are concentrated on a few vertices,a hybrid policy based on branching learning adopted nogood path and degree constraint is proposed to increase the learning experience of dynamic search and reduce the local redundancy caused by the greedy strategy in backtracking.Specific work includes:(1)To avoid invalid searches,degree rule is used to remove candidate vertices with degrees are smaller than the degree of current vertex in target graph.Reduce the matchable range of the pattern graph(2)Remove the vertices that appear in the nogood records,select a vertex in the decreasing order of their rewards.Nogood records is the branch path without target solution before each restart.After restarting,the vertices appearing in these records are removed from historical search by checking the nogood records base,which induces the search space.(3)The new hybrid policy rewards each vertex and match pair receives with the upper bound reduction,and alternatively selects the vertex or match pair to branch,such that the solution can be found as early as possible and the local optima can be avoided.14,220 instances from biology,image and so on are computed.Experimental results show that SIBL solves 10.08%(19.88%)instances more than the state-of-the-art Glasgow(Mc Split+RL＿SI).The method of branch learning improves significantly the SI algorithms.