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

doi:10.1109/TCYB.2019.2913038

	A Quantum-Inspired Similarity Measure for the Analysis of Complete Weighted Graphs
	Bai, Lu 5; Rossi, Luca 3; Cui, Lixin 4; Cheng, Jian 2; Hancock, Edwin R.1
刊名	IEEE TRANSACTIONS ON CYBERNETICS
	2020-03-01
卷号	50 期号:3 页码:1264-1277
关键词	Kernel Quantum computing Weight measurement Image edge detection Time series analysis Entropy Laplace equations Financial networks graph kernels graph similarity Jensen-Shannon divergence quantum walks
ISSN号	2168-2267
DOI	10.1109/TCYB.2019.2913038
通讯作者	Rossi, Luca(rossil@sustech.edu.cn) ; Cui, Lixin(cuilixin@cufe.edu.cn)
英文摘要	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.
资助项目	National Natural Science Foundation of China[61602535] ; National Natural Science Foundation of China[61503422] ; Open Project Program of the National Laboratory of Pattern Recognition (NLPR) ; Program for Innovation Research in Central University of Finance and Economics
WOS关键词	TIME-SERIES ; KERNELS ; WALKS ; COSPECTRALITY ; PREDICTION ; NETWORK
WOS研究方向	Automation & Control Systems ; Computer Science
语种	英语
出版者	IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
WOS记录号	WOS:000510941100033
资助机构	National Natural Science Foundation of China ; Open Project Program of the National Laboratory of Pattern Recognition (NLPR) ; Program for Innovation Research in Central University of Finance and Economics
内容类型	期刊论文
源URL	[http://ir.ia.ac.cn/handle/173211/28606]
专题	类脑芯片与系统研究
通讯作者	Rossi, Luca; Cui, Lixin
作者单位	1.Univ York, Dept Comp Sci, York Y010 5DD, N Yorkshire, England 2.Chinese Acad Sci, Inst Automat, Natl Lab Pattern Recognit, Beijing 100190, Peoples R China 3.Southern Univ Sci & Technol, Shenzhen 518055, Guangdong, Peoples R China 4.Cent Univ Finance & Econ, Beijing 100081, Peoples R China 5.Cent Univ Finance & Econ, Sch Informat, Beijing 100081, Peoples R China
推荐引用方式 GB/T 7714	Bai, Lu,Rossi, Luca,Cui, Lixin,et al. A Quantum-Inspired Similarity Measure for the Analysis of Complete Weighted Graphs[J]. IEEE TRANSACTIONS ON CYBERNETICS,2020,50(3):1264-1277.
APA	Bai, Lu,Rossi, Luca,Cui, Lixin,Cheng, Jian,&Hancock, Edwin R..(2020).A Quantum-Inspired Similarity Measure for the Analysis of Complete Weighted Graphs.IEEE TRANSACTIONS ON CYBERNETICS,50(3),1264-1277.
MLA	Bai, Lu,et al."A Quantum-Inspired Similarity Measure for the Analysis of Complete Weighted Graphs".IEEE TRANSACTIONS ON CYBERNETICS 50.3(2020):1264-1277.