A quantum Jensen-Shannon graph kernel using the continuous-time quantum walk

Lu Bai; Edwin R. Hancock; Andrea Torsello; Luca Rossi

doi:10.1007/978-3-642-38221-5_13

A quantum Jensen-Shannon graph kernel using the continuous-time quantum walk

Lu Bai, Edwin R. Hancock, Andrea Torsello, Luca Rossi

College of Engineering and Physical Sciences

Research output: Chapter in Book/Published conference output › Conference publication

Abstract

In this paper, we use the quantum Jensen-Shannon divergence as a means to establish the similarity between a pair of graphs and to develop a novel graph kernel. In quantum theory, the quantum Jensen-Shannon divergence is defined as a distance measure between quantum states. In order to compute the quantum Jensen-Shannon divergence between a pair of graphs, we first need to associate a density operator with each of them. Hence, we decide to simulate the evolution of a continuous-time quantum walk on each graph and we propose a way to associate a suitable quantum state with it. With the density operator of this quantum state to hand, the graph kernel is defined as a function of the quantum Jensen-Shannon divergence between the graph density operators. We evaluate the performance of our kernel on several standard graph datasets from bioinformatics. We use the Principle Component Analysis (PCA) on the kernel matrix to embed the graphs into a feature space for classification. The experimental results demonstrate the effectiveness of the proposed approach.

Original language	English
Title of host publication	Graph-Based Representations in Pattern Recognition
Subtitle of host publication	9th IAPR-TC-15 international workshop, GbRPR 2013, Vienna, Austria, May 15-17, 2013. Proceedings
Editors	Walter G. Kropatsch, Nicole M. Artner, Yll Haxhimusa, Xiaoyi Jiang
Place of Publication	Berlin (DE)
Publisher	Springer
Pages	121-131
Number of pages	11
ISBN (Electronic)	978-3-642-38221-5
ISBN (Print)	978-3-642-38220-8
DOIs	https://doi.org/10.1007/978-3-642-38221-5_13
Publication status	Published - 2013
Event	9th IAPR-TC15 workshop on Graph-based Representations in pattern recognition - Wien, Austria Duration: 15 May 2013 → 17 May 2013

Publication series

Name	Lecture notes in computer science
Publisher	Springer
Volume	7877
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Workshop

Workshop	9th IAPR-TC15 workshop on Graph-based Representations in pattern recognition
Abbreviated title	GbR 2013
Country/Territory	Austria
City	Wien
Period	15/05/13 → 17/05/13

Keywords

continuous-time quantum walk
graph kernels
quantum Jensen-Shannon divergence

Access to Document

10.1007/978-3-642-38221-5_13

Cite this

Bai, L., Hancock, E. R., Torsello, A., & Rossi, L. (2013). A quantum Jensen-Shannon graph kernel using the continuous-time quantum walk. In W. G. Kropatsch, N. M. Artner, Y. Haxhimusa, & X. Jiang (Eds.), Graph-Based Representations in Pattern Recognition: 9th IAPR-TC-15 international workshop, GbRPR 2013, Vienna, Austria, May 15-17, 2013. Proceedings (pp. 121-131). (Lecture notes in computer science; Vol. 7877). Springer. https://doi.org/10.1007/978-3-642-38221-5_13

Bai, Lu ; Hancock, Edwin R. ; Torsello, Andrea et al. / A quantum Jensen-Shannon graph kernel using the continuous-time quantum walk. Graph-Based Representations in Pattern Recognition: 9th IAPR-TC-15 international workshop, GbRPR 2013, Vienna, Austria, May 15-17, 2013. Proceedings. editor / Walter G. Kropatsch ; Nicole M. Artner ; Yll Haxhimusa ; Xiaoyi Jiang. Berlin (DE) : Springer, 2013. pp. 121-131 (Lecture notes in computer science).

@inproceedings{e7371123c0bf42548402cdbcd1f72f48,

title = "A quantum Jensen-Shannon graph kernel using the continuous-time quantum walk",

abstract = "In this paper, we use the quantum Jensen-Shannon divergence as a means to establish the similarity between a pair of graphs and to develop a novel graph kernel. In quantum theory, the quantum Jensen-Shannon divergence is defined as a distance measure between quantum states. In order to compute the quantum Jensen-Shannon divergence between a pair of graphs, we first need to associate a density operator with each of them. Hence, we decide to simulate the evolution of a continuous-time quantum walk on each graph and we propose a way to associate a suitable quantum state with it. With the density operator of this quantum state to hand, the graph kernel is defined as a function of the quantum Jensen-Shannon divergence between the graph density operators. We evaluate the performance of our kernel on several standard graph datasets from bioinformatics. We use the Principle Component Analysis (PCA) on the kernel matrix to embed the graphs into a feature space for classification. The experimental results demonstrate the effectiveness of the proposed approach.",

keywords = "continuous-time quantum walk, graph kernels, quantum Jensen-Shannon divergence",

author = "Lu Bai and Hancock, {Edwin R.} and Andrea Torsello and Luca Rossi",

year = "2013",

doi = "10.1007/978-3-642-38221-5_13",

language = "English",

isbn = "978-3-642-38220-8",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "121--131",

editor = "Kropatsch, {Walter G.} and Artner, {Nicole M.} and Yll Haxhimusa and Xiaoyi Jiang",

booktitle = "Graph-Based Representations in Pattern Recognition",

address = "Germany",

note = "9th IAPR-TC15 workshop on Graph-based Representations in pattern recognition, GbR 2013 ; Conference date: 15-05-2013 Through 17-05-2013",

}

Bai, L, Hancock, ER, Torsello, A & Rossi, L 2013, A quantum Jensen-Shannon graph kernel using the continuous-time quantum walk. in WG Kropatsch, NM Artner, Y Haxhimusa & X Jiang (eds), Graph-Based Representations in Pattern Recognition: 9th IAPR-TC-15 international workshop, GbRPR 2013, Vienna, Austria, May 15-17, 2013. Proceedings. Lecture notes in computer science, vol. 7877, Springer, Berlin (DE), pp. 121-131, 9th IAPR-TC15 workshop on Graph-based Representations in pattern recognition, Wien, Austria, 15/05/13. https://doi.org/10.1007/978-3-642-38221-5_13

A quantum Jensen-Shannon graph kernel using the continuous-time quantum walk. / Bai, Lu; Hancock, Edwin R.; Torsello, Andrea et al.
Graph-Based Representations in Pattern Recognition: 9th IAPR-TC-15 international workshop, GbRPR 2013, Vienna, Austria, May 15-17, 2013. Proceedings. ed. / Walter G. Kropatsch; Nicole M. Artner; Yll Haxhimusa; Xiaoyi Jiang. Berlin (DE): Springer, 2013. p. 121-131 (Lecture notes in computer science; Vol. 7877).

Research output: Chapter in Book/Published conference output › Conference publication

TY - GEN

T1 - A quantum Jensen-Shannon graph kernel using the continuous-time quantum walk

AU - Bai, Lu

AU - Hancock, Edwin R.

AU - Torsello, Andrea

AU - Rossi, Luca

PY - 2013

Y1 - 2013

N2 - In this paper, we use the quantum Jensen-Shannon divergence as a means to establish the similarity between a pair of graphs and to develop a novel graph kernel. In quantum theory, the quantum Jensen-Shannon divergence is defined as a distance measure between quantum states. In order to compute the quantum Jensen-Shannon divergence between a pair of graphs, we first need to associate a density operator with each of them. Hence, we decide to simulate the evolution of a continuous-time quantum walk on each graph and we propose a way to associate a suitable quantum state with it. With the density operator of this quantum state to hand, the graph kernel is defined as a function of the quantum Jensen-Shannon divergence between the graph density operators. We evaluate the performance of our kernel on several standard graph datasets from bioinformatics. We use the Principle Component Analysis (PCA) on the kernel matrix to embed the graphs into a feature space for classification. The experimental results demonstrate the effectiveness of the proposed approach.

AB - In this paper, we use the quantum Jensen-Shannon divergence as a means to establish the similarity between a pair of graphs and to develop a novel graph kernel. In quantum theory, the quantum Jensen-Shannon divergence is defined as a distance measure between quantum states. In order to compute the quantum Jensen-Shannon divergence between a pair of graphs, we first need to associate a density operator with each of them. Hence, we decide to simulate the evolution of a continuous-time quantum walk on each graph and we propose a way to associate a suitable quantum state with it. With the density operator of this quantum state to hand, the graph kernel is defined as a function of the quantum Jensen-Shannon divergence between the graph density operators. We evaluate the performance of our kernel on several standard graph datasets from bioinformatics. We use the Principle Component Analysis (PCA) on the kernel matrix to embed the graphs into a feature space for classification. The experimental results demonstrate the effectiveness of the proposed approach.

KW - continuous-time quantum walk

KW - graph kernels

KW - quantum Jensen-Shannon divergence

UR - http://www.scopus.com/inward/record.url?scp=84883316374&partnerID=8YFLogxK

UR - http://link.springer.com/chapter/10.1007%2F978-3-642-38221-5_13

U2 - 10.1007/978-3-642-38221-5_13

DO - 10.1007/978-3-642-38221-5_13

M3 - Conference publication

AN - SCOPUS:84883316374

SN - 978-3-642-38220-8

T3 - Lecture notes in computer science

SP - 121

EP - 131

BT - Graph-Based Representations in Pattern Recognition

A2 - Kropatsch, Walter G.

A2 - Artner, Nicole M.

A2 - Haxhimusa, Yll

A2 - Jiang, Xiaoyi

PB - Springer

CY - Berlin (DE)

T2 - 9th IAPR-TC15 workshop on Graph-based Representations in pattern recognition

Y2 - 15 May 2013 through 17 May 2013

ER -

Bai L, Hancock ER, Torsello A, Rossi L. A quantum Jensen-Shannon graph kernel using the continuous-time quantum walk. In Kropatsch WG, Artner NM, Haxhimusa Y, Jiang X, editors, Graph-Based Representations in Pattern Recognition: 9th IAPR-TC-15 international workshop, GbRPR 2013, Vienna, Austria, May 15-17, 2013. Proceedings. Berlin (DE): Springer. 2013. p. 121-131. (Lecture notes in computer science). doi: 10.1007/978-3-642-38221-5_13

A quantum Jensen-Shannon graph kernel using the continuous-time quantum walk

Abstract

Publication series

Workshop

Keywords

Access to Document

Other files and links

Fingerprint

A continuous-time quantum walk kernel for unattributed graphs

Cite this