Abstract
Mining from graph-structured data has its root in concept formation. Recent advancement of data mining techniques has broadened its applicability. Graph mining faces with subgraph isomorphism which is known to be NP-complete. Two contrasting approaches of our work on extracting frequent subgraphs are revisited, one using complete search (AGM) and the other using heuristic search (GBI). Both use canonical labelling to deal with subgraph isomorphism. AGM represents a graph by its adjacency matrix and employs an Apriori-like bottom up search algorithm using anti-monotonicity of frequency. It can handle both connected and dis-connected graphs, and has been extended to handle a tree data and a sequential data by incorporating a different bias to each in joining operators. It has also been extended to incorporate taxonomy in labels to extract generalized subgraphs. GBI employs a notion of chunking, which recursively chunks two adjoining nodes, thus generating fairly large subgraphs at an early stage of search. The recent improved version extends it to employ pseudo-chunking which is called chunkingless chunking, enabling to extract overlapping subgraphs. It can impose two kinds of constraints to accelerate search, one to include one or more of the designated subgraphs and the other to exclude all of the designated sub-graphs. It has been extended to extract paths and trees from a graph data by placing a restriction on pseudo-chunking operations. GBI can further be used as a feature constructor in decision tree building. The paper explains how both GBI and AGM with their extended versions can be applied to solve various data mining problems which are difficult to solve by other methods.
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
Cook, D.J., Holder, L.B.: Graph-based data mining. IEEE Intelligent Systems 15(2), 32–41 (2000)
Geamsakul, W., Yoshida, T., Ohara, K., Motoda, H., Yokoi, H., Takabayashi, K.: Constructing a decision tree for graph-structured data and its applications. Journal of Fundamenta Informatiae, Special issue on Advances in Mining Graphs, Trees and Sequence 66(1-2), 131–160 (2005)
Inokuchi, A., Washio, T., Motoda, H.: Complete mining of frequent patterns from graphs: Mining graph data machine learning, 50(3), 321–354 (2003)
Inokuchi, A., Washio, T., Motoda, H.: An apriori-based algorithm for mining frequent substructures from graph data. In: Proc. of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, pp. 13–23 (2000)
Inokuchi, A., Washio, T., Motoda, H.: General framework for mining frequent subgraphs from labeled graphs. Journal of Fundamenta Informatiae, Special issue on Advances in Mining Graphs, Trees and Sequence 66(1-2), 53–82 (2005)
Kuramochi, M., Karypis, G.: An efficient algorithm for discovering frequent subgraphs. IEEE Trans. Knowledge and Data Engineering 16(9), 1038–1051 (2004)
Matsuda, T., Motoda, H., Washio, T.: Graph-based induction and its applications. Advanced Engineering Informatics 16(2), 135–143 (2002)
Nguyen, P.C., Ohara, K., Motoda, H., Washio, T.: Cl-gbi: A novel approach for extracting typical patterns from graph-structured data. In: Proceedings of the 9th Pacific-Asia Conference on Knowledge Discovery and Data Mining (2005)
Yada, K., Motoda, H., Washio, T., Miyawaki, A.: Consumer behavior analysis by graph mining technique. New Mathematics and Natural Computation 2(1), 59–68 (2005)
Yan, X., Han, J.: gspan: Graph-based structure pattern mining. In: Proc. of the 2nd IEEE International Conference on Data Mining, pp. 721–724. IEEE Computer Society Press, Los Alamitos (2002)
Yoshida, K., Motoda, H.: Clip: Concept learning from inference pattern. Journal of Artificial Intelligence 75(1), 63–92 (1995)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Motoda, H. (2007). Pattern Discovery from Graph-Structured Data - A Data Mining Perspective. In: Okuno, H.G., Ali, M. (eds) New Trends in Applied Artificial Intelligence. IEA/AIE 2007. Lecture Notes in Computer Science(), vol 4570. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73325-6_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-73325-6_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73322-5
Online ISBN: 978-3-540-73325-6
eBook Packages: Computer ScienceComputer Science (R0)