# A Parallel Approach for Frequent Subgraph Mining in a Single Large Graph Using Spark
## 4 Experimental Evaluation
### Experimental Setup  
**Dataset:** We experiment on four real graph datasets, whose main characteristics are summarized in Table 1. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Dataset** & **\#Node** & **\#L(Node)** & **\#Edge** & **\#L(Edge)** & **Density** \\ \hline DBLP & 151,574 & 7 & 191,840 & 17 & Medium \\ Aviation & 101,185 & 6173 & 133,087 & 41 & Sparse \\ GDELT & 1,515,712 & 14,816 & 2,832,692 & 8 & Sparse \\ Twitter & 11,316,811 & 40 & 85,331,846 & 1 & Dense \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Datasets and their characteristics. ```
0: A graph \(G\), support threshold \(\tau\) and Spark context \(sc\), parallelism \(n\)
0: All subgraphs \(S\) of \(G\) such that \(Sup_{MNI}(S,G)\geq\tau\)
1: result \(S\leftarrow\varnothing\), intermediate subgrah set \(S_{ndd}\leftarrow\varnothing\)
2: load \(Graph_{ndd}\) from \(G\) using \(sc.GraphX\)
3: detect connected areas of \(Graph_{ndd}\)
4:\(FreEdge_{ndd}\gets Graph_{ndd}\)
5:\(FFSM\gets FreEdge_{ndd}\)
6:\(FFSM_{ndd}=sc.\textbf{broadcast}(FFSM)\)
7: initial frequent subgraphs \(S_{1}\gets FreEdge_{ndd}\)
8:\(S_{ndd}\gets S_{1}\)
9:while\(S_{ndd}.count>0\)do
10:\(S_{k-1}\leftarrow S_{ndd}\)
11:\(S_{k}\leftarrow\textbf{ParaGenSubgraphs}(S_{k-1},FFSM_{ndd},sc)\)
12:\(NewSub_{ndd}\gets S_{k}\)
13:\(OldSub_{ndd}\gets NewSub_{ndd}.clone\)
14:\(ExtEdge_{ndd}\gets NewSub_{ndd}.\textbf{join}(FreEdge_{ndd})\)
15:\(OldSub_{ndd}\leftarrow\textbf{LoadBalancing}(OldSub_{ndd},n,sc)\)
16:\(CandSub_{ndd}\gets OldSub_{ndd}.\textbf{join}(ExtEdge_{ndd})\)
17:\(S_{ndd}\gets CandSub_{ndd}.\textbf{flatmap}\)
18: let current subgraph be \(s\)
19:\(D_{s}\gets s\)
20: if\(\textbf{IFs}\textbf{Frequent(}S,D_{s},\tau\textbf{)}\)then
21:return\(s\)
22:\(\textbf{).collect}
23:\(S\gets S\cup S_{rdd}\)
24:endwhile
25:return\(S\)
```  
**Algorithm 4** The SSiGraM Algorithm. _DBLP_ ([[http://dblp.uni-trier.de/db/](http://dblp.uni-trier.de/db/)]([http://dblp.uni-trier.de/db/](http://dblp.uni-trier.de/db/))). The DBLP (DataBase systems and Logic Programming) bibliographic dataset models the co-authorship information and consists of 150 K nodes and nearly 200 K edges. Vertices represent authors and are labeled with the author's field of interest. Edges represent collaboration between two authors and are labeled with the number of co-authored papers. _Aviation_ ([[http://ailab.wsu.edu/subdue/](http://ailab.wsu.edu/subdue/)]([http://ailab.wsu.edu/subdue/](http://ailab.wsu.edu/subdue/))). This dataset contains a list of event records extracted from the aviation safety database. The events are transformed to a graph which consists of 100 K nodes and 133 K edges. The nodes represent event ids and attribute values. Edges represent attribute names and the \"near_to\" relationship between two events. _GDELT_ ([[https://bigquery.cloud.google.com/table/gdelt-bq:full.events?pli=1](https://bigquery.cloud.google.com/table/gdelt-bq:full.events?pli=1)]([https://bigquery.cloud.google.com/table/gdelt-bq:full.events?pli=1](https://bigquery.cloud.google.com/table/gdelt-bq:full.events?pli=1))). This dataset is constructed from part of the raw events exported from the GDELT (Global Data on Events, Location and Tone) dataset. It consists of 1.5 M nodes and 2.8 M edges. Similar to the Aviation dataset, nodes represent events and attribute values (and are labeled with event types and actual attribute values). Edges represents attribute name and the \"relate_to\" relationship between two events. _Twitter_ ([[http://socialcomputing.asu.edu/datasets/Twitter](http://socialcomputing.asu.edu/datasets/Twitter)]([http://socialcomputing.asu.edu/datasets/Twitter](http://socialcomputing.asu.edu/datasets/Twitter))). This graph models the social news of Twitter and consists of 11M nodes and 85 M edges. Each node represents a Twitter user and each edge represents an interaction between two users. The original graph does not have labels, so we randomly added 40 labels to the nodes, the randomization of which follows a Gaussian distribution. In detail, the mean value was set to 50 and the std-deviance 15.