论文标题
状态的密度图内核
Density of States Graph Kernels
论文作者
论文摘要
图形结构数据的基本问题是量化图之间的相似性。图内核是针对此类任务的既定技术。特别是，基于随机步行和返回概率的人已被证明在广泛的应用程序中有效，从生物信息学到社交网络再到计算机视觉。但是，随机步行内核通常会遭受缓慢和颤抖的痛苦，这种效果导致步行过度强调本地图形拓扑，从而降低了全球结构的重要性。 To correct for these issues, we recast return probability graph kernels under the more general framework of density of states -- a framework which uses the lens of spectral analysis to uncover graph motifs and properties hidden within the interior of the spectrum -- and use our interpretation to construct scalable, composite density of states based graph kernels which balance local and global information, leading to higher classification accuracies on a host of benchmark datasets.
A fundamental problem on graph-structured data is that of quantifying similarity between graphs. Graph kernels are an established technique for such tasks; in particular, those based on random walks and return probabilities have proven to be effective in wide-ranging applications, from bioinformatics to social networks to computer vision. However, random walk kernels generally suffer from slowness and tottering, an effect which causes walks to overemphasize local graph topology, undercutting the importance of global structure. To correct for these issues, we recast return probability graph kernels under the more general framework of density of states -- a framework which uses the lens of spectral analysis to uncover graph motifs and properties hidden within the interior of the spectrum -- and use our interpretation to construct scalable, composite density of states based graph kernels which balance local and global information, leading to higher classification accuracies on a host of benchmark datasets.
