AGraP: an algorithm for mining frequent patterns in a single graph using inexact matching
Por:
Flores-Garrido M., Carrasco-Ochoa J.-A., Martínez-Trinidad J.F.
Publicada:
1 ene 2015
Resumen:
Frequent graph mining algorithms commonly use graph isomorphism to identify occurrences of a given pattern, but in the last years, a few works have focused on the case where a pattern could differ from its occurrences, which can be important to analyze noisy data. These later algorithms allow differences in labels and structural differences in edges, but to the best of our knowledge, none of them considers structural differences in vertices. How can we identify occurrences that differ by one (or several) nodes from the pattern they represent? Our work approaches the problem of frequent graph pattern mining with two main characteristics. First, we use inexact matching, allowing structural differences in both edges and vertices. Second, we focus on the problem of mining patterns in a single graph, a problem that has been less explored than the case in which patterns are mined from a graph collection. In this paper, we introduce two similarity functions to compare graphs using inexact matching and an algorithm, AGraP, able to identify patterns that can have structural differences with respect to their occurrences. Our experimental results show that AGraP is able to find patterns that cannot be found by other state-of-the-art algorithms. Additionally, we show that the patterns mined by AGraP are useful in classification tasks. © 2014, Springer-Verlag London.
Filiaciones:
Flores-Garrido M.:
Instituto Nacional de Astrofísica, Óptica y Electrónica, Luis Enrique Erro No.1, Sta. Maria Tonantzintla, ZIP 72840, Puebla, Mexico
Carrasco-Ochoa J.-A.:
Instituto Nacional de Astrofísica, Óptica y Electrónica, Luis Enrique Erro No.1, Sta. Maria Tonantzintla, ZIP 72840, Puebla, Mexico
Martínez-Trinidad J.F.:
Instituto Nacional de Astrofísica, Óptica y Electrónica, Luis Enrique Erro No.1, Sta. Maria Tonantzintla, ZIP 72840, Puebla, Mexico
|