Attributed Graph Kernels Using the Jensen-Tsallis Q-Differences
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.
Cite
Text
Bai et al. "Attributed Graph Kernels Using the Jensen-Tsallis Q-Differences." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2014. doi:10.1007/978-3-662-44848-9_7Markdown
[Bai et al. "Attributed Graph Kernels Using the Jensen-Tsallis Q-Differences." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2014.](https://mlanthology.org/ecmlpkdd/2014/bai2014ecmlpkdd-attributed/) doi:10.1007/978-3-662-44848-9_7BibTeX
@inproceedings{bai2014ecmlpkdd-attributed,
title = {{Attributed Graph Kernels Using the Jensen-Tsallis Q-Differences}},
author = {Bai, Lu and Rossi, Luca and Bunke, Horst and Hancock, Edwin R.},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2014},
pages = {99-114},
doi = {10.1007/978-3-662-44848-9_7},
url = {https://mlanthology.org/ecmlpkdd/2014/bai2014ecmlpkdd-attributed/}
}