\(1.0\times 10^{6}\) edges [12], there exist more than \(2.0\times 10^{10}\) four-node CIS. Furthermore, because the number of k-node CIS generally increases exponentially with k, the number of five-node CIS is higher in both of these graphs. To solve this problem, many existing works [12; 13; 14; 15; 16] have explored approximate algorithms to estimate these statistics, making a trade-off between accuracy and computational time. These methods perform node sampling, edge sampling, or path sampling on the original graph and use the sampled graph to inference the statistics of all subgraphs in the original graph. The above sampling schemes usually prefer frequent motifs and under-sample rare ones (i.e., motifs with low frequencies). Among them, both [16] and our method can estimate motif frequencies, although our method is mainly biased towards rare motifs, and the algorithms of the two are different. As a result, these methods exhibit large errors for estimating rare motifs' statistics, and fail in many real applications such as anomaly detection (i.e., finding rare or unusual patterns) [17; 18] and community search (i.e., finding the densest subgraphs and cliques) [19; 20]. A potential way to solve the above problem is stratified sampling with the proportion-ate allocation strategy [21], the basic idea of which can be simply described as follows. For a motif \(M\) with frequency \(n\) (i.e., \(G\) has \(n\) CIS isomorphic to \(M\)), we suppose that each of its CISe (i.e., CIS in \(G\) isomorphic to \(M\)) is independently sampled with the same probability \(\gamma\). Then, we estimate the motif frequency \(n\) as \(\hat{n}=\frac{m}{\gamma}\), where \(m\) is the number of sampled CIS for which the original CIS are isomorphic to \(M\). We can easily find that the variance of \(\hat{n}\) is \(n(\frac{1}{\gamma}-1)\), which implies that we can reduce the estimation error by increasing \(\gamma\). With a fixed sampling budget, we can reduce the total estimation errors of characterizing all motifs by assigning larger probabilities to motifs with lower frequencies. However, it is not feasible to directly sample CIS in a graph with pre-defined probability \(\gamma\), which hinders us from performing stratified sampling. To address the above challenge, in this paper we propose a novel method called Mosar, (Motif Sampling and Retrieving), to estimate all motif frequencies. Mosar first obtains a sampled graph \(G^{*}\) from the graph \(G\) under study using random edge sampling, i.e., each and every edge in \(G\) is sampled with the same probability \(p\). In our experiments, we observe that motifs with more edges usually have lower frequencies for many real-world graphs. Moreover, the probability of a \(k\)-node CIS s in \(G\) also appearing as a \(k\)-node CIS in \(G^{*}\) increases with the number of edges in \(s\), where \(k\) is the size of motifs under study. For example, an unclosed wedge and a triangle in \(G\) are observed in \(G^{*}\) with probabilities \(p^{2}\) and \(3p^{2}-2p^{3}\), respectively (note that \(3p^{2}-2p^{3}\approx 3p^{2}\) when \(p<0.1\)). Thus, Mosar can be simply viewed as a novel weighted motif sampling method, and it tends to sample rare motifs. Clearly, \(G^{*}\) may exhibit different motif statistics from \(G\) due to two kinds of uncertainties: (1) CIS in \(G^{*}\) and their original CIS in \(G\) may be different; and (2) CIS are not sampled uniformly. For example, Figure 1 shows that a sample graph \(G^{*}\) has three-node directed motif concentrations which differ greatly from \(G\); the Flickr graph [22] is used as \(G\) and \(G^{*}\) is obtained by randomly sampling each edge of \(G\) with the same probability \(0.05\). To remove the error introduced by these two uncertainties, [PERSON] retrieves the original CIS of all \(k\)-node CIS in \(G^{*}\) and then builds a probabilistic model to \"re-weight\" sampled CIS to compute motif statistics. Our experiments on a variety of public datasets show that our method is two orders of magnitude more accurate state-of-the-art methods.