论文标题
Qesk：用于图形分类的基于量子的熵子树核
QESK: Quantum-based Entropic Subtree Kernels for Graph Classification
论文作者
论文摘要
在本文中，我们提出了一种新颖的图内核，即基于量子的熵子树（Qesk）进行图形分类。为此，我们通过计算在每个图结构上演变的连续时间量子步行（CTQW）的平均混合矩阵（AMM）开始。此外，我们展示了如何使用此AMM矩阵来计算与经典Weisfeiler-Lehman（WL）算法相关的一系列熵子树表示。对于一对图，Qesk内核是通过计算其熵子树表示之间的负欧几里得距离的指示来定义的，从理论上讲导致正定的定义图内核。我们表明，所提出的QESK内核不仅封装了通过CTQW的图形结构的复杂固有的基于量子的结构特性，而且理论上也解决了忽略在最新的r-convolution voldolution图形核心中忽略未共样子结构的影响的缺点。此外，与经典的R-Convolution核不同，提出的Qesk可以根据全球图结构来区分同构子树的区别，从理论上讲，从理论上讲。实验表明，提出的QESK内核可以显着胜过最先进的图形内核和图形分类问题的深度学习方法。
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.
