last updated 15-Oct-2018
Extends association analysis to finding frequent subgraphs
Useful for
A graph is isomorphic if it is topologically equivalent to another graph
Each transaction is a clique of nodes
Graphs as transactions
Node may contain duplicate labels
Support and confidence measures
Additional constraints imposed by pattern structure
Apriori-like approach: Use frequent k-subgraphs to generate frequent (k+1) subgraphs
What is k?
Support: number of graphs that contain a particular subgraph
Apriori principle still holds
Level-wise (Apriori-like) approach:
Find frequent 1-subgraphs
Repeat:
Candidate generation
- Use frequent (k-1)-subgraphs to generate candidate k-subgraph
Candidate pruning
- Prune candidate subgraphs that contain infrequent (k-1)-subgraphs
Support counting
- Count the support of each remaining candidate
Eliminate candidate k-subgraphs that are infrequent
In Apriori: Merging two frequent k-itemsets will produce a candidate (k+1)-itemset
In frequent subgraph mining (vertex/edge growing)
Merging two frequent k-subgraphs may produce more than one candidate (k+1)-subgraph
Case 1: identical vertex labels
Case 1: if a ≠ c and b ≠ d | Case 2: if a = c and b ≠ d | Case 3: if a ≠ c and b = d |
---|---|---|