  In this paper, we propose a novel graph kernel, namely the Quantum-based
Entropic Subtree Kernel (QESK), for Graph Classification. To this end, we
commence by computing the Average Mixing Matrix (AMM) of the Continuous-time
Quantum Walk (CTQW) evolved on each graph structure. Moreover, we show how this
AMM matrix can be employed to compute a series of entropic subtree
representations associated with the classical Weisfeiler-Lehman (WL) algorithm.
For a pair of graphs, the QESK kernel is defined by computing the
exponentiation of the negative Euclidean distance between their entropic
subtree representations, theoretically resulting in a positive definite graph
kernel. We show that the proposed QESK kernel not only encapsulates complicated
intrinsic quantum-based structural characteristics of graph structures through
the CTQW, but also theoretically addresses the shortcoming of ignoring the
effects of unshared substructures arising in state-of-the-art R-convolution
graph kernels. Moreover, unlike the classical R-convolution kernels, the
proposed QESK can discriminate the distinctions of isomorphic subtrees in terms
of the global graph structures, theoretically explaining the effectiveness.
Experiments indicate that the proposed QESK kernel can significantly outperform
state-of-the-art graph kernels and graph deep learning methods for graph
classification problems.
