A continuous-time quantum walk kernel for unattributed graphs

Luca Rossi, Andrea Torsello, Edwin R. Hancock

Research output: Chapter in Book/Published conference outputConference publication

Abstract

Kernel methods provide a way to apply a wide range of learning techniques to complex and structured data by shifting the representational problem from one of finding an embedding of the data to that of defining a positive semidefinite kernel. In this paper, we propose a novel kernel on unattributed graphs where the structure is characterized through the evolution of a continuous-time quantum walk. More precisely, given a pair of graphs, we create a derived structure whose degree of symmetry is maximum when the original graphs are isomorphic. With this new graph to hand, we compute the density operators of the quantum systems representing the evolutions of two suitably defined quantum walks. Finally, we define the kernel between the two original graphs as the quantum Jensen-Shannon divergence between these two density operators. The experimental evaluation shows 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
Pages101-110
Number of pages10
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
Country/TerritoryAustria
CityWien
Period15/05/1317/05/13

Keywords

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

Fingerprint

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

    Bai, L., Hancock, E. R., Torsello, A. & Rossi, L., 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. 121-131 11 p. (Lecture notes in computer science; vol. 7877).

    Research output: Chapter in Book/Published conference outputConference publication

Cite this