Attributed graph kernels using the Jensen-Tsallis q-differences

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

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

28 Citations (Scopus)


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 - European Conference, ECML PKDD 2014, Proceedings
PublisherSpringer Verlag
Number of pages16
EditionPART 1
ISBN (Print)9783662448472
Publication statusPublished - Sept 2014
Externally publishedYes
EventEuropean Conference on Machine Learning and Knowledge Discovery in Databases, ECML PKDD 2014 - Nancy, France
Duration: 15 Sept 201419 Sept 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume8724 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceEuropean Conference on Machine Learning and Knowledge Discovery in Databases, ECML PKDD 2014


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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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

Cite this