Quantum kernels for unattributed graphs using discrete-time quantum walks

Lu Bai, Luca Rossi, Lixin Cui, Zhihong Zhang, Peng Ren, Xiao Bai, Edwin R. Hancock

Research output: Contribution to journalArticle

Abstract

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.
Original languageEnglish
Pages (from-to)96-103
Number of pages8
JournalPattern Recognition Letters
Volume87
Early online date9 Sep 2016
DOIs
Publication statusPublished - 1 Feb 2017

Cite this

Bai, L., Rossi, L., Cui, L., Zhang, Z., Ren, P., Bai, X., & Hancock, E. R. (2017). Quantum kernels for unattributed graphs using discrete-time quantum walks. Pattern Recognition Letters, 87, 96-103. https://doi.org/10.1016/j.patrec.2016.08.019
Bai, Lu ; Rossi, Luca ; Cui, Lixin ; Zhang, Zhihong ; Ren, Peng ; Bai, Xiao ; Hancock, Edwin R. / Quantum kernels for unattributed graphs using discrete-time quantum walks. In: Pattern Recognition Letters. 2017 ; Vol. 87. pp. 96-103.
@article{a53842ba555e410e974f6fc7c56768d3,
title = "Quantum kernels for unattributed graphs using discrete-time quantum walks",
abstract = "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.",
author = "Lu Bai and Luca Rossi and Lixin Cui and Zhihong Zhang and Peng Ren and Xiao Bai and Hancock, {Edwin R.}",
year = "2017",
month = "2",
day = "1",
doi = "10.1016/j.patrec.2016.08.019",
language = "English",
volume = "87",
pages = "96--103",
journal = "Pattern Recognition Letters",
issn = "0167-8655",
publisher = "Elsevier",

}

Bai, L, Rossi, L, Cui, L, Zhang, Z, Ren, P, Bai, X & Hancock, ER 2017, 'Quantum kernels for unattributed graphs using discrete-time quantum walks', Pattern Recognition Letters, vol. 87, pp. 96-103. https://doi.org/10.1016/j.patrec.2016.08.019

Quantum kernels for unattributed graphs using discrete-time quantum walks. / Bai, Lu; Rossi, Luca; Cui, Lixin; Zhang, Zhihong; Ren, Peng; Bai, Xiao; Hancock, Edwin R.

In: Pattern Recognition Letters, Vol. 87, 01.02.2017, p. 96-103.

Research output: Contribution to journalArticle

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 R.

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.

U2 - 10.1016/j.patrec.2016.08.019

DO - 10.1016/j.patrec.2016.08.019

M3 - Article

VL - 87

SP - 96

EP - 103

JO - Pattern Recognition Letters

JF - Pattern Recognition Letters

SN - 0167-8655

ER -