GREW - A scalable frequent subgraph discovery algorithm

Michihiro Kuramochi, George Karypis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

78 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings - Fourth IEEE International Conference on Data Mining, ICDM 2004
EditorsR. Rastogi, K. Morik, M. Bramer, X. Wu
Pages439-442
Number of pages4
DOIs
StatePublished - 2004
EventProceedings - Fourth IEEE International Conference on Data Mining, ICDM 2004 - Brighton, United Kingdom
Duration: Nov 1 2004Nov 4 2004

Publication series

NameProceedings - Fourth IEEE International Conference on Data Mining, ICDM 2004

Other

OtherProceedings - Fourth IEEE International Conference on Data Mining, ICDM 2004
Country/TerritoryUnited Kingdom
CityBrighton
Period11/1/0411/4/04

Keywords

  • Frequent pattern discovery
  • Frequent subgraph
  • Graph mining

Fingerprint

Dive into the research topics of 'GREW - A scalable frequent subgraph discovery algorithm'. Together they form a unique fingerprint.

Cite this