Paper Info
Title
Mining frequent subgraphs from tremendous amount of small graphs using MapReduce.
Abstract
Frequent subgraph mining from a tremendous amount of small graphs is a primitive operation for many data mining applications. Existing approaches mainly focus on centralized systems and suffer from the scalability issue. Consider the increasing volume of graph data and mining frequent subgraphs is a memory-intensive task, it is difficult to tackle this problem on a centralized machine efficiently. In this paper, we therefore propose an efficient and scalable solution, called MRFSE, using MapReduce. MRFSE adopts the breadth-first search strategy to iteratively extract frequent subgraphs, i.e., all frequent subgraphs with \(i+1\) edges are generated based on frequent subgraphs with i edges at the ith iteration. In our design, existing frequent subgraph mining techniques in centralized systems can be easily extended and integrated. More importantly, new frequent subgraphs are generated without performing any isomorphism test which is costly and imperative in existing frequent subgraph mining techniques. Besides, various optimization techniques are proposed to further reduce the communication and I/O cost. Extensive experiments conducted on our in-house clusters demonstrate the superiority of our proposed solution in terms of both scalability and efficiency.
Year
DOI
Venue
2018
10.1007/s10115-017-1104-7
Knowl. Inf. Syst.
Keywords
Field
DocType
Frequent subgraph mining,MapReduce,Isomorphism-testing-free
Data mining,Graph,Computer science,Theoretical computer science,Isomorphism,Scalability
Journal
Volume
Issue
ISSN
56
3
0219-1377
Citations 
PageRank 
References 
1
0.37
20
Authors
7
Name
Order
Citations
PageRank
Zhe Peng1518.32
Tongtong Wang2166.10
Wei Lu331962.97
Hao Huang4897.77
Xiaoyong Du5882123.29
Feng Zhao6434.92
Anthony K. H. Tung73263189.90