Graph Mining

The task of graph mining is to extract patters (sub-graphs) of interest from graphs, that describe the underlying data and could be used further, e.g., for classification or clustering.

Even though sub-graph isomorphism is a NP-complete problem, many graph mining tools for frequent sub-graph mining exist (like e.g., gSpan or GASTON) that can be applied to large databases (due to efficient candidate generation and unique canonical representations).

Graph mining has a vast number of applications, e.g. biological networks or web data. Cheminformatics is another important application of graph mining: frequent sub-graph mining can yield structural alerts, i.e., structural sub-graphs that have a huge impact on the activity of chemical compounds (as used in  Cheminformatics and Predictive Toxicology).