Mining Frequent Most Informative Subgraphs

Abstract. The main practical problem encountered with frequent subgraph search methods is the tens of thousands of returned graph patterns that make their visual analysis impossible. In order to face this problem, are introduced a very restricted family of relevant graph patterns called the most informative patterns along with an algorithm to mine them and associated experimental results. In graph-based data mining problems, mined patterns are connected labelled graphs isomorphically distinct. Several algorithms have been proposed [1–4] to mine frequent graph patterns in graph databases by analogy with the frequent itemset search problem. Given a graph database, the frequency of a graph pattern is the number of graphs in the database containing at least one subgraph isomorphic to the pattern. The frequent subgraph search problem consists in determining the set of frequent patterns whose frequency is higher than a minimum threshold along with their frequency. The main practical problem encountered with frequent patterns in general and frequent subgraphs in particular is thei