  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. By
transductively training the C-SVM classifier, experimental evaluations
demonstrate the effectiveness of the new transitive-aligned kernel. The
proposed kernel can outperform state-of-the-art graph kernels on standard
graph-based datasets in terms of the classification accuracy.
