OpenAIRE is about to release its new face with lots of new content and services.
During September, you may notice downtime in services, while some functionalities (e.g. user registration, login, validation, claiming) will be temporarily disabled.
We apologize for the inconvenience, please stay tuned!
For further information please contact helpdesk[at]

fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Bai, Lu; Rossi, Luca; Torsello, Andrea; Hancock, Edwin R.
Languages: English
Types: Article
Subjects: 1712, 1711, Settore INF/01 - Informatica, 1707, 1702
In this paper, we use the quantum Jensen-Shannon divergence as a means of measuring the information theoretic dissimilarity of graphs and thus develop a novel graph kernel. In quantum mechanics, the quantum Jensen-Shannon divergence can be used to measure the dissimilarity of quantum systems specified in terms of their density matrices. We commence by computing the density matrix associated with a continuous-time quantum walk over each graph being compared. In particular, we adopt the closed form solution of the density matrix introduced in Rossi et al. (2013) [27,28] to reduce the computational complexity and to avoid the cumbersome task of simulating the quantum walk evolution explicitly. Next, we compare the mixed states represented by the density matrices using the quantum Jensen-Shannon divergence. With the quantum states for a pair of graphs described by their density matrices to hand, the quantum graph kernel between the pair of graphs is defined using the quantum Jensen-Shannon divergence between the graph density matrices. We evaluate the performance of our kernel on several standard graph datasets from both bioinformatics and computer vision. The experimental results demonstrate the effectiveness of the proposed quantum graph kernel.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] B.Scho¨lkopf, A. Smola, Learning with Kernels, MIT Press, 2002.
    • [2] D. Haussler, Convolution kernels on discrete structures, Technical Report UCS-CRL-99-10, Santa Cruz, CA, USA, 1999.
    • [3] H. Kashima, K. Tsuda, A. Inokuchi, Marginalized kernels between labeled graphs, In: Proceedings of International Conference on Machine Learning (ICML), 2003, pp. 321-328.
    • [4] K.M. Borgwardt, H.P. Kriegel, Shortest-path kernels on graphs, In: Proceedings of the IEEE International Conference on Data Mining (ICDM), 2005, pp. 74-81.
    • [5] N. Shervashidze, P. Schweitzer, E.J. van Leeuwen, K. Mehlhorn, K.M. Borgwardt, Weisfeiler-lehman graph kernels, Journal of Machine Learning Research 1, (2010) 1-48.
    • [6] F. Aziz, R.C. Wilson, E.R. Hancock, Backtrackless walks on a graph, IEEE Transections on Neural Network and Learning System 24, (2013) 977-989.
    • [7] F. Costa, K.D. Grave, Fast neighborhood subgraph pairwise distance kernel, in: Proceedings of International Conference on Machine Learning (ICML), PP. 255-262, 2010.
    • [8] Kriege Nils, Mutzel Petra, Subgraph Matching Kernels for Attributed Graphs., in: Proceedings of International Conference on Machine Learning (ICML), 2012.
  • No related research data.
  • No similar publications.
Cookies make it easier for us to provide you with our services. With the usage of our services you permit us to use cookies.
More information Ok