By the same authors

An Attributed Graph Kernel from the Jensen-Shannon Divergence

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Published copy (DOI)



Publication details

Title of host publicationProceedings of the 22nd International Conference on Pattern Recognition
DatePublished - 2014
Number of pages6
PublisherIEEE Computer Society Press
Original languageEnglish


Bai and Hancock recently proposed a novel information theoretic kernel for graphs, namely the Jensen-Shannongraph kernel. One drawback of their approach is that it cannot be applied to either attributed or labeled graphs. In this paper,
we aim to define a new Jensen-Shannon diffusion kernel for attributed graphs. We commence by using a tree-index based
label strengthening method on an attributed graph with the objection of strengthening the vertex labels. We compute a label entropy to measure the uncertainty of the strengthened
labels. With the required label entropies for a pair of graphs to hand, a new kernel for the pair of graphs can be defined by measuring the Jensen-Shannon divergence between the entropies. As the strengthened label of a vertex corresponds to a subtree rooted at the vertex, the label entropy of a graph is determined by all subtrees identified by the tree-index algorithm. As a result, unlike most existing graph kernels in the literature which
merely enumerate pairs of isomorphic substructures, our method incorporates all the identified subtrees into the computation of the kernel. The new kernel thus overcomes the shortcoming of discarding substructures having no corresponding isomorphic substructures. We explore our kernel on several graph datasets abstracted from bioinformatics databases.

    Research areas

  • Accuracy, Biochemistry, Bioinformatics, Entropy, Kernel, Probability distribution, Time complexity

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations