B FGMAC : breadth - first frequent subgraph mining with ARC consistency

• Autorzy: Douar B. , Latiri C. , Liquiere M. , Slimani Y.
• Języki publikacji: EN

Abstrakty

EN

The paper presents a new projection operator for graphs named AC-projection, which exhibits nice theoretical complexity properties unlike to the graph isomorphism operator typically used in graph mining. 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.

Słowa kluczowe

EN

graph mining; arc consistency; AC-projection; projection operator; AC-reduced; subgraph mining; polynomial complexity projection

• Wydawca: University of Social Sciences
• Czasopismo: Journal of Artificial Intelligence and Soft Computing Research
• Rocznik: 2011
• Tom: Vol. 1, No. 4
• Strony: 269--281
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Douar B.

• LIRMM, Montpellier, France
• URPAH Team, Faculty of Sciences of Tunis

autor

Latiri C.

• URPAH Team, Faculty of Sciences of Tunis

autor

Liquiere M.

• LIRMM, Montpellier, France
• IUT Béziers

autor

Slimani Y.

• URPAH Team, Faculty of Sciences of Tunis

Bibliografia

• [1] R. Agrawal and R. Skirant. Fast algorithms for mining association rules. In proceedings of the 20th International Conference on Very Large Databases, Santiago, Chile, pages 478–499, June 1994.
• [2] C. Bessi`ere and J.-C. R´egin. Mac and combined heuristics: Two reasons to forsake fc (and cbj?) on hard problems. In E. C. Freuder, editor, CP, volume 1118 of Lecture Notes in Computer Science, pages 61–75. Springer, 1996.
• [3] D. J. Cook and L. B. Holder. Mining Graph Data. John Wiley & Sons, 2006.
• [4] B. Douar, M. Liquiere, C. C. Latiri, and Y. Slimani. Fgmac: Frequent subgraph mining with arc consistency. In Proceedings of the IEEE Symposium on Computational Intelligence and Data Mining, CIDM 2011, part of the IEEE Symposium Series on Computational Intelligence 2011, pages 112–119.IEEE, 2011.
• [5] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NPCompleteness. W. H. Freeman & Co., New York, NY, USA, 1979.
• [6] P. Hell and J. Nesetril. Graphs and homomorphism, volume 28. Oxford University Press, Oxford, 2004.
• [7] C. Helma, R. D. King, S. Kramer, and A. Srinivasan. The predictive toxicology challenge 20002001. Bioinformatics, 17(1):107–108, 2001.
• [8] J. Huan, W. Wang, and J. Prins. Efficient mining of frequent subgraphs in the presence of isomorphism. In International Conference on Data Mining, page 549. IEEE Computer Society, 2003.
• [9] A. Inokuchi, T. Washio, and H. Motoda. Complete mining of frequent patterns from graphs: Mining graph data. Machine Learning, 50(3):321–354, 2003.
• [10] M. Kuramochi and G. Karypis. Frequent subgraph discovery. In N. Cercone, T. Y. Lin, and X. Wu, editors, International Conference on Data Mining, pages 313–320. IEEE Computer Society, 2001.
• [11] M. Kuramochi and G. Karypis. An efficient algorithm for discovering frequent subgraphs. IEEE Transactions on Knowledge and Data Engineering, 16:1038–1051, 2004.
• [12] M. Liquiere. Arc consistency projection: A new generalization relation for graphs. In U. Priss, S. Polovina, and R. Hill, editors, ICCS, volume 4604 of LNCS, pages 333–346. Springer, 2007.
• [13] A. K. Mackworth. Consistency in networks of relations. Artif. Intell., 8(1):99–118, 1977.
• [14] S. Nijssen and J. N. Kok. The gaston tool for frequent subgraph mining. In International Workshop on Graph-Based Tools (Grabats). Electronic Notes in Theoretical Computer Science, pages 77–87, 2004.
• [15] J. R. Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, 1 edition, January 1993.
• [16] M. D. Wessel, P. C. Jurs, J. W. Tolan, and S. M. Muskal. Prediction of human intestinal absorption of drug compounds from molecular structure. Journal of Chemical Information and Computer Sciences, 38(4):726–735, 1998.
• [17] I. H. Witten and E. Frank. Data Mining: Practical Machine Learning Tools and Techniques, Second Edition (Morgan Kaufmann Series in Data Management Systems). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2005.
• [18] M. W¨orlein, T. Meinl, I. Fischer, and M. Philippsen. A quantitative comparison of the subgraph miners mofa, gspan, ffsm, and gaston. In European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, volume 3721 of LNCS, pages 392–403. Springer, 2005.
• [19] X. Yan and J. Han. gspan: Graph-based substructure pattern mining. In International Conference on Data Mining, pages 721–724. IEEE Computer Society, 2002.