Skip to Main content Skip to Navigation
Journal articles

A Projection Bias in Frequent Subgraph Mining Can Make a Difference

Abstract : The aim of the frequent subgraph mining task is to find frequently occurring subgraphs in a large graph database. However, this task is a thriving challenge, as graph and subgraph isomorphisms play a key role throughout the computations. Since subgraph isomorphism testing is a hard problem, subgraph 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. This paper presents a new projection operator for graphs named AC-projection, which exhibits nice theoretical complexity properties. We study the size of the search space as well as some practical properties of the projection operator. We also introduce a novel breadth-first algorithm for frequent AC-reduced subgraphs mining. Then, we prove experimentally that we can achieve an important performance gain (polynomial complexity projection) without or with non-significant loss of discovered patterns in terms of quality.
Document type :
Journal articles
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01275714
Contributor : Joël Quinqueton <>
Submitted on : Monday, October 15, 2018 - 7:28:32 PM
Last modification on : Monday, January 11, 2021 - 5:24:17 PM
Long-term archiving on: : Wednesday, January 16, 2019 - 4:21:10 PM

File

IJAIT2014.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Brahim Douar, Chiraz Latiri, Michel Liquière, Yahya Slimani. A Projection Bias in Frequent Subgraph Mining Can Make a Difference. International Journal on Artificial Intelligence Tools, World Scientific Publishing, 2014, 23 (5), pp.#1450005. ⟨10.1142/S0218213014500055⟩. ⟨lirmm-01275714⟩

Share

Metrics

Record views

255

Files downloads

199