# Learning Knowledge Using Frequent Subgraph Mining from Ontology Graph Data
## 2 Methodology
### Frequent Subgraph Mining  
As mentioned above, the existing methodologies for frequent subgraph mining primarily focused on enhancing computational performance without considering the semantic information for each node and edge, mainly from the perspective of candidate generation or the isomorphism test. The proposed methodology assumes an ontology graph and utilizes semantic and mining query information to decompose a large graph into small unit subgraphs, thereby maintaining semantic information and improving computational efficiency. As shown in Figure 1, the methodology comprises three main steps. The first is a preprocessing step in which the mining query is used to find all possible paths in the ontology graph while removing irrelevant components. In the second step, the irrelevant components are removed from the instance graph, after which instance triple paths corresponding to the paths of the ontology graph obtained in the first step are generated, through which the unit subgraphs are generated and restructured. In the third and final step, using these generated unit subgraphs as the unit of frequency, chunking and candidate generation considering the chunk option and chunk label are repeated until the threshold is satisfied, after which the final frequent subgraphs are extracted. Before explaining the detailed methodology, several terms are defined, and their meanings and assumptions used in this study are described. The ontology graph is shown in Figure 2a. Each class (node) and property (edge) are unique in a total ontology graph and multiple properties (multi edge) are allowed. Figure 2b is an example of an instance graph. A class of ontology graphs has one or more instances, and one or more properties between classes are inherited by the property between two instances. Figure 1: Proposed methodology. Owing to the enormous cost of directly searching for frequent subgraph patterns in an entire graph, this study attempts to improve the efficiency of this process by dividing the entire graph into \"unit subgraph.\" \"Unit subgraph\" is a set of instances and properties generated by the mining query. It comprises all paths from an instance of a start class to all instances of the end classes and becomes the basic unit for calculating the frequency. \"Mining Query\" is basically a concept for defining the extent of the subgraph when dividing a large graph into subgraphs of small units. In this study, knowledge graphs based on the ontology graph are the subject of the study, so we tried to make the most use of the information that ontology has. When an expert with information about a specific domain ontology performs frequent subgraph mining on his ontology-based knowledge graph, \"Mining Query\" allows his domain knowledge to be fully reflected in the analysis. The \"Mining Query\" concept is defined as follows. \[\text{Mining Query:}=(SC,\,EC,\,CO) \tag{1}\]  
The mining query comprises three parts, which are defined as follows:  
1. SC (Start Class): the start class of an ontology graph; each instance of this class is a start node of a unit subgraph;
2. EC (End Class): a set of end classes; all instances of these classes are end nodes of the unit subgraph;
3. CO (Chunking Option): chunking option; a set of classes to be chunked considering instances as their classes in a unit subgraph (if not specified, instance level chunking is performed). For example, given a mining query \"Q\" (Equation (2)) has the following meanings: \"We try to find the frequent pattern in the linked relationship of \"User\" and \"Academy\", \"Genre\" and \"Rating\" and in the case of \"WatchingEvent\" and \"Movie\" classes, the information in their instances is not used for analysis.\" This approach is significant in that it can incorporate domain information of experts into the frequent subgraph mining.