Zhang Yi, Wang Lulu, Wilson Richard C, Liu Kai
IEEE Trans Neural Netw Learn Syst. 2022 Jan;33(1):292-303. doi: 10.1109/TNNLS.2020.3027687. Epub 2022 Jan 5.
In this article, 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 multistep 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 walk-based methods.
在本文中，针对无属性图提出了一种名为快速量子游走核（FQWK）的新型R-卷积核。在FQWK中，通过两个节点之间量子游走的叠加幅度来衡量两个节点之间邻域对结构的相似性。这种局部子结构中的量子干涉提供了关于子结构的更多信息，使得FQWK能够捕捉图的更细粒度的局部结构特征。此外，为了高效计算多步离散时间量子游走的转移幅度，设计了一种快速递归方法。因此，与所有现有的基于量子游走的核相比，FQWK具有最高的计算速度。大量实验表明，在无属性图的分类准确率方面，FQWK优于当前最先进的图核。同时，它可以应用于区分更大类别的图，包括同谱图、正则图，甚至强正则图，而这些图是基于经典游走的方法无法区分的。
