FGMAC: Frequent Subgraph Mining with Arc Consistency

Abstract : With the important growth of requirements to analyze large amount of structured data such as chemical compounds, proteins structures, XML documents, to cite but a few, graph mining has become an attractive track and a real challenge in the data mining field. Among the various kinds of graph patterns, frequent subgraphs seem to be relevant in characterizing graphsets, discriminating different groups of sets, and classifying and clustering graphs. Because of the NP-Completeness of subgraph isomorphism test as well as the huge search space, fragment miners are exponential in runtime and/or memory consumption. In this paper we study a new polynomial projection operator named AC-Projection based on a key technique of constraint programming namely Arc Consistency (AC). This is intended to replace the use of the exponential subgraph isomorphism. We study the relevance of frequent AC-reduced graph patterns on classification and we prove that we can achieve an important performance gain without or with non-significant loss of discovered pattern's quality.
Type de document :
Communication dans un congrès
CIDM'11: IEEE Symposium on Computational Intelligence and Data Mining, Apr 2011, France. IEEE, pp.112-119, 2011
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00757478
Contributeur : Michel Liquiere <>
Soumis le : mardi 27 novembre 2012 - 09:58:41
Dernière modification le : jeudi 11 janvier 2018 - 06:26:23

Identifiants

  • HAL Id : lirmm-00757478, version 1

Collections

Citation

Brahim Douar, Michel Liquière, Chiraz Latiri, Yahya Slimani. FGMAC: Frequent Subgraph Mining with Arc Consistency. CIDM'11: IEEE Symposium on Computational Intelligence and Data Mining, Apr 2011, France. IEEE, pp.112-119, 2011. 〈lirmm-00757478〉

Partager

Métriques

Consultations de la notice

84