# A Parallel Approach for Frequent Subgraph Mining in a Single Large Graph Using Spark
## 2 Formalism  
A graph \(G=(V,E)\) is defined to be a set of vertexes (nodes) \(V\) which are interconnected by a set of edges (links) \(E\subseteq V\times V\)[26]. A labelled graph also consists of a labeling function \(L\) besides \(V\) and \(E\) that assigns labels to \(V\) and \(E\). Usually, the graphs used in FSM are assumed to be labelled simple graphs, i.e., un-weighted and un-directed labeled graphs with no loops and no multiple links between any two distinct nodes [27]. To simplify the presentation, our SSiGraM is illustrated with an undirected graph with a single label for each node and edge. Nevertheless, as mentioned above, the SSiGraM can also be extended to support either directed or weighted graphs. In the following, a number of widely used definitions used later in this paper are introduced. Definition 1: (Labelled Graph): A labelled graph can be represented as \(G=(V,E,L_{V},L_{E},\varphi)\), where \(V\) is a set of vertexes, \(E\subseteq V\times V\) a set of edges. \(L_{V}\) and \(L_{E}\) are sets of vertex and edge labels respectively. \(\varphi\) is a label function that defines the mappings \(V\to L_{V}\) and \(E\to L_{E}\). Definition 2: (Subgraph): Given two graphs \(G_{1}=(V_{1},E_{1},L_{V_{1}},L_{E_{1}},\varphi_{1})\) and \(G_{2}=(V_{2},E_{2},L_{V_{2}},L_{E_{2}},\varphi_{2})\), \(G_{1}\) is a subgraph of \(G_{2}\), if and only if (i) \(V_{1}\subseteq V_{2}\), and \(\forall v\in V_{1}\), \(\varphi_{1}(v)=\varphi_{2}(v)\); (ii) \(E_{1}\subseteq E_{2}\), and \(\forall(u,v)\in E_{1}\), \(\varphi_{1}(u,v)=\varphi_{2}(u,v)\). \(G_{2}\) is also called a supergraph of \(G_{1}\). Definition 3: (Subgraph Isomorphism): Let \(G_{1}=(V_{1},E_{1},L_{V_{1}},L_{E_{1}},\varphi_{1})\) be a subgraph of \(G\). \(G_{1}\) is subgraph isomorphic to graph \(G\), if and only if there exists another subgraph \(G_{2}=(V_{2},E_{2},L_{V_{2}},L_{E_{2}},\varphi_{2})\subseteq G\) and a bijection \(f:V_{1}\to V_{2}\) satisfying: (i) \(\forall u\in V_{1}\), \(\varphi_{1}(u)=\varphi_{2}(f(u))\); (ii) \(\forall(u,v)\in E_{1}\)\(\iff(f(u),f(v))\in E_{2}\); and (iii) \(\forall(u,v)\in E_{1}\), \(\varphi_{1}(u,v)=\varphi_{2}(f(u),f(v))\). \(G_{2}\) is also called an embedding of \(G_{1}\) in \(G\). For example, Figure 1a illustrates a labelled graph of event interaction graph. Node labels represent the event actor's type (e.g., GOV: government) in CAMEO (Conflict And Mediation Event Observations) codes [28] and edge labels represent the event type [28] between the two actors. Figure 1b,c shows two subgraphs of Figure 1a. Figure 1b (\({v_{1}}\overset{3}{\underset{3}{\underset{2}{\underset{2}{\underset{2}{\underset{ 2}{\underset{2}{\underset{2}{\underset{2}{\underset{2}{\underset{2}{ \underset{2}{\underset{2}{\underset{2}}{\underset{2}{\underset{2}{\underset{2} {\underset{2}{\underset{2}{\underset{2}{\underset{2}{\underset{2}{\underset{2}{ \underset{2}}{\underset{\underset{2}}{\underset{2}{\underset{2}}{\underset{2}{\underset{2}}{ \underset{2}{\_where \(S\) denotes the set of subgraphs in \(G\) with support greater or equal to \(\tau\)._  
For a subgraph \(G_{1}\) and input graph \(G\), the straightforward way to compute the support of \(G_{1}\) in graph \(G\) is to count all its isomorphisms of \(G_{1}\) in \(G\)[29]. Unfortunately, such a method does not satisfy the downward closure property (DCP) since there are cases where a subgraph appears fewer times than its supergraph. For example, in Figure 1a, the single node graph REF (Refugee) appears three times, while its supergraph REF\({}^{3}\)-GOV appears four times. Without the DCP, the search space cannot be pruned and the exhaustive search is unavoidable [30]. To address this issue, we employ the minimum image (MNI) based support which is anti-monotonic introduced in [31]. **Definition 5**. : _(MNI Support): For a subgraph \(G_{1}\), let \(\sum(S)=\{\phi_{1},\phi_{2},...,\phi_{m}\}\) denote the set of all isomorphisms/embeddings of \(G_{1}\) in the input graph \(G\).