# Learning Knowledge Using Frequent Subgraph Mining from Ontology Graph Data
## 2 Methodology
### Movie Rating Prediction
#### 2.2.2 Graph Similarity and Entropy  
The rating graph is a set of patterns (i.e., instance triples), but it is also a graph. Accordingly, this study measures the graph similarity between the target item graph and the rating graph containing the knowledge experienced by the user, and the most similar rating is used as the predicted value. To calculate the graph similarity, a modified Levenshtein distance (edit distance) [23] was used, and entropy was defined for the cost of adding and deleting triples. Typical definition of Graph Edit distance (GED) is known as follows. **Definition 2**. : _Given a set of graph edit operations (also known as elementary graph operations), the graph edit distance \((GED(g_{1},g_{2}))\) between two graphs \(g_{1}\) and \(g_{2}\) can be defined as_  
\[GED(g_{1},g_{2})=\min_{(e_{1},\ldots e_{k})\in P(g_{1},g_{2})}\sum_{i=1}^{k}c( e_{i}) \tag{4}\]  
_where \(P(g_{1},g_{2})\) is the set of edit paths transforming \(g_{1}\) into \(g_{2}\) and \(c(e)\geq 0\) is the cost of each graph edit operation \(e\). In this study, edit operations are addition and deletion of triple considering the graph as a set of triples and paths is not needed when considering characteristics of target graph consisting of \"novie\" and its attributes. In terms of the cost of operation, addition and deletion have the same value, but different values by triple. The concept of \"entropy\" is defined to work as a kind of cost._  
Entropy was defined as the proportion of information contained in each triple or graph in all frequent subgraphs obtained in the previous step. Figure 18 shows the graphs for which the graph similarity must be measured. In this process, each triple constituting the rating graph represents frequency information indicating the number of times they occur in the training data. Each triple contains a different amount of information; therefore, the edit distance is calculated with different contributions corresponding to their different entropies rather than equal contributions. Figure 18: Rating graph and target item graph subject to similarity calculation. Before describing the method for calculating the entropy, several definitions should be presented. First, the rating graphs consist of the subgraphs extracted for each rating, and the entropy is calculated considering the entire rating subgraph set. \(m\) is the number of triples in the rating graph, and \(n\) is the number of rating classes that the user has evaluated. In the case of the movie rating dataset used in the experiment of Section 3.1, the user can assign a rating from 0.5 to 5.0 in units of 0.5, in which case \(n=10\). Rating Graph Entropy (RGE) of rating \(j\) is the proportion of each rating in the rating subgraph set. Accordingly, it is obtained by dividing the sum of the triple frequencies constituting each rating graph by the sum of all triple frequencies of all ratings. \[RGE_{j}=\frac{\sum_{i=1}^{m}f_{ij}}{\sum_{j=1}^{m}\sum_{i=1}^{m}f_{ij}} \tag{5}\]  
where \(f_{ij}\) is the frequency of the triple \(i\) in rating \(j\). In each rating graph, the importance of the triple is assigned differently. The triple with the highest frequency in each rating graph is defined as the Seed Triple (colored section in Table 3), and the entropy of the seed triple has the same value as the RGE of the rating to which the seed triple belongs. The entropy of a triple that is not a seed triple is calculated by dividing the frequency of the triple by that of the seed triple. Thus, Triple Entropy (TE) is the ratio of the information indicating the influence or dominance of each triple in the rating graph. \(sf_{j}\) is the frequency of the seed triple in rating \(j\). \[TE_{ij}=\frac{f_{ij}}{sf_{j}} \tag{6}\]