By the same authors

From the same journal

From the same journal

A quantum Jensen-Shannon graph kernel for unattributed graphs

Research output: Contribution to journalArticlepeer-review

Full text download(s)

Published copy (DOI)



Publication details

Journal Pattern Recognition
DateAccepted/In press - 21 Mar 2014
DateE-pub ahead of print (current) - 4 Apr 2014
Issue number2
Number of pages12
Pages (from-to)344-355
Early online date4/04/14
Original languageEnglish


In this paper, we use the quantum Jensen-Shannon divergence as a means of measuring the information theoretic dissimilarity of graphs and thus develop a novel graph kernel. In quantum mechanics, the quantum Jensen-Shannon divergence can be used to measure the dissimilarity of quantum systems specified in terms of their density matrices. We commence by computing the density matrix associated with a continuous-time quantum walk over each graph being compared. In particular, we adopt the closed form solution of the density matrix introduced in Rossi et al. (2013) [27,28] to reduce the computational complexity and to avoid the cumbersome task of simulating the quantum walk evolution explicitly. Next, we compare the mixed states represented by the density matrices using the quantum Jensen-Shannon divergence. With the quantum states for a pair of graphs described by their density matrices to hand, the quantum graph kernel between the pair of graphs is defined using the quantum Jensen-Shannon divergence between the graph density matrices. We evaluate the performance of our kernel on several standard graph datasets from both bioinformatics and computer vision. The experimental results demonstrate the effectiveness of the proposed quantum graph kernel.

Bibliographical note

© 2014, Elsevier. This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details

    Research areas

  • Graph kernels, Continuous-time quantum walk, Quantum state, Quantum Jensen-Shannon divergence

Discover related content

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

View graph of relations