Crossover Operator for Frequent Subgraph Mining

Abstract

Graph-based data mining approaches have been mainly proposed to the task popularly known as frequent subgraph mining subject to a single user pref- erence, like frequency, size, etc. In this work, I propose a new crossover oper- ator for frequent subgraph mining problem, where a subgraph (or solution) is defined by a genetic algorithm through several iterations, reproductions and filtering. I have develop a standard genetic algorithm, which includes most of the used stages as selection, crossover (without mutation), evalua- tion and replacement. Evolutionary algorithm for Graph-base data mining approaches is a very recent field, and the genetic algorithms for frequent subgraph mining subject is introduced in this project, with the proposal of a new crossover operator. This project is based in the framework of Subdue algorithm for subgraph mining. The method is called optimization by genetic algorithms (GAOptimize) and has several advantages: (i) optimization from a Subdue’s solutions stack in a single run (ii) selection of different constraints for substructure selection and reproduction (iii) search in the subgraphs lat- tice space and (iv) capability to deal with different isomorphic graph search algorithms. The good performance of GAOptimize is shown on two samples datasets from Subdue and two real-life datasets.