Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00757478
Contributor : Michel Liquiere <>
Submitted on : Tuesday, November 27, 2012 - 9:58:41 AM
Last modification on : Thursday, May 24, 2018 - 3:59:23 PM

Identifiers

  • 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. pp.112-119. ⟨lirmm-00757478⟩

Share

Metrics

Record views

175