LC-mine: a framework for frequent subgraph mining with local consistency techniques

Abstract : Developing algorithms that discover all frequently occurring subgraphs in a large graph database is computationally extensive, as graph and subgraph isomorphisms play a key role throughout the computations. Since subgraph isomorphism testing is a hard problem, fragment miners are exponential in runtime. To alleviate the complexity issue, we propose to introduce a bias in the projection operator and instead of using the costly subgraph isomorphism projection, one can use a polynomial projection having a semantically valid structural interpretation. In this paper, our purpose is to present LC-mine, a generic and efficient framework to mine frequent subgraphs by the means of local consistency techniques used in the constraint programming field. Two instances of the framework based on the arc consistency technique are developed and presented in this paper. The first instance follows a breadth-first order, while the second is a pattern-growth approach that follows a depth-first search space exploration strategy. Then, we prove experimentally that we can achieve an important performance gain without or with nonsignificant loss of discovered patterns in terms of quality.
Type de document :
Article dans une revue
Knowledge and Information Systems (KAIS), Springer, 2015, 44 (1), pp.1-25. 〈http://link.springer.com/journal/10115〉. 〈10.1007/s10115-014-0769-4〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01275709
Contributeur : Joël Quinqueton <>
Soumis le : jeudi 18 février 2016 - 09:08:55
Dernière modification le : jeudi 11 janvier 2018 - 06:26:23

Identifiants

Collections

Citation

Brahim Douar, Michel Liquière, Chiraz Latiri, Yahya Slimani. LC-mine: a framework for frequent subgraph mining with local consistency techniques. Knowledge and Information Systems (KAIS), Springer, 2015, 44 (1), pp.1-25. 〈http://link.springer.com/journal/10115〉. 〈10.1007/s10115-014-0769-4〉. 〈lirmm-01275709〉

Partager

Métriques

Consultations de la notice

40