Name
Title | ||
|---|---|---|
Random-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation |
Abstract | ||
|---|---|---|
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 |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1109/TKDE.2007.46 | IEEE Trans. Knowl. Data Eng. |
Keywords | Field | DocType |
laplacian matrix,relational databases,relational database,elements increase,proximity measures,commute time,information filtering,statistical relational learning.,statistical relational learning framework,markov-chain model,graph analysis,laplacian matrix algebra,undirected graph theory,spectral clustering,undirected graph,random-walk computation,graph pca,graph theory,fiedler vector,graph and database mining,collaborative recommendation,euclidean distance,graph partitioning,movielens database show,average commute time,principal component analysis,markov processes,graph kernels,random walk,similitude,markov chain model,pattern recognition,machine learning,markov model,markov chain,case based reasoning,perspective,database,modeling,cinema,variance,inner product,data mining,similarity,statistical relational learning,collaboration,classification,artificial intelligence,vector space,laplacian,motion pictures,kernel,pseudoinverse,information extraction,movies,cooperation,domain decomposition,random walk model | Strength of a graph,Data mining,Computer science,Artificial intelligence,Adjacency matrix,Laplacian matrix,Discrete mathematics,Directed graph,Algebraic connectivity,Null graph,Random geometric graph,Graph (abstract data type),Machine learning | Journal |
Volume | Issue | ISSN |
19 | 3 | 1041-4347 |
Citations | PageRank | References |
461 | 21.09 | 30 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Francois Fouss | 1 | 624 | 34.41 |
| Alain Pirotte | 2 | 916 | 260.52 |
| Jean Michel Renders | 3 | 874 | 70.31 |
| Marco Saerens | 4 | 1221 | 87.07 |