# A Parallel Approach for Frequent Subgraph Mining in a Single Large Graph Using Spark
## 3 The SSiGraM Approach
### Parallel Support Evaluation  
Our SSiGraM approach employs the CSP model [12] as the subgraph support evaluation strategy. The constraint satisfaction problem (CSP) is an efficient method for finding subgraph isomorphisms (Definition 3), which is illustrated as follows:  
**Definition 10**.: _(CSP Model): Let \(G_{1}=(V_{1},E_{1},L_{V_{1}},L_{E_{1}},\varphi_{1})\) be a subgraph of a graph \(G=(V,E,L_{V},L_{E},\varphi)\). Finding isomorphisms of \(G_{1}\) in \(G\) is a CSP\((\mathcal{X},\mathcal{D},\mathcal{C})\) where: 1. \(\mathcal{X}\) is an ordered set of variables which contains a variable \(x_{v}\) for each node \(v\in V_{1}\). 2. \(\mathcal{D}\) is the set of domains for each variable \(x_{v}\in\mathcal{X}\). Each domain is a subset of \(V\). 3. Set \(\mathcal{C}\) contains the following constraint rules: \(\bullet\)\(\forall x_{v},x_{v^{\prime}}\in\mathcal{X}\), \(x_{v}\
eq x_{v^{\prime}}\). \(\bullet\)\(\forall x_{v}\in\mathcal{X}\) and the corresponding \(v\in V_{1}\), \(\varphi(x_{v})=\varphi_{1}(v)\)._\(\forall x_{v},x_{v^{\prime}}\in\mathcal{X}\) and the corresponding \(v,v^{\prime}\in V_{1}\), \(\varphi(x_{v},x_{v^{\prime}})=\varphi_{1}(v,v^{\prime})\).  
For example, the CSP model of a subgraph in Figure 1b under graph Figure 1a is:  
\[\left(\begin{array}{c}\mathcal{X}:\{x_{v_{1}},x_{v_{2}},x_{v_{3}}\},\\ \mathcal{D}:\{\{u_{1},u_{2},...,u_{10}\},\{u_{1},u_{2},...,u_{10}\},\{u_{1},u_ {2},...,u_{10}\}\},\\ \mathcal{C}:\{x_{v_{1}}\
eq x_{v_{2}}\
eq x_{v_{3}},\\ \varphi(v_{1})=\text{REF},\varphi(v_{2})=\text{GOV},\varphi(v_{3})=\text{GOV},\\ \varphi(v_{1},v_{2})=3,\varphi(v_{2},v_{3})=9\}\end{array}\right)\]  
Theorem 2[12] describes the relation between subgraph isomorphism and the CSP model. Intuitively, the CSP model is similar to a template, in which each variable in \(\mathcal{X}\) is a slot. A _solution_ is a correct slot fitting which assigns a different node of \(G\) to each node of \(G_{1}\), such that the labels of the corresponding nodes and edges match. For instance, a solution to the CSP of the above example is the assignment \((x_{v_{1}},x_{v_{2}},x_{v_{3}})=(u_{2},u_{4},u_{5})\). If there exists a solution that assigns a node \(u\) to variable \(x_{v}\), then this assignment is valid. \(x_{v_{1}}=u_{2}\) is a valid assignment while \(x_{v_{1}}=u_{1}\) is invalid in this example.  
Theorem 2: _A solution of the subgraph \(G_{1}\) to graph \(G\) CSP corresponds to a subgraph isomorphism of \(G_{1}\) to \(G\)._  
Theorem 3: _Let \((\mathcal{X},\mathcal{D},\mathcal{C})\) be the subgraph CSP of \(G_{1}\) under graph \(G\). The MNI support of \(G_{1}\) in \(G\) satisfying:_  
\[Sup_{MNI}(G_{1},G)\geq\tau\iff\forall x_{v}\in\mathcal{X},ASS_{valid}(x_{v}) \geq\tau.\]  
_where \(ASS_{valid}(x_{v})\) is the total count of valid assignments of variable \(x_{v}\)._  
According to Theorem 3[12], we can consider the CSP of subgraph \(G_{1}\) to graph \(G\) and check the count of valid assignments of each variable. If there exist \(\tau\) or more valid assignments for every variable, in other words, at least \(\tau\) nodes in each domain \(D_{1},...,D_{n}\) for the corresponding variables \(x_{v_{1}},...,x_{v_{n}}\), then subgraph \(G_{1}\) is frequent under the MNI support. Thus, the main idea of the heuristic search strategy is elaborated as: if any variable domain remains with less than \(\tau\) candidates during the search process, then the subgraph cannot be frequent.