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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Siddiqi, K., Shokoufandeh, A., Dickinson, S., Zucker, S.: Shock graphs and shape matching. International Journal of Computer Vision 35, 13–32 (1999)
Jeong, H., Tombor, B., Albert, R., Oltvai, Z., Barabási, A.: The large-scale organization of metabolic networks. Nature 407, 651–654 (2000)
Ito, T., Chiba, T., Ozawa, R., Yoshida, M., Hattori, M., Sakaki, Y.: A comprehensive two-hybrid analysis to explore the yeast protein interactome. Proceedings of the National Academy of Sciences 98, 4569 (2001)
Kalapala, V., Sanwalani, V., Moore, C.: The structure of the united states road network. University of New Mexico (2003) (preprint)
Schölkopf, B., Smola, A.J.: Learning with kernels: Support vector machines, regularization, optimization, and beyond. MIT Press (2001)
Vapnik, V.: Statistical learning theory (1998)
Gärtner, T., Flach, P.A., Wrobel, S.: On graph kernels: Hardness results and efficient alternatives. In: Schölkopf, B., Warmuth, M.K. (eds.) COLT/Kernel 2003. LNCS (LNAI), vol. 2777, pp. 129–143. Springer, Heidelberg (2003)
Borgwardt, K., Kriegel, H.: Shortest-path kernels on graphs. In: Fifth IEEE International Conference on Data Mining, p. 8. IEEE (2005)
Shervashidze, N., Vishwanathan, S., Petri, T., Mehlhorn, K., Borgwardt, K.: Efficient graphlet kernels for large graph comparison. In: Proceedings of the International Workshop on Artificial Intelligence and Statistics. Society for Artificial Intelligence and Statistics (2009)
Haussler, D.: Convolution kernels on discrete structures. Technical report, UC Santa Cruz (1999)
Bai, L., Hancock, E.: Graph kernels from the Jensen-Shannon divergence. Journal of Mathematical Imaging and Vision, 1–10 (2012)
Farhi, E., Gutmann, S.: Quantum computation and decision trees. Physical Review A 58, 915 (1998)
Kempe, J.: Quantum random walks: an introductory overview. Contemporary Physics 44, 307–327 (2003)
Emms, D., Wilson, R., Hancock, E.: Graph embedding using quantum commute times. Graph-Based Representations in Pattern Recognition, 371–382 (2007)
Rossi, L., Torsello, A., Hancock, E.R.: Approximate axial symmetries from continuous time quantum walks. In: Gimel’farb, G., Hancock, E., Imiya, A., Kuijper, A., Kudo, M., Omachi, S., Windeatt, T., Yamada, K. (eds.) SSPR & SPR 2012. LNCS, vol. 7626, pp. 144–152. Springer, Heidelberg (2012)
Majtey, A., Lamberti, P., Prato, D.: Jensen-Shannon divergence as a measure of distinguishability between mixed quantum states. Physical Review A 72, 052310 (2005)
Lamberti, P., Majtey, A., Borras, A., Casas, M., Plastino, A.: Metric character of the quantum Jensen-Shannon divergence. Physical Review A 77, 052311 (2008)
Nielsen, M., Chuang, I.: Quantum computation and quantum information. Cambridge University Press (2010)
Briët, J., Harremoës, P.: Properties of classical and quantum jensen-shannon divergence. Physical review A 79, 52311 (2009)
Torsello, A., Rossi, L.: Supervised learning of graph structure. Similarity-Based Pattern Recognition, 117–132 (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rossi, L., Torsello, A., Hancock, E.R. (2013). A Continuous-Time Quantum Walk Kernel for Unattributed Graphs. In: Kropatsch, W.G., Artner, N.M., Haxhimusa, Y., Jiang, X. (eds) Graph-Based Representations in Pattern Recognition. GbRPR 2013. Lecture Notes in Computer Science, vol 7877. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38221-5_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-38221-5_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38220-8
Online ISBN: 978-3-642-38221-5
eBook Packages: Computer ScienceComputer Science (R0)