A quickstart in frequent structure mining can make a difference

TLDR

Structure mining algorithms search for substructures—such as graphs, trees, and paths—that meet constraints like minimum frequency, confidence, interest, and maximum frequency, and many such algorithms have been proposed. The study aims to make graph mining more efficient by applying the quickstart principle, which exploits the containment relationships among structure classes to split the search into progressively more complex steps. To implement this principle, the authors introduce the Gaston algorithm, which first searches for frequent paths, then frequent free trees, and finally cyclic graphs. Experimental results comparing two alternatives for computing structure frequencies demonstrate the effectiveness of the Gaston approach.

Abstract

Given a database, structure mining algorithms search for substructures that satisfy constraints such as minimum frequency, minimum confidence, minimum interest and maximum frequency. Examples of substructures include graphs, trees and paths. For these substructures many mining algorithms have been proposed. In order to make graph mining more efficient, we investigate the use of the "quickstart principle", which is based on the fact that these classes of structures are contained in each other, thus allowing for the development of structure mining algorithms that split the search into steps of increasing complexity. We introduce the GrAph/Sequence/Tree extractiON (Gaston) algorithm that implements this idea by searching first for frequent paths, then frequent free trees and finally cyclic graphs. We investigate two alternatives for computing the frequency of structures and present experimental results to relate these alternatives.