## 4 The Proposed Model
### The General Framework  
This paper adopts the filtering-verification solving strategy, which is commonly used in graph query problems [16; 17]. For this novel graph query task, both the filtering process and verification process have new content. In the filtering process, a series of candidate subgraphs is generated by searching the induced subgraph space. The induced subgraph space refers to the set of all the induced subgraphs of the given graph. The generated candidate subgraphs are the points in the induced subgraph space. Then, the candidate subgraphs that do not meet the conditions are filtered out by various pruning methods. In the verification process, the subgraph isomorphism testing is performed to check whether the candidate subgraphs generated in the filtering process are unique or not. Subgraph isomorphism has been proven to be an NP-complete problem in many papers [12; 13]. Therefore, the times of subgraph isomorphism testing must be reduced as much as possible due to its high cost. This requires us to design better candidate set generation and pruning strategies. The above steps ensure the induced subgraph property and uniqueness property of MUIS, but the minimality property cannot be guaranteed. The minimality property requires that the found MUIS has the least number of vertices in all unique induced subgraphs containing the query position. Therefore, we cannot judge whether an induced unique subgraph containing the query position is MUIS before we know that all the induced subgraphs containing the query position with less vertices are not unique. In Figure 4, considering that \(v_{1}\) is the query position, we can see that the induced subgraph \(g_{3}\) is unique and contains the query positon, but we cannot judge whether \(g_{3}\) is MUIS, as explained above. From the figure, we can also see that the induced subgraph \(g_{2}\) containing the query positon is also unique, and the number of vertices is less than that of \(g_{3}\). Therefore, when searching the induced subgraph space, the search must be performed from the lower layer to the higher layer, that is to say, the induced subgraphs are searched in ascending order of the number of vertices. Figure 4: An example to show the importance of searching induced subgraphs in ascending order of the number of vertices. The general framework for MUIS query is given in Algorithm 1, which contains a global Boolean variable _Found_ to show whether MUIS has been found. We search the space from the lower layer to the high layer (Lines 2\(\sim\)3). We then check whether the subgraph is unique in Line 4. Line 5 is a further uniqueness testing for Line 4, which will be explained in detail later. When MUIS is found, we can exit the main loops of the algorithm (Lines 6\(\sim\)15). If the value of _Found_ is still false after searching all the induced subgraph space, the data graph itself is the MUIS since it is a unique induced subgraph and the number of vertices is minimal in this situation (Lines 16\(\sim\)17). Line 5 addresses the self-isomorphism problem, which may cause misjudgment. Figure 5 is a false positive example. Consider data graph \(G\) and the query position \(v_{3}\). \(g_{3}\) is an induced graph containing the query position and has the minimal number of vertices. However, it is isomorphic to itself under mapping \(M=\{(v_{1},v_{1}),(v_{4},v_{2}),(v_{2},v_{4})\}\). Since \(g_{3}\) gets an isomorphic induced subgraph, we may judge it to be not unique. However, in fact, there is no other induced subgraph isomorphic to \(g_{3}\) in \(G\). Therefore, \(g_{3}\) is unique. It is necessary to avoid such a misjudgment. If all the vertices of the two induced subgraphs are the same in the original data graph, it is self-isomorphism.