## 4 The Proposed Model
### Query Position-Based Subgraph Isomorphism  
Subgraph isomorphism is used to check the uniqueness of candidate subgraphs in our paper. Most subgraph isomorphism algorithms are implemented with the backtracking strategy [15; 16; 17], which finds solutions by incrementing partial solutions or abandoning them when it is determined that they cannot be completed until a full match is found. A set of candidate vertices \(C(u)\) for query vertex \(u\) is computed at the first step according to specific rules. If \(C(u)\) is empty, that is to say no isomorphic subgraphs, the programs exit. Otherwise, the algorithms invoke the main recursive function \(SubgraphSearch\) to match one query vertex with one data vertex one time. Figure 8: An example of the matched vertices-based pruning strategy. Figure 7: An example to show isomorphism between the hypergraph and subgraph. We propose a query positon-based subgraph isomorphism algorithm to improve the testing efficiency for our application. The main ideas is discussed in detail as follows. 1. Use the query position as the starting vertex of the isomorphism testing Using the query position as the starting vertex of the isomorphism testing makes full use of the query position in the data graph, and it is the most important improvement in the isomorphism testing algorithm. When the subgraph isomorphism testing is performed on candidate subgraphs, matching the query position first can avoid invalid and extra isomorphism testing. Figure 9 is an illustration of the importance of matching the query position first. Considering the data graph \(G\) and the query position \(v_{1}\), \(g_{3}\) is an induced subgraph of \(G\) containing the query position with three vertices. If we do not use \(v_{1}\) as the first matching vertex, it will be matched in two directions. For the first direction, we can get matched pairs of vertices \((v_{3},v_{3})\), \((v_{2},v_{2})\) and \((v_{1},v_{1})\), where the isomorphic subgraph is \(g_{3}\) itself. For the other direction, we can get matched pairs of vertices \((v_{3},v_{3})\) and \((v_{2},v_{4})\) and will stop for the non-matched vertices \(v_{1}\) in \(g_{3}\) and \(v_{5}\) in \(G\). We have to do more testing to judge whether \(g_{3}\) is unique. When using \(v_{1}\) as the first matching vertex, the second direction testing can be avoided. In fact, much local or partial matching can be avoided when using the query position as the starting vertex of the isomorphism testing, thus judging whether the induced subgraph is unique as soon as possible and improving the efficiency of verification process. In addition, we use the query rewrite method in [17] to rank the other vertices in the query graph and get a matching order according to the ranking value. In this way, we can reduce the candidate regions for performing subgraph isomorphism search and improve the efficiency. 2. Sorting the candidate vertices by degree for pruning For vertex pairs \((u,v)\) in the candidate set \(P\), \(u\) represents the vertex from induced subgraph \(g_{i}\), and the set of \(u\) can be denoted as \(P(g_{i})\), while \(v\) represents the vertex from data graph \(G\), and the set of \(v\) can be denoted as \(P(G)\). In the undirected graph, before judging whether vertex pairs \((u,v)\) in \(P\) are matched, sort the vertices in \(P(G)\) by degree in descending order. Since \(u\) and \(v\) are matched only when the degree of \(v\) is greater than or equal to the degree of \(u\), when the degree of \(v\) is less than the degree of \(u\), it can be pruned. For a given vertex \(u\), if the degree of the vertex \(v\) taken from the sorted \(P(G)\) is less than the degree of \(u\), then the degree of the vertices after \(v\) in \(P(G)\) must be less than the degree of \(u\), which can be pruned directly without further judgment. The pruning algorithm is denoted as \(PruningDegree(u,v)\). In the directed graph, the vertices can be sorted by in degree and out degree. Both can be used for pruning.