Database Reference
In-Depth Information
n
s
−
(
p
)
=
2
|
r
i
|+
r
i
.
{
i
|˜
y
i
=−
1,
x
i
,
j
=
1
}
i
=
1
3.4
LEAP: A Structural Leap Search Approach
Yan et al. [
50
] proposed an efficient algorithm which mines the most significant
subgraph pattern with respect to an objective function. A major contribution of this
study is the proposal of a general approach for significant graph pattern mining with
non-monotonic objective functions. The mining strategy, called
LEAP
(Descending
Leap Mine), explored two new mining concepts: (1)
structural leap search
, and
(2)
frequency-descending mining
, both of which are related to specific properties
in pattern search space. The same mining strategy can also be applied to searching
other simpler structures such as itemsets, sequences and trees.
Structural Leap Search
Figure
13.4
shows a search space of subgraph patterns. If
we examine the search structure horizontally, we find that the subgraphs along the
neighbor branches likely have similar compositions and frequencies, hence similar
objective scores. Take the branches
A
and
B
as an example. Suppose
A
and
B
split
on a common subgraph pattern
g
. Branch
A
contains all the supergraphs of
g
e
and
e
. For a graph
g
in branch
B
contains all the supergraphs of
g
except those of
g
B, let
g
=
g
e
in branch
A
.
LEAP
assumes each input graph is assigned either a positive or a negative label
(
e.g.
, compounds active or inactive to a virus). One can divide the graph dataset
into two subsets: a positive set
D
+
and a negative set
D
−
. Let
p
(
g
) and
q
(
g
) be the
frequency of a graph pattern
g
in positive graphs and negative graphs. Many objective
