Finding frequent patterns in a large sparse graph

Michihiro Kuramochi, George Karypis

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

39 Scopus citations

Abstract

This paper presents two algorithms based on the horizontal and vertical pattern discovery paradigms that find the connected subgraphs that have a sufficient number of edge-disjoint embeddings in a single large undirected labeled sparse graph. These algorithms use three different methods to determine the number of the edge-disjoint embeddings of a subgraph that are based on approximate and exact maximum independent set computations and use it to prune infrequent subgraphs. Experimental evaluation on real datasets from various domains show that both algorithms achieve good performance, scale well to sparse input graphs with more than 100,000 vertices, and significantly outperform a previously developed algorithm.

Original languageEnglish (US)
Title of host publicationProceedings of the Fourth SIAM International Conference on Data Mining
EditorsM.W. Berry, U. Dayal, C. Kamath, D. Skillicorn
Pages345-356
Number of pages12
StatePublished - Jun 22 2004
EventProceedings of the Fourth SIAM International Conference on Data Mining - Lake Buena Vista, FL, United States
Duration: Apr 22 2004Apr 24 2004

Other

OtherProceedings of the Fourth SIAM International Conference on Data Mining
CountryUnited States
CityLake Buena Vista, FL
Period4/22/044/24/04

Keywords

  • Frequent subgraph
  • Graph mining
  • Pattern discovery

Fingerprint Dive into the research topics of 'Finding frequent patterns in a large sparse graph'. Together they form a unique fingerprint.

Cite this