Title: Efficient frequent connected induced subgraph mining in graphs of bounded treewidth
Authors: Horvath, Tamas ×
Otaki, Keisuke
Ramon, Jan #
Issue Date: Sep-2013
Publisher: Springer
Series Title: Lecture Notes in Computer Science vol:8188 pages:622-637
Conference: European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD) location:Prague, Czech republic date:23-27 September 2013
Article number: 397
Abstract: Abstract. We study frequent connected induced subgraph mining, i.e.,
the problem of listing all connected graphs that are induced subgraph
isomorphic to at least a certain 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 algo-
rithm 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.
ISSN: 0302-9743
Publication status: published
KU Leuven publication type: IC
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
pkdd13.pdfdraft Published 374KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.