Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Cyclic pattern kernels revisited

 
: Horváth, T.

Ho, T.B.:
Advances in knowledge discovery and data mining : 9th Pacific-Asia conference, PAKDD 2005, Hanoi, Vietnam, May 18 - 20, 2005. Proceedings
Berlin: Springer, 2005 (Lecture Notes in Artificial Intelligence 3518)
ISBN: 3-540-26076-5
ISBN: 978-3-540-26076-9
pp.791-801
Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD) <9, 2005, Hanoi>
English
Conference Paper
Fraunhofer AIS ( IAIS) ()
data mining; graph mining; algorithm

Abstract
The cyclic pattern kernel (CPK) is a powerful graph kernel based on patterns formed by simple cycles of labeled graphs. In a recent work, we proposed a method for computing CPK which is restricted to graphs containing polynomial number of simple cycles. In this work, we present two approaches relaxing this limitation. We first show that for graphs of bounded treewidth, CPK can be computed in time polynomial in the number of cyclic patterns, which in turn can be exponentially smaller than that of simple cycles. We then propose an alternative CPK based on the set of relevant cycles which is known to be enumerable with polynomial delay and its cardinality is typically only cubic in the number of vertices. Empirical results on the NCI-HIV dataset indicate that there is no significant difference in predictive performance between CPK based on simple cycles and that based on relevant cycles.

: http://publica.fraunhofer.de/documents/N-28897.html