A Projection Bias in Frequent Subgraph Mining Can Make a Difference - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles International Journal on Artificial Intelligence Tools Year : 2014

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

Dates and versions

lirmm-01275714 , version 1 (15-10-2018)

Identifiers

Cite

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, 2014, 23 (5), pp.#1450005. ⟨10.1142/S0218213014500055⟩. ⟨lirmm-01275714⟩
117 View
107 Download

Altmetric

Share

Gmail Facebook X LinkedIn More