Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download
Contributor : Joël Quinqueton Connect in order to contact the contributor
Submitted on : Thursday, October 18, 2018 - 12:54:12 PM
Last modification on : Monday, October 11, 2021 - 1:24:08 PM
Long-term archiving on: : Saturday, January 19, 2019 - 1:57:21 PM


Files produced by the author(s)




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. ⟨10.1007/s10115-014-0769-4⟩. ⟨lirmm-01275709⟩



Record views


Files downloads