Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation
Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation
复制标题
DOI：
10.1109/tkde.2007.46
复制
发表时间：
2007-03-01
影响因子：
8.9
通讯作者：
Saerens, Marco
中科院分区：
文献类型：
--
作者：
Fouss, Francois;Pirotte, Alain;Saerens, Marco
这项工作提出了一个新的视角来描述数据库元素之间的相似性，或者更一般地说，加权和无向图的节点之间的相似性。它基于随机遍历数据库的马尔可夫链模型。更准确地说，我们计算数量（平均通勤时间，图的拉普拉斯矩阵的伪逆，等等），提供任何一对节点之间的相似性，具有当连接这些元素的路径数量增加和路径“长度”减少时增加的良好特性。结果表明，平均通勤时间的平方根是欧几里得距离，而拉普拉斯矩阵的伪逆是核矩阵（其元素是与通勤时间密切相关的内积）。引入了图的主成分分析（PCA）来计算节点向量的子空间投影，以尽可能多地保留欧几里得通勤时间距离方面的方差。这个图PCA为广泛用于图分区的“费德勒向量”提供了一个很好的解释。该模型是在一个协作推荐任务上进行评估的，该任务是根据人们过去看过的电影来建议他们应该看哪些电影。在MovieLens数据库上的实验结果表明，与其他方法相比，基于拉普拉斯的相似度方法具有较好的效果。该模型非常适合所谓的“统计关系学习”框架，也可以用于计算文档或单词的相似性，更一般地说，它可以应用于涉及关系数据库的机器学习和模式识别任务。
This work presents a new perspective on characterizing the similarity between elements of a database or, more generally, nodes of a weighted and undirected graph. It is based on a Markov-chain model of random walk through the database. More precisely, we compute quantities (the average commute time, the pseudoinverse of the Laplacian matrix of the graph, etc.) that provide similarities between any pair of nodes, having the nice property of increasing when the number of paths connecting those elements increases and when the "length" of paths decreases. It turns out that the square root of the average commute time is a Euclidean distance and that the pseudoinverse of the Laplacian matrix is a kernel matrix (its elements are inner products closely related to commute times). A principal component analysis (PCA) of the graph is introduced for computing the subspace projection of the node vectors in a manner that preserves as much variance as possible in terms of the Euclidean commute-time distance. This graph PCA provides a nice interpretation to the "Fiedler vector," widely used for graph partitioning. The model is evaluated on a collaborative-recommendation task where suggestions are made about which movies people should watch based upon what they watched in the past. Experimental results on the MovieLens database show that the Laplacian-based similarities perform well in comparison with other methods. The model, which nicely fits into the so-called " statistical relational learning" framework, could also be used to compute document or word similarities, and, more generally, it could be applied to machine-learning and pattern-recognition tasks involving a relational database.