Frequent subgraph discovery

Michihiro Kuramochi, George Karypis

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

804 Scopus citations

Abstract

As data mining techniques are being increasingly applied to non-traditional domains, existing approaches for finding frequent itemsets cannot be used as they cannot model the requirement of these domains. An alternate way of modeling the objects in these data sets is to use graphs. Within that model, the problem of finding frequent patterns becomes that of discovering subgraphs that occur frequently over the entire set of graphs. In this paper we present a computationally efficient algorithm for finding all frequent subgraphs in large graph databases. We evaluated the performance of the algorithm by experiments with synthetic datasets as well as a chemical compound dataset. The empirical results show that our algorithm scales linearly with the number of input transactions and it is able to discover frequent subgraphs from a set of graph transactions reasonably fast, even though we have to deal with computationally hard problems such as canonical labeling of graphs and subgraph isomorphism which are not necessary for traditional frequent itemset discovery.

Original languageEnglish (US)
Title of host publicationProceedings - 2001 IEEE International Conference on Data Mining, ICDM'01
Pages313-320
Number of pages8
StatePublished - Dec 1 2001
Event1st IEEE International Conference on Data Mining, ICDM'01 - San Jose, CA, United States
Duration: Nov 29 2001Dec 2 2001

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
ISSN (Print)1550-4786

Other

Other1st IEEE International Conference on Data Mining, ICDM'01
Country/TerritoryUnited States
CitySan Jose, CA
Period11/29/0112/2/01

Fingerprint

Dive into the research topics of 'Frequent subgraph discovery'. Together they form a unique fingerprint.

Cite this