Database Reference
In-Depth Information
searching similar branches in the pattern search tree. Its goal is to help program search
significantly distinct branches, and limit the chance of missing the most significant
pattern.
Algorithm 14 outlines the pseudo code of structural leap search (sLeap). The leap
condition is tested on Lines 7-8. Note that sLeap does not guarantee the optimality
of result.
Frequency Descending Mining
Structural leap search takes advantages of the cor-
relation between structural similarity and significance similarity. However, it does
not exploit the possible relationship between patterns' frequency and patterns' ob-
jective scores. Existing solutions have to set the frequency threshold very low so that
the optimal pattern will not be missed. Unfortunately, low-frequency threshold could
generate a huge set of low-significance redundant patterns with long mining time.
Although most of objective functions are not correlated with frequency mono-
tonically or anti-monotonically, they are not independent of each other. Cheng et al.
[
9
] derived a frequency upper bound of discriminative measures such as information
gain and Fisher score, showing a relationship between frequency and discriminative
measures. According to this analytical result, if all frequent subgraphs are ranked
in increasing order of their frequency, significant subgraph patterns are often in
the high-end range, though their real frequency could vary dramatically across
different datasets.
Figure
13.5
illustrates the relationship between frequency and G-test score for
an AIDS Anti-viral dataset [
50
]. It is a contour plot displaying isolines of G-test
score in two dimensions. The X axis is the frequency of a subgraph
g
in the positive
