A Study on Frequent Subgraph Mining Approaches: Challenges and Future Directions

Graph mining has become a well-established discipline within the domain of data mining. It has received much interest over the last decade as advances in computer hardware have provided the processing power to enable large-scale graph data mining to be conducted. Frequent subgraph mining (FSM) plays a very significant role in graph mining, attracting a great deal of attention in different domains, such as Bioinformatics, web data mining and social networks. Research on FSM started around 1994, but it has become popular since 2008 when the size of graphs in different domains became relatively large. Several techniques have been proposed in the literature for the FSM problem. In this paper, we reviewed some recently presented FSM techniques and investigated some challenges and future research directions. A few surveys have been conducted to review different techniques for the FSM problem. However, existing surveys highlighted only the methodology adopted for frequent subgraph discover but did not critically review their shortcomings. Also, the existing surveys/reviews are not comprehensive enough and are insufficient to highlight the challenges in the FSM domain along with their possible solutions. Consequently, there is a need for a survey that incorporates recent techniques. Therefore, this study aimed to comprehensively survey the current research in the field of FSM. In this survey the key characteristics of each FSM approach are analyzed, such as the proposed methodology, which type of graph structure is used, applied similarity measures, metrics used for measuring the performance, uncertainty handled or not, used data set, capabilities of the techniques, evidence used and limitations of these techniques. As a result, this paper identifies the current status of the research in the FSM, and future research directions in this field are determined based on opportunities and several open issues in FSM domination. These research directions, facilitate the exploration of the domain and the development of optimal techniques to address FSM.