A quantum Jensen-Shannon graph kernel using discrete-time quantum walks

Lu Bai, Luca Rossi, Peng Ren, Zhihong Zhang, Edwin R. Hancock

Research output: Chapter in Book/Published conference outputConference publication


In this paper, we develop a new graph kernel by using the quantum Jensen-Shannon divergence and the discrete-time quantum walk. To this end, we commence by performing a discrete-time quantum walk to compute a density matrix over each graph being compared. For a pair of graphs, we compare the mixed quantum states represented by their density matrices using the quantum Jensen-Shannon divergence. With the density matrices for a pair of graphs to hand, the quantum graph kernel between the pair of graphs is defined by exponentiating the negative quantum Jensen-Shannon divergence between the graph density matrices. We evaluate the performance of our kernel on several standard graph datasets, and demonstrate the effectiveness of the new kernel.
Original languageEnglish
Title of host publicationGraph-based representations in pattern recognition
Subtitle of host publication10th IAPR-TC-15 international workshop, GbRPR 2015, Beijing, China, May 13-15, 2015. Proceedings
EditorsCheng-Lin Liu, Bin Luo, Walter G. Kropatsch, Jian Cheng
Place of PublicationChem (CH)
Number of pages10
ISBN (Electronic)978-3-319-18224-7
ISBN (Print)978-3-319-18223-0
Publication statusPublished - 2015
Event10th IAPR-TC-15 international workshop, GbRPR 2015 - Beijing, China
Duration: 13 May 201515 May 2015

Publication series

NameLecture notes in computer science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Workshop10th IAPR-TC-15 international workshop, GbRPR 2015

Bibliographical note

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-18224-7_25

Funding: UK Royal Society

Cite this