A Hierarchical Transitive-Aligned Graph Kernel for Un-attributed Graphs

Lu Bai, Lixin Cui, Hancock Edwin
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:1327-1336, 2022.

Abstract

In this paper, we develop a new graph kernel, namely the Hierarchical Transitive-Aligned Kernel, by transitively aligning the vertices between graphs through a family of hierarchical prototype graphs. Comparing to most existing state-of-the-art graph kernels, the proposed kernel has three theoretical advantages. First, it incorporates the locational correspondence information between graphs into the kernel computation, and thus overcomes the shortcoming of ignoring structural correspondences arising in most R-convolution kernels. Second, it guarantees the transitivity between the correspondence information that is not available for most existing matching kernels. Third, it incorporates the information of all graphs under comparisons into the kernel computation process, and thus encapsulates richer characteristics. Experimental evaluations demonstrate the effectiveness of the new transitive-aligned kernel.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-bai22a, title = {A Hierarchical Transitive-Aligned Graph Kernel for Un-attributed Graphs}, author = {Bai, Lu and Cui, Lixin and Edwin, Hancock}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {1327--1336}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/bai22a/bai22a.pdf}, url = {https://proceedings.mlr.press/v162/bai22a.html}, abstract = {In this paper, we develop a new graph kernel, namely the Hierarchical Transitive-Aligned Kernel, by transitively aligning the vertices between graphs through a family of hierarchical prototype graphs. Comparing to most existing state-of-the-art graph kernels, the proposed kernel has three theoretical advantages. First, it incorporates the locational correspondence information between graphs into the kernel computation, and thus overcomes the shortcoming of ignoring structural correspondences arising in most R-convolution kernels. Second, it guarantees the transitivity between the correspondence information that is not available for most existing matching kernels. Third, it incorporates the information of all graphs under comparisons into the kernel computation process, and thus encapsulates richer characteristics. Experimental evaluations demonstrate the effectiveness of the new transitive-aligned kernel.} }
Endnote
%0 Conference Paper %T A Hierarchical Transitive-Aligned Graph Kernel for Un-attributed Graphs %A Lu Bai %A Lixin Cui %A Hancock Edwin %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-bai22a %I PMLR %P 1327--1336 %U https://proceedings.mlr.press/v162/bai22a.html %V 162 %X In this paper, we develop a new graph kernel, namely the Hierarchical Transitive-Aligned Kernel, by transitively aligning the vertices between graphs through a family of hierarchical prototype graphs. Comparing to most existing state-of-the-art graph kernels, the proposed kernel has three theoretical advantages. First, it incorporates the locational correspondence information between graphs into the kernel computation, and thus overcomes the shortcoming of ignoring structural correspondences arising in most R-convolution kernels. Second, it guarantees the transitivity between the correspondence information that is not available for most existing matching kernels. Third, it incorporates the information of all graphs under comparisons into the kernel computation process, and thus encapsulates richer characteristics. Experimental evaluations demonstrate the effectiveness of the new transitive-aligned kernel.
APA
Bai, L., Cui, L. & Edwin, H.. (2022). A Hierarchical Transitive-Aligned Graph Kernel for Un-attributed Graphs. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:1327-1336 Available from https://proceedings.mlr.press/v162/bai22a.html.

Related Material