By the same authors

From the same journal

An R-convolution Graph Kernel based on Fast Discrete-Time Quantum Walk

Research output: Contribution to journalArticle

Full text download(s)

Author(s)

Department/unit(s)

Publication details

JournalIEEE Transactions on Neural Networks and Learning Systems
DateAccepted/In press - 27 Sep 2020
Number of pages12
Original languageEnglish

Abstract

In this paper, 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 multi-step 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 walkbased
methods.

Bibliographical note

© IEEE 2020. This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details.

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations