Discriminative Closed Fragment Mining and Perfect Extensions in MoFa

Abstract

In the past few years many algorithms for discovering frequent subgraphs in graph databases have been proposed. However, most of these methods are limited to finding only relatively small fragments or restrict the discovered structures in other ways, which makes them not very useful for applications in biochemistry. Recently the authors of the original gSpan algorithm have shown how the usage of closed fragments can considerably speed up their algorithm. However, the main limitation to small fragments still remains. In this paper we show how the more versatile search algorithm underlying MoFa can benefit greatly from using closed fragments as well and how the concept of perfect extensions quite naturally allows to prune the underlying search tree. We demonstrate how this results in speed-ups on the NCI’s HIV database.