TY - JOUR

T1 - A Quantum-Inspired Similarity Measure for the Analysis of Complete Weighted Graphs

AU - Bai, Lu

AU - Rossi, Luca

AU - Cui, Lixin

AU - Cheng, Jian

AU - Hancock, Edwin R.

N1 - Funding Information:
Manuscript received September 26, 2017; revised September 13, 2018 and April 11, 2019; accepted April 19, 2019. Date of publication July 11, 2019; date of current version January 21, 2020. This work was supported in part by the National Natural Science Foundation of China under Grant 61602535 and Grant 61503422, in part by the Open Project Program of the National Laboratory of Pattern Recognition (NLPR), and in part by the Program for Innovation Research in Central University of Finance and Economics. This paper was recommended by Associate Editor M. Last. (Corresponding authors: Luca Rossi; Lixin Cui.) L. Bai and L. Cui are with the Central University of Finance and Economics, Beijing 100081, China (e-mail: [email protected]; [email protected]). L. Rossi is with the Southern University of Science and Technology, Guangdong 518055, China (e-mail: [email protected]). J. Cheng is with the National Laboratory of Pattern Recognition, Institute of Automation, Chinese Academy of Sciences, Beijing 100190, China. E. R. Hancock is with the University of York, York Y010 5DD, U.K. This paper has supplementary downloadable material available at http://ieeexplore.ieee.org, provided by the author. Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TCYB.2019.2913038
Publisher Copyright:
© 2013 IEEE.

PY - 2020/3

Y1 - 2020/3

N2 - We develop a novel method for measuring the similarity between complete weighted graphs, which are probed by means of the discrete-time quantum walks. Directly probing complete graphs using discrete-time quantum walks is intractable due to the cost of simulating the quantum walk. We overcome this problem by extracting a commute time minimum spanning tree from the complete weighted graph. The spanning tree is probed by a discrete-time quantum walk which is initialized using a weighted version of the Perron-Frobenius operator. This naturally encapsulates the edge weight information for the spanning tree extracted from the original graph. For each pair of complete weighted graphs to be compared, we simulate a discrete-time quantum walk on each of the corresponding commute time minimum spanning trees and, then, compute the associated density matrices for the quantum walks. The probability of the walk visiting each edge of the spanning tree is given by the diagonal elements of the density matrices. The similarity between each pair of graphs is then computed using either: 1) the inner product or 2) the negative exponential of the Jensen-Shannon divergence between the probability distributions. We show that in both cases the resulting similarity measure is positive definite and, therefore, corresponds to a kernel on the graphs. We perform a series of experiments on publicly available graph datasets from a variety of different domains, together with time-varying financial networks extracted from data for the New York Stock Exchange. Our experiments demonstrate the effectiveness of the proposed similarity measures.

AB - We develop a novel method for measuring the similarity between complete weighted graphs, which are probed by means of the discrete-time quantum walks. Directly probing complete graphs using discrete-time quantum walks is intractable due to the cost of simulating the quantum walk. We overcome this problem by extracting a commute time minimum spanning tree from the complete weighted graph. The spanning tree is probed by a discrete-time quantum walk which is initialized using a weighted version of the Perron-Frobenius operator. This naturally encapsulates the edge weight information for the spanning tree extracted from the original graph. For each pair of complete weighted graphs to be compared, we simulate a discrete-time quantum walk on each of the corresponding commute time minimum spanning trees and, then, compute the associated density matrices for the quantum walks. The probability of the walk visiting each edge of the spanning tree is given by the diagonal elements of the density matrices. The similarity between each pair of graphs is then computed using either: 1) the inner product or 2) the negative exponential of the Jensen-Shannon divergence between the probability distributions. We show that in both cases the resulting similarity measure is positive definite and, therefore, corresponds to a kernel on the graphs. We perform a series of experiments on publicly available graph datasets from a variety of different domains, together with time-varying financial networks extracted from data for the New York Stock Exchange. Our experiments demonstrate the effectiveness of the proposed similarity measures.

KW - Financial networks

KW - graph kernels

KW - graph similarity

KW - Jensen-Shannon divergence

KW - quantum walks

UR - http://www.scopus.com/inward/record.url?scp=85078506517&partnerID=8YFLogxK

U2 - 10.1109/TCYB.2019.2913038

DO - 10.1109/TCYB.2019.2913038

M3 - Journal article

C2 - 31295131

AN - SCOPUS:85078506517

SN - 2168-2267

VL - 50

SP - 1264

EP - 1277

JO - IEEE Transactions on Cybernetics

JF - IEEE Transactions on Cybernetics

IS - 3

M1 - 8759946

ER -