Abstract
Graph mining means a series of processes for finding frequent sub-graphs in graph databases with complex structures. To obtain useful sub-graphs, isomorphic decision is needed since one graph data can contain lots of duplicated patterns. Therefore, we need to consider only patterns without duplications. However, these operations can cause enormous overheads due to knotty characteristics of graphs, which is called NP-hard problem. In addition, there also exists a problem that exponentially increases the number of unnecessary operations whenever any pattern size grows. In this paper, we propose a method that enhances efficiency of isomorphic decision in cyclic graphs based on a state-of-the-art algorithm, Gaston, which is called Egaston-CS (Efficient gaston for Cyclic-edge and Spanning-tree). In experiments, we compare our algorithm with previous algorithms, and thereby we demonstrate that Egaston-CS outperforms the others in terms of isomorphic decision.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bifet A, Holmes G, Pfahringer B, Gavalda R (2011) Mining frequent closed graphs on evolving data streams. In: KDD’11 Proceedings of the 17th ACM SIGKDD international conference on knowledge discovery and data mining, pp 591–599
Bogdanov P, Mongiovi M, Singh AK (2011) Mining heavy subgraphs in time-evolving networks. ICDM, pp 81–90
Günnemann S, Seidl T (2010) Subgraph mining on directed and weighted graphs. PAKDD 6119:133–146
Han J, Kamber M (2005) Data mining: concepts and techniques. Morgan Kaufmann, Publishers, San Francisco
Lahiri M, Berger TY (2010) Periodic subgraph mining in dynamic networks. Knowl Inf Syst 24(3):467–497
Lini T, Thomas SR, Valluri KK (2006) MARGIN: Maximal frequent Subgraph mining. ICDM, pp 1097–1101
Nijssen S, Kok JN (2005) The Gaston tool for frequent subgraph mining. Electron Notes Theor Comput Sci 127(1):77–87
Nijssen S, Kok JN (2004) A quickstart in frequent structure mining can make a difference, In: Proceedings of the tenth ACM SIGKDD international conference on knowledge discovery and data mining, pp 647–652
Silva A, Meira W Jr, Zaki MJ (2012) Mining attribute-structure correlated patterns in large attributed graphs. PVLDB 5(5):466–477
Yan X, Han J (2002) gSpan: graph-based substructure pattern mining. In: Proceedings of the 2002 IEEE international conference on data mining, pp 721–724
Zhiwen Y, Zhiyong Y, Xingshe Z, Christian B, Yuichi N (2012) Tree-based mining for discovering patterns of human interaction in meetings. IEEE Trans Knowl Data Eng 24(4):759–768
Zou Z, Li J, Gao H, Zhang S (2010) Mining frequent subgraph patterns from uncertain graph data. IEEE Trans Knowl Data Eng 22(9):1203–1218
Zhu F, Yan X, Han J Yu PS (2007) gPrune: a constraint pushing framework for graph pattern mining. In: Proceeding 2007 Pacific-Asia conference on knowledge discovery and data mining (PAKDD’07), pp 388–400
Acknowledgments
This research was supported by the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (NRF No. 2012-0003740 and 2012-0000478).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer Science+Business Media Dordrecht
About this paper
Cite this paper
Lee, G., Yun, U. (2013). Efficient Isomorphic Decision for Mining Sub Graphs with a Cyclic Form. In: Kim, K., Chung, KY. (eds) IT Convergence and Security 2012. Lecture Notes in Electrical Engineering, vol 215. Springer, Dordrecht. https://doi.org/10.1007/978-94-007-5860-5_114
Download citation
DOI: https://doi.org/10.1007/978-94-007-5860-5_114
Published:
Publisher Name: Springer, Dordrecht
Print ISBN: 978-94-007-5859-9
Online ISBN: 978-94-007-5860-5
eBook Packages: EngineeringEngineering (R0)