Quantum kernels for unattributed graphs using discrete-time quantum walks


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.

Publication DOI: https://doi.org/10.1016/j.patrec.2016.08.019
Divisions: College of Engineering & Physical Sciences
?? 50811700Jl ??
College of Engineering & Physical Sciences > Systems analytics research institute (SARI)
Publication ISSN: 1872-7344
Last Modified: 06 Dec 2023 10:13
Date Deposited: 22 Nov 2016 13:30
Full Text Link: 10.1016/j.patrec.2016.08.019
Related URLs:
PURE Output Type: Article
Published Date: 2017-02-01
Published Online Date: 2016-09-09
Accepted Date: 2016-08-19
Submitted Date: 2015-11-30
Authors: Bai, Lu
Rossi, Luca (ORCID Profile 0000-0002-6116-9761)
Cui, Lixin
Zhang, Zhihong
Ren, Peng
Bai, Xiao
Hancock, Edwin R.

Export / Share Citation


Additional statistics for this record