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/Report/Conference proceedingConference contribution

Abstract

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)
PublisherSpringer
Pages252-261
Number of pages10
ISBN (Electronic)978-3-319-18224-7
ISBN (Print)978-3-319-18223-0
DOIs
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
PublisherSpringer
Volume9069
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

Workshop10th IAPR-TC-15 international workshop, GbRPR 2015
CountryChina
CityBeijing
Period13/05/1515/05/15

Fingerprint

divergence

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

Bai, L., Rossi, L., Ren, P., Zhang, Z., & Hancock, E. R. (2015). A quantum Jensen-Shannon graph kernel using discrete-time quantum walks. In C-L. Liu, B. Luo, W. G. Kropatsch, & J. Cheng (Eds.), Graph-based representations in pattern recognition: 10th IAPR-TC-15 international workshop, GbRPR 2015, Beijing, China, May 13-15, 2015. Proceedings (pp. 252-261). (Lecture notes in computer science ; Vol. 9069). Chem (CH): Springer. https://doi.org/10.1007/978-3-319-18224-7_25
Bai, Lu ; Rossi, Luca ; Ren, Peng ; Zhang, Zhihong ; Hancock, Edwin R. / A quantum Jensen-Shannon graph kernel using discrete-time quantum walks. Graph-based representations in pattern recognition: 10th IAPR-TC-15 international workshop, GbRPR 2015, Beijing, China, May 13-15, 2015. Proceedings. editor / Cheng-Lin Liu ; Bin Luo ; Walter G. Kropatsch ; Jian Cheng. Chem (CH) : Springer, 2015. pp. 252-261 (Lecture notes in computer science ).
@inproceedings{8974924ccd5c4977a30fea8d61e5d770,
title = "A quantum Jensen-Shannon graph kernel using discrete-time quantum walks",
abstract = "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.",
author = "Lu Bai and Luca Rossi and Peng Ren and Zhihong Zhang and Hancock, {Edwin R.}",
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",
year = "2015",
doi = "10.1007/978-3-319-18224-7_25",
language = "English",
isbn = "978-3-319-18223-0",
series = "Lecture notes in computer science",
publisher = "Springer",
pages = "252--261",
editor = "Cheng-Lin Liu and Bin Luo and Kropatsch, {Walter G.} and Jian Cheng",
booktitle = "Graph-based representations in pattern recognition",
address = "Germany",

}

Bai, L, Rossi, L, Ren, P, Zhang, Z & Hancock, ER 2015, A quantum Jensen-Shannon graph kernel using discrete-time quantum walks. in C-L Liu, B Luo, WG Kropatsch & J Cheng (eds), Graph-based representations in pattern recognition: 10th IAPR-TC-15 international workshop, GbRPR 2015, Beijing, China, May 13-15, 2015. Proceedings. Lecture notes in computer science , vol. 9069, Springer, Chem (CH), pp. 252-261, 10th IAPR-TC-15 international workshop, GbRPR 2015, Beijing, China, 13/05/15. https://doi.org/10.1007/978-3-319-18224-7_25

A quantum Jensen-Shannon graph kernel using discrete-time quantum walks. / Bai, Lu; Rossi, Luca; Ren, Peng; Zhang, Zhihong; Hancock, Edwin R.

Graph-based representations in pattern recognition: 10th IAPR-TC-15 international workshop, GbRPR 2015, Beijing, China, May 13-15, 2015. Proceedings. ed. / Cheng-Lin Liu; Bin Luo; Walter G. Kropatsch; Jian Cheng. Chem (CH) : Springer, 2015. p. 252-261 (Lecture notes in computer science ; Vol. 9069).

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

TY - GEN

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

AU - Bai, Lu

AU - Rossi, Luca

AU - Ren, Peng

AU - Zhang, Zhihong

AU - Hancock, Edwin R.

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

PY - 2015

Y1 - 2015

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

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

U2 - 10.1007/978-3-319-18224-7_25

DO - 10.1007/978-3-319-18224-7_25

M3 - Conference contribution

SN - 978-3-319-18223-0

T3 - Lecture notes in computer science

SP - 252

EP - 261

BT - Graph-based representations in pattern recognition

A2 - Liu, Cheng-Lin

A2 - Luo, Bin

A2 - Kropatsch, Walter G.

A2 - Cheng, Jian

PB - Springer

CY - Chem (CH)

ER -

Bai L, Rossi L, Ren P, Zhang Z, Hancock ER. A quantum Jensen-Shannon graph kernel using discrete-time quantum walks. In Liu C-L, Luo B, Kropatsch WG, Cheng J, editors, Graph-based representations in pattern recognition: 10th IAPR-TC-15 international workshop, GbRPR 2015, Beijing, China, May 13-15, 2015. Proceedings. Chem (CH): Springer. 2015. p. 252-261. (Lecture notes in computer science ). https://doi.org/10.1007/978-3-319-18224-7_25