Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. Cyclic pattern kernels revisited
 Ho, T.B.: Advances in knowledge discovery and data mining : 9th PacificAsia conference, PAKDD 2005, Hanoi, Vietnam, May 18  20, 2005. Proceedings Berlin: Springer, 2005 (Lecture Notes in Artificial Intelligence 3518) ISBN: 3540260765 ISBN: 9783540260769 pp.791801 
 PacificAsia 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 NCIHIV dataset indicate that there is no significant difference in predictive performance between CPK based on simple cycles and that based on relevant cycles.