Finding frequent patterns in a large sparse graph

Michihiro Kuramochi; George Karypis

Finding frequent patterns in a large sparse graph

Michihiro Kuramochi, George Karypis

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

47 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 language	English (US)
Title of host publication	Proceedings of the Fourth SIAM International Conference on Data Mining
Editors	M.W. Berry, U. Dayal, C. Kamath, D. Skillicorn
Pages	345-356
Number of pages	12
State	Published - Jun 22 2004
Event	Proceedings of the Fourth SIAM International Conference on Data Mining - Lake Buena Vista, FL, United States Duration: Apr 22 2004 → Apr 24 2004

Other

Other	Proceedings of the Fourth SIAM International Conference on Data Mining
Country/Territory	United States
City	Lake Buena Vista, FL
Period	4/22/04 → 4/24/04

Keywords

Frequent subgraph
Graph mining
Pattern discovery

Find It

Find It at U of M Libraries

Cite this

@inproceedings{b7cb16f8dabf4b21b8bbde66aa71ad1a,

title = "Finding frequent patterns in a large sparse graph",

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.",

keywords = "Frequent subgraph, Graph mining, Pattern discovery",

author = "Michihiro Kuramochi and George Karypis",

year = "2004",

month = jun,

day = "22",

language = "English (US)",

pages = "345--356",

editor = "M.W. Berry and U. Dayal and C. Kamath and D. Skillicorn",

booktitle = "Proceedings of the Fourth SIAM International Conference on Data Mining",

note = "Proceedings of the Fourth SIAM International Conference on Data Mining ; Conference date: 22-04-2004 Through 24-04-2004",

}

TY - GEN

T1 - Finding frequent patterns in a large sparse graph

AU - Kuramochi, Michihiro

AU - Karypis, George

PY - 2004/6/22

Y1 - 2004/6/22

N2 - 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.

AB - 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.

KW - Frequent subgraph

KW - Graph mining

KW - Pattern discovery

UR - http://www.scopus.com/inward/record.url?scp=2942592528&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=2942592528&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:2942592528

SP - 345

EP - 356

BT - Proceedings of the Fourth SIAM International Conference on Data Mining

A2 - Berry, M.W.

A2 - Dayal, U.

A2 - Kamath, C.

A2 - Skillicorn, D.

T2 - Proceedings of the Fourth SIAM International Conference on Data Mining

Y2 - 22 April 2004 through 24 April 2004

ER -

Finding frequent patterns in a large sparse graph

Abstract

Other

Keywords

Find It

Other files and links

Fingerprint

Cite this