.png){kind=icon}
.png){kind=icon}
Return
An R-Convolution Graph Kernel Based on Fast Discrete-Time Quantum Walk
.png){kind=icon}
OA
AI
DOI：10.1109/TNNLS.2020.3027687.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this article, a novel R-convolution kernel, named the fast quantum walk kernel (FQWK), is proposed for unattributed graphs. In FQWK, the similarity of the neighborhood-pair substructure between two nodes is measured via the superposition amplitude of quantum walks between those nodes. The quantum interference in this kind of local substructures provides more information on the substructures so that FQWK can capture finer-grained local structural features of graphs. In addition, to efficiently compute the transition amplitudes of multistep discrete-time quantum walks, a fast recursive method is designed. Thus, compared with all the existing kernels based on the quantum walk, FQWK has the highest computation speed. Extensive experiments demonstrate that FQWK outperforms state-of-the-art graph kernels in terms of classification accuracy for unattributed graphs. Meanwhile, it can be applied to distinguish a larger family of graphs, including cospectral graphs, regular graphs, and even strong regular graphs, which are not distinguishable by classical walk-based methods.
Keywords:
Kernel
Quantum computing
Interference
Frequency measurement
Computer science
Quantum mechanics
Entropy
Discrete-time quantum walk (DTQW)
graph classification
graph kernel
R-convolution kernel
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
8.9
Papers:
7.5K
Citations:
7.2W