Measuring the expressivity of graph kernels through Statistical Learning Theory

Kernels for structured domains are widely adopted in real-world applications that involve learning on structured data. In this context many kernels have been proposed in literature, but no theoretical comparison among them is present. In this paper we provide different formal definitions of expressiveness of a kernel by exploiting the most recent results in the field of Statistical Learning Theory, and analyze the differences among some state-of-the-art graph kernels. Results on real world datasets confirm some known properties of graph kernels, showing that Statistical Learning Theory is indeed a powerful and practical tool able to perform this analysis.