Top-k frequent induced subgraph mining on a sliding window using sampling
Van T. T. Duong, Kifayat Ullah Khan, Young-Koo Lee · 2017
Finding Frequent Induced Subgraph in a stream of graph data is critical for many application such as frequent substructures in biological networks, chemical compounds, or community detection in social networks. Some approaches have been proposed for mining frequent induced subgraph in graph database. However, existing methods take long execution time since they perform numerous subgraph isomorphism (SI) operations, thus, these approach is not efficience for mining on streaming environment. In this paper, we propose k-FISMW, a new sampling-based method for top-k Frequent Induced Subgraph Mining on a sliding Window. We use a specialized data structure called WSTable (Window Summary Table) to maintain information of recent graphs in the sliding windows. To avoid SI operations in kFISM, we present a measure, indFreq, to compute frequency of subgraphs. k-FISMW executes a biased random walkbased sampling over fixed-size vertex-induced subgraphs on the current window 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 k-FISMW on both real-life and synthetic dataset. We observe that our proposed method outperforms state of the art approach in execution time and accuracy.