论文标题
多尺度的Wasserstein最短路径图内核用于图形分类
Multi-scale Wasserstein Shortest-path Graph Kernels for Graph Classification
论文作者
论文摘要
图内核是用于计算图形相似性的常规方法。但是，现有的R-Convolution Graph内核无法解决两个挑战中的两个挑战：1）比较多个不同尺度的图，以及2）在计算内核矩阵时考虑子结构的分布。这两个挑战限制了他们的表现。为了缓解这两个挑战，我们提出了一个新的图表内核，称为多尺度Wasserstein最短路径图内核（MWSP），其核心是最短路径节点特征图，每个元素都表示围绕node最短路径的发生数量。最短路径是由其中所有节点标签的串联表示。由于最短的路径节点特征映射只能比较局部尺度上的图形，因此我们将图形结构的多个不同尺度纳入其中，这些尺度由截短的BFS树捕获，这些深度为不同深度，这些深度在图中每个节点。我们使用Wasserstein距离来计算两个图的多尺度最短路径节点特征图之间的相似性，考虑到最短路径的分布。我们在各种基准图数据集上经验验证了MWSP，并证明它在大多数数据集中实现了最先进的性能。
Graph kernels are conventional methods for computing graph similarities. However, the existing R-convolution graph kernels cannot resolve both of the two challenges: 1) Comparing graphs at multiple different scales, and 2) Considering the distributions of substructures when computing the kernel matrix. These two challenges limit their performances. To mitigate both of the two challenges, we propose a novel graph kernel called the Multi-scale Wasserstein Shortest-Path graph kernel (MWSP), at the heart of which is the multi-scale shortest-path node feature map, of which each element denotes the number of occurrences of the shortest path around a node. The shortest path is represented by the concatenation of all the labels of nodes in it. Since the shortest-path node feature map can only compare graphs at local scales, we incorporate into it the multiple different scales of the graph structure, which are captured by the truncated BFS trees of different depths rooted at each node in a graph. We use the Wasserstein distance to compute the similarity between the multi-scale shortest-path node feature maps of two graphs, considering the distributions of shortest paths. We empirically validate MWSP on various benchmark graph datasets and demonstrate that it achieves state-of-the-art performance on most datasets.
