Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds

Download PDF

Abstract

Frequent subgraph mining is an important and well-studied prob- lem with numerous applications such as the prediction of protein functionalities and graph indexing. Many studies use the minimum- image-based support (MNI) to measure the frequency of subgraphs in single graph mining. Given a graph G and an integer k, top-k frequent subgraph mining is to ￿nd top-: frequent subgraphs in the graph ⌧ based on MNI. However, there are two main challenges in top-k frequent subgraph mining. (1) Computing MNI is time- consuming. (2) The number of subgraphs for which MNI should be computed is large. In this paper, we propose a novel algorithm Minting to address these challenges. We propose a method to significantly reduce the number of subgraphs for which MNI computation is required by using a tight upper bound of the MNI value. We also improve the computation of MNI itself by utilizing both a lower bound and an upper bound of the MNI value. Experiments shows that our algorithm outperforms the state-of-the-art algorithms by up to three orders of magnitude in terms of the elapsed time. Our algorithm is also a feasible solution for this challenging problem, even for large k.