A hybrid reproducing graph kernel based on information entropy

- We prove the H1-reproducing graph kernel satisfies the condition of Mercer kernel.
- We propose a novel reproducing graph kernel based on approximated von Neumann entropy.
- We propose a novel reproducing graph kernel based on Shannon entropy.
- We propose a hybrid reproducing graph kernel based on information entropy.
- We demonstrate the effectiveness of the proposed hybrid reproducing graph kernel.

A number of graph kernel-based methods have been developed with great success in many fields, but very little research has been published that is concerned with a graph kernel in Reproducing Kernel Hilbert Space (RKHS). In this paper, we firstly start with a derived expression for two forms of information entropy of an undirected graph. They are approximated von Neumann entropy and Shannon entropy, and depend on vertex degree statistics. Secondly, we show the basic solution of a generalized differential operator. This solution is a specific reproducing kernel called the H1-reproducing kernel in H1-space, and then it is proven to satisfy the condition of Mercer kernel. Thirdly, based on the two aforementioned forms of information entropy and H1-reproducing kernel, we define two reproducing graph kernels: one is approximated von Neumann entropy reproducing graph kernel (AVNERGK), the other is Shannon entropy reproducing graph kernel (SERGK). And then we prove that they satisfy the condition of Mercer kernel. Finally, to obtain better classification results, we further propose a hybrid reproducing graph kernel (HRGK) based on the two reproducing graph kernels. We use the HRGK as a means to establish the similarity between a pair of graphs. Experimental results reveal that our method gives better classification performance on graphs extracted from several graph datasets.