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
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Cites
Nonparametric Statistics for the Behavioral Sciences
Guitton, H., & Siegel, S. (1958) · Revue économique · doi:10.2307/3498751 · Cited by 35,281 · see citing works
Social Network Analysis: Methods and Applications
Wasserman, S. S., & Faust, K. (1994) · Cited by 18,005 · see citing works
Social Network Analysis: Methods and Applications
Wasserman, S., & Faust, K. (1994) · doi:10.1017/cbo9780511815478 · Cited by 17,557 · see citing works
Normalized cuts and image segmentation
Shi, J., & Malik, J. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.868688 · Cited by 15,842 · see citing works
Iterative Methods for Sparse Linear Systems
Saad, Y. E.-M. (2003) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898718003 · Cited by 13,931 · see citing works
(1999) · Cited by 12,854 · see citing works
Schölkopf, B., & Smola, A. J. (2001) · The MIT Press eBooks · doi:10.7551/mitpress/4175.001.0001 · Cited by 11,934 · see citing works
Baeza-Yates, R. A., & Ribeiro-Neto, B. A. (1999) · Cited by 11,498 · see citing works
Applied Multivariate Statistical Analysis.
Johnson, A., & Wichern, D. W. (1988) · Biometrics · doi:10.2307/2531616 · Cited by 11,374 · see citing works
Advances in Neural Information Processing Systems 14
(2002) · The MIT Press eBooks · doi:10.7551/mitpress/1120.001.0001 · Cited by 9,184 · see citing works
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1999) · Journal of the ACM · doi:10.1145/324133.324140 · Cited by 9,032 · see citing works
Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
Belkin, M., & Niyogi, P. (2003) · Neural Computation · doi:10.1162/089976603321780317 · Cited by 7,562 · see citing works
Kernel Methods for Pattern Analysis
Shawe-Taylor, J. S., & Cristianini, N. (2004) · Cambridge University Press eBooks · doi:10.1017/cbo9780511809682 · Cited by 6,610 · see citing works
Chung, F. (1996) · Regional conference series in mathematics · doi:10.1090/cbms/092 · Cited by 5,918 · see citing works
Evaluating collaborative filtering recommender systems
Herlocker, J. L., Konstan, J. A., Terveen, L. G., & Riedl, J. T. (2004) · ACM Transactions on Information Systems · doi:10.1145/963770.963772 · Cited by 5,798 · see citing works
Generalized Inverses: Theory and Applications
Rohatgi, V. K., Ben-Israel, A., & Greville, T. N. E. (1976) · International Statistical Review · doi:10.2307/1403291 · Cited by 4,568 · see citing works
Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering
Belkin, M., & Niyogi, P. (2002) · The MIT Press eBooks · doi:10.7551/mitpress/1120.003.0080 · Cited by 4,534 · see citing works
A New Status Index Derived from Sociometric Analysis
Katz, L. (1953) · Psychometrika · doi:10.1007/bf02289026 · Cited by 3,945 · see citing works
Kemeny, J. G., & Snell, J. L. (1976) · Medical Entomology and Zoology · Cited by 2,813 · see citing works
A measure of betweenness centrality based on random walks
Newman, M. E. J. (2005) · Social Networks · doi:10.1016/j.socnet.2004.11.009 · Cited by 2,471 · see citing works
Generalized Inverse of Matrices and Its Applications
Banerjee, K. S. (1973) · Technometrics · doi:10.1080/00401706.1973.10489026 · Cited by 2,291 · see citing works
Applied Multivariate Statistical Analysis
Härdle, W. K., & Simar, L. (2003) · Springer eBooks · doi:10.1007/978-3-662-05802-2 · Cited by 2,277 · see citing works
Generalized Inverses of Linear Transformations
Campbell, S. L., & Meyer, C. D. (2009) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719048 · Cited by 1,922 · see citing works
Random Walks and Electric Networks
Doyle, P. G., & Snell, J. L. (1984) · The Carus mathematical monographs · doi:10.5948/upo9781614440222 · Cited by 1,846 · see citing works
Modern Multidimensional Scaling
Borg, I., & Groenen, P. J. F. (1997) · Springer series in statistics · doi:10.1007/978-1-4757-2711-1 · Cited by 1,745 · see citing works
Partitioning Sparse Matrices with Eigenvectors of Graphs
Pothen, A., Simon, H. D., & Liou, K.-P. (1990) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0611030 · Cited by 1,703 · see citing works
Modern multidimensional scaling : theory and applications
Borg, I., & Groenen, P. J. F. (1997) · Springer eBooks · doi:10.1007/0-387-28981-x · Cited by 1,615 · see citing works
Nonparametric Statistics for the Behavioral Sciences
(2010) · Encyclopedia of Research Design · doi:10.4135/9781412961288.n273 · Cited by 1,414 · see citing works
Parzen, E. (1999) · doi:10.1137/1.9781611971125 · Cited by 1,389 · see citing works
Klein, D. J., & Randić, M. (1993) · Journal of Mathematical Chemistry · doi:10.1007/bf01164627 · Cited by 1,384 · see citing works
Norris, J. R. (1997) · Cambridge University Press eBooks · doi:10.1017/cbo9780511810633 · Cited by 1,255 · see citing works
Generalized Inverse of Matrices and its Applications
Mayne, A. J. (1972) · Journal of the Operational Research Society · doi:10.1057/jors.1972.96 · Cited by 1,213 · see citing works
A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory
Fiedler, M. (1975) · Czechoslovak Mathematical Journal · doi:10.21136/cmj.1975.101357 · Cited by 1,069 · see citing works
Iterative Methods for Solving Linear Systems
Quarteroni, A. M., Sacco, R., & Saleri, F. (2006) · Springer eBooks · doi:10.1007/0-387-22750-4_4 · Cited by 1,032 · see citing works
Iterative Methods for Solving Linear Systems
Greenbaum, A. (1997) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970937 · Cited by 962 · see citing works
Metric and Euclidean properties of dissimilarity coefficients
Gower, J. C., & Legendre, P. (1986) · Journal of Classification · doi:10.1007/bf01896809 · Cited by 937 · see citing works
Kernels and Regularization on Graphs
Smola, A. J., & Kondor, R. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45167-9_12 · Cited by 857 · see citing works
Matrices with Applications in Statistics.
Thomas, G. E., & Graybill, F. A. (1984) · Journal of the Royal Statistical Society Series A (General) · doi:10.2307/2981752 · Cited by 744 · see citing works
(1990) · Choice Reviews Online · doi:10.5860/choice.28-0347 · Cited by 741 · see citing works
Diffusion Kernels on Graphs and Other Discrete Input Spaces
Kondor, R., & Lafferty, J. (2002) · Cited by 728 · see citing works
H., A. S., & Noble, B. (1970) · Mathematics of Computation · doi:10.2307/2004636 · Cited by 707 · see citing works
Huang, Z., Chen, H., & Zeng, D. D. (2004) · ACM Transactions on Information Systems · doi:10.1145/963770.963775 · Cited by 652 · see citing works
Evaluation of Item-Based Top- N Recommendation Algorithms
Karypis, G. (2001) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/502585.502627 · Cited by 586 · see citing works
Proceedings of the European Conference on Machine Learning
Brazdil, P. (1993) · Cited by 548 · see citing works
Markov Chains -- Theory and Applications
Unwin, A., Isaacson, D., & Madsen, R. W. (1977) · Operational Research Quarterly (1970-1977) · doi:10.2307/3008804 · Cited by 487 · see citing works
Diffusion kernels on graphs and other discrete structures
Kondor, R. (2002) · Cited by 424 · see citing works
Algorithms for estimating relative importance in networks
White, S., & Smyth, P. (2003) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/956750.956782 · Cited by 410 · see citing works
Learning from labeled and unlabeled data on a directed graph
Zhou, D., Huang, J., & Schölkopf, B. (2005) · International Conference on Machine Learning · doi:10.1145/1102351.1102482 · Cited by 410 · see citing works
The Role of the Group Generalized Inverse in the Theory of Finite Markov Chains
Meyer, C. D. (1975) · SIAM Review · doi:10.1137/1017044 · Cited by 376 · see citing works
The electrical resistance of a graph captures its commute and cover times
Chandra, A. K., Raghavan, P., Ruzzo, W. L., et al. (1989) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/73007.73062 · Cited by 367 · see citing works
Diffusion Maps, Spectral Clustering and Eigenfunctions of Fokker-Planck operatorsPreprint
Nadler, B., Lafon, S., Coifman, R. R., & Kevrekidis, I. G. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.math/0506090 · Cited by 351 · see citing works
Fast discovery of connection subgraphs
Faloutsos, C., McCurley, K. S., & Tomkins, A. (2004) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1014052.1014068 · Cited by 346 · see citing works
Matrices: methods and applications
(1991) · Choice Reviews Online · doi:10.5860/choice.28-5115 · Cited by 321 · see citing works
Džeroski, S. (2003) · ACM SIGKDD Explorations Newsletter · doi:10.1145/959242.959245 · Cited by 268 · see citing works
Göbel, F., & Jagers, A. A. (1974) · Stochastic Processes and their Applications · doi:10.1016/0304-4149(74)90001-5 · Cited by 251 · see citing works
Laplace eigenvalues of graphs—a survey
Mohar, B. (1992) · Discrete Mathematics · doi:10.1016/0012-365x(92)90288-q · Cited by 230 · see citing works
The Principal Components Analysis of a Graph, and Its Relationships to Spectral Clustering
Saerens, M., Fouss, F., Yen, L., et al. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-30115-8_35 · Cited by 222 · see citing works
Self-citationTHE MATRIX-FOREST THEOREM AND MEASURING RELATIONS IN SMALL SOCIAL GROUPS
Chebotarev, P., & Shamis, E. (1997) · Automation and Remote Control · Cited by 169 · see citing works
Modeling the Internet and the Web: Probabilistic Method and Algorithms
Baldi, P., Frasconi, P., & Smyth, P. (2003) · Wiley eBooks · Cited by 158 · see citing works
Evaluation of Item-Based Top-N Recommendation Algorithms
Karypis, G. (2001) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/502624.502627 · Cited by 157 · see citing works
A Modified Cholesky Algorithm Based on a Symmetric Indefinite Factorization
Cheng, S. H., & Higham, N. J. (1998) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479896302898 · Cited by 122 · see citing works
Modeling the Internet and the Web: Probabilistic Methods and Algorithms
Baldi, P., Frasconi, P., & Smyth, P. (2002) · Wiley eBooks · doi:10.1002/047086799x · Cited by 117 · see citing works
OntoDM: An Ontology of Data Mining
Panov, P., Deroski, S., & Soldatova, L. (2008) · IEEE ... International Conference on Data Mining workshops · doi:10.1109/icdmw.2008.62 · Cited by 111 · see citing works
On Clustering Using Random Walks
Harel, D., & Koren, Y. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45294-x_3 · Cited by 105 · see citing works
An Experimental Investigation of Graph Kernels on a Collaborative Recommendation Task
Fouss, F., Yen, L., Pirotte, A., et al. (2006) · Proceedings · doi:10.1109/icdm.2006.18 · Cited by 101 · see citing works
Self-citationOn Proximity Measures for Graph VerticesPreprint
Chebotarev, P., & Shamis, E. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.math/0602073 · Cited by 97 · see citing works
A random walks perspective on maximizing satisfaction and profit
Brand, M. (2005) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972757.2 · Cited by 96 · see citing works
The Matrix of Maximum Out Forests of a Digraph and Its ApplicationsPreprint
Agaev, R., & Chebotarev, P. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.math/0602059 · Cited by 91 · see citing works
Algorithms for estimating relative importance in networks
White, S., & Smyth, P. (2003) · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/956755.956782 · Cited by 87 · see citing works
Fouss, F., Pirotte, A., & Saerens, M. (2005) · doi:10.1109/wi.2005.9 · Cited by 74 · see citing works
Self-citationSellami, T., Berriri, H., Mimouni, M. F., Jelassi, S., & Darcherif, A. (2014) · HAL · Cited by 73 · see citing works
Application of kernels to link analysis
Ito, T., Shimbo, M., Kudo, T., & Matsumoto, Y. (2005) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1081870.1081941 · Cited by 70 · see citing works
Markov Chains, Theory and Applications.
Paige, C. C., Isaacson, D., & Madsen, R. W. (1977) · Journal of the American Statistical Association · doi:10.2307/2286253 · Cited by 63 · see citing works
Electricity based external similarity of categorical attributes
Palmer, C. R., & Faloutsos, C. (2003) · doi:10.5555/1760894.1760959 · Cited by 59 · see citing works
Spanning Forests of a Digraph and Their Applications
Agaev, R. P., & Chebotarev, P. Y. (2001) · Automation and Remote Control · doi:10.1023/a:1002862312617 · Cited by 57 · cited 1× · see citing works
“However, the nice interpretation in terms of the pseudoinverse of the Laplacian matrix does not apply in this case (still, see [1], [2] for potential generalizations to directed graphs).”
BackgroundNonnegative Lagrangian Relaxation of K-Means and Spectral Clustering
Ding, C. H. Q., He, X., & Simon, H. D. (2005) · Lecture notes in computer science · doi:10.1007/11564096_51 · Cited by 56 · see citing works
Extended Latent Class Models for Collaborative Recommendation
Cheung, W. K., Tsui, K. C., & Liu, J. (2004) · IEEE Transactions on Systems Man and Cybernetics - Part A Systems and Humans · doi:10.1109/tsmca.2003.818877 · Cited by 52 · see citing works
On the Optimality of the Median Cut Spectral Bisection Graph Partitioning Method
Chan, T. F.-C., Ciarlet, P., & Szeto, W. K. (1997) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827594262649 · Cited by 45 · see citing works
Matrix Theory and Linear Algebra
de Queiroz, M. S., Cai, X., & Feemster, M. G. (2018) · doi:10.1002/9781118887455.app1 · Cited by 39 · see citing works
Electricity Based External Similarity of Categorical Attributes
Palmer, C. R., & Faloutsos, C. (2003) · Lecture notes in computer science · doi:10.1007/3-540-36175-8_49 · Cited by 31 · see citing works
On the pseudo-inverse of the Laplacian of a bipartite graph
Ho, N.-D., & Dooren, P. V. (2005) · Applied Mathematics Letters · doi:10.1016/j.aml.2004.07.034 · Cited by 25 · see citing works
Fouss, F., Pirotte, A., Saerens, M., Renders, J.-M., & Yen, L. (2006) · DIAL (Catholic University of Leuven) · Cited by 24 · see citing works
Self-citationApplication of Kernels to Link Analysis: First Results
Ito, T., Shimbo, M., Kudo, T., & Matsumoto, Y. (2004) · Cited by 7 · see citing works
On a Duality between Metrics and $Σ$-ProximitiesPreprint
Chebotarev, P., & Shamis, E. (2005) · doi:10.48550/arxiv.math/0508183 · Cited by 3 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293 · see citing works
DeepWalk: online learning of social representations
Perozzi, B., Al-Rfou, R., & Skiena, S. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623732 · Cited by 10,123 · see citing works
Graph embedding techniques, applications, and performance: A survey
Goyal, P., & Ferrara, E. (2018) · Knowledge-Based Systems · doi:10.1016/j.knosys.2018.03.022 · Cited by 1,801 · see citing works
Wolf, F. A., Hamey, F. K., Plass, M., Solana, J., Dahlin, J. S., Göttgens, B., Rajewsky, N., Simon, L., & Theis, F. J. (2019) · Genome Biology · doi:10.1186/s13059-019-1663-x · Cited by 1,698 · see citing works
Network meta‐analysis, electrical networks and graph theory
Rücker, G. (2012) · Research Synthesis Methods · doi:10.1002/jrsm.1058 · Cited by 730 · see citing works
Registration of 3D Point Clouds and Meshes: A Survey from Rigid to Nonrigid
Tam, G. K. L., Cheng, Z.-Q., Lai, Y.-K., Langbein, F. C., Liu, Y., Marshall, D., Martin, R. R., Sun, X.-F., & Rosin, P. L. (2013) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2012.310 · Cited by 679 · see citing works
Dual Graph Convolutional Networks for Graph-Based Semi-Supervised Classification
Zhuang, C., & Ma, Q. (2018) · Proceedings of the 2018 World Wide Web Conference on World Wide Web - WWW '18 · doi:10.1145/3178876.3186116 · Cited by 423 · see citing works
Random Walks: A Review of Algorithms and Applications
Xia, F., Liu, J., Nie, H., Fu, Y., Wan, L., & Kong, X. (2020) · IEEE Transactions on Emerging Topics in Computational Intelligence · doi:10.1109/tetci.2019.2952908 · Cited by 295 · see citing works
Li, Z. (., Fang, X., & Sheng, O. R. L. (2018) · ACM Transactions on Management Information Systems · doi:10.1145/3131782 · Cited by 65 · see citing works
Failure Diagnosis in Microservice Systems: A Comprehensive Survey and Analysis
Zhang, S., Xia, S., Fan, W., Shi, B., Xiong, X., Zhong, Z., Ma, M., Sun, Y., & Pei, D. (2026) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/3715005 · Cited by 57 · see citing works
A Graph-based model for context-aware recommendation using implicit feedback data
Yao, W., He, J., Huang, G., Cao, J., & Zhang, Y. (2015) · World Wide Web · doi:10.1007/s11280-014-0307-z · Cited by 54 · see citing works
Poisoning Federated Recommender Systems with Fake Users
Yin, M., Xu, Y., Fang, M., & Gong, N. Z. (2024) · Proceedings of the ACM Web Conference 2024 · doi:10.1145/3589334.3645492 · Cited by 27 · see citing works
- Authors
- Fouss, F., Pirotte, A., Renders, J.-M., & Saerens, M.
- Affiliations
- UCLouvain (BE)
- Xerox (France) (FR)
- Venue
- IEEE Transactions on Knowledge and Data Engineering
- Published
- 2007-03
- Volume
- 19
- Issue
- 3
- Pages
- 355-369
- ISSN
- 1041-4347 (ISSN-L)
- OpenAlex
- W2161984370
- Cited by
- 1,265
- References
- 84
- Citations by year
- 2026: 13 · 2025: 37 · 2024: 46 · 2023: 55 · 2022: 71 · 2021: 111 · 2020: 82 · 2019: 88 · 2018: 100 · 2017: 88 · 2016: 63 · 2015: 75 · 2014: 96 · 2013: 77 · 2012: 75
- FWCI
- 118.88
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Knowledge and Data Engineering (publishedVersion)
- Digital Access to Libraries (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Information Systems › Recommender Systems and Techniques
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Advanced Graph Neural Networks
- Keywords
- node similarity, random walks, commuting time, Fiedler vector, collaborative recommendation, recommender systems, statistical relational learning, weighted undirected graphs, kernel matrix, document similarity
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
