Mining closed relational graphs with connectivity constraints

Relational graphs are widely used in modeling large scale networks such as biological networks and social networks. In this kind of graph, connectivity becomes critical in identifying highly associated groups and clusters. In this paper, we investigate the issues of mining closed frequent graphs with connectivity constraints in massive relational graphs where each graph has around 10K nodes and 1M edges. We adopt the concept of edge connectivity and apply the results from graph theory, to speed up the mining process. Two approaches are developed to handle different mining requests: CLOSECUT, a pattern-growth approach, and SPLAT, a pattern-reduction approach. We have applied these methods in biological datasets and found the discovered patterns interesting.