Université Catholique de Louvain, ICTEAM & LSM, Louvain-la-Neuve and Mons, Belgium.
Neural Netw. 2012 Jul;31:53-72. doi: 10.1016/j.neunet.2012.03.001. Epub 2012 Mar 20.
This paper presents a survey as well as an empirical comparison and evaluation of seven kernels on graphs and two related similarity matrices, that we globally refer to as "kernels on graphs" for simplicity. They are the exponential diffusion kernel, the Laplacian exponential diffusion kernel, the von Neumann diffusion kernel, the regularized Laplacian kernel, the commute-time (or resistance-distance) kernel, the random-walk-with-restart similarity matrix, and finally, a kernel first introduced in this paper (the regularized commute-time kernel) and two kernels defined in some of our previous work and further investigated in this paper (the Markov diffusion kernel and the relative-entropy diffusion matrix). The kernel-on-graphs approach is simple and intuitive. It is illustrated by applying the nine kernels to a collaborative-recommendation task, viewed as a link prediction problem, and to a semisupervised classification task, both on several databases. The methods compute proximity measures between nodes that help study the structure of the graph. Our comparisons suggest that the regularized commute-time and the Markov diffusion kernels perform best on the investigated tasks, closely followed by the regularized Laplacian kernel.
本文对七种图核和两种相关相似性矩阵进行了调查和实证比较与评估，我们通常简称为“图核”。它们是指数扩散核、拉普拉斯指数扩散核、冯·诺依曼扩散核、正则化拉普拉斯核、交流时间（或电阻距离）核、随机游走重启相似矩阵，最后是本文首次引入的核（正则化交流时间核），以及我们之前的工作中定义并在本文中进一步研究的两个核（马尔可夫扩散核和相对熵扩散矩阵）。图核方法简单直观。通过将这九个核应用于协作推荐任务（视为链接预测问题）和半监督分类任务，在多个数据库上进行了说明。这些方法计算节点之间的接近度度量，有助于研究图的结构。我们的比较表明，正则化交流时间核和马尔可夫扩散核在研究的任务中表现最佳，紧随其后的是正则化拉普拉斯核。
