Mining Closed Relational Graphs with Connectivity Constraints Xifeng Yan, Jasmine Zhou, and Jiawei Han   View Paper (PDF)   Return to Research Session 7 [Graph Mining] Abstract 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. ©2006 Association for Computing Machinery