Abstract
Frequent sub-graph mining entails two significant overheads. The first is concerned with candidate set generation. The second with isomorphism checking. These are also issues with respect to other forms of frequent pattern mining but are exacerbated in the context of frequent sub-graph mining. To reduced the search space, and address these twin overheads, a weighted approach to sub-graph mining is proposed. However, a significant issue in weighted sub-graph mining is that the anti-monotone property, typically used to control candidate set generation, no longer holds. This paper examines a number of edge weighting schemes; and suggests three strategies for controlling candidate set generation. The three strategies have been incorporated into weighted variations of gSpan: ATW-gSpan, AW-gSpan and UBW-gSpan respectively. A complete evaluation of all three approaches is presented.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barber, B., Hamilton, H.J.: Extracting Share Frequent Itemsets with Infrequent Subsets. Journal of Data Mining and Knowledge Discovery 7, 153–185 (2003)
Carter, C.L., Hamilton, H.J., Cercone, N.: Share based Measures for Itemsets. In: Komorowski, J., Żytkow, J.M. (eds.) PKDD 1997. LNCS, vol. 1263, pp. 14–24. Springer, Heidelberg (1997)
Cook, D.J., Holder, L.B.: Substructure Discovery Using Minimum Description Length and Background Knowledge. Journal of Artificial Intelligenc Research 1, 231–255 (1994)
Elsayed, A., Coenen, F., Jiang, C., Garca-Fiana, M., Sluming, V.: Corpus Callosum MR Image Classification. Journal of Knowledge Based Systems (to appear 2010)
Huan, J., Wang, W., Prins, J.: Efficient Mining of Frequent Subgraph in the Presence of Isomorphism. In: Proceedings of the 2003 International Conference on Data Mining, ICDM 2003 (2003)
Inokuchi, A., Washio, T., Motoda, H.: An Apriori-based Algorithm for Mining Frequent Substructures from Graph Data. In: Proceedings of the 4th European Conference on Principles and Practice of Knowledge Discovery in Databases (2000)
Jiang, C., Coenen, F., Sanderson, R., Zito, M.: Text Classification using Graph Mining-Based Feature Extraction. The Journal of Knowledge Based Systems (to appear 2010)
Kuramochi, M., Karypis, G.: Frequent Subgraph Discovery. In: Proceedings of IEEE International Conference on Data Mining (2001)
Robinson, S.E., Christley, R.M.: Identifying Temporal Variation in Reported Births, Deaths and Movements of Cattle in Britain. Journal of BMC Verterinary Research (2006), doi:10.1186/1746-6148-2-11
Tao, F., Murtagh, F., Farid, M.: Weighted Association Rule Mining using Weighted Support and Significance Framework. In: The Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (ACM SIGKDD 2003), Washington DC, USA, pp. 661–666 (2003)
Yan, X., Han, J.: gSpan: Graph-based Substructure Pattern Mining. In: Proceedings of 2002 International Conference on Data Mining (2002)
Yan, X., Han, J.: CloseGraph: Mining Closed Frequent Graph Patterns. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington DC, USA, pp. 286–295 (2003)
Yun, U.: WIS: Weighted Interesting Sequential Pattern Mining with a Similar Level of Support and/or Weight. ETRI Journal 29(3), 336–352 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jiang, C., Coenen, F., Zito, M. (2010). Frequent Sub-graph Mining on Edge Weighted Graphs. In: Bach Pedersen, T., Mohania, M.K., Tjoa, A.M. (eds) Data Warehousing and Knowledge Discovery. DaWaK 2010. Lecture Notes in Computer Science, vol 6263. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15105-7_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-15105-7_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15104-0
Online ISBN: 978-3-642-15105-7
eBook Packages: Computer ScienceComputer Science (R0)