Tree++: Truncated Tree Based Graph Kernels
Tree++: Truncated Tree Based Graph Kernels
复制标题
DOI：
10.1109/tkde.2019.2946149
复制
发表时间：
2020-02
影响因子：
8.9
通讯作者：
Wei Ye;Zhen Wang;Rachel Redberg;Ambuj K. Singh
中科院分区：
文献类型：
--
作者：
Wei Ye;Zhen Wang;Rachel Redberg;Ambuj K. Singh
图结构数据在许多应用领域中普遍存在。一个基本问题是量化它们的相似性。图内核通常用于此目的，它将图分解为子结构并比较这些子结构。然而，大多数现有的图内核不具有尺度自适应性，即它们无法在多个粒度级别上比较图。许多现实世界的图（例如分子）表现出不同粒度级别的结构。为了解决这个问题，我们在本文中提出了一种名为 Tree++ 的新图内核。 Tree++ 的核心是一个称为路径模式图内核的图内核。路径模式图内核首先构建以每个顶点为根的截断 BFS 树，然后使用截断 BFS 树中从根到每个顶点的路径作为特征来表示图。路径模式图内核只能捕获细粒度的图相似性。为了捕获粗粒度的图相似性，我们在其中引入了一个称为超级路径的新概念。超级路径包含以路径顶点为根的截断 BFS 树。我们对各种现实世界图的评估表明，与以前的图内核相比，Tree++ 实现了最佳的分类精度。
Graph-structured data arise ubiquitously in many application domains. A fundamental problem is to quantify their similarities. Graph kernels are often used for this purpose, which decompose graphs into substructures and compare these substructures. However, most of the existing graph kernels do not have the property of scale-adaptivity, i.e., they cannot compare graphs at multiple levels of granularities. Many real-world graphs such as molecules exhibit structure at varying levels of granularities. To tackle this problem, we propose a new graph kernel called Tree++ in this paper. At the heart of Tree++ is a graph kernel called the path-pattern graph kernel. The path-pattern graph kernel first builds a truncated BFS tree rooted at each vertex and then uses paths from the root to every vertex in the truncated BFS tree as features to represent graphs. The path-pattern graph kernel can only capture graph similarity at fine granularities. In order to capture graph similarity at coarse granularities, we incorporate a new concept called super path into it. The super path contains truncated BFS trees rooted at the vertices in a path. Our evaluation on a variety of real-world graphs demonstrates that Tree++ achieves the best classification accuracy compared with previous graph kernels.