Efficient frequent connected subgraph mining in graphs of bounded tree-width
T. Horvath, and J. Ramon.. Proceedings of LWA2010 - Workshop-Woche: Lernen, Wissen & Adaptivitaet, Kassel, Germany, (2010)
Abstract
The frequent connected subgraph mining problem, i.e., the problem of listing all connected graphs that are subgraph isomorphic to at least a certain number of transaction graphs of a database, cannot be solved in output polynomial time in the general case. If, however, the transaction graphs are restricted to forests then the problem becomes tractable. In this paper we generalize the positive result on forests to graphs of bounded tree-width. In particular, we show that for this class of transaction graphs, frequent connected subgraphs can be listed in incremental polynomial time. Since subgraph isomorphism remains NP-complete for bounded treewidth graphs, the positive complexity result of this paper shows that efficient frequent pattern mining is possible even for computationally hard pattern matching operators.
%0 Conference Paper
%1 kdml25
%A Horvath, Tamas
%A Ramon., Jan
%B Proceedings of LWA2010 - Workshop-Woche: Lernen, Wissen & Adaptivitaet
%C Kassel, Germany
%D 2010
%E Atzmüller, Martin
%E Benz, Dominik
%E Hotho, Andreas
%E Stumme, Gerd
%K complexity data graph mining room:0446 session:kdml4 workshop:kdml
%T Efficient frequent connected subgraph mining in graphs of bounded tree-width
%U http://www.kde.cs.uni-kassel.de/conf/lwa10/papers/kdml25.pdf
%X The frequent connected subgraph mining problem, i.e., the problem of listing all connected graphs that are subgraph isomorphic to at least a certain number of transaction graphs of a database, cannot be solved in output polynomial time in the general case. If, however, the transaction graphs are restricted to forests then the problem becomes tractable. In this paper we generalize the positive result on forests to graphs of bounded tree-width. In particular, we show that for this class of transaction graphs, frequent connected subgraphs can be listed in incremental polynomial time. Since subgraph isomorphism remains NP-complete for bounded treewidth graphs, the positive complexity result of this paper shows that efficient frequent pattern mining is possible even for computationally hard pattern matching operators.
@inproceedings{kdml25,
abstract = {The frequent connected subgraph mining problem, i.e., the problem of listing all connected graphs that are subgraph isomorphic to at least a certain number of transaction graphs of a database, cannot be solved in output polynomial time in the general case. If, however, the transaction graphs are restricted to forests then the problem becomes tractable. In this paper we generalize the positive result on forests to graphs of bounded tree-width. In particular, we show that for this class of transaction graphs, frequent connected subgraphs can be listed in incremental polynomial time. Since subgraph isomorphism remains NP-complete for bounded treewidth graphs, the positive complexity result of this paper shows that efficient frequent pattern mining is possible even for computationally hard pattern matching operators.},
added-at = {2010-10-05T14:15:12.000+0200},
address = {Kassel, Germany},
author = {Horvath, Tamas and Ramon., Jan},
biburl = {https://www.bibsonomy.org/bibtex/22d9797b3dffbff363a8fc77d1147b0f2/lwa2010},
booktitle = {Proceedings of LWA2010 - Workshop-Woche: Lernen, Wissen {\&} Adaptivitaet},
crossref = {lwa2010},
editor = {Atzmüller, Martin and Benz, Dominik and Hotho, Andreas and Stumme, Gerd},
interhash = {56e9f18ad756600d7e6d8f8386d0ed57},
intrahash = {2d9797b3dffbff363a8fc77d1147b0f2},
keywords = {complexity data graph mining room:0446 session:kdml4 workshop:kdml},
presentation_end = {2010-10-06 11:30:00},
presentation_start = {2010-10-06 11:07:30},
room = {0446},
session = {kdml4},
timestamp = {2010-10-05T14:15:13.000+0200},
title = {Efficient frequent connected subgraph mining in graphs of bounded tree-width},
track = {kdml},
url = {http://www.kde.cs.uni-kassel.de/conf/lwa10/papers/kdml25.pdf},
year = 2010
}