Random walk graph kernels and rational kernels

Random walk graph kernels (Gartner et al., 2003 [5]; Borgwardt et al., 2005 [1]) count matching random walks, and are defined using the tensor product graph. Loosely speaking, rational kernels (Cortes et al., 2004, 2003, 2002 [4, 3, 2]) use the weight assigned by a transducer to define a kernel. The kernel is shown to be positive semi-definite when the transducer can be written as a composition of two identical transducers. In our talk we will establish explicit connections between random walk graph kernels and rational kernels. More concretely, we show that composition of transducers is analogous to computing product graphs, and that rational kernels on weighted transducers may be viewed as generalizations of random walk kernels to weighted automata. In order to make these connections explicit we adapt slightly non-standard notation for weighted transducers, extensively using matrices and tensors wherever possible. We prove that under certain conditions rational kernels are positive semi-definite. Our proof only uses basic linear algebra and is simpler than the one presented in Cortes et al., 2004[4].