Representative frequent approximate subgraph mining on multi-graph collections
Niusvel Acosta Mendoza · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · 2018
Nowadays, there has been an increase in the use of frequent approximate subgraph (FAS) mining for different real-world applications such as image classification, social network analysis and natural language processing, among others. In several of these applications, in the last years, multi-graphs have been used to model data, because, in the real-world, commonly there are more than one relation (edge) between the entities represented as vertices. However, the reported FAS miners have been designed to work with simple-graphs. Therefore, in order to solve the problem of mining FASs from multi-graph collections, we explore two alternatives in this research: (1) transforming the multi-graphs into simple-graphs and the FASs are obtained by applying conventional FAS miners over the transformed simple-graph collection, and (2) proposing algorithms for mining FAS directly from multi-graph collections. Following the first alternative, a method, called allEdges, based on graph transformations for mining all FASs on multi-graph collections by means of applying simple-graph FAS miners was proposed. Later, for speeding up the mining process, an alternative method, called onlyMulti, based on graph transformation for mining some FASs over multi-graph collections was proposed. Despite the fact that both allEdges and onlyMulti allow using simple-graph FAS miners for mining multi-graph FASs, the graph transformation processes increase the size of the graph collection and therefore, the mining process cost is increased. Thus, an algorithm, called MgVEAM, for mining all FASs directly over multi-graph collections without graph transformations was proposed. After, in order to accelerate the mining process, another algorithm, called AMgMiner, for directly mining all multi-graph FASs was proposed. AMgMiner is faster than MgVEAM, but the former requires more memory than the later. All the proposed methods and algorithms were evaluated and compared by using di_erent multi-graph datasets. The large number of mined FASs is one of the fundamental drawbacks of FAS mining, which makes difficult the further use of the mined FASs. Therefore, in order to mine only a subset of representative FASs from multi-graph collections, we proposed two algorithms; one for mining generalized closed FASs and another for mining clique FASs. Experiments on different databases were carried out to show the performance of our proposals.