Boosting Item-based Collaborative Filtering via Nearly Uncoupled Random Walks

Athanasios N. Nikolakopoulos, George Karypis

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


Item-based models are among the most popular collaborative filtering approaches for building recommender systems. Random walks can provide a powerful tool for harvesting the rich network of interactions captured within these models. They can exploit indirect relations between the items, mitigate the effects of sparsity, ensure wider itemspace coverage, as well as increase the diversity of recommendation lists. Their potential however, can be hindered by the tendency of the walks to rapidly concentrate towards the central nodes of the graph, thereby significantly restricting the range of K-step distributions that can be exploited for personalized recommendations. In this work, we introduce RecWalk; a novel random walk-based method that leverages the spectral properties of nearly uncoupled Markov chains to provably lift this limitation and prolong the influence of users' past preferences on the successive steps of the walk - thereby allowing the walker to explore the underlying network more fruitfully. A comprehensive set of experiments on real-world datasets verify the theoretically predicted properties of the proposed approach and indicate that they are directly linked to significant improvements in top-n recommendation accuracy. They also highlight RecWalk's potential in providing a framework for boosting the performance of item-based models. RecWalk achieves state-of-the-art top-n recommendation quality outperforming several competing approaches, including recently proposed methods that rely on deep neural networks.

Original languageEnglish (US)
Article number3406241
JournalACM Transactions on Knowledge Discovery from Data
Issue number6
StatePublished - Oct 2020

Bibliographical note

Funding Information:
This work was supported in part by NSF (1901134, 1447788, 1704074, 1757916, and 1834251), Army Research Office (W911NF1810344), Intel Corp, and the Digital Technology Center at the University of Minnesota. Authors’ addresses: A. N. Nikolakopoulos and G. Karypis, University of Minnesota, 499 Walter Library, 117 Pleasant Street SE, Minneapolis, Minnesota, 55455; emails: {anikolak, karypis} Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from © 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM. 1556-4681/2020/09-ART64 $15.00

Publisher Copyright:
© 2020 ACM.


  • Collaborative filtering
  • Top-N recommendation
  • nearly uncoupled markov chains
  • random walks


Dive into the research topics of 'Boosting Item-based Collaborative Filtering via Nearly Uncoupled Random Walks'. Together they form a unique fingerprint.

Cite this