# A Parallel Approach for Frequent Subgraph Mining in a Single Large Graph Using Spark
## 3 The SSiGraM Approach
### Parallel Subgraph Extension  
Our approach employs a breadth first search (BFS) strategy that generates all subgraphs in parallel through FFSM-Join and FFSM-Extend proposed in [23]. Similarly, we organize all the suboptimal CAMs of subgraphs in a graph \(G\) into a rooted tree, that follows the rules: (i) The root of the tree is an empty matrix. (ii) Each node in the tree is a distinct subgraph of \(G\), represented by its suboptimal CAM that is either a CAM or a proper suboptimal CAM. (iii) For a given non-root node (with suboptimal CAM \(M\)), its parent is the graph represented by the maximal proper submatrix of \(M\). The completeness of the suboptimal CAM tree is guaranteed by the Theorem 1. For the formal proof, we refer to the appendix in [23].  
Figure 4: Framework of the SSiGraM(Spark based Single Graph Mining) approach. Green notations on the right side are main Spark resilient distributed dataset (RDD) transformations or actions used during the algorithm pipeline. Abbreviations: CAM (Canonical Adjacency Matrix), HDFS (Hadoop Distributed File System), FFSM (Fast Frequent Subgraph Mining).  
**Theorem 1**.: _For a graph \(G\), let \(C_{k-1}\) and \(C_{k}\) be sets of the suboptimal CAMs of all the subgraphs with \((k-1)\) edges and \(k\) edges (\(k\geq 2\)). Every member of set \(C_{k}\) can be enumerated unambiguously either by joining two members of set \(C_{k-1}\) or by extending a member in \(C_{k-1}\)._  
Algorithm 1 shows how the subgraph extension process is conducted in parallel. Actually, the extension process is implemented in parallel at the parent subgraph scale (Lines 6-15), which means that each group of subgraphs with the same parent will be sent to an executor for extension in the Spark cluster. The FFSM operator is provided by [32], which implements the FFSM-Join and FFSM-Extend. After extension, all of the extended results are collected to the driver node (Line 16) from the cluster. Because of the extension on more than one executors at the same time, the indexes of the new generated subgraphs from different executors may be duplicated. As a result, the subgraph indexes are reassigned at the end (Line 17).  
To perform a parallel subgraph extension, Line 11 and Line 13 conduct the joining and extension of CAM across all Spark executors. The overall complexity is \(\mathcal{O}(n^{2}\cdot m)\) where \(n\) is the number of nodes in subgraph and \(m\) number of edges. A complete graph with \(n\) vertices consists of \(n(n-1)/2\) edges. Thus, the final complexity is \(\mathcal{O}(m^{2})\).  
```
0: frequent subgraphs \(S_{k-1}\), broadcasted FFSM operator \(FFSRRDD\), Spark context \(sc\)
0: new generated \(S_{k}\) that extend \(S_{k-1}\)
1:functionParaGenSubgraphs(\(S_{k-1},FFSRRDD\),\(sc\))
2:\(S_{k}\leftarrow\varnothing\)
3:\(FFSMOperator\gets FFSRRDD\)
4:\(PGraph_{S_{k-1}}\gets S_{k-1}\), group by parents
5:\(PGraphRDD_{S_{k-1}}\gets sc.\textbf{parallelize}(PGraph_{S_{k-1}})\)
6:\(S_{k}\gets PGraphRDD_{S_{k-1}}.\textbf{map}\)
7:\(S_{t}\leftarrow\varnothing\)
8:\(C_{list}\leftarrow\) child subgraphs of present parent
9:for\(s_{i}\) in \(C_{list}\)do
10:for\(s_{i}\) in \(C_{list}\)do
11:\(S_{t}\gets S_{t}\cup FFSMOperator.join(s_{i},s_{j})\)
12:endfor
13:\(S_{t}\gets S_{t}\cup FFSMOperator.extend(s_{i})\)
14:endfor
15:return\(S_{t}\)
16:}.collect
17: reassign subgraph indexes in \(S_{k}\)
18:return\(S_{k}\)
19:endfunction
```  
**Algorithm 1** Parallel Subgraph Extension.