## 4 Motif Sampling and Retrieving
### Motif Frequency Estimation  
Using the probabilistic model above, we put forward a method a method to estimate motif frequencies. The pseudocode for motif frequency estimation is shown in Algorithm 2. ```
input :\(S^{(k)}_{G^{*},G}\) and \(P_{i,j}\) output :\(n^{(k)}_{j}\) /* motif frequency estimation. */ for\((s^{*},s)\in S^{(k)}_{G^{*},G}\)do /* \(m^{(k)}_{i,j}\) is the number of pairs \((s^{*},s)\in S^{(k)}_{G^{*},G}\). */  Generate \(m^{(k)}_{i,j}\);  end for for\(i\in(1,T_{k})\)do if\(P_{i,j}>0\)then \(\hat{n}^{(k)}_{j}\gets m^{(k)}_{i,j}/P_{(i,j)}\) end \(n^{(k)}_{j}\leftarrow\hat{n}^{(k,i)}_{j}\)  end
```  
**Algorithm 2**The pseudocode for Motif Frequency Estimation. Figure 4: Overview of Mosar. Define \(m^{(k)}_{i,j}\), \(1\leq i\leq T_{k}\), as the number of pairs \((s^{*},s)\in S^{(k)}_{G^{*},G}\), where \(s^{*}\) is isomorphic to motif \(M^{(k)}_{i}\) and \(s\) is isomorphic to motif \(M^{(k)}_{j}\). Then, the expectation of \(m^{(k)}_{i,j}\) is computed as  
\[\mathbb{E}[m^{(k)}_{i,j}]=P_{i,j}n^{(k)}_{j}. \tag{4}\]  
When \(P_{i,j}>0\), we have the following estimator of \(n^{(k)}_{j}\):  
\[\hat{n}^{(k,i)}_{j}=\frac{m^{(k)}_{i,j}}{P_{i,j}}. \tag{5}\]  
Denote \(Z_{j}=\{i:i=1,\ldots,T_{k}\), and \(P_{i,j}>0\}\). Thus, we have \(|Z_{j}|\) estimators of \(n^{(k)}_{j}\), i.e., \(\hat{n}^{(k,i)}_{j}\), \(i\in Z_{j}\). Let \(s_{1}\) and \(s_{2}\) be two \(k\)-node CIS in \(G\) isomorphic to the \(j\)-th \(k\)-node motif. Denote \(s^{*}_{1}\) and \(s^{*}_{2}\) as the induced subgraphs of node sets \(V(s_{1})\) and \(V(s_{2})\) in \(G^{*}\), respectively. Define \(\tau_{i,j}(s_{1},s_{2})\) as the probability that \(s^{*}_{1}\) and \(s^{*}_{2}\) are both isomorphic to the \(i\)-th \(k\)-node motif. We can easily find that \(\pi_{i,j}(s_{1},s_{2})=P^{2}_{i,j}\) when \(s_{1}\) and \(s_{2}\) have no common edges (i.e., \(E(s_{2})\cap E(s_{1})\
eq\emptyset\)), and \(\pi_{i,j}(s_{1},s_{2})>P^{2}_{i,j}\) otherwise. For example, as shown in Figure 5, we have \(\pi_{1,2}(s_{1},s_{2})=p^{4}q+4p^{3}q^{2}\) and \(\pi_{2,2}(s_{1},s_{2})=p^{5}\) for the undirected three-node motifs in Figure 3a. Then, we have the following theorem. **Theorem 1**. : _For each \(i\in Z_{j}\), \(\hat{n}^{(k,i)}_{j}\) is an unbiased estimator of \(n^{(k)}_{j}\), i.e.,_  
\[\mathbb{E}(\hat{n}^{(k,i)}_{j})=n^{(k)}_{j}, \tag{6}\]  
_and the variance of \(\hat{n}^{(k,i)}_{j}\) is_  
\[\begin{split}&\  
Place \(\mathbf{1}(\mathbb{X})\) to indicate a signal function that the predicate \(\mathbb{X}\) is true and equal to one, and zero otherwise. Define function  
\[\delta(s)=\mathbf{1}(\exists s^{*},(s^{*},s)\in S_{\mathbb{G}^{*},G}^{(k)}). \tag{9}\]  
Then we can write \(\hat{n}_{j}^{(k,i)}\) as  
\[\hat{n}_{j}^{(k,i)}=\frac{1}{P_{i,j}}\sum_{s\in C_{j}^{(k)}}\delta(s) \tag{10}\]  
Thus, \(\text{Var}(\hat{n}_{j}^{(k,i)})\) is computed as  
\[\text{Var}(\hat{n}_{j}^{(k,i)}) =\frac{1}{P_{i,j}^{2}}\text{Var}(\sum_{s\in C_{j}^{(k)}}\delta(s)) \tag{11}\] \[=\frac{1}{P_{i,j}^{2}}\sum_{s_{1}\in C_{j}^{(k)}}\sum_{s_{2}\in C _{j}^{(k)}}\text{Cov}(\delta(s_{1}),\delta(s_{2}))\] \[=\frac{1}{P_{i,j}^{2}}\sum_{s_{1}\in C_{j}^{(k)}}\sum_{s_{2}\in C _{j}^{(k)}}\pi_{i,j}(s_{1},s_{2})-P_{i,j}^{2}.\]  
Finally, we have  
\[\text{Var}(\hat{n}_{j}^{(k,i)})=\frac{1}{P_{i,j}}n_{j}^{(k)}(1-P_ {i,j}) \tag{12}\] \[\mathbb{E}[m^{(k)}_{i,j}]=P_{i,j}n^{(k)}_{j}. \tag{4}\]0  
In the derivation above, we use \(\pi_{i,j}(s_{1},s_{2})=P_{i,j}\) when \(s_{1}=s_{2}\), and \(\pi_{i,j}(s_{1},s_{2})=P_{i,j}^{2}\) when \(s_{1}\) and \(s_{2}\) have no common edges. Example: For the undirected three-node motifs in Figure 3a, \(\hat{n}_{2}^{(3,1)}\) and \(\hat{n}_{2}^{(3,2)}\) are two estimators of \(n_{2}^{(3)}\), i.e., the number of triangles in \(G\). Note that \(\hat{n}_{2}^{(3,2)}\) is the same estimator of \(n_{2}^{(3)}\) in [23]. Let \(\Gamma\) be the number of pairs of triangles that are not edge disjoint. Then, we have  
\[\mathbb{E}[m^{(k)}_{i,j}]=P_{i,j}n^{(k)}_{j}. \tag{4}\]1  
where parameters \(0\leq\alpha_{i,j}\leq 1\), and \(\sum_{i\in Z_{j}}\alpha_{i,j}=1\).