|
Published Articles >> Table of Contents >> Abstract
Fourth IEEE International Conference on Data Mining (ICDM'04)
pp. 439-442
GREW-A Scalable Frequent Subgraph Discovery Algorithm
Michihiro Kuramochi, University of Minnesota
George Karypis, University of Minnesota
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICDM.2004.10024
Send link to a friend
| 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, for graphs that do not share these characteristics, these algorithms become highly unscalable. In this paper we present 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.
|
 Additional Information
|
Index Terms- frequent pattern discovery, frequent subgraph, graph mining
Citation:
Michihiro Kuramochi, George Karypis,
"GREW-A Scalable Frequent Subgraph Discovery Algorithm,"
icdm,
pp. 439-442,
Fourth IEEE International Conference on Data Mining (ICDM'04),
2004
|
|
