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/5

Y1 - 2013/5

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

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

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

M3 - Conference article published in proceeding or book

AN - SCOPUS:84883316374

SN - 9783642382208

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 121

EP - 131

BT - Graph-Based Representations in Pattern Recognition - 9th IAPR-TC-15 International Workshop, GbRPR 2013, Proceedings

T2 - 9th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2013

Y2 - 15 May 2013 through 17 May 2013

ER -