FGMAC: Frequent Subgraph Mining with Arc Consistency - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2011

FGMAC: Frequent Subgraph Mining with Arc Consistency


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.
No file

Dates and versions

lirmm-00757478 , version 1 (27-11-2012)


  • HAL Id : lirmm-00757478 , version 1


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⟩
114 View
0 Download


Gmail Mastodon Facebook X LinkedIn More