## 4 Proposed Algorithm
### Expand Occurrences  
After the candidate subgraphs are generated, the process of identifying their corresponding occurrences within the graph collection begins. To do this, each occurrence of the frequent subgraph that originated the candidate subgraph is expanded.  
To explain the expansion process in detail, the following considerations must be established:  
* If the node dictionary \((\gamma)\) or edge dictionary \((\delta)\), or both, are included, they must be considered when evaluating similarities between labels. Figure 2 illustrates the structure of these dictionaries, each composed of three elements (origin label, similar label, and similarity percentage). In the node dictionary, the node label 'A' has a 90% similarity to label 'B', while in the edge dictionary, the edge label 'A' has a 100% similarity to the edge label 'B'. It is important to note that the dictionaries' similarities do not apply in both directions; for example, in the node dictionary, label 'A' has a 90% similarity to label 'B', but this does not imply that label 'B' has a 90% similarity to label 'A'.
* The new node, \(\
u_{new}\), is the last node added to a frequent subgraph to form a candidate subgraph.
* A node in a subgraph may have a corresponding node (not necessarily with the same label) in the occurrence, which we will call a mapped node. Since the nodes differ, the maximum allowable dissimilarity must be controlled.
* Not all nodes in the occurrence need to be mapped to nodes in the subgraph. Nodes that are not mapped are called extra nodes.  
Figure 1: Cases of subgraph expansion during the pattern growth process. (**a**) The frequent subgraph is highlighted in pink. (**b**) Expansion of the frequent subgraph joining the neighbor node \⃝{} through the edge \(\blacktriangle\) highlighted in yellow. (**c**) Expansion of the frequent subgraph adding the edge \(\blacktriangle\) highlighted in yellow, which creates a cycle.  
Before expanding the occurrence \(o_{curr}\), it must be verified whether, without modifying it, it fulfills the dissimilarity threshold. Figure 3b shows an example where the occurrence does not expand but is considered a candidate occurrence.  
To expand each occurrence \(o_{curr}\) of the frequent subgraph that originated the candidate subgraph, the first step is to search for all possible nodes for expansion within the graph containing \(o_{curr}\). Each potential expansion node \(v_{exp}\) must be similar to \(v_{new}\). The extra nodes within \(o_{curr}\) are also considered in the search. If the \(\beta\)-occurrence \(o_{curr}\) and the candidate subgraph belong to the same graph, the nodes of the candidate subgraph are not considered in the search. From this, there are three possibilities:  
* If \(v_{exp}\) is a neighbor of the occurrence \(o_{curr}\), a new candidate occurrence \(o_{new}\) is created, joining the occurrence \(o_{curr}\) with the node \(v_{exp}\), and \(v_{exp  
considered occurrences of the candidate subgraph and maintained as candidate subgraph occurrences. Occurrences that do not fulfill the dissimilarity threshold are eliminated.  
The support of a candidate subgraph is calculated using its occurrences to determine whether a candidate subgraph is a frequent subgraph (see Definition 6). If the support is greater than the support threshold, the candidate subgraph becomes a frequent subgraph. Otherwise, the candidate subgraph is pruned (discarded), according to the anti-monotonicity property. This property implies that if an expansion of a candidate subgraph does not fulfill the support threshold, then no further expansions will fulfill this threshold. Thus, no more frequent subgraphs can be obtained by expanding this candidate.  
Since the processes followed by the proposed algorithm could produce repeated frequent subgraphs, a frequent subgraph is stored only if it has not been stored previously.