- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Measuring graph similarity through continuous-time quantum walks and the quantum Jensen-Shannon divergence

Luca Rossi1, Andrea Torsello2, and Edwin R. Hancock3

  • 1School of Computer Science, University of Birmingham, United Kingdom
  • 2Dipartimento di Scienze Ambientali, Informatica e Statistica, Università Ca' Foscari Venezia, Venezia, Italy
  • 3Department of Computer Science, University of York, United Kingdom

PDF

Phys. Rev. E 91, 022815 – Published 23 February, 2015

DOI: https://doi.org/10.1103/PhysRevE.91.022815

Abstract

In this paper we propose a quantum algorithm to measure the similarity between a pair of unattributed graphs. We design an experiment where the two graphs are merged by establishing a complete set of connections between their nodes and the resulting structure is probed through the evolution of continuous-time quantum walks. In order to analyze the behavior of the walks without causing wave function collapse, we base our analysis on the recently introduced quantum Jensen-Shannon divergence. In particular, we show that the divergence between the evolution of two suitably initialized quantum walks over this structure is maximum when the original pair of graphs is isomorphic. We also prove that under special conditions the divergence is minimum when the sets of eigenvalues of the Hamiltonians associated with the two original graphs have an empty intersection.

View figure in article

Article Text

References (50)

  1. K. Siddiqi, A. Shokoufandeh, S. J. Dickinson, and S. W. Zucker, Shock graphs and shape matching, Int. J. Comput. Vision 35, 13 (1999).
  2. H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai, and A. L. Barabási, The large-scale organization of metabolic networks, Nature (London) 407, 651 (2000).
  3. T. Ito, T. Chiba, R. Ozawa, M. Yoshida, M. Hattori, and Y. Sakaki, A comprehensive two-hybrid analysis to explore the yeast protein interactome, Proc. Natl. Acad. Sci. USA 98, 4569 (2001).
  4. V. Kalapala, V. Sanwalani, A. Clauset, and C. Moore, Scale invariance in road networks, Phys. Rev. E 73, 026130 (2006).
  5. B. Schölkopf and A. J. Smola, Learning with kernels: Support Vector Machines, Regularization, Optimization, and Beyond (MIT Press, Cambridge, MA, 2001).
  6. V. N. Vapnik, Statistical Learning Theory (Wiley-Interscience, 1998).
  7. D. Haussler, Convolution kernels on discrete structures, Technical report UCS-CRL-99-10, UC Santa Cruz, 1999 (unpublished).
  8. T. Gärtner, P. Flach, and S. Wrobel, On graph kernels: Hardness results and efficient alternatives, in Learning Theory and Kernel Machines, edited by B. Schölkopf and M. K. Warmuth (Springer, Berlin, 2003), pp. 129–143.
  9. K. M. Borgwardt and H. P. Kriegel, Shortest-path kernels on graphs, in Fifth IEEE International Conference on Data Mining, edited by J. Han and B. Wah (IEEE, New York, 2005) p. 8.
  10. N. Shervashidze, S. Vishwanathan, T. Petri, K. Mehlhorn, and K. Borgwardt, Efficient graphlet kernels for large graph comparison, in Proceedings of the International Workshop on Artificial Intelligence and Statistics, edited by D. van Dyk and M. Welling (Society for Artificial Intelligence and Statistics, Clearwater Beach, Florida, 2009).
  11. L. Bai and E. R. Hancock, Graph kernels from the Jensen-Shannon divergence, J. Math. Imaging Vision 47, 60 (2013).
  12. A. F. T. Martins, N. A. Smith, E. P. Xing, P. M. Q. Aguiar, and M. A. T. Figueiredo, Nonextensive information theoretic kernels on measures, J. Mach. Learn. Res. 10, 935 (2009).
  13. F. Passerini and S. Severini. The Von Neumann entropy of networks, arXiv:0812.2597v2.
  14. J. Kempe, Quantum random walks: An introductory overview, Contemp. Phys. 44, 307 (2003).
  15. A. Ambainis, Quantum walks and their algorithmic applications, Int. J. Quantum. Inf. 01, 507 (2003).
  16. A. M. Childs, Universal computation by quantum walk, Phys. Rev. Lett. 102, 180501 (2009).
  17. M. Santha, Quantum walk based search algorithms, in Theory and Applications of Models of Computation, edited by M. Agrawal, D.-Z. Du, Z. Duan, and A. Li (Springer, Berlin, 2008), pp. 31–46.
  18. O. Mülken and A. Blumen, Continuous-time quantum walks: Models for coherent transport on complex networks, Phys. Rep. 502, 37 (2011).
  19. V. Kendon, Decoherence in quantum walks—-a review, Math. Structures Comput. Sci. 17, 1169 (2007).
  20. N. Shenvi, J. Kempe, and K. Birgitta Whaley, Quantum random-walk search algorithm, Phys. Rev. A 67, 052307 (2003).
  21. E. Farhi and S. Gutmann, Quantum computation and decision trees, Phys. Rev. A 58, 915 (1998).
  22. H. Krovi and T. A. Brun, Quantum walks with infinite hitting times, Phys. Rev. A 74, 042334 (2006).
  23. D. Emms, R. C. Wilson, and E. R. Hancock, Graph embedding using a quasi-quantum analog of the hitting times of continuous time quantum walks, Quantum Inf. Comput. 9, 231 (2009).
  24. L. Rossi, A. Torsello, and E. R. Hancock, Approximate axial symmetries from continuous time quantum walks, in Structural, Syntactic, and Statistical Pattern Recognition, edited by G. L. Gimel'farb, E. R. Hancock, A. Imiya, A. Kuijper, M. Kudo, S. Omachi, T. Windeatt, and K. Yamada (Springer, Berlin Heidelberg, 2012), pp. 144–152.
  25. L. Rossi, A. Torsello, E. R. Hancock, and R. C. Wilson, Characterizing graph symmetries through quantum Jensen-Shannon divergence, Phys. Rev. E 88, 032806 (2013).
  26. A. Majtey, P. W. Lamberti, M. T. Martin, and A. Plastino, Wootters' distance revisited: A new distinguishability criterium, Eur. Phys. J. D 32, 413 (2005).
  27. A. P. Majtey, P. W. Lamberti, and D. P. Prato, Jensen-Shannon divergence as a measure of distinguishability between mixed quantum states, Phys. Rev. A 72, 052310 (2005).
  28. P. W. Lamberti, A. P. Majtey, A. Borras, M. Casas, and A. Plastino, Metric character of the quantum Jensen-Shannon divergence, Phys. Rev. A 77, 052311 (2008).
  29. J. Lin, Divergence measures based on the Shannon entropy, IEEE Trans. Inf. Theory 37, 145 (1991).
  30. L. Rossi, A. Torsello, and E. R. Hancock, A continuous-time quantum walk kernel for unattributed graphs, in Graph-Based Representations in Pattern Recognition, edited by W. G. Kropatsch, N. M. Artner, Y. Haxhimusa, and X. Jiang (Springer, Berlin, 2013), pp. 101–110.
  31. L. Rossi, A. Torsello, and E. R. Hancock, Attributed graph similarity from the quantum Jensen-Shannon divergence, in Similarity-Based Pattern Recognition, edited by E. R. Hancock and M. Pelillo (Springer, Berlin, 2013), pp. 204–218.
  32. L. Bai, L. Rossi, A. Torsello, and E. R. Hancock, A quantum Jensen-Shannon graph kernel for unattributed graphs, Pattern Recognition 48, 344 (2015).
  33. J. Jost, Riemannian Geometry and Geometric Analysis (Springer, Berlin, 2011).
  34. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, Cambridge, 2010).
  35. W. K. Wootters, Statistical distance and Hilbert space, Phys. Rev. D 23, 357 (1981).
  36. G. Lindblad, Entropy, information and quantum measurements, Commun. Math. Phys. 33, 305 (1973).
  37. D. Bures, An extension of Kakutani's theorem on infinite product measures to the tensor product of semifinite w* algebras, Trans. AMS 135, 199 (1969).
  38. J. Briët and P. Harremoës, Properties of classical and quantum Jensen-Shannon divergence, Phys. Rev. A 79, 052311 (2009).
  39. A. K. Debnath, R. L. Lopez de Compadre, G. Debnath, A. J. Shusterman, and C. Hansch, Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds, Correlation with molecular orbital energies and hydrophobicity, J. Med. Chem. 34, 786 (1991).
  40. F. Escolano, E. R. Hancock, and M. A. Lozano, Heat diffusion: Thermodynamic depth complexity of networks, Phys. Rev. E 85, 036206 (2012).
  41. G. Li, M. Semerci, B. Yener, and M. J. Zaki, Effective graph classification based on topological and label attributes, Stat. Anal. Data Mining 5, 265 (2012).
  42. S. K. Nayar, S. A. Nene, and H. Murase, Columbia object image library (coil 100), Technical Report No. CUCS-006-96, Department of Computer Science, Columbia University, 1996 (unpublished).
  43. A. Torsello and E. R. Hancock, Correcting curvature-density effects in the Hamilton-Jacobi skeleton, IEEE Trans. Image Process. 15, 877 (2006).
  44. A. Torsello and L. Rossi, Supervised learning of graph structure, in Similarity-Based Pattern Recognition, edited by M. Pelillo and E. R. Hancock (Springer, Berlin, 2011), pp. 117–132.
  45. C. C. Chang and C. J. Lin, Libsvm: A library for support vector machines, ACM Trans. Intelligent Syst. Technol. (TIST) 2, 27 (2011).
  46. N. Shervashidze, P. Schweitzer, E. J. Van Leeuwen, K. Mehlhorn, and K. M. Borgwardt, Weisfeiler-Lehman graph kernels, J. Machine Learning Res. 12, 2539 (2011).
  47. Trevor F. Cox and Michael AA Cox, Multidimensional Scaling (CRC Press, Boca Raton, FL, 2010).
  48. X. Gao, B. Xiao, D. Tao, and X. Li, A survey of graph edit distance, Pattern Anal. Applic. 13, 113 (2010).
  49. H. Bunke, On a relation between graph edit distance and maximum common subgraph, Pattern Recognition Lett. 18, 689 (1997).
  50. S. Vichy N. Vishwanathan, Nicol N. Schraudolph, Risi Kondor, and Karsten M. Borgwardt, Graph kernels, J. Machine Learning Res. 11, 1201 (2010).

Outline

Information

Phys. Rev. E 91, 022815– Published 23 February, 2015
  • Received 30 July 2014
  • Revised 7 December 2014

©2015 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation