Database Reference
In-Depth Information
An important property, called
anti-monotonicity
, is crucial to confine the search
space of frequent subgraph mining.
Definition 13.3 (Anti-Monotonicity)
Anti-monotonicity means that a size-k sub-
graph is frequent only if all of its subgraphs are frequent.
Many frequent graph pattern mining algorithms [
7
,
8
,
14
,
16
,
20
,
21
,
23
,
24
,
29
,
30
,
31
,
38
,
45
] have been proposed. Holder et al. [
20
] developed
SUBDUE
to
do approximate graph pattern discovery based on minimum description length and
background knowledge. Dehaspe et al. [
14
] applied inductive logic programming
to predict chemical carcinogenicity by mining frequent subgraphs. Besides these
studies, there are two basic approaches to the frequent subgraph mining problem:
the
Apriori
-based approach and the pattern-growth approach.
2.2
Apriori-Based Approach
Apriori
-based frequent subgraph mining algorithms share similar characteristics with
Apriori
-based frequent itemset mining algorithms. The search for frequent subgraphs
starts with small-size subgraphs, and proceeds in a bottom-up manner. At each iter-
ation, the size of newly discovered frequent subgraphs is increased by one. These
new subgraphs are generated by joining two similar but slightly different frequent
subgraphs that were discovered already. The frequency of the newly formed graphs is
then checked. The framework of Apriori-based methods is outlined in Algorithm 11.
Typical Apriori-based frequent subgraph mining algorithms include
AGM
by
Inokuchi et al. [
24
],
FSG
by Kuramochi and Karypis [
29
], and an edge-disjoint
path-join algorithm by Vanetik et al. [
38
].
