  Motivated by chemical applications, we revisit and extend a family of
positive definite kernels for graphs based on the detection of common subtrees,
initially proposed by Ramon et al. (2003). We propose new kernels with a
parameter to control the complexity of the subtrees used as features to
represent the graphs. This parameter allows to smoothly interpolate between
classical graph kernels based on the count of common walks, on the one hand,
and kernels that emphasize the detection of large common subtrees, on the other
hand. We also propose two modular extensions to this formulation. The first
extension increases the number of subtrees that define the feature space, and
the second one removes noisy features from the graph representations. We
validate experimentally these new kernels on binary classification tasks
consisting in discriminating toxic and non-toxic molecules with support vector
machines.
