Enhancing Shortest-Path Graph Kernels via Graph Augmentation

Abstract

The conventional shortest-path graph kernel (SP) decomposes graphs into shortest paths and computes their frequencies in each graph. However, SP cannot compare graphs with variable scales of the graph structure well and cannot compare attributed graphs whose vertices have continuous attributes. To overcome these two challenges, we propose to enhance SP via graph augmentation: Variable scales of the graph structure around vertices are extracted to augment vertices; the graph structure is augmented by graph filtration. After graph augmentation, variable scales of the graph structure are incorporated into SP. Intriguingly, graph filtration, depending on the edge weights, which can be computed by the Euclidean distance between the continuous attributes of connected vertices, enables SP to compare attributed graphs. Since the distribution (frequency) of the shortest paths changes across augmented graphs, we employ the Wasserstein distance to track the changes. Our novel graph kernel is called the Augmented SP (ASP). We conduct experiments on various benchmark graph datasets to evaluate ASP’s performance, which outperforms the state-of-the-art graph kernels on most datasets.