TY - JOUR
T1 - Quantum kernels for unattributed graphs using discrete-time quantum walks
AU - Bai, Lu
AU - Rossi, Luca
AU - Cui, Lixin
AU - Zhang, Zhihong
AU - Ren, Peng
AU - Bai, Xiao
AU - Hancock, Edwin
N1 - Funding Information:
This work is supported by the National Natural Science Foundation of China (Grant no. 61503422, 61602535 and 61402389), and the Open Projects Program of National Laboratory of Pattern Recognition. Lu Bai is supported by the program for innovation research in Central University of Finance and Economics. Xiao Bai is suported by NSFC project No. 61370123 and BNSF project No. 4162037. Edwin R. Hancock is supported by a Royal Society Wolfson Research Merit Award.
Publisher Copyright:
© 2016 Elsevier B.V.
PY - 2017/2/1
Y1 - 2017/2/1
N2 - In this paper, we develop a new family of graph kernels where the graph structure is probed by means of a discrete-time quantum walk. Given a pair of graphs, we let a quantum walk evolve on each graph and compute a density matrix with each walk. With the density matrices for the pair of graphs to hand, the kernel between the graphs is defined as the negative exponential of the quantum Jensen–Shannon divergence between their density matrices. In order to cope with large graph structures, we propose to construct a sparser version of the original graphs using the simplification method introduced in Qiu and Hancock (2007). To this end, we compute the minimum spanning tree over the commute time matrix of a graph. This spanning tree representation minimizes the number of edges of the original graph while preserving most of its structural information. The kernel between two graphs is then computed on their respective minimum spanning trees. We evaluate the performance of the proposed kernels on several standard graph datasets and we demonstrate their effectiveness and efficiency.
AB - In this paper, we develop a new family of graph kernels where the graph structure is probed by means of a discrete-time quantum walk. Given a pair of graphs, we let a quantum walk evolve on each graph and compute a density matrix with each walk. With the density matrices for the pair of graphs to hand, the kernel between the graphs is defined as the negative exponential of the quantum Jensen–Shannon divergence between their density matrices. In order to cope with large graph structures, we propose to construct a sparser version of the original graphs using the simplification method introduced in Qiu and Hancock (2007). To this end, we compute the minimum spanning tree over the commute time matrix of a graph. This spanning tree representation minimizes the number of edges of the original graph while preserving most of its structural information. The kernel between two graphs is then computed on their respective minimum spanning trees. We evaluate the performance of the proposed kernels on several standard graph datasets and we demonstrate their effectiveness and efficiency.
KW - Discrete-time quantum walks
KW - Graph kernels
KW - Quantum Jensen–Shannon divergence
UR - http://www.scopus.com/inward/record.url?scp=84994472145&partnerID=8YFLogxK
U2 - 10.1016/j.patrec.2016.08.019
DO - 10.1016/j.patrec.2016.08.019
M3 - Journal article
AN - SCOPUS:84994472145
SN - 0167-8655
VL - 87
SP - 96
EP - 103
JO - Pattern Recognition Letters
JF - Pattern Recognition Letters
ER -