A new algorithm for approximate pattern mining in multi-graph collections

摘要

In recent years, an increasing number of works have been reported that modeling data as multi-graphs more efficiently solves some practical problems. In these contexts, data mining techniques could be useful for discovering patterns, helping to solve more complex tasks like classification. Additionally, in real world applications, it is very useful to mine patterns allowing approximate matching between graphs. However, to the best of our knowledge, in literature there is only one method that allows mining these types of patterns in multi-graph collections. This method does not compute the approximate patterns directly from the multi-graph collections, which makes it inefficient. In this paper, an algorithm for directly mining patterns in multi-graph collections in a more efficient way than the only alternative reported in the literature is proposed. Our algorithm, introduces an extension of a canonical form based on depth-first search, which allows representing multi-graphs. Experiments on different public standard databases are carried out to demonstrate the performance of the proposed algorithm. The algorithm is compared with the only alternative reported in the literature for mining patterns in multi-graph collections. Note that the new algorithm and the referenced algorithm [N. Acosta-Mendoza, J.A. Carrasco-Ochoa, J.F. Martinez Trinidad, A. Gago-Alonso, and J.E. Medina-Pagola. A New Method Based on Graph Transformation for FAS Mining in Multi-graph Collections. In The 7th Mexican Conference on Pattern Recognition (MCPR'2015), Pattern Recognition, volume LNCS 9116, pages 13-22. Springer, 2015.] produce the same results but the new algorithm is more efficient. (C) 2016 Elsevier B.V. All rights reserved.