Measuring the expressivity of graph kernels through Statistical Learning Theory

作者：Oneto Luca^*; Navarin Nicolo; Donini Michele; Sperduti Alessandro; Aiolli Fabio; Anguita Davide

来源：Neurocomputing, 2017, 268: 4-16.

DOI：10.1016/j.neucom.2017.02.088

• Kernel
• Structured domain
• Expressivity
• Graph kernels
• Statistical Learning Theory
• Rademacher Complexity
• Local Rademacher Complexity
• Algorithmic Stability

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.

• 出版日期2017-12-13