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.
Type de document :
Article dans une revue
International Journal on Artificial Intelligence Tools, World Scientific Publishing, 2014, 23 (5), 〈http://www.worldscientific.com/worldscinet/ijait〉. 〈10.1142/S0218213014500055〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01275714
Contributeur : Joël Quinqueton <>
Soumis le : jeudi 18 février 2016 - 09:21:52
Dernière modification le : jeudi 24 mai 2018 - 15:59:23

Identifiants

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), 〈http://www.worldscientific.com/worldscinet/ijait〉. 〈10.1142/S0218213014500055〉. 〈lirmm-01275714〉

Partager

Métriques

Consultations de la notice

98