TY - GEN

T1 - Attributed graph kernels using the Jensen-Tsallis q-differences

AU - Bai, Lu

AU - Rossi, Luca

AU - Bunke, Horst

AU - Hancock, Edwin R.

PY - 2014/9

Y1 - 2014/9

N2 - 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.

AB - 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.

KW - continuous-time quantum walk

KW - Graph kernels

KW - Jensen-Tsallis q-differences

KW - tree-index method

UR - http://www.scopus.com/inward/record.url?scp=84907007930&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-44848-9_7

DO - 10.1007/978-3-662-44848-9_7

M3 - Conference article published in proceeding or book

AN - SCOPUS:84907007930

SN - 9783662448472

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 99

EP - 114

BT - Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2014, Proceedings

PB - Springer Verlag

T2 - European Conference on Machine Learning and Knowledge Discovery in Databases, ECML PKDD 2014

Y2 - 15 September 2014 through 19 September 2014

ER -