Abstract

Recent research on pattern discovery has progressed form mining frequent itemsets and sequences to mining structured patterns including trees, lattices, and graphs. As a general data structure, graph can model complicated relations among data with wide applications in bioinformatics, Web exploration, and etc. However, mining large graph patterns in challenging due to the presence of an exponential number of frequent subgraphs. Instead of mining all the subgraphs, we propose to mine closed frequent graph patterns. A graph g is closed in a database if there exists no proper supergraph of g that has the same support as g. A closed graph pattern mining algorithm, CloseGraph, is developed by exploring several interesting pruning methods. Our performance study shows that CloseGraph not only dramatically reduces unnecessary subgraphs to be generated but also substantially increases the efficiency of mining, especially in the presence of large graph patterns.

Original languageEnglish (US)
Pages286-295
Number of pages10
DOIs
StatePublished - Dec 1 2003
Event9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '03 - Washington, DC, United States
Duration: Aug 24 2003Aug 27 2003

Other

Other9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '03
CountryUnited States
CityWashington, DC
Period8/24/038/27/03

Fingerprint

Bioinformatics
Data structures

Keywords

  • Canonical label
  • Closed pattern
  • Frequent graph
  • Graph representation

ASJC Scopus subject areas

  • Software
  • Information Systems

Cite this

Yan, X., & Han, J. (2003). CloseGraph: Mining closed frequent graph patterns. 286-295. Paper presented at 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '03, Washington, DC, United States. https://doi.org/10.1145/956750.956784

CloseGraph : Mining closed frequent graph patterns. / Yan, Xifeng; Han, Jiawei.

2003. 286-295 Paper presented at 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '03, Washington, DC, United States.

Research output: Contribution to conferencePaper

Yan, X & Han, J 2003, 'CloseGraph: Mining closed frequent graph patterns' Paper presented at 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '03, Washington, DC, United States, 8/24/03 - 8/27/03, pp. 286-295. https://doi.org/10.1145/956750.956784
Yan X, Han J. CloseGraph: Mining closed frequent graph patterns. 2003. Paper presented at 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '03, Washington, DC, United States. https://doi.org/10.1145/956750.956784
Yan, Xifeng ; Han, Jiawei. / CloseGraph : Mining closed frequent graph patterns. Paper presented at 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '03, Washington, DC, United States.10 p.
@conference{1836f9cf97204084ab61f9e4ea6005f6,
title = "CloseGraph: Mining closed frequent graph patterns",
abstract = "Recent research on pattern discovery has progressed form mining frequent itemsets and sequences to mining structured patterns including trees, lattices, and graphs. As a general data structure, graph can model complicated relations among data with wide applications in bioinformatics, Web exploration, and etc. However, mining large graph patterns in challenging due to the presence of an exponential number of frequent subgraphs. Instead of mining all the subgraphs, we propose to mine closed frequent graph patterns. A graph g is closed in a database if there exists no proper supergraph of g that has the same support as g. A closed graph pattern mining algorithm, CloseGraph, is developed by exploring several interesting pruning methods. Our performance study shows that CloseGraph not only dramatically reduces unnecessary subgraphs to be generated but also substantially increases the efficiency of mining, especially in the presence of large graph patterns.",
keywords = "Canonical label, Closed pattern, Frequent graph, Graph representation",
author = "Xifeng Yan and Jiawei Han",
year = "2003",
month = "12",
day = "1",
doi = "10.1145/956750.956784",
language = "English (US)",
pages = "286--295",
note = "9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '03 ; Conference date: 24-08-2003 Through 27-08-2003",

}

TY - CONF

T1 - CloseGraph

T2 - Mining closed frequent graph patterns

AU - Yan, Xifeng

AU - Han, Jiawei

PY - 2003/12/1

Y1 - 2003/12/1

N2 - Recent research on pattern discovery has progressed form mining frequent itemsets and sequences to mining structured patterns including trees, lattices, and graphs. As a general data structure, graph can model complicated relations among data with wide applications in bioinformatics, Web exploration, and etc. However, mining large graph patterns in challenging due to the presence of an exponential number of frequent subgraphs. Instead of mining all the subgraphs, we propose to mine closed frequent graph patterns. A graph g is closed in a database if there exists no proper supergraph of g that has the same support as g. A closed graph pattern mining algorithm, CloseGraph, is developed by exploring several interesting pruning methods. Our performance study shows that CloseGraph not only dramatically reduces unnecessary subgraphs to be generated but also substantially increases the efficiency of mining, especially in the presence of large graph patterns.

AB - Recent research on pattern discovery has progressed form mining frequent itemsets and sequences to mining structured patterns including trees, lattices, and graphs. As a general data structure, graph can model complicated relations among data with wide applications in bioinformatics, Web exploration, and etc. However, mining large graph patterns in challenging due to the presence of an exponential number of frequent subgraphs. Instead of mining all the subgraphs, we propose to mine closed frequent graph patterns. A graph g is closed in a database if there exists no proper supergraph of g that has the same support as g. A closed graph pattern mining algorithm, CloseGraph, is developed by exploring several interesting pruning methods. Our performance study shows that CloseGraph not only dramatically reduces unnecessary subgraphs to be generated but also substantially increases the efficiency of mining, especially in the presence of large graph patterns.

KW - Canonical label

KW - Closed pattern

KW - Frequent graph

KW - Graph representation

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

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

U2 - 10.1145/956750.956784

DO - 10.1145/956750.956784

M3 - Paper

AN - SCOPUS:77952334885

SP - 286

EP - 295

ER -