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 -