Graph kernels based on optimal node assignment

摘要

The success of kernel algorithms depends on the kernel it uses and hence the development of kernels for structured data like graphs is an active research field. We designed two graph kernels by making use of the optimal assignment kernel framework, which is a less explored graph framework compared to its counterpart, namely, R-convolution kernels. In our work, the bijection associated with the optimal assignment framework is defined between sets that consist of the nodes of the graph kernel arguments and hence we named the proposed kernels as optimal node assignment kernels (ONA). In ONA, the nodes of the given data are divided into groups named as neighbourhood sets on the basis of the labels generated by the Weisfeiler–Lehman (WL) test for graph isomorphism and a matrix representation is defined for them. A kernel is then defined over the domain that consists of the neighbourhood sets in terms of such matrices and an aggregate measure of those kernel values is used for defining ONA kernel. The validity of the proposed kernels is mathematically proved. The kernel calculation using the hierarchy structure associated with the optimal assignment framework is also discussed. The performance of the proposed ONA kernels was analysed using graph classification datasets and was found to be superior in comparison with the other state-of-the-art graph kernels.