Attributed graph kernels using the Jensen-Tsallis q-differences

Lu Bai, Luca Rossi, Horst Bunke, Edwin R. Hancock

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We propose a family of attributed graph kernels based on mutual information measures, i.e., the Jensen-Tsallis (JT) q-differences (for q  ∈ [1,2]) between probability distributions over the graphs. To this end, we first assign a probability to each vertex of the graph through a continuous-time quantum walk (CTQW). We then adopt the tree-index approach [1] to strengthen the original vertex labels, and we show how the CTQW can induce a probability distribution over these strengthened labels. We show that our JT kernel (for q  = 1) overcomes the shortcoming of discarding non-isomorphic substructures arising in the R-convolution kernels. Moreover, we prove that the proposed JT kernels generalize the Jensen-Shannon graph kernel [2] (for q = 1) and the classical subtree kernel [3] (for q = 2), respectively. Experimental evaluations demonstrate the effectiveness and efficiency of the JT kernels.

Original languageEnglish
Title of host publicationMachine Learning and Knowledge Discovery in Databases
Subtitle of host publicationEuropean Conference, ECML PKDD 2014, Nancy, France, September 15-19, 2014. Proceedings
EditorsToon Calders, Floriana Esposito, Eyke Hüllermeier, Rosa Meo
Place of PublicationBerlin (DE)
PublisherSpringer
Pages99-114
Number of pages16
ISBN (Electronic)978-3-662-44848-9
ISBN (Print)978-3-662-44847-2
DOIs
Publication statusPublished - 31 Dec 2014
EventEuropean Conference on Machine Learning and Knowledge Discovery in Databases - Nancy, France
Duration: 15 Sep 201419 Sep 2014

Publication series

NameLecture notes in computer science
PublisherSpringer
Volume8724
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceEuropean Conference on Machine Learning and Knowledge Discovery in Databases
Abbreviated titleECML PKDD 2014
CountryFrance
CityNancy
Period15/09/1419/09/14

Keywords

  • continuous-time quantum walk
  • Graph kernels
  • Jensen-Tsallis q-differences
  • tree-index method

Fingerprint Dive into the research topics of 'Attributed graph kernels using the Jensen-Tsallis <i>q-</i>differences'. Together they form a unique fingerprint.

  • Cite this

    Bai, L., Rossi, L., Bunke, H., & Hancock, E. R. (2014). Attributed graph kernels using the Jensen-Tsallis q-differences. In T. Calders, F. Esposito, E. Hüllermeier, & R. Meo (Eds.), Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2014, Nancy, France, September 15-19, 2014. Proceedings (pp. 99-114). (Lecture notes in computer science; Vol. 8724). Springer. https://doi.org/10.1007/978-3-662-44848-9_7