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

Original language | English |
---|---|

Title of host publication | Machine Learning and Knowledge Discovery in Databases |

Subtitle of host publication | European Conference, ECML PKDD 2014, Nancy, France, September 15-19, 2014. Proceedings |

Editors | Toon Calders, Floriana Esposito, Eyke Hüllermeier, Rosa Meo |

Place of Publication | Berlin (DE) |

Publisher | Springer |

Pages | 99-114 |

Number of pages | 16 |

ISBN (Electronic) | 978-3-662-44848-9 |

ISBN (Print) | 978-3-662-44847-2 |

DOIs | |

Publication status | Published - 31 Dec 2014 |

Event | European Conference on Machine Learning and Knowledge Discovery in Databases - Nancy, France Duration: 15 Sep 2014 → 19 Sep 2014 |

### Publication series

Name | Lecture notes in computer science |
---|---|

Publisher | Springer |

Volume | 8724 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | European Conference on Machine Learning and Knowledge Discovery in Databases |
---|---|

Abbreviated title | ECML PKDD 2014 |

Country | France |

City | Nancy |

Period | 15/09/14 → 19/09/14 |

### Keywords

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

## Fingerprint Dive into the research topics of 'Attributed graph kernels using the Jensen-Tsallis <i>q-</i>differences'. Together they form a unique fingerprint.

## Cite this

*q-*differences. In T. Calders, F. Esposito, E. Hüllermeier, & R. Meo (Eds.),

*Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2014, Nancy, France, September 15-19, 2014. Proceedings*(pp. 99-114). (Lecture notes in computer science; Vol. 8724). Springer. https://doi.org/10.1007/978-3-662-44848-9_7