QBMK: Quantum-based Matching Kernels for Un-attributed Graphs

Lu Bai, Lixin Cui, Ming Li, Yue Wang, Edwin Hancock
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:2364-2374, 2024.

Abstract

In this work, we develop a new Quantum-based Matching Kernel (QBMK) for un-attributed graphs, by computing the kernel-based similarity between the quantum Shannon entropies of aligned vertices through the Continuous-time Quantum Walk (CTQW). The theoretical analysis reveals that the proposed QBMK kernel not only addresses the shortcoming of neglecting the structural correspondence information between graphs arising in existing R-convolution graph kernels, but also overcomes the problem of neglecting the structural differences between pairs of aligned vertices arising in existing vertex-based matching kernels. Moreover, the proposed QBMK kernel can simultaneously capture both global and local structural characteristics through the quantum Shannon entropies. Experimental evaluations on standard graph datasets demonstrate that the proposed QBMK kernel is able to outperform state-of-the-art graph kernels and graph deep learning approaches.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-bai24a, title = {{QBMK}: Quantum-based Matching Kernels for Un-attributed Graphs}, author = {Bai, Lu and Cui, Lixin and Li, Ming and Wang, Yue and Hancock, Edwin}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {2364--2374}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/bai24a/bai24a.pdf}, url = {https://proceedings.mlr.press/v235/bai24a.html}, abstract = {In this work, we develop a new Quantum-based Matching Kernel (QBMK) for un-attributed graphs, by computing the kernel-based similarity between the quantum Shannon entropies of aligned vertices through the Continuous-time Quantum Walk (CTQW). The theoretical analysis reveals that the proposed QBMK kernel not only addresses the shortcoming of neglecting the structural correspondence information between graphs arising in existing R-convolution graph kernels, but also overcomes the problem of neglecting the structural differences between pairs of aligned vertices arising in existing vertex-based matching kernels. Moreover, the proposed QBMK kernel can simultaneously capture both global and local structural characteristics through the quantum Shannon entropies. Experimental evaluations on standard graph datasets demonstrate that the proposed QBMK kernel is able to outperform state-of-the-art graph kernels and graph deep learning approaches.} }
Endnote
%0 Conference Paper %T QBMK: Quantum-based Matching Kernels for Un-attributed Graphs %A Lu Bai %A Lixin Cui %A Ming Li %A Yue Wang %A Edwin Hancock %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-bai24a %I PMLR %P 2364--2374 %U https://proceedings.mlr.press/v235/bai24a.html %V 235 %X In this work, we develop a new Quantum-based Matching Kernel (QBMK) for un-attributed graphs, by computing the kernel-based similarity between the quantum Shannon entropies of aligned vertices through the Continuous-time Quantum Walk (CTQW). The theoretical analysis reveals that the proposed QBMK kernel not only addresses the shortcoming of neglecting the structural correspondence information between graphs arising in existing R-convolution graph kernels, but also overcomes the problem of neglecting the structural differences between pairs of aligned vertices arising in existing vertex-based matching kernels. Moreover, the proposed QBMK kernel can simultaneously capture both global and local structural characteristics through the quantum Shannon entropies. Experimental evaluations on standard graph datasets demonstrate that the proposed QBMK kernel is able to outperform state-of-the-art graph kernels and graph deep learning approaches.
APA
Bai, L., Cui, L., Li, M., Wang, Y. & Hancock, E.. (2024). QBMK: Quantum-based Matching Kernels for Un-attributed Graphs. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:2364-2374 Available from https://proceedings.mlr.press/v235/bai24a.html.

Related Material