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

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

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

11 Citations (Scopus)

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 languageEnglish
Title of host publicationGraph-Based Representations in Pattern Recognition - 9th IAPR-TC-15 International Workshop, GbRPR 2013, Proceedings
Pages121-131
Number of pages11
DOIs
Publication statusPublished - May 2013
Externally publishedYes
Event9th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2013 - Vienna, Austria
Duration: 15 May 201317 May 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7877 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2013
Country/TerritoryAustria
CityVienna
Period15/05/1317/05/13

Keywords

  • Continuous-time Quantum Walk
  • Graph Kernels
  • Quantum Jensen-Shannon Divergence

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'A quantum Jensen-Shannon graph kernel using the continuous-time quantum walk'. Together they form a unique fingerprint.

Cite this