## 4 The Proposed Model
### Query Position-Based Subgraph Isomorphism
Algorithm 3 is a detailed description of the query position-based subgraph isomorphism. The algorithm starts from empty mapping \(M\), and the global Boolean variable \(unique\) is set to true value at the beginning in Line 1. The algorithm uses the query position as the starting point of the isomorphism testing in Line 2. The \(PruningDegree\) pruning function is called before adding the first vertex mapping pair to maximize the performance (Line 3). Then, we invoke \(QueryRevrite\) to get the matching order of the other vertices except the query position (Line 4). For each vertex that matches  
Figure 9: The importance of matching the query position first. the query position, the algorithm calls the recursive subroutine \(SubgraphSearch\) to find the complete isomorphism mapping (Lines 5\(\sim\)8). ```
0: data graph, \(G=(V,E,l)\); query position, \(q\); induced graph, \(g_{i}\)
0: Boolean variable to answer whether another induced graph in \(G\) isomorphic to graph \(g_{i}\), \(unique\);
1:\(M:=\emptyset\), \(unique=true\);
2: get all vertices \(w_{q}\) (\(\in P(G)\)) whose label is the same as \(q\), sort \(P(G)\) by degree in descending order;
3:\(PruningDegree(q,w_{q})\);
4:\(O=QueryRewrite(q,g_{i})\);
5:for each \(w_{q}\in P(G)\)do
6:\(M:=M\cup(q,w_{q})\);
7:\(subgraphsearch(g_{i},G,M,O,...)\)
8:endfor
9: Subroutine SubgraphSearch
10:if\(|M|=|V(g_{i})|\)then
11:\(report\)\(M\);
12:if the isomorphism subgraph of \(G\) is \(g_{i}\) itself then
13:\(report\)\(self\)\(isomorphism\);
14:else
15: set \(unique=false\), stop all procedures;
16:endif
17:else
18:\(v:=NextQueryVertex(O,...)\);
19: compute candidate vertices \(w\) (\(\in W\)) of \(v\);
20:\(PruningDegree(v,w)\) ;
21:for each \(w\in W\) and \(w\) is not yet matched do
22:if\(Isjoinable(g_{i},G,M,v,w,...)\)then
23: set \(M:=M\cup(v,w)\);
24:\(subgraphsearch(g_{i},G,M,O,...)\)
25:endif
26:endfor
27:endif
```  
**Algorithm 3** Query position-based subgraph isomorphism. In \(SubgraphSearch\), Lines 1\(\sim\)7 present the termination condition of the program. When a full mapping is found (Line 1), we check whether it is self-isomorphism (Line 3). If it is self-isomorphism, we continue to find the real isomorphism subgraph (Line 4). If not, we set \(unique\) as false and stop the procedure (Line 6). If \(unique\) is true when compared with all other induced subgraphs containing \(q\), all main programs exit, and MUIS is obtained. Lines 8\(\sim\)18 show how to increase partial mapping. The \(NextQueryVertex\) function is invoked to get the next query vertex (Line 9). For the current query vertex \(v\), compute and refine the candidate vertex set \(W\) subsequently (Lines 10\(\sim\)11). Then, for each vertex \(w\) in \(W\), the \(Isjoinable\) function is invoked to check whether the edges between \(v\) and already matched query vertices in query graph \(g_{i}\) have corresponding edges between \(w\) and already matched data vertices in data graph \(G\) (Lines 12\(\sim\)13). If \(w\) is qualified, add \((v,w)\) to the already matched pairs of vertices (Line 14), and then, continue to invoke \(SubgraphSearch\) recursively to match the remaining query vertices and data vertices (Line 15).