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.

Measuring the expressivity of graph kernels through Statistical Learning Theory

Oneto, Luca;
2017-01-01

Abstract

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
Oneto, Luca; Navarin, Nicolã²; Donini, Michele; Sperduti, Alessandro; Aiolli, Fabio; Anguita, Davide
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/996674
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? ND
social impact