Investigation of techniques to increase the scalability of graph based data mining algorithms

Frequent subgraph pattern recognition and graph-based relational learning have been an emerging area of data mining research with scientific and commercial applications. At the kernel of these algorithms are the computationally-expensive graph and subgraph isomorphism tests.; The graph isomorphism problem consists in deciding whether two graphs are isomorphic i.e., whether there is a one-one mapping between the vertices of the two graphs that respects the edge connections. Many graphs will be depicted quite differently but in actuality have the same inherent structure. This leads to the isomorphism problem. The graph isomorphism problem belongs to the class of NP problems and has been conjectured intractable though probably not NP-complete.; We hypothesize that approximation algorithms can be developed for the graph and subgraph isomorphism problems, and that these algorithms can improve the runtime of data mining systems that rely on these capabilities. (Abstract shortened by UMI.)...