Database Reference
In-Depth Information
Fig. 13.3
Branch-and-bound
search
search stop
cut
cut
...
...
Figure
13.3
depicts a graph pattern search tree where each node represents a
graph. A graph
g
is a child of another graph
g
if
g
is a supergraph of
g
with one
more edge.
g
is also written as
g
e
, where
e
is the extra edge. In order
to find an optimal rule, the branch-and-bound search estimates the upper bound of
the gain function for all descendants below a node
g
. If it is smaller than the value
of the best subgraph seen so far, it cuts the search branch of that node. Under the
branch-and-bound search, a tighter upper bound is always preferred since it means
faster pruning.
Algorithm 12 outlines the framework of branch-and-bound for searching the
optimal graph pattern. In the initialization, all the subgraphs with one edge are enu-
merated first and these seed graphs are then iteratively extended to large subgraphs.
Since the same graph could be grown in different ways, Line 5 checks whether it has
been discovered before; if it has, then there is no need to grow it again. The optimal
gain
(
=
g
t
,
t
,
y
ˆ
) discovered so far is maintained. If
μ
(
t
)
≤
gain
(
y
ˆ
), the branch of
t
can safely be pruned.
