Kernels for Structured Data

• We can use a transformation \(\phi\) to map data space \(R^d\) to a higher dimensional feature space \(R^p\)
• Kernel is a function that implicitly and efficiently calculate inner product in feature space
  • Calculate the inner product without calculate \(\phi\)
  • That means we don’t have to know the explicit analytical form of \(\phi\)
  • Kernel function can be extended to structured data, like string, tree, and graph

\[\kappa(x_i,x_j) = <\phi(x_i),\phi(x_j)^T>\]

String kernel

• 2002, Journal of Machine Learning Research 2, Text Classification using String Kernels
  • String subsequence kernel
    • feature transformation
    • kernel function

Tree kernel

Graph kernel

• The R-convolution Convolution kernels on discrete structures

• Decompose two object into two sets of components, perform pairwise comparison between these components, and summarize to a numeric value

• Graphlet
• Subtree Patterns
  • Weisfeiler-Lehman algorithm
  • Weisfeiler-Lehman
  • 2010, Journal of Machine Learning Research, Weisfeiler-Lehman graph kernels
• Random Walks

Implementations

• graphkit-learn
• GraphKernels
• GraKeL
• EDeN