# A Parallel Approach for Frequent Subgraph Mining in a Single Large Graph Using Spark
## 4 Experimental Evaluation
### Experimental Results  
**Performance:** At the top part of Figure 7, we show the performance comparison between SSiGraM and GraMi on DBLP, Aviation, GDELT and Twitter datasets. The number of results grows exponentially when the support threshold \(\tau\) decreases. Thus, the running time of all algorithms also grows exponentially. Our results indicate that SSiGraM outperforms GraMi by an order of magnitude for all datasets. For bigger dataset GDELT and lower \(\tau\) (9600), GraMi ran out of memory and was not able to produce a result. For smaller dataset Aviation and bigger \(\tau\) (2200, 2300 and 2400), GraMi is faster because the resource scheduling of Hadoop YARN in SSiGraM will cost 10 to 20 s. Actually, in this circumstance, there is no need to use parallel mining algorithms since GraMi can give results within a few seconds. For the Twitter dataset, SSiGraM is about five times faster than GraMi because of the existence of nodes with a big degree. When a subgraph involves such a node, SSiGraM will not go to the next iteration until the executor finishes calculating the support of this subgraph.  
Figure 7: Performance of SSiGraM and GraMi on the four different datasets. Abbreviations: DBLP (DataBase systems and Logic Programming), GDELT (Global Data on Events, Location and Tone).  
The bottom part of Figure 7 illustrates the total numbers of identified frequent subgraphs on each dataset. The identical numbers of frequent subgraphs of SSiGraM and GraMi elaborate the correctness of our SSIGraM algorithm.  
**Optimization:** Figure 8 demonstrates the effect of the three optimizations discussed above on the DBLP and GDELT datasets. For both datasets, the SSIGraM with all optimizations (denoted by All opts. in Figure 8) definitely performs best. For the DBLP dataset, when \(\tau>3500\), load balancing is the most effective optimization while as \(\tau\) becomes bigger, pre-search pruning becomes the most effective. For the GDELT dataset, the pre-pruning is always the most effective optimization. When no optimization is involved (denoted by No opt. in Figure 8), the algorithm performs worst. Actually, the effect of each optimization strategy varies with input graphs and different thresholds.  
**Parallelism:** Finally, to evaluate the effect of the number of executors, we fix the supports of each dataset and vary the _num-executor_ parameter of the Spark configuration file. According to the principle of the same allocated memory from YARN, we set _num-executors_ to 20, 15, 10, 5 and 1 with _executor-memory_ being 6 GB, 8 GB, 12 GB, 24 GB and 120 GB respectively. The results shown in Figure 9 lead to three major observations. First, compared with GraMi's performance shown in Figure 7, the proposed algorithm outperforms the GraMi algorithm even when only one executor was used. This is because the complexity of SSGraMi is less than that of GraMi ( \(\mathcal{O}(n\cdot N^{n-1})\) ), especially when \(n\) is large. Second, the runtime decreases with the increment of parallelism for each dataset overall. Third, when the _num-executor_ is bigger than 10, the performance improvement is less obvious because  
Figure 8: The effect of each optimization. **All opts.**: All optimization enabled; **Load balancing:** Only load balancing enabled; **Pre-pruning:** Only pre-search pruning enabled; **Top-down prune:** Only top-down pruning enabled; **No Opt.** No optimization strategies involved.  
Figure 9: The effect of the number of executors on each dataset.  
the final performance will be dependent on a few time-consuming subgraphs. Thus, most executors will wait until these subgraphs are finished. More executors cannot avoid this phenomenon.