Accession Number:

ADA439436

Title:

GREWA Scalable Frequent Subgraph Discovery Algorithm

Descriptive Note:

Technical rept.

Corporate Author:

MINNESOTA UNIV MINNEAPOLIS DEPT OF COMPUTER SCIENCE

Report Date:

2004-06-22

Pagination or Media Count:

15.0

Abstract:

Existing algorithms that mine graph datasets to discover patterns corresponding to frequently occurring subgraphs can operate efficiently on graphs that are sparse, contain a large number of relatively small connected components, have vertices with low and bounded degrees, and contain well-labeled vertices and edges. However, there are a number of applications that lead to graphs that do not share these characteristics, for which these algorithms highly become unscalable. In this paper we propose a heuristic algorithm called GREW to overcome the limitations of existing complete or heuristic frequent subgraph discovery algorithms. GREW is designed to operate on a large graph and to find patterns corresponding to connected subgraphs that have a large number of vertex-disjoint embeddings. Our experimental evaluation shows that GREW is efficient, can scale to very large graphs, and find non-trivial patterns that cover large portions of the input graph and the lattice of frequent patterns.

Subject Categories:

  • Numerical Mathematics
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE