Information Technology Reference
In-Depth Information
horizontal axis shows the minimal support in percent (IC93) or as an absolute
number (steroids). For the experiments of Figure 11.11 and Figure 11.12 we used
ring mining, which means that rings in a user-defined size range (here: 5 to 6
bonds) are not built edge by edge, but added in one step. The technique underly-
ing such ring mining was introduced in [8] for a repository of processed fragments
to avoid redundant search, but later extended in [2] to work with canonical form
pruning (using a code word reorganization technique that is similar to the one
presented in this paper, but more complex).
In each diagram the dashed gray line refers to the basic algorithm without
any perfect extension pruning, the gray solid line to partial perfect extension
pruning and the black solid line to full perfect extension pruning. These results
show that full perfect extension pruning indeed leads to some non-negligible
gains (in the order of about 5 to 10%) over partial perfect extension pruning,
even though the main gains clearly result from partial perfect extension pruning.
Tests we ran during the development of the program indicated that relaxing the
constraints for perfect extensions (that is, also edges closing rings/cycles are
allowed as perfect extensions instead of only bridges) improved performance by
up to an additional 3%.
11.8
Conclusions
In this paper we fixed the flaw of the original descriptions of perfect extension
pruning by requiring that perfect extensions must be bridges, but still allowing
edges that close rings/cycles apart from bridges. In addition, we introduced
full perfect extension pruning, which consists in pruning not only the search
tree branches to the right (partial perfect extension pruning as it is used in
Closegraph [17]), but also those to the left of the perfect extension branch. To
make this possible in combination with canonical form pruning, we allowed for
a (strictly limited) reorganization of code words as they result from the search.
The experimental results show that this method can actually further reduce the
complexity of the search, although the main improvement comes from partial
perfect extension pruning. Future work is directed at combining sibling perfect
extensions into one extension, so that perfect extensions, once found, need not
be rediscovered and reprocessed.
References
1. Borgelt, C.: On Canonical Forms for Frequent Graph Mining. In: Proc. 3rd Int.
Workshop on Mining Graphs, Trees and Sequences, MGTS 2005, Porto, Portugal,
1-12. ECML/PKDD 2005 Organization Committee, Porto, Portugal (2005)
2. Borgelt, C.: Combining Ring Extensions and Canonical Form Pruning. In: Pro-
ceedings of the 4th International Workshop on Mining and Learning in Graphs
(MLG 2006), ECML/PKDD 2006 Organization Committee, Berlin, pp. 109-116
(2006)
