Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Efficient frequent connected induced subgraph mining in graphs of bounded tree-width

: Horváth, T.; Otaki, K.; Ramon, J.


Blockeel, H.:
Machine learning and knowledge discovery in databases. Proceedings Pt. 1 : European conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013
Berlin: Springer, 2013 (Lecture Notes in Computer Science (LNCS) 8188)
ISBN: 978-3-642-40987-5
ISBN: 3-642-40987-3
ISBN: 978-3-642-40988-2
European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD) <2013, Prague>
Fraunhofer IAIS ()

We study the frequent connected induced subgraph mining problem, i.e., the problem of listing all connected graphs that are induced subgraph isomorphic to a given number of transaction graphs. We first show that this problem cannot be solved for arbitrary transaction graphs in output polynomial time (if P NP) and then prove that for graphs of bounded tree-width, frequent connected induced subgraph mining is possible in incremental polynomial time by levelwise search. Our algorithm is an adaptation of the technique developed for frequent connected subgraph mining in bounded tree-width graphs. While the adaptation is relatively natural for many steps of the original algorithm, we need entirely different combinatorial arguments to show the correctness and efficiency of the new algorithm. Since induced subgraph isomorphism between bounded tree-width graphs is NP-complete, the positive result of this paper provides another example of efficient pattern mining with respect to computationally intractable pattern matching operators.