Tastelink paper #1: Random Walks Method for Taste Based Recommendations
A layman’s introduction to the research presented in: Maarten Clements, Arjen P. de Vries and Marcel J. T. Reinders, The Task Dependent Effect of Tags and Ratings on Social Media Access. ACM Transactions on Information Systems, 28 (4), October 2010.
Search and recommendation are two fundamental technologies in the backbone of today’s internet experience. They are closely related, as is perhaps easiest grasped when thinking of recommendation as a search where the query is implicit, based on what we observed from the user’s history. Considering this view, it may not come as a surprise that their core algorithms have always had much in common. Here, we look into random walks over graphs as a cornerstone technology for creating recommendations online.
The key idea is straightforward. We start out by representing our data as graphs: nodes connected by edges. This data representation is particularly relevant for recommenders, as we can treat multiple types of nodes uniformly – in the TOIS paper the nodes correspond to the users, items and tags present in a crawl of LibraryThing (a social network where users share a love of books).
Recommendations are then made by assigning to each of the nodes a score, determined by walking at random over this graph structure. In essence, we simply count the number of times a node is visited when we randomly move along the graph structure. The starting nodes are selected based on the type of recommendation problem that is solved; when we recommend content to a user, we start walking from the target user node, a personalized search is realized by also activating the nodes of tags occurring in the user’s query, and a tag recommendation starts from both the user and item nodes.
The use of random walks over graphs is similar in spirit to Google’s PageRank – which measures a web page’s importance by the other important pages that point to it – as well as earlier approaches in bibliometrics, sociology and economics. The approach is however adapted to the specific context of recommendation, where we personalize the random walk to a specific target user, and prefer new content, not yet known to the user, to be considered for recommendation.
Previous applications of random walks, including PageRank, have considered the state of the graph after infinitely long walks – resulting in a popularity based ranking of all the nodes. Based on our experiments, we conclude however that PageRank and its adaptation for recommendation (personalized PageRank) are sub-optimal when we want to recommend new items, not yet known to the user – almost all of the probability mass is assigned to those items already seen. An improved solution is found by making shorter walks over a modified graph structure, where nodes are extended with self-transitions (this alternative to using infinite walks has previously been found useful to improve image search with suggestions derived from click logs). The slow diffusion of a walk with high self-transition probability ensures that most of the probability mass does stay close to the starting nodes, while all nodes can be reached – realizing a desirably soft clustering effect of the original historic data.
The TOIS paper discusses in detail how the graph and algorithm can be setup to make recommendations of items, tags as well as users. Using historic data to evaluate, we carried out experiments with the previously mentioned LibraryThing crawl, the well-known Movielens dataset(s) as well as a dataset provided by Bibsonomy.
Not only did we find competitive recommendation accuracy when compared to previous approaches, we could also shed some light on the relative importance of tagging and rating to achieve good recommendations. An important result is that a user’s personally created tags rarely contribute to improved content recommendation – the tags that other people assign to your content are most helpful when making predictions on held-out data. Both rating and tagging contribute to better recommendations.
Longer walks exhibit a stronger clustering effect, which seems particularly beneficial for users with relatively short profiles (who, arguably, could benefit the most from getting recommendations, as they still need to get to know the collection).
Why does it matter?
The particular approach to recommendation that we discussed is motivated by the flexibility of the graph data representation: the basic algorithm, to perform random walks over the graph, is agnostic of the types of nodes that we consider.*
We can therefore easily extend the graph structure with, for example, item genre information or, the specific interest of Tastelink, user taste: simply add nodes to represent genre or taste, and connect items or users to their genre or taste nodes. Because the random walks take “new routes” through the graph, the genre or taste information is automatically taken into account when making new recommendations.
What is particularly useful is that the structure of the graph can follow our understanding of the world, letting us explain the results of the random walks in terms of that structure – a huge benefit over previous approaches to recommendations over heterogeneous types of nodes. Our ultimate goal is to find a method that makes recommendations across domains. While it is impossible to predict whether this particular setup will lead to successful cross-domain recommendations, the choice for a graph-based representation and algorithm eases experiments into this direction.
*Obviously, this is not a silver bullet – we do need to determine the transition probabilities for each pair of node types from historic data.