Lower and upper queries for graph-mining

International audienceCanonical encoding is one of the key operations required by subgraph mining algorithms for candidates generation. They enable to query the exact number of frequent subgraphs. Existing approaches make use of canonical encodings with an exponential time complexity. As a consequence, mining all frequent patterns for large graphs is com- putationally expensive. In this paper, we propose to relax the canonicity property, leading to two encodings, lower and upper encodings, with a polynomial time complexity, allowing to tightly enclose the exact set of frequent subgraphs. These two encodings allow two kinds of queries, lower and upper queries, to get respectively a subset and a superset of frequent patterns. Lower and upper encodings have been integrated in Gaston. Experiments performed on large and dense synthetic graphs show that, these two encodings are very effective compared to Gaston and gSpan, while on large real world sparse graphs they remain very competitive