Recommendation via Query Centered Random Walk on K-Partite Graph
Cheng, H., Tan, P.-N., Sticklen, J., & Punch, W. F.
IEEE ICDM '07
http://www.cse.msu.edu/~ptan/papers/icdm2007b.pdf
Abstract
This paper presents a recommendation algorithm that performs a query dependent random walk on a k-partite graph constructed from the various features relevant to the recommendation task. Given the massive size of a k-partite graph, executing the query centered random walk in an online fashion is computationally infeasible. To overcome this challenge, we propose to apply multi-way clustering on the k-partite graph to reduce the dimensionality of the problem. Random walk is then performed on the subgraph induced by the clusters. Experimental results on three real data sets demonstrate both the effectiveness and efficiency of the proposed algorithm.
1 Introduction
Recommender systems are tools that automatically filter a large set of items (movies, books, scientific papers, music, jokes, etc) in order to identify those that are most relevant to user’s interest. There are two common strategies adopted for making recommendations—content-based filtering and collaborative filtering. Content-based filtering utilizes the features of an item to determine its relevance whereas collaborative filtering makes its recommendation based on ratings provided by other users with similar interests.
Recently there have been considerable interests in applying graph-based methods for generating recommendations [8]. These methods represent the users and items as nodes of a bipartite graph and employ a Markov chain random walk algorithm to rank the nodes based on their authoritativeness. Random walk approaches are advantageous because they consider the relationships between users and items from a global perspective, as opposed to the local pairwise similarity methods used by standard content-based and collaborative filtering approaches.
Besides information about users and items, other domain features are often available to improve the recommendations. For example, when recommending scientific papers, the additional features include author names, keywords, publication venue, and reference citations of the papers. A natural way for incorporating these multivariate features is by using a k-partite graph. Applying random walk on a k-partite graph however is extremely costly, not only due to the massive graph size but also because the random walk must be guided by the features relevant to each user.
In this paper, we propose a graph-based recommendation algorithm that performs a query dependent random walk on a k-partite graph. We empirically demonstrate the benefits of using the proposed algorithm compared to contentbased filtering, collaborative filtering, and random walk on bipartite graph approaches. To improve its efficiency, we apply multi-way clustering to reduce the dimensionality of the problem. Our clustering approach is based on the idea of decomposing the adjacency matrices of the k-partite graph using the non-negative matrix factorization approach. A query centered random walk is then performed on the subgraph induced by the clusters. Experiments performed on three real-world data sets demonstrate the efficiency and effectiveness of our proposed algorithms.
K-partite graph is the graph whose nodes can be partitioned into k disjoint sets so that no two nodes from the same partition are adjacent.
1. Cluster to group together related nodes of the k-partite graph.
2. Apply the QRank approach.
References
- none