On the Usefulness of Weight-Based Constraints in Frequent Subgraph Mining
- Author: Frank Eichinger, Matthias Huber, Klemens Böhm
Proceedings of the 30th BCS SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence (AI), Cambridge, UK, 2010
Karlsruhe Reports in Informatics 2010,10, Department of Informatics, Karlsruhe Institute of Technology (KIT)
Frequent subgraph mining is an important data-mining technique. In this paper we look at weighted graphs, which are ubiquitous in the real world. The analysis of weights in combination with mining for substructures might yield more precise results. In particular, we study frequent subgraph mining in the presence of weight-based constraints and explain how to integrate them into mining algorithms. While such constraints only yield approximate mining results in most cases, we demonstrate that such results are useful nevertheless and explain this effect. To do so, we both assess the completeness of the approximate result sets, and we carry out application-oriented studies with real-world data-analysis problems: software-defect localization, weighted graph classification and explorative mining in logistics. Our results are that the runtime can improve by a factor of up to 3.5 in defect localization and classification and 7 in explorative mining. At the same time, we obtain an even slightly increased defect-localization precision, stable classification precision and obtain good explorative mining results.