Abstract
In this paper, we use the quantum Jensen-Shannon divergence as a means to establish the similarity between a pair of graphs and to develop a novel graph kernel. In quantum theory, the quantum Jensen-Shannon divergence is defined as a distance measure between quantum states. In order to compute the quantum Jensen-Shannon divergence between a pair of graphs, we first need to associate a density operator with each of them. Hence, we decide to simulate the evolution of a continuous-time quantum walk on each graph and we propose a way to associate a suitable quantum state with it. With the density operator of this quantum state to hand, the graph kernel is defined as a function of the quantum Jensen-Shannon divergence between the graph density operators. We evaluate the performance of our kernel on several standard graph datasets from bioinformatics. We use the Principle Component Analysis (PCA) on the kernel matrix to embed the graphs into a feature space for classification. The experimental results demonstrate the effectiveness of the proposed approach.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsPreview
Unable to display preview. Download preview PDF.
References
Schölkopf, B., Smola, A.: Learning with Kernels. MIT Press (2002)
Haussler, D.: Convolution kernels on discrete structures. Technical Report UCS-CRL-99-10, Santa Cruz, CA, USA (1999)
Kashima, H., Tsuda, K., Inokuchi, A.: Marginalized kernels between labeled graphs. In: Proceedings of International Conference on Machine Learning, pp. 321–328 (2003)
Borgwardt, K.M., Kriegel, H.P.: Shortest-path kernels on graphs. In: Proceedings of the IEEE International Conference on Data Mining, pp. 74–81 (2005)
Shervashidze, N., Schweitzer, P., van Leeuwen, E.J., Mehlhorn, K., Borgwardt, K.M.: Weisfeiler-lehman graph kernels. Journal of Machine Learning Research 1, 1–48 (2010)
Lamberti, P., Majtey, A., Borras, A., Casas, M., Plastino, A.: Metric character of the quantum jensen-shannon divergence. Physical Review A 77, 052311 (2008)
Bai, L., Hancock, E.R.: Graph kernels from the jensen-shannon divergence. Journal of Mathematical Imaging and Vision (to appear)
Majtey, A., Lamberti, P., Prato, D.: Jensen-shannon divergence as a measure of distinguishability between mixed quantum states. Physical Review A 72, 052310 (2005)
Farhi, E., Gutmann, S.: Quantum computation and decision trees. Physical Review A 58, 915 (1998)
Dirac, P.: The Principles of Quantum Mechanics, 4th edn. Oxford Science Publications (1958)
Kempe, J.: Quantum random walks: an introductory overview. Contemporary Physics 44, 307–327 (2003)
Nielsen, M., Chuang, I.: Quantum computation and quantum information. Cambridge university press (2010)
Martins, A.F., Smith, N.A., Xing, E.P., Aguiar, P.M., Figueiredo, M.A.: Nonextensive information theoretic kernels on measures. Journal of Machine Learning Research 10, 935–975 (2009)
Konder, R., Lafferty, J.: Diffusion kernels on graphs and other discrete input spaces. In: Proceedings of International Conference on Machine Learning, pp. 315–322 (2002)
Neuhaus, M., Bunke, H.: Bridging the gap between graph edit distance and kernel machines. World Scientific (2007)
Escolano, F., Hancock, E.R., Lozano, M.A.: Heat diffusion: Thermodynamic depth complexity of networks. Physical Review E 85, 036206 (2012)
Dehmer, M.: Information processing in complex networks: Graph entropy and information functionals. Applied Mathematics and Computation 201, 82–94 (2008)
Ren, P., Wilson, R.C., Hancock, E.R.: Graph characterization via ihara coefficients. IEEE Transactions on Neural Networks 22, 233–245 (2011)
Schölkopf, B., Smola, A.J., Müller, K.R.: Kernel principal component analysis. In: Proceedings of International Conference on Artificial Neural Networks, pp. 583–588 (1997)
Platt, J.C.: Fast training of support vector machines using sequential minimal optimization. In: Schölkopf, B., Burges, C.J.C., Smola, A.J. (eds.) Advances in Kernel Methods, pp. 185–208 (1999)
Witten, I.H., Frank, E., Hall, M.A.: Data Mining: Practical Machine Learning Tools and Techniques. Morgan Kaufmann (2011)
Bai, L., Hancock, E.R., Ren, P.: A jensen-shannon kernel for hypergraphs. 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. 181–189. Springer, Heidelberg (2012)
Ren, P., Aleksic, T., Emms, D., Wilson, R., Hancock, E.: Quantum walks, ihara zeta functions and cospectrality in regular graphs. Quantum Information Processing 10, 405–417 (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
Bai, L., Hancock, E.R., Torsello, A., Rossi, L. (2013). A Quantum Jensen-Shannon Graph Kernel Using the Continuous-Time Quantum Walk. 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_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-38221-5_13
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)