Cyclic pattern kernels revisited

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.