Efficient graphlet kernels for large graph comparison
Efficient graphlet kernels for large graph comparison
复制标题
DOI：
--
复制
发表时间：
2009-04
影响因子：
1.9
通讯作者：
N. Shervashidze;S. Vishwanathan;Tobias Petri;K. Mehlhorn;Karsten M. Borgwardt
中科院分区：
文献类型：
--
作者：
N. Shervashidze;S. Vishwanathan;Tobias Petri;K. Mehlhorn;Karsten M. Borgwardt
最先进的图形内核不能扩展到具有数百个节点和数千条边的大型图形。在这篇文章中，我们建议通过计算图来比较图，即，有k个节点的子图，其中k ∈ {3，4，5}。穷举所有graphlets是昂贵的，我们介绍了两个理论接地加速方案，一个基于采样和第二个专门设计的有界度图。在我们的实验评估中，我们的新型内核使我们能够有效地比较现有图内核无法处理的大型图。
State-of-the-art graph kernels do not scale to large graphs with hundreds of nodes and thousands of edges. In this article we propose to compare graphs by counting graphlets, i.e., subgraphs with k nodes where k ∈ {3, 4, 5}. Exhaustive enumeration of all graphlets being prohibitively expensive, we introduce two theoretically grounded speedup schemes, one based on sampling and the second one specifically designed for bounded degree graphs. In our experimental evaluation, our novel kernels allow us to efficiently compare large graphs that cannot be tackled by existing graph kernels.