Top- k frequent induced subgraph mining using sampling
Van T. T. Duong, Kifayat Ullah Khan, Byeong-Soo Jeong, Young-Koo Lee · 2016
These days Frequent Induced Subgraph Mining (FISM) is an active research direction, in various application domains like biological networks, chemical, or social networks. A number of FISM approaches have been proposed over the years. However, existing methods take long execution time since they perform numerous subgraph isomorphism (SI) operations, an NP-hard for counting frequency of subgraphs in a graph database. In this paper, we propose kFISM, a new sampling-based method for top-k Frequent Induced Subgraph Mining from a graph database. To avoid SI operations in kFISM, we present a measure, indFreq, to compute frequency of subgraphs. kFISM executes a biased random walk-based sampling over fixed-size vertex-induced subgraphs so that the potentially frequent subgraphs are visited with high probability. We evaluate execution time and accuracy of finding our desired types of subgraphs using kFISM on a real-life dataset. We observe that our proposed method outperforms state of the art approach in execution time and accuracy.