A continuous-time quantum walk kernel for unattributed graphs

Luca Rossi, Andrea Torsello, Edwin R. Hancock

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

15 Citations (Scopus)

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 - 9th IAPR-TC-15 International Workshop, GbRPR 2013, Proceedings
Pages101-110
Number of pages10
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 Classification
  • Graph Kernels
  • Quantum Jensen-Shannon Divergence

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

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

Cite this