# FSM-BC-BSP: Frequent Subgraph Mining Algorithm Based on BC-BSP
## 3 Proposed Method
### Detailed Design
#### 3.2.3 Local Computing  
The local computing phase of FSM-BC-BSP is responsible for generating candidate subgraphs and performing subgraph isomorphism tests. Candidate subgraphs are generated using the rightmost path extension strategy, and subgraph isomorphism is achieved through specification encoding. For a given frequent pattern of size \(k\), a candidate pattern of size \(k+1\) is obtained by adding a frequent edge belonging to the EEM during the candidate subgraph generation stage. If a frequent edge introduces a new vertex, we say that this frequent edge is the outer edge; otherwise, for the inner edge, the latter simply connects the existing vertices in the frequent pattern. The newly added vertex in the outer edge is given an ID, which is the largest of the already existing vertices in the frequent pattern; the size of the vertex IDs represents the order in which they were added as they were expanded outside. In the topological structure of graph mining, the candidate pattern is called the frequent edge sub-node and the frequent edge is called the parent node of the candidate pattern. Based on this parent-child relationship, a candidate subgraph spanning tree can be constructed during the mining job. It should be noted that if the candidate pattern has \(k+1\) edges, the candidate pattern will have multiple paths in the candidate subgraph spanning tree according to the order of edges added. However, in FSM-BC-BSP, it is stated that only one build path will be considered valid and no other redundant candidate patterns will be generated. With such a constraint, it is guaranteed that such a candidate subgraph spanning tree is unique to an FSM-BC-BSP task. In this paper, the rightmost path generation strategy is used. In short, the rightmost path is the shortest path from the vertex with the smallest ID to the vertex with the largest ID, and the graph is extended on such a path. In the process of building candidate subgraphs, multiple generation paths may produce the same candidate subgraph, necessitating subgraph isomorphism detection. FSM-BC-BSP uses the minimal DFS code specification encoding method. The same minimal DFS code within the same structure facilitates pruning and supports the calculation of candidate subgraphs on different vertices. An example of the principle of the minimal DFS code is shown in Figure 4. The DFS of Figure 4a, depending on the order of the access vertices, may lead to different depth-first search trees, i.e., a graph may correspond to multiple depth-first search trees, Figure 4b-d are the depth-first search trees of Figure 4a. Converting each subscripted graph into an edge sequence leads to DFS encoding. DFS encoding establishes two types of order; in order to select the smallest encoding DFS encoding as the standard encoding, one is the order of the edge, which is also the access sequence, as shown in Figure 4b. For the forward edge order (0,1) (1,2) (1,3), backward edge order (2,0), one is the sequence order. Table 1 presents the DFS encoding corresponding to the DFS tree in Figure 4.  
For the edge sequences, we establish two edge sequences \(e_{1}\) = (\(i_{1}\), \(j_{1}\)) and \(e_{2}\) = (\(i_{2}\), \(j_{2}\)). If one of the following four conditions is true, then \(e_{1}\prec e_{2}\). 1. If both are forward edges, then (\(j_{1}<j_{2}\)) or (\(i_{1}<i_{2}\) and \(j_{1}=j_{2}\));
2. If both are backward edges, then (\(i_{1}<i_{2}\)) or (\(i_{1}=i_{2}\) and \(j_{1}<j_{2}\));  
Figure 4: An example of DFS trees. (**a**) Original image; (**b–d**) Different depth-first search trees of (**a**). 3. If \(e_{1}\) is the backward edge, and \(e_{2}\) is the forward edge, then \(i_{1}<i_{2}\);
4. If \(e_{1}\) is the forward edge, and \(e_{2}\) is the backward edge, then \(j_{1}\leq j_{2}\);  
For the sequence order, it is necessary to define the order of different sequences in different DFS codes.