GraphConnect: Framework of Discovering Closed Highly Connected Pattern from Semistructured Dataset

摘要

Semistructured data appears when the source does not impose a rigid structure on the data, such as the web, or when data is combined from several heterogeneous sources. In mathematical terms, we called semi structured data set as graph data set One particular interesting in mining semi structured pattern is finding frequent highly connected subgraph in large relational graphs. The common problem is to find not only frequent graphs, but also graphs that satisfy the connectivity constraint. We identify three major characteristics different from the previous frequent graph mining problem, first, in relational graphs each node represents a distinct object. No two nodes share the same label. In biological networks, nodes often represent unique objects like genes and enzymes. Secondly, relational graphs may be very large. Thirdly, the interesting patterns should not only be frequent but also satisfy the connectivity constraint. . In order to handle these new challenges, we identify two issues have to be solved: (1) how to mine frequent graphs efficiently in large relational graphs, and (2) how to handle the connectivity constraint. Since frequent graph mining usually generates too many patterns, it is more appealing to mine closed frequent graphs only. Our major contribution is to tackle the connectivity constraint. We use the minimum cut criterion to measure the connectivity of a pattern and examine the issues of integrating the connectivity constraint with the closed graph mining process.