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 1; Rossi, Luca 3; Cui, Lixin 2; Cheng, Jian4 ; Hancock, Edwin R.5
发表期刊	IEEE TRANSACTIONS ON CYBERNETICS
ISSN	2168-2267
	2020-03-01
卷号	50 期号:3 页码:1264-1277
通讯作者	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.
关键词	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
DOI	10.1109/TCYB.2019.2913038
关键词[WOS]	TIME-SERIES ; KERNELS ; WALKS ; COSPECTRALITY ; PREDICTION ; NETWORK
收录类别	SCI
语种	英语
资助项目	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 ; 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
项目资助者	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
WOS研究方向	Automation & Control Systems ; Computer Science
WOS类目	Automation & Control Systems ; Computer Science, Artificial Intelligence ; Computer Science, Cybernetics
WOS记录号	WOS:000510941100033
出版者	IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
引用统计	被引频次：17[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://ir.ia.ac.cn/handle/173211/28607
专题	复杂系统认知与决策实验室_高效智能计算与学习
通讯作者	Rossi, Luca; Cui, Lixin
作者单位	1.Cent Univ Finance & Econ, Sch Informat, Beijing 100081, Peoples R China 2.Cent Univ Finance & Econ, Beijing 100081, Peoples R China 3.Southern Univ Sci & Technol, Shenzhen 518055, Guangdong, Peoples R China 4.Chinese Acad Sci, Inst Automat, Natl Lab Pattern Recognit, Beijing 100190, Peoples R China 5.Univ York, Dept Comp Sci, York Y010 5DD, N Yorkshire, England
推荐引用方式 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.