An Aligned Subgraph Kernel Based on Discrete-Time Quantum Walk

Abstract

In this paper, a novel graph kernel is designed by aligning the amplitude representation of the vertices. Firstly, the amplitude representation of a vertex is calculated based on the discrete-time quantum walk. Then a matching-based graph kernel is constructed through identifying the correspondence between the vertices of two graphs. The newly proposed kernel can be regarded as a kind of aligned subgraph kernel that incorporates the explicit local information of substructures. Thus, it can address the disadvantage arising in the classical R-convolution kernel that the relative locations of substructures between the graphs are ignored. Experiments on several standard datasets demonstrate that the proposed kernel has better performance compared with other state-of-the-art graph kernels in terms of classification accuracy.