Downloads: 244

Files in This Item:
File Description SizeFormat 
s10994-010-5215-6.pdf339.61 kBAdobe PDFView/Open
Title: Efficiently mining δ-tolerance closed frequent subgraphs
Authors: Takigawa, Ichigaku
Mamitsuka, Hiroshi  kyouindb  KAKEN_id  orcid (unconfirmed)
Author's alias: 瀧川, 一学
Keywords: Frequent subgraph mining
δ-tolerance closedness
Partial reverse search
Issue Date: Feb-2011
Publisher: Springer, Part of Springer Science+Business Media
Journal title: Machine Learning
Volume: 82
Issue: 2
Start page: 95
End page: 121
Abstract: The output of frequent pattern mining is a huge number of frequent patterns, which are very redundant, causing a serious problem in understandability. We focus on mining frequent subgraphs for which well-considered approaches to reduce the redundancy are limited because of the complex nature of graphs. Two known, standard solutions are closed and maximal frequent subgraphs, but closed frequent subgraphs are still redundant and maximal frequent subgraphs are too specific. A more promising solution is δ-tolerance closed frequent subgraphs, which decrease monotonically in δ, being equal to maximal frequent subgraphs and closed frequent subgraphs for δ=0 and 1, respectively. However, the current algorithm for mining δ-tolerance closed frequent subgraphs is a naive, two-step approach in which frequent subgraphs are all enumerated and then sifted according to δ-tolerance closedness. We propose an efficient algorithm based on the idea of “reverse-search” by which the completeness of enumeration is guaranteed and for which new pruning conditions are incorporated. We empirically demonstrate that our approach significantly reduced the amount of real computation time of two compared algorithms for mining δ-tolerance closed frequent subgraphs, being pronounced more for practical settings.
Rights: The final publication is available at
This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。
DOI(Published Version): 10.1007/s10994-010-5215-6
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks

Export Format: 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.