On Valid Optimal Assignment Kernels and Applications to Graph Classification

Understand

The success of kernel methods has initiated the design of novel positive semidefinite functions, in particular for structured data.

• A leading design paradigm for this is the convolution kernel, which decomposes structured objects into their parts and sums over all pairs of parts.
• Assignment kernels, in contrast, are obtained from an optimal bijection between parts, which can provide a more valid notion of similarity.
• In general however, optimal assignments yield indefinite functions, which complicates their use in kernel methods.