## 3 Notation and Preliminaries
* The edge deletion cost of deleting an \(\epsilon_{2}\)-labeled edge is \(1\). Since the proposed algorithm performs frequent approximate subgraph mining, it must be defined when a subgraph is considered frequent. To establish this, we introduce the following definitions. First, we consider whether a subgraph allowing label and structural variations appears in a graph collection. If it appears, each appearance is viewed as an occurrence of the subgraph:  
**Definition 5** (Occurrence). : _Let \(D=\{G_{1},G_{2},\ldots G_{n}\}\) be a graph collection of \(n\) undirected labeled simple graphs, \(G^{\prime}\) be a subgraph, \(\beta\) be a dissimilarity threshold, and \(\text{dissimilarity}(G_{i},G_{j})\) be the graph dissimilarity function described in Definition 4. Then \(G^{\prime\prime}\), a subgraph of \(G_{i}\in D\), is an occurrence of \(G^{\prime}\) if \(\text{dissimilarity}(G^{\prime},G^{\prime\prime})\leq\beta\)._  
Next, we define the support of a subgraph, which counts the number of graphs in the collection in which the subgraph has at least one occurrence:  
**Definition 6** (Support). : _Let \(D=\{G_{1},G_{2},\ldots G_{n}\}\) be a graph collection of \(n\) undirected labeled simple graphs and \(\beta\) a dissimilarity threshold. The support of a subgraph \(G^{\prime}\) in \(D\), denoted as \(Support(G^{\prime},D)\), is defined as:_  
\[Support(G^{\prime},D)=\frac{\sum_{j=1}^{n}f(G^{\prime},G_{j})}{|D|} \tag{2}\]  
_where,_  
\[f(G^{\prime},G_{j})= \begin{cases}1&\text{if }\exists\ G^{\prime\prime}\text{ subgraph of }G_{j}\text{ such that }G^{\prime\prime}\text{ is an occurrence }\text{ of }G^{\prime}\text{ in }G_{j}\\ 0&\text{otherwise}\end{cases}  \tag{3}\]  
Before defining a frequent subgraph, we first define a frequent node, which is the simplest form of a frequent subgraph, consisting of a single node:  
**Definition 7** (Frequent node). : _Let \(D=\{G_{1},G_{2},\ldots G_{n}\}\) be a graph collection of \(n\) undirected labeled simple graphs and a be a support threshold. A node \(v\) is said to be frequent in the graph collection \(D\) if the number of graphs in which it appears, divided by the number of graphs in the collection, is greater than or equal to the support threshold \(\alpha\)._  
Finally, we define frequent subgraph:  
**Definition 8** (Frequent subgraph). : _Let \(D=\{G_{1},G_{2},\ldots G_{n}\}\) be a graph collection of \(n\) undirected labeled simple graphs, \(\alpha\) a support threshold, and \(\beta\) a dissimilarity threshold. A subgraph \(G^{\prime}\) is considered frequent within the graph collection \(D\) if there exists at least one frequent node \(v_{f}\), according to \(\alpha\) (see Definition 7), such that for each occurrence \(G^{\prime\prime}\) of \(G^{\prime}\), according to \(\beta\) (see Definition 5), \(v_{f}\in V_{G^{\prime\prime}}\), and \(Support(G^{\prime},D)\geq\alpha\)._Another important aspect to consider is to reduce the search space and speed up the mining process. For this purpose, we use the anti-monotonicity property, which is defined as follows:  
**Definition 9** (Anti-monotonicity property). : _Let \(D\) be a graph collection of \(n\) undirected labeled simple graphs, and \(G^{\prime}\) and \(G^{\prime\prime}\) be two graphs in the graph collection \(D\). If \(G^{\prime\prime}\) is a subgraph of \(G^{\prime}\) then \(Support(G^{\prime\prime},D)\geq Support(G^{\prime},D)\)._  
The anti-monotonicity property states that if a subgraph is not frequent, then none of its supergraphs is frequent; thus, they can be pruned without affecting the search.