  In recent years, kernel methods are widespread in tasks of similarity
measuring. Specifically, graph kernels are widely used in fields of
bioinformatics, chemistry and financial data analysis. However, existing
methods, especially entropy based graph kernels are subject to large
computational complexity and the negligence of node-level information. In this
paper, we propose a novel labeled subgraph entropy graph kernel, which performs
well in structural similarity assessment. We design a dynamic programming
subgraph enumeration algorithm, which effectively reduces the time complexity.
Specially, we propose labeled subgraph, which enriches substructure topology
with semantic information. Analogizing the cluster expansion process of gas
cluster in statistical mechanics, we re-derive the partition function and
calculate the global graph entropy to characterize the network. In order to
test our method, we apply several real-world datasets and assess the effects in
different tasks. To capture more experiment details, we quantitatively and
qualitatively analyze the contribution of different topology structures.
Experimental results successfully demonstrate the effectiveness of our method
which outperforms several state-of-the-art methods.
