📚 Data Mining Tutorial

Data Mining

Learn Data Mining concepts with simple explanations, examples, techniques and practical notes.

← Back to Data Mining

Graph Pattern Mining

Graph pattern mining is a process in which the mining techniques are used in finding a pattern or relationship in the given real-world collection of graphs. By mining the graph, frequent substructures and relationships can be identified which helps in clustering the graph sets, finding a relationship between graph sets, or discriminating or characterizing graphs.

Graph Pattern Mining − It is the mining of frequent subgraphs in one or a set of graphs.

There are two steps in finding frequent subgraphs.

  • The first step is to create frequent substructure candidates.
  • The second step is to find the support of each and every candidate.

There are various approaches for mining graph patterns can be categorized into Apriori-based and pattern growth–based approaches.

The Apriori-based approach: The approach to find the frequent graphs begin from the graph with a small size. The approach advances in a bottom-up way by creating candidates with extra vertex or edge. This algorithm is called an Apriori Graph.

The Pattern-growth approach: This pattern-growth approach can use both BFS and DFS (Depth First Search). DFS is preferred for this approach due to its less memory consumption nature.

Example:

Three example graphs g1, g2 and g3 made of S, C, N and O vertices: g1 is S-C-C-N with an O double-bonded to the second C, g2 is C-C-N-C with an O double-bonded above the second C and an S below the first C, and g3 is C-S-C-C with N=O attached below the third vertex.

From the above given graphs, the following are frequent subgraphs with frequency 2 and 3.

Frequent subgraphs: S-C-C=O with N attached to the second C has frequency 2, and C-C-N has frequency 3.