TY - GEN
T1 - A continuous-time quantum walk kernel for unattributed graphs
AU - Rossi, Luca
AU - Torsello, Andrea
AU - Hancock, Edwin R.
PY - 2013/5
Y1 - 2013/5
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
U2 - 10.1007/978-3-642-38221-5_11
DO - 10.1007/978-3-642-38221-5_11
M3 - Conference article published in proceeding or book
AN - SCOPUS:84883319471
SN - 9783642382208
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 101
EP - 110
BT - Graph-Based Representations in Pattern Recognition - 9th IAPR-TC-15 International Workshop, GbRPR 2013, Proceedings
T2 - 9th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2013
Y2 - 15 May 2013 through 17 May 2013
ER -