FSMS: A Frequent Subgraph Mining Algorithm using Mapping Sets
Abstract
With the increasing prevalence of data that model relationships between various entities, the use of a graph-based representation for real-world problems offers a logical strategy for organizing information and making knowledge-based decisions. In particular, often it is useful to identify the most frequent patterns or relationships amongst the data in a graph, which requires finding frequent subgraphs. Algorithms for addressing that problem have been proposed for over 15 years. In the worst case, all subgraphs in the graph must be examined, which is exponential in complexity, and subgraph isomorphisms must be computed, which is an NP-complete problem. Frequent subgraph algorithms may attempt to improve the actual runtime performance by reducing the size of the search space, avoiding duplicate comparisons, and/or minimizing the amount of memory required for compiling intermediate results. Herein we present a frequent subgraph mining algorithm that leverages mapping sets in order to eliminate the isomorphism computation during the search for non-edge-disjoint frequent subgraphs. Experimental results show that absence of isomorphism computation leads to much faster frequent subgraph detection when there is a need to identify all occurrences of those subgraphs.
Recommended Citation
A. Abedijaberi and J. Leopold, "FSMS: A Frequent Subgraph Mining Algorithm using Mapping Sets," Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9729, pp. 761 - 773, Springer Verlag, Jul 2016.
The definitive version is available at https://doi.org/10.1007/978-3-319-41920-6_58
Meeting Name
12th International Conference on Machine Learning and Data Mining in Pattern Recognition, MLDM 2016 (2016: Jul. 16-21, New York, NY)
Department(s)
Computer Science
Keywords and Phrases
Algorithms; Artificial intelligence; Computational complexity; Graphic methods; Knowledge based systems; Learning systems; Mapping; Pattern recognition; Set theory; Frequent subgraph mining; Frequent subgraphs; Graph mining; Graph-based representations; Intermediate results; Model relationships; Run-time performance; Subgraph isomorphism; Data mining; Mapping sets
International Standard Book Number (ISBN)
978-3-319-41919-0
International Standard Serial Number (ISSN)
0302-9743
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2016 Springer Verlag, All rights reserved.
Publication Date
01 Jul 2016
