## 3 Problem Formulation  
In this section, we introduce motif statistics. For readability, the notations used throughout the paper are listed in Table 1. We denote the graph of interest as a labeled undirected graph \(G=(V,E,L)\), where \(V\) is the set of nodes, \(E\) is a set of _undirected_ edges, and \(L\) is a set of labels \(l_{u,v}\) associated with undirected edges \((u,v)\in E\). For example: (1) directed networks use labels \(l_{u,v}\in\{\rightarrow,\leftarrow,\leftrightarrow\}\) to indicate the direction of the edges \((u,v)\in E\); (2) \(l_{u,v}\in\{+,-\}\) for edges in signed networks having positive or negative labels; (3) a regular undirected graph can be represented by setting \(L\) to null. \begin{table}
\begin{tabular}{c l} \hline \hline \(G\) & \(G=(V,E,L)\) is the graph of interest \\ \hline \(G^{*}\) & \(G^{*}=(V^{*},E^{*},L^{*})\) is a sampled graph \\ \hline \(V(s),s\in C^{(k)}\) & set of nodes in \(k\)-node CIS \(s\) \\ \hline \(E(s),s\in C^{(k)}\) & set of edges in \(k\)-node CIS \(s\) \\ \hline \(M(s)\) & motif class ID of CIS \(s\) \\ \hline \(T_{k}\) & number of \(k\)-node subgraph classes \\ \hline \(M_{i}^{(k)}\) & \(i\)-th \(k\)-node motif \\ \hline \(C^{(k)}\) & set of \(k\)-node CIS in \(G\) \\ \hline \(C^{(k*)}\) & set of \(k\)-node CIS in \(G^{*}\) \\ \hline \(C_{i}^{(k)}\) & set of CIS in \(G\) isomorphic to \(M_{i}^{(k)}\) \\ \hline \(n^{(k)}=|C^{(k)}|\) & number of \(k\)-node CIS in \(G\) \\ \hline \(n_{i}^{(k)}=|C_{i}^{(k)}|\) & number of CIS in \(G\) isomorphic to \(M_{i}^{(k)}\) \\ \hline \(\omega_{i}^{(k)}=\frac{n_{i}^{(k)}}{n^{(k)}}\) & concentration of motif \(M_{i}^{(k)}\) in \(G\) \\ \hline \(P\) & matrix \(P=[P_{ij}]_{1\leq i,j\leq T_{k}}\) \\ \hline \(p_{i,j}\) & probability that \(s^{*}\) isomorphic to \(M_{i}^{(k)}\) given \\  & \(s\) isomorphic to \(M_{j}^{(k)}\) \\ \hline \(Z_{j}\) & \(Z_{j}=\{i:i=1,\ldots,T_{k},\text{ and }P_{i,j}>0\}\) \\ \hline \(\phi_{i,j}\) & number of subgraphs of \(M_{j}^{(k)}\) isomorphic \\  & to \(M_{i}^{(k)}\) \\ \hline \(S_{G^{*},G}^{(k)}\) & \(S_{G^{*},G}^{(k)}=\{(s^{*},s):s^{*}\in C^{(k*)},s\in C^{(k)},\) \\  & \(V(s^{*})=V(s)\}\) \\ \hline \(\pi_{i,j}(s_{1},s_{2})\) & \(s_{1}\) and \(s_{2}\) are two \(k\)-node CIS in \(G\) \\  & isomorphic to motif \(M_{j}^{(k)}\). Let \(s_{1}^{*}\) and \(s_{2}^{*}\) be the induced subgraphs of node sets \(V(s_{1})\) \\  & and \(V(s_{2})\) in \(G^{*}\), respectively. \(\pi_{i,j}(s_{1},s_{2})\) \\  & is defined as the probability that \(s_{1}^{*}\) and \(s_{2}^{*}\) are both isomorphic to motif \(M_{i}^{(k)}\). \\ \hline \(m_{i,j}^{(k)}\) & number of elements \((s^{*},s)\in S_{G^{*},G}^{(k)}\), where \\  & \(s^{*}\) is isomorphic to motif \(M_{i}^{(k)}\) and \(s\) is isomorphic to motif \(M_{j}^{(k)}\) \\ \hline \(p\) & probability of sampling an edge \\ \hline \(q\) & \(q=1-p\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Table of notations. \(G\) is any signed network; in this case, \(T_{3}=7\). Figure 3c reveals all motifs with three nodes for any directed network; in such a case, \(T_{3}=13\). Figure 3d reveals all four-node motifs of any unlabeled and undirected network; in this case, \(T_{4}=6\). Figure 3e shows all five-node motifs of any unlabeled and undirected network; in this case, \(T_{5}=21\). Throughout the paper, \(C_{i}^{(k)}\) is defined as the set of CIS in \(G\) that are isomorphic to the \(i\)-th \(k\)-node motif \(M_{i}^{(k)}\). Define the frequency of motif \(M_{i}^{(k)}\) as \(n_{i}^{(k)}=|C_{i}^{(k)}|\), i.e., the number of CIS in \(C_{i}^{(k)}\). For example, \(C_{1}^{(3)}\) includes two CIS for the directed graph \(G\) in Figure 2: (1) the CIS made up of \(a\), \(b\), and \(d\), and (2) the CIS made up of \(a\), \(c\), and \(d\). Thus, \(n_{1}^{(3)}=2\). In this paper, we focus on designing fast and accurate sampling methods to reduce the time needed to count motif frequencies.