Attributed graph kernels using the Jensen-Tsallis q-differences

Bai, Lu, Rossi, Luca, Bunke, Horst and Hancock, Edwin R. (2014). Attributed graph kernels using the Jensen-Tsallis q-differences. IN: Machine Learning and Knowledge Discovery in Databases. Calders, Toon; Esposito, Floriana; Hüllermeier, Eyke and Meo, Rosa (eds) Lecture notes in computer science . Berlin (DE): Springer.


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.

Publication DOI:
Divisions: Engineering & Applied Sciences
Event Title: European Conference on Machine Learning and Knowledge Discovery in Databases
Event Type: Other
Event Dates: 2014-09-15 - 2014-09-19
Uncontrolled Keywords: continuous-time quantum walk,Graph kernels,Jensen-Tsallis q-differences,tree-index method,Computer Science(all),Theoretical Computer Science
Full Text Link:
Related URLs:
Published Date: 2014
Authors: Bai, Lu
Rossi, Luca
Bunke, Horst
Hancock, Edwin R.


Item under embargo

Export / Share Citation


Additional statistics for this record