LC-mine: a framework for frequent subgraph mining with local consistency techniques - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Knowledge and Information Systems (KAIS) Year : 2015

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.
Fichier principal
Vignette du fichier
KAIS20141.pdf (1.52 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-01275709 , version 1 (18-10-2018)

Identifiers

Cite

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), 2015, 44 (1), pp.1-25. ⟨10.1007/s10115-014-0769-4⟩. ⟨lirmm-01275709⟩
135 View
167 Download

Altmetric

Share

Gmail Facebook X LinkedIn More