A Projection Bias in Frequent Subgraph Mining Can Make a Difference - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue International Journal on Artificial Intelligence Tools Année : 2014

A Projection Bias in Frequent Subgraph Mining Can Make a Difference

Résumé

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
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

Citer

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⟩
119 Consultations
113 Téléchargements

Altmetric

Partager

Gmail Mastodon Facebook X LinkedIn More