Discriminative Closed Fragment Mining and Perfect Extensions in MoFa
Thorsten Meinl, Christian Borgelt, Michael R. Berthold · KOPS (University of Konstanz) · 2004
Abstract. In the past few years many algprilluns for 4iscovering frequent subgraphs in graph databases have been proposed. However,.most of these ·methods. are limited to finding only relatively small fragments or restrict tlie discovereds.tructures in other ways, which makes them not very useful for applications ill biOChemistry. Recently the authors of the original gSpan. algorithm have·shoWn hoW the usage of closed frag-ments can considerably speed up their algorithm. However, the main limitation to small fragments still retruiins. In this.paper we · shoW how the more versatile search algorithm underlying MoFacan bene~t from using'C\\osed:fragments as well and how 'the concept of perfect extensions,quite naturally alloWs 10 prune the underlying search tree. We demonstrate how this results in considerable si>eect-ups on the NCI's mv database.