Subgraph-subsequence pair

The first, key idea for enumerating all frequent subgraph-subsequence pairs efficiently is the following property, which is called downward closure ... 

A subgraph-subsequence pair is infrequent if this pair contains any smaller infrequent subgraph-subsequence pairs. 

Fig. 2 An example of the search space. The search space (c) is defined as the graph product of two enumeration trees for subsequences (a) and for subgraphs (b). (c) Covers all possible frequent subgraph-subsequence pairs...

Proposition 2 (Dynamic programming for subgraph-subsequence pairs)... 

In practice, all combinations of frequent subgraphs and frequent subsequences may have a lot of infrequent subgraph-subsequence pairs, and so we can use the downward closure property on the product graph of the two enumeration trees, which can be clearly stated as follows ... 

If a subgraph-subsequence pair (g, s) is infrequent, then subgraph-subsequence pairs (s -,s) (where 3 3 and jcj ) are all infrequent. Thus, if... 

Fig. 3 A sample for enumerating all subgraph-subsequence pairs with the support of 3 or larger of 10 graph-sequence pairs (1,2,..., 10). This table corresponds to two enumeration trees of Fig. 2a, b...

The support of a subgraph-subsequence pair is monotonically decreasing with increasing the size of the subgraph or the subsequence, meaning that a subgraph on a deeper level in an enumeration tree has a smaller support. 

---