  In this work, we develop an Aligned Entropic Reproducing Kernel (AERK) for
graph classification. We commence by performing the Continuous-time Quantum
Walk (CTQW) on each graph structure, and computing the Averaged Mixing Matrix
(AMM) to describe how the CTQW visit all vertices from a starting vertex. More
specifically, we show how this AMM matrix allows us to compute a quantum
Shannon entropy for each vertex of a graph. For pairwise graphs, the proposed
AERK kernel is defined by computing a reproducing kernel based similarity
between the quantum Shannon entropies of their each pair of aligned vertices.
The analysis of theoretical properties reveals that the proposed AERK kernel
cannot only address the shortcoming of neglecting the structural correspondence
information between graphs arising in most existing R-convolution graph
kernels, but also overcome the problem of neglecting the structural differences
between pairs of aligned vertices arising in existing vertex-based matching
kernels. Moreover, unlike existing classical graph kernels that only focus on
the global or local structural information of graphs, the proposed AERK kernel
can simultaneously capture both global and local structural information through
the quantum Shannon entropies, reflecting more precise kernel based similarity
measures between pairs of graphs. The above theoretical properties explain the
effectiveness of the proposed kernel. The experimental evaluation on standard
graph datasets demonstrates that the proposed AERK kernel is able to outperform
state-of-the-art graph kernels for graph classification tasks.
