- QESK: A Quantum-Based Entropic Subtree Kernel for Graph Classification
Authors: Lu Bai, Lixin Cui, Edwin R. Hancock
Abstract: In this paper, we propose a new graph kernel for graph classification, namely the quantum-based entropic subtree kernel (QESK). To this end, we start by computing the average mixing matrix (AMM) of the continuous-time quantum walks (CTQWs) evolved on each graph structure. Furthermore, we show how to use this AMM matrix to compute a set 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 power of the negative Euclidean distance between their entropic subtree representations, which theoretically results in a positive definite graph kernel. The proposed QESK kernel not only encapsulates the complex inherent quantum-based structural properties of graph structures through CTQWs, but also theoretically addresses the shortcoming of ignoring the effects of unshared substructures that occur in state-of-the-art R-convolutional graph kernels. Moreover, unlike the traditional R-convolutional kernels, the proposed QESK is able to distinguish between isomorphic subtree distinctions in terms of global graph structure, and we theoretically explain its effectiveness. Experiments show that the proposed QESK kernel can significantly outperform state-of-the-art graph kernels and graph deep learning methods for graph classification problems.
