Random walk graph kernels and rational kernels

author: S.V.N. Vishwanathan, Department of Computer Science, University of California Santa Cruz
published: Sept. 7, 2007,   recorded: September 2007,   views: 8658

Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


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].

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: