Abstract
Conceptual Graphs (CGs) are a graph-based knowledge representation formalism. In this paper we propose cgSpan a CG frequent pattern mining algorithm. It extends the DMGM-GSM algorithm that takes taxonomy-based labeled graphs as input; it includes three more kinds of knowledge of the CG formalism: (a) the fixed arity of relation nodes, handling graphs of neighborhoods centered on relations rather than graphs of nodes, (b) the signatures, avoiding patterns with concept types more general than the maximal types specified in signatures and (c) the inference rules, applying them during the pattern mining process. The experimental study highlights that cgSpan is a functional CG Frequent Pattern Mining algorithm and that including CGs specificities results in a faster algorithm with more expressive results and less redundancy with vocabulary.
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
Baget, J.-F., Croitoru, M., Gutierrez, A., Leclère, M., Mugnier, M.-L.: Translations between RDF(S) and conceptual graphs. In: Croitoru, M., Ferré, S., Lukose, D. (eds.) ICCS-ConceptStruct 2010. LNCS (LNAI), vol. 6208, pp. 28–41. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14197-3_7
Cakmak, A., Ozsoyoglu, G.: Taxonomy-superimposed graph mining. In: Proceedings of the 11th International Conferences on Extending Database Technology: Advances in Database Technology, pp. 217–228 (2008)
Chein, M., Mugnier, M.L.: A Graph-Based Approach to Knowledge Representation: Computational Foundations of Conceptual Graphs (Part. I). Springer (2008). https://doi.org/10.1007/978-1-84800-286-9
Chung, F., Lu, L.: The average distances in random graphs with given expected degrees. Proc. Nat. Acad. Sci. 99(25), 15879–15882 (2002)
Elseidy, M., Abdelhamid, E., Skiadopoulos, S., Kalnis, P.: Grami: frequent subgraph and pattern mining in a single large graph. Proc. VLDB Endowment 7(7), 517–528 (2014)
Han, J., Cheng, H., Xin, D., Yan, X.: Frequent pattern mining: current status and future directions. Data Min. Knowl. Discov. 15(1), 55–86 (2007)
Inokuchi, A.: Mining generalized substructures from a set of labeled graphs. In: Proceedings of the 4th IEEE International Conferences on Data Mining (ICDM’04), pp. 415–418. IEEE (2004)
Iyer, A.P., Liu, Z., Jin, X., Venkataraman, S., Braverman, V., Stoica, I.: ASAP: fast, approximate graph pattern mining at scale. In: Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation OSDI 18, pp. 745–761 (2018)
Petermann, A., Micale, G., Bergami, G., Pulvirenti, A., Rahm, E.: Mining and ranking of generalized multi-dimensional frequent subgraphs. In: Proceedings of the 12th International Conferences on Digital Information Management (ICDIM), pp. 236–245. IEEE (2017)
Yan, X., Han, J.: cgSpan: graph-based substructure pattern mining. In: Proceedings of IEEE International Conferences on Data Mining, ICDM’02, pp. 721–724. IEEE (2002)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Faci, A., Lesot, MJ., Laudy, C. (2021). cgSpan: Pattern Mining in Conceptual Graphs. In: Rutkowski, L., Scherer, R., Korytkowski, M., Pedrycz, W., Tadeusiewicz, R., Zurada, J.M. (eds) Artificial Intelligence and Soft Computing. ICAISC 2021. Lecture Notes in Computer Science(), vol 12855. Springer, Cham. https://doi.org/10.1007/978-3-030-87897-9_14
Download citation
DOI: https://doi.org/10.1007/978-3-030-87897-9_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-87896-2
Online ISBN: 978-3-030-87897-9
eBook Packages: Computer ScienceComputer Science (R0)