A path-finding based method for concept discovery in graphs

In the multi-relational data mining, concept discovery is the problem of inducing definitions of a relation in terms of other relations provided. In this paper, we present a method that combines graph-based and association rule mining-based methods for concept discovery in graphs. The proposed method is related to graphs as the data, which is initially stored in a relational database, is represented as a graph and concept descriptors are the paths that connect certain vertices; and it is related to association rule mining as it uses methods of association rule mining to prune the search space and evaluate the quality of the concept descriptors. The method is evaluated on several data sets, and the experimental results show that it is compatible with the state-of-the art methods in terms of accuracy and coverage of the induced concept descriptors and the running time of the application.