Distributional Shortest-Path Graph Kernels

Traditional shortest-path graph kernels generate for each graph a histogram-like feature map, whose elements represent the number of occurrences of non-isomorphic shortest paths in this graph. The histogram-like feature map does not contain the distributions of the shortest paths within and across graphs, causing inaccurate graph similarities. To this end, we propose a novel graph kernel called the Distributional Shortest-Path (DSP) graph kernel to embrace both types of distribution information. Since the distribution of substructures (e.g., the shortest paths) follows a power law like that of words in natural language, we utilize neural language models to learn each node's distributional shortest-path feature map, encompassing the distributions and dependencies of the shortest paths in each graph. Moreover, we design the Partition Kernel (PK) to capture the dataset-wide distribution information of the shortest paths. PK projects similar (i.e., belonging to the same partition) distributional shortest-path node feature maps to the same point in the Reproducing Kernel Hilbert Space. Finally, Kernel Mean Embedding (KME) is applied to compute graph feature maps and efficiently construct the DSP graph kernel. Empirical experiments demonstrate that DSP outperforms state-of-the-art graph kernels on most benchmark datasets.