.png){kind=icon}
返回
Fast depth-based subgraph kernels for unattributed graphs
.png){kind=icon}
OA
AI
DOI：10.1016/j.patcog.2015.08.006.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In this paper, we investigate two fast subgraph kernels based on a depth-based representation of graphstructure. Both methods gauge depth information through a family of K-layer expansion subgraphs rooted at a vertex [1]. The first method commences by computing a centroid-based complexity trace for each graph, using a depth-based representation rooted at the centroid vertex that has minimum shortest path length variance to the remaining vertices [2]. This subgraph kernel is computed by measuring the Jensen-Shannon divergence between centroid-based complexity entropy traces. The second method, on the other hand, computes a depth-based representation around each vertex in turn. The corresponding subgraph kernel is computed using isomorphisms tests to compare the depth-based representation rooted at each vertex in turn. For graphs with n vertices, the time complexities for the two new kernels are O(n(2)) and O(n(3)), in contrast to O(n(6)) for the classic Gartner graph kernel [3]. Key to achieving this efficiency is that we compute the required Shannon entropy of the random walk for our kernels with O(n(2)) operations. This computational strategy enables our subgraph kernels to easily scale up to graphs of reasonably large sizes and thus overcome the size limits arising in state-of-the-art graph kernels. Experiments on standard bioinformatics and computer vision graph datasets demonstrate the effectiveness and efficiency of our new subgraph kernels. (C) 2015 Elsevier Ltd. All rights reserved.
Keyword:
Depth-based representations
Entropy
Graph kernels
The Jensen-Shannon divergence
Graph isomorphism tests
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
7.6
论文数:
1.3W
被引数:
4.5W
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容