Abstract In this paper, we develop a novel graph kernel by aligning the Jensen-Shannon (JS) representations of vertices. We commence by describing how to compute the JS representation of a vertex by measuring the JS divergence (JSD) between the corresponding h-layer depth-based (DB) representations developed in [Bai et al., 2014a]). By aligning JS representations of vertices, we identify the correspondence between the vertices of two graphs and this allows us to construct a matching-based graph kernel. Unlike existing R-convolution kernels [Haussler, 1999] that roughly record the isomorphism information between any pair of substructures under a type of graph decomposition, the new kernel can be seen as an aligned subgraph kernel that incorporates explicit local correspondences of substructures (i.e., the local information graphs [Dehmer and Mowshowitz, 2011]) into the process of kernelization through the JS representation alignment. The new kernel thus addresses the drawback of neglecting the relative locations between substructures that arises in the R-convolution kernels. Experiments demonstrate that our kernel can easily outperform state-of-the-art graph kernels in terms of the classification accuracies.