# A Parallel Approach for Frequent Subgraph Mining in a Single Large Graph Using Spark
## 6 Discussion  
The proposed algorithm in this paper is applied to FSM on a single large certain graph data, in which each edge definitely exists. However, uncertain graphs are also common and have practical importance in the real world, e.g., the telecommunication or electrical networks. In the uncertain graph model [33], each edge of a graph is associated with a probability to quantify the likelihood that this edge exists in the graph. Usually the existence of edges is assumed to be independent. There are also two types of FSM on uncertain graphs: transaction based and single graph based. Most existing work on FSM on uncertain graphs is developed on transaction settings, i.e., multiple small/medium uncertain graphs. FSM on uncertain graph transactions under expected semantics considers a subgraph frequent if its expected support is greater than the threshold. Representative algorithms include Mining Uncertain Subgraph patterns (MUSE) [34], Weighted MUSE (WMUSE) [35], Uncertain Graph Index(UGRAPH) [36] and Mining Uncertain Subgraph patterns under Probabilistic semantics (MUSE-P) [37]. They are proposed under expected semantics or the probabilistic semantics. Here, we mainly discuss the measurement of uncertainty and applications of techniques proposed in this paper considering single uncertain graph. The measurement of uncertainty is important when considering an uncertain graph. Combining labelled graph in Definition 1 in this paper, an uncertain graph is a tuple \(G^{u}=(G,P)\), where \(G\) is the _backbone_ labelled graph, and \(P:E\rightarrow(0,1]\) is a probability function that assigns each edge \(e\) with an existence probability, denoted by \(P(e),e\in E\). An uncertain graph \(G^{u}\) implies \(2^{|E|}\) possible graphs in total, each of which is a structure \(G^{u}\) may exist as. The existence probability of \(G^{i}\) can be computed by the joint probability distribution:  
\[P(G^{u}\Rightarrow G^{i})=\prod_{e\in E_{G^{i}}}P(e)\prod_{e\in E_{G}/E_{G^{i} }}(1-P(e)).\]  
Generally speaking, FSM on single uncertain graph can also be divided into two phases: subgraph extension and support evaluation. The subgraph extension phase is the same as that for FSM on the backbone graph \(G\). Thus, techniques used in this paper, such as canonical adjacency matrix for representing subgraphs and the parallel extension for extending subgraphs, can be used in the single uncertain graph. The biggest difference lies in the support evaluation phase. The support of a subgraph \(g\) in an uncertain graph \(G^{u}\) is measured by _expected support_. A straightforward procedure to compute the expected support is generating all implied graphs, computing and aggregating the support of the subgraph in every implied graph, and last deriving the expected support, which can be accomplished by the CSP model used in this paper. Formally, the expected support is a probability distribution over the support in implied graphs:  
\[eSup(g,G^{u})=\sum_{i=1}^{2^{|E|}}P(G^{u}\Rightarrow G^{i})\cdot Sup(g,G^{i}),\]  
where \(G^{i}\) is an implied graph of \(G^{u}\). The support measure \(Sup\) can be the MNI support introduced in Definition 5, which is computed efficiently. Thus, given an uncertain graph \(G^{u}=(G,P)\) and an expected support threshold \(\tau\), FSM on an uncertain graph finds all subgraphs \(g\) whose expected support is no less than the threshold, i.e., \(G=\{g|eSup(g,G^{u})\geq\tau\wedge g\subseteq G\}\). Furthermore, let \(P_{j}(g,G^{u})\) denote the aggregated probability that the support of \(g\) in an implied graph is no less than \(j\):  
\[P_{j}(g,G^{u})=\sum_{G^{i}\in\Delta_{j}(g)}P(G^{u}\Rightarrow G^{i}),\]  
where \(\Delta_{j}(g)=\{G^{i}|Supg,G^{i}\geq j\}\). The expected support can be reformulated as:  
\[eSup(g,G^{u})=\sum_{j=1}^{M_{g}}P_{j}(g,G^{u}),\]  
where \(M_{g}\) is the maximum support of \(g\) among all implied graphs of \(G^{u}\). For the detailed proof, we refer to [25].