Graph Alignment Kernels using Weisfeiler and Leman Hierarchies

Giannis Nikolentzos, Michalis Vazirgiannis
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:2019-2034, 2023.

Abstract

Graph kernels have become a standard approach for tackling the graph similarity and learning tasks at the same time. Most graph kernels proposed so far are instances of the R-convolution framework. These kernels decompose graphs into their substructures and sum over all pairs of these substructures. However, considerably less attention has been paid to other types of kernels. In this paper, we propose a new kernel between graphs which reorders the adjacency matrix of each graph based on soft permutation matrices, and then compares those aligned adjacency matrices to each other using a linear kernel. To compute the permutation matrices, the kernel finds corresponding vertices in different graphs. Two vertices match with each other if the Weisfeiler-Leman test of isomorphism assigns the same label to both of them. The proposed kernel is evaluated on several graph classification and graph regression datasets. Our results indicate that the kernel is competitive with traditional and state-of-the-art methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-nikolentzos23b, title = {Graph Alignment Kernels using Weisfeiler and Leman Hierarchies}, author = {Nikolentzos, Giannis and Vazirgiannis, Michalis}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {2019--2034}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/nikolentzos23b/nikolentzos23b.pdf}, url = {https://proceedings.mlr.press/v206/nikolentzos23b.html}, abstract = {Graph kernels have become a standard approach for tackling the graph similarity and learning tasks at the same time. Most graph kernels proposed so far are instances of the R-convolution framework. These kernels decompose graphs into their substructures and sum over all pairs of these substructures. However, considerably less attention has been paid to other types of kernels. In this paper, we propose a new kernel between graphs which reorders the adjacency matrix of each graph based on soft permutation matrices, and then compares those aligned adjacency matrices to each other using a linear kernel. To compute the permutation matrices, the kernel finds corresponding vertices in different graphs. Two vertices match with each other if the Weisfeiler-Leman test of isomorphism assigns the same label to both of them. The proposed kernel is evaluated on several graph classification and graph regression datasets. Our results indicate that the kernel is competitive with traditional and state-of-the-art methods.} }
Endnote
%0 Conference Paper %T Graph Alignment Kernels using Weisfeiler and Leman Hierarchies %A Giannis Nikolentzos %A Michalis Vazirgiannis %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-nikolentzos23b %I PMLR %P 2019--2034 %U https://proceedings.mlr.press/v206/nikolentzos23b.html %V 206 %X Graph kernels have become a standard approach for tackling the graph similarity and learning tasks at the same time. Most graph kernels proposed so far are instances of the R-convolution framework. These kernels decompose graphs into their substructures and sum over all pairs of these substructures. However, considerably less attention has been paid to other types of kernels. In this paper, we propose a new kernel between graphs which reorders the adjacency matrix of each graph based on soft permutation matrices, and then compares those aligned adjacency matrices to each other using a linear kernel. To compute the permutation matrices, the kernel finds corresponding vertices in different graphs. Two vertices match with each other if the Weisfeiler-Leman test of isomorphism assigns the same label to both of them. The proposed kernel is evaluated on several graph classification and graph regression datasets. Our results indicate that the kernel is competitive with traditional and state-of-the-art methods.
APA
Nikolentzos, G. & Vazirgiannis, M.. (2023). Graph Alignment Kernels using Weisfeiler and Leman Hierarchies. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:2019-2034 Available from https://proceedings.mlr.press/v206/nikolentzos23b.html.

Related Material