Mining maximal frequent patterns in a single graph using inexact matching

Despite being a popular problem during the last years, frequent graph mining has some important research lines still open for further exploration; among them, the possibility of using inexact matching in order to discover patterns otherwise missed, and the aim at reducing the set of mined patterns to facilitate their analysis and use. We present an algorithm that mines maximal patterns in a single graph using inexact matching. By allowing structural differences, in vertices as well as in edges, between a pattern and its occurrences, our algorithm is able to identify different, often larger, patterns than those found by other state-of-the-art algorithms. On the other hand, by focusing on maximal graphs the output set is significantly downsized without losing patterns, as they can be recovered from the maximal ones. Experiments show that the “extra” patterns found by our algorithm can help in supervised tasks like classification, thus suggesting that useful information about the input data can be captured through the maximal patterns mined with inexact matching.