Material Detail

Random walk graph kernels and rational kernels

Random walk graph kernels and rational kernels

This video was recorded at 6th Slovenian International Conference on Graph Theory, Bled 2007. 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... Show More


  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material


Log in to participate in the discussions or sign up if you are not already a MERLOT member.