An Aligned Subgraph Kernel Based on Discrete-Time Quantum Walk

Kai Liu, Lulu Wang, Yi Zhang
Proceedings of The 13th Asian Conference on Machine Learning, PMLR 157:145-157, 2021.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v157-liu21a, title = {An Aligned Subgraph Kernel Based on Discrete-Time Quantum Walk}, author = {Liu, Kai and Wang, Lulu and Zhang, Yi}, booktitle = {Proceedings of The 13th Asian Conference on Machine Learning}, pages = {145--157}, year = {2021}, editor = {Balasubramanian, Vineeth N. and Tsang, Ivor}, volume = {157}, series = {Proceedings of Machine Learning Research}, month = {17--19 Nov}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v157/liu21a/liu21a.pdf}, url = {https://proceedings.mlr.press/v157/liu21a.html}, 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.} }
Endnote
%0 Conference Paper %T An Aligned Subgraph Kernel Based on Discrete-Time Quantum Walk %A Kai Liu %A Lulu Wang %A Yi Zhang %B Proceedings of The 13th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Vineeth N. Balasubramanian %E Ivor Tsang %F pmlr-v157-liu21a %I PMLR %P 145--157 %U https://proceedings.mlr.press/v157/liu21a.html %V 157 %X 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.
APA
Liu, K., Wang, L. & Zhang, Y.. (2021). An Aligned Subgraph Kernel Based on Discrete-Time Quantum Walk. Proceedings of The 13th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 157:145-157 Available from https://proceedings.mlr.press/v157/liu21a.html.

Related Material