## 2 Formal Definition and Properties  
In this section, we formulate the minimal unique induced subgraph query and discuss the properties of MUIS. Definition 1: (Graph) A labeled graph \(G\) is defined as \((V,E,l)\) where \(V\) is the set of vertices, \(E(\subseteq V\times V)\) is the set of edges and \(l\) is a label function that maps a vertex or an edge to a set of labels. Definition 2: (Subgraph) If a graph \(G^{\prime}\) has vertices and edges forming subsets of the vertices and edges of a given graph \(G\), \(G^{\prime}\) is a subgraph of \(G\). Definition 3: (Induced subgraph) For a graph \(G=(V,E)\), an induced subgraph \(G^{\prime}=(V^{\prime},E^{\prime})\) of \(G\) is the graph whose vertex set \(V^{\prime}\) is the subset of \(V\) and whose edge set \(E^{\prime}\) consists of all the edges in \(E\) with both endpoints in \(V^{\prime}\). In Figure 1, the vertex set of \(g_{2}\) is \(V_{2}=\{v_{1},v_{2},v_{3}\}\) and the edge set of \(g_{2}\) is \(E_{2}=\{(v_{1},v_{2}),(v_{1},v_{3})\}\). The vertex set of \(g_{1}\) is \(V_{1}=\{v_{1},v_{2},v_{3},v_{4}\}\), and the edge set of \(g_{1}\) is \(E_{1}=\{(v_{1},v_{2}),(v_{1},v_{3}),(v_{1},v_{4})\}\). It is easy to get \(V_{2}\subset V_{1}\) and \(E_{2}\subset E_{1}\). Moreover, \(l_{1}(v_{1})=l_{2}(v_{1})=a\), \(l_{1}(v_{2})=l_{2}(v_{2})=b\), \(l_{1}(v_{3})=l_{2}(v_{3})=b\), \(l_{1}(v_{1},v_{2})=l_{2}(v_{1},v_{2})=x\), \(l_{1}(v_{1},v_{3})=l_{2}(v_{1},v_{3})=x\) and \((v_{1},v_{2})\in E_{2},(v_{1},v_{3})\in E_{2}\Leftrightarrow(v_{1},v_{2})\in E _{1},(v_{1},v_{3})\in E_{1}\). Therefore, \(g_{2}\) is an induced subgraph of graph \(g_{1}\). **Definition 4**. : (_Graph isomorphism_) _A labeled graph \(G^{\prime}=(V^{\prime},E^{\prime},l^{\prime})\) is isomorphic to another graph \(G=(V,E,l)\), denoted by \(G^{\prime}\approx G\), iff there exists a bijection \(M:V\to V^{\prime}\) such that:_  
(1) \(\forall u\in V,l(u)\subseteq l^{\prime}(M(u))\)_,_  
(2) \(\forall(u,v)\in E,(M(u),M(v))\in E^{\prime}\) and \(l(u,v)=l^{\prime}(M(u),M(v))\)_,_  
The bijection \(M\) is called an isomorphism between \(G^{\prime}\) and \(G\). We also say that \(G\) is isomorphic to \(G^{\prime}\) and vice versa. **Definition 5**. : (_Subgraph isomorphism_) _A labeled graph \(G^{\prime}\) is subgraph isomorphic to a labeled graph \(G\), denoted by \(G^{\prime}\subseteq G\), iff there exists a subgraph \(G^{\prime\prime}\) of \(G\) such that \(G^{\prime}\) is isomorphic to \(G^{\prime\prime}\)._  
In Figure 2, we find subgraphs of data graph \(g\) that are isomorphic to query graph \(q\). According to the definition of subgraph isomorphism, there exists two bijections \(M_{1}\) and \(M_{2}\),  
\(M_{1}=\{(u_{1},v_{3}),(u_{2},v_{5}),(u_{3},v_{9}),(u_{4},v_{6})\}\); \(M_{2}=\{(u_{1},v_{6}),(u_{2},v_{5}),(u_{3},v_{9}),(u_{4},v_{3})\}\). **Definition 6**. : (_Self-isomorphism_) _If a labeled graph is isomorphic to itself, we call it self-isomorphism._  
In Figure 2, query graph \(q\) is self-isomorphism. There exists a self-isomorphism bijection \(M_{0}\), \(M_{0}=\{(u_{1},u_{4}),(u_{2},u_{2}),(u_{3},u_{3}),(u_{4},u_{1})\}\). It can be seen from the bijection \(M_{0}\) that the vertices \(u_{1}\) and \(u_{4}\) can be interchanged in query graph \(q\). The two vertices can be regarded as equivalent points. Self-isomorphism graphs usually contain equivalent points. Before the formal definition of MUIS is given, a definition of the Smallest Unique Induced Subgraph (SUIS) that is closely related to the MUIS definition is first given. **Definition 7**. : (_SUIS_) _A labeled graph \(G_{s}=(V_{s},E_{s},l_{s})\) is a SUIS of graph \(G=(V,E,l)\), such that:_  
Figure 1: An example of an induced subgraph. Figure 2: An example of subgraph isomorphism. \(G_{s}\) is a an induced subgraph of \(G\) (induced subgraph property). 2. \(G_{s}\) is unique in the set of induced subgraphs of \(G\), that is to say, there is no other induced subgraph of graph \(G\) isomorphic to \(G_{s}\) except itself (uniqueness property). 3.