A continuous-time quantum walk kernel for unattributed graphs

Luca Rossi; Andrea Torsello; Edwin R. Hancock

doi:10.1007/978-3-642-38221-5_11

A continuous-time quantum walk kernel for unattributed graphs

Luca Rossi, Andrea Torsello, Edwin R. Hancock

College of Engineering and Physical Sciences

Research output: Chapter in Book/Published conference output › Conference 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 language	English
Title of host publication	Graph-Based Representations in Pattern Recognition
Subtitle of host publication	9th IAPR-TC-15 international workshop, GbRPR 2013, Vienna, Austria, May 15-17, 2013. Proceedings
Editors	Walter G. Kropatsch, Nicole M. Artner, Yll Haxhimusa, Xiaoyi Jiang
Place of Publication	Berlin (DE)
Publisher	Springer
Pages	101-110
Number of pages	10
ISBN (Electronic)	978-3-642-38221-5
ISBN (Print)	978-3-642-38220-8
DOIs	https://doi.org/10.1007/978-3-642-38221-5_11
Publication status	Published - 2013
Event	9th IAPR-TC15 workshop on Graph-based Representations in pattern recognition - Wien, Austria Duration: 15 May 2013 → 17 May 2013

Publication series

Name	Lecture notes in computer science
Publisher	Springer
Volume	7877
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Workshop

Workshop	9th IAPR-TC15 workshop on Graph-based Representations in pattern recognition
Abbreviated title	GbR 2013
Country/Territory	Austria
City	Wien
Period	15/05/13 → 17/05/13

Keywords

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

Access to Document

10.1007/978-3-642-38221-5_11

Cite this

Rossi, L., Torsello, A., & Hancock, E. R. (2013). A continuous-time quantum walk kernel for unattributed graphs. In W. G. Kropatsch, N. M. Artner, Y. Haxhimusa, & X. Jiang (Eds.), Graph-Based Representations in Pattern Recognition: 9th IAPR-TC-15 international workshop, GbRPR 2013, Vienna, Austria, May 15-17, 2013. Proceedings (pp. 101-110). (Lecture notes in computer science; Vol. 7877). Springer. https://doi.org/10.1007/978-3-642-38221-5_11

Rossi, Luca ; Torsello, Andrea ; Hancock, Edwin R. / A continuous-time quantum walk kernel for unattributed graphs. Graph-Based Representations in Pattern Recognition: 9th IAPR-TC-15 international workshop, GbRPR 2013, Vienna, Austria, May 15-17, 2013. Proceedings. editor / Walter G. Kropatsch ; Nicole M. Artner ; Yll Haxhimusa ; Xiaoyi Jiang. Berlin (DE) : Springer, 2013. pp. 101-110 (Lecture notes in computer science).

@inproceedings{39fc794bebc94342b375720555559479,

title = "A continuous-time quantum walk kernel for unattributed graphs",

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.",

keywords = "continuous-time quantum walk, graph classification, graph kernels, quantum Jensen-Shannon divergence",

author = "Luca Rossi and Andrea Torsello and Hancock, {Edwin R.}",

year = "2013",

doi = "10.1007/978-3-642-38221-5_11",

language = "English",

isbn = "978-3-642-38220-8",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "101--110",

editor = "Kropatsch, {Walter G.} and Artner, {Nicole M.} and Yll Haxhimusa and Xiaoyi Jiang",

booktitle = "Graph-Based Representations in Pattern Recognition",

address = "Germany",

note = "9th IAPR-TC15 workshop on Graph-based Representations in pattern recognition, GbR 2013 ; Conference date: 15-05-2013 Through 17-05-2013",

}

Rossi, L, Torsello, A & Hancock, ER 2013, A continuous-time quantum walk kernel for unattributed graphs. in WG Kropatsch, NM Artner, Y Haxhimusa & X Jiang (eds), Graph-Based Representations in Pattern Recognition: 9th IAPR-TC-15 international workshop, GbRPR 2013, Vienna, Austria, May 15-17, 2013. Proceedings. Lecture notes in computer science, vol. 7877, Springer, Berlin (DE), pp. 101-110, 9th IAPR-TC15 workshop on Graph-based Representations in pattern recognition, Wien, Austria, 15/05/13. https://doi.org/10.1007/978-3-642-38221-5_11

A continuous-time quantum walk kernel for unattributed graphs. / Rossi, Luca; Torsello, Andrea; Hancock, Edwin R.
Graph-Based Representations in Pattern Recognition: 9th IAPR-TC-15 international workshop, GbRPR 2013, Vienna, Austria, May 15-17, 2013. Proceedings. ed. / Walter G. Kropatsch; Nicole M. Artner; Yll Haxhimusa; Xiaoyi Jiang. Berlin (DE): Springer, 2013. p. 101-110 (Lecture notes in computer science; Vol. 7877).

Research output: Chapter in Book/Published conference output › Conference publication

TY - GEN

T1 - A continuous-time quantum walk kernel for unattributed graphs

AU - Rossi, Luca

AU - Torsello, Andrea

AU - Hancock, Edwin R.

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - continuous-time quantum walk

KW - graph classification

KW - graph kernels

KW - quantum Jensen-Shannon divergence

UR - http://www.scopus.com/inward/record.url?scp=84883319471&partnerID=8YFLogxK

UR - http://link.springer.com/chapter/10.1007%2F978-3-642-38221-5_11

U2 - 10.1007/978-3-642-38221-5_11

DO - 10.1007/978-3-642-38221-5_11

M3 - Conference publication

AN - SCOPUS:84883319471

SN - 978-3-642-38220-8

T3 - Lecture notes in computer science

SP - 101

EP - 110

BT - Graph-Based Representations in Pattern Recognition

A2 - Kropatsch, Walter G.

A2 - Artner, Nicole M.

A2 - Haxhimusa, Yll

A2 - Jiang, Xiaoyi

PB - Springer

CY - Berlin (DE)

T2 - 9th IAPR-TC15 workshop on Graph-based Representations in pattern recognition

Y2 - 15 May 2013 through 17 May 2013

ER -

Rossi L, Torsello A, Hancock ER. A continuous-time quantum walk kernel for unattributed graphs. In Kropatsch WG, Artner NM, Haxhimusa Y, Jiang X, editors, Graph-Based Representations in Pattern Recognition: 9th IAPR-TC-15 international workshop, GbRPR 2013, Vienna, Austria, May 15-17, 2013. Proceedings. Berlin (DE): Springer. 2013. p. 101-110. (Lecture notes in computer science). doi: 10.1007/978-3-642-38221-5_11

A continuous-time quantum walk kernel for unattributed graphs

Abstract

Publication series

Workshop

Keywords

Access to Document

Other files and links

Fingerprint

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

Cite this