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/Published conference outputConference 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 languageEnglish
Title of host publicationGraph-Based Representations in Pattern Recognition
Subtitle of host publication9th IAPR-TC-15 international workshop, GbRPR 2013, Vienna, Austria, May 15-17, 2013. Proceedings
EditorsWalter G. Kropatsch, Nicole M. Artner, Yll Haxhimusa, Xiaoyi Jiang
Place of PublicationBerlin (DE)
PublisherSpringer
Pages121-131
Number of pages11
ISBN (Electronic)978-3-642-38221-5
ISBN (Print)978-3-642-38220-8
DOIs
Publication statusPublished - 2013
Event9th IAPR-TC15 workshop on Graph-based Representations in pattern recognition - Wien, Austria
Duration: 15 May 201317 May 2013

Publication series

NameLecture notes in computer science
PublisherSpringer
Volume7877
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

Workshop9th IAPR-TC15 workshop on Graph-based Representations in pattern recognition
Abbreviated titleGbR 2013
CountryAustria
CityWien
Period15/05/1317/05/13

Keywords

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

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.
  • A continuous-time quantum walk kernel for unattributed graphs

    Rossi, L., Torsello, A. & Hancock, E. R., 2013, Graph-Based Representations in Pattern Recognition: 9th IAPR-TC-15 international workshop, GbRPR 2013, Vienna, Austria, May 15-17, 2013. Proceedings. Kropatsch, W. G., Artner, N. M., Haxhimusa, Y. & Jiang, X. (eds.). Berlin (DE): Springer, p. 101-110 10 p. (Lecture notes in computer science; vol. 7877).

    Research output: Chapter in Book/Published conference outputConference publication

Cite this