Attributed graph kernels using the Jensen-Tsallis q-differences

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

Research output: Chapter in Book/Published conference outputConference publication


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)
Number of pages16
ISBN (Electronic)978-3-662-44848-9
ISBN (Print)978-3-662-44847-2
Publication statusPublished - 31 Dec 2014
EventEuropean Conference on Machine Learning and Knowledge Discovery in Databases - Nancy, France
Duration: 15 Sept 201419 Sept 2014

Publication series

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


ConferenceEuropean Conference on Machine Learning and Knowledge Discovery in Databases
Abbreviated titleECML PKDD 2014


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


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

Cite this