Transport based Graph Kernels
This work addresses graph classification tasks by improving similarity measures for researchers and practitioners in machine learning, though it appears incremental as it builds on existing optimal transport and graph kernel frameworks.
The authors tackled the problem of graph similarity measurement by incorporating hierarchical structure information, which existing graph kernels often ignore, and proposed pyramid and subgraph kernels based on optimal transport, with results showing that their algorithms outperform state-of-the-art methods in most benchmark classification tasks.
Graph kernel is a powerful tool measuring the similarity between graphs. Most of the existing graph kernels focused on node labels or attributes and ignored graph hierarchical structure information. In order to effectively utilize graph hierarchical structure information, we propose pyramid graph kernel based on optimal transport (OT). Each graph is embedded into hierarchical structures of the pyramid. Then, the OT distance is utilized to measure the similarity between graphs in hierarchical structures. We also utilize the OT distance to measure the similarity between subgraphs and propose subgraph kernel based on OT. The positive semidefinite (p.s.d) of graph kernels based on optimal transport distance is not necessarily possible. We further propose regularized graph kernel based on OT where we add the kernel regularization to the original optimal transport distance to obtain p.s.d kernel matrix. We evaluate the proposed graph kernels on several benchmark classification tasks and compare their performance with the existing state-of-the-art graph kernels. In most cases, our proposed graph kernel algorithms outperform the competing methods.