This paper describes our approach to the challenge of graphbased tag recommendation in social bookmarking services. Along the ECML PKDD 2009 Discovery Challenge, we design a tag recommender that accurately predicts the tagging behavior of users within the Bibsonomy bookmarking service. We nd that the tagging vocabularies among folksonomy users di er radically due to multilingual aspects as well as heterogeneous tagging habits. Our model overcomes the prediction problem resulting from these heterogeneities by translating user vocabularies, so called personomies, to the global folksonomy vocabulary and vice versa. Furthermore we combine our user-centric translation approach with item-centric methods to achieve more accurate solutions. Since our method is purely graph-based, it can also readily be applied to other folksonomies.
Over the last years, social bookmarking services, such as Delicious3, Bibsonomy4
and CiteULike5, have grown rapidly in terms of usage and perceived value. One
distinguishing feature provided by these services is the concept of tagging - the
labeling of content with freely chosen keywords (tags). Tagging enables users to
describe and categorize resources in order to organize their bookmark collections
and ease later retrieval. Social bookmarking services are therefore the classic
example of collaborative tagging communities, so called folksonomies [
Most folksonomy solutions assist users during the bookmarking process by recommending tags. Thus, a user can select recommended tags from various sets in addition to entering tags manually. Despite their positive e ect on usability, these recommenders are e ective tools to limit tag divergence within 3 http://delicious.com 4 http://bibsonomy.org 5 http://citeulike.org 6 http:// ickr.com 7 http://www.youtube.com folksonomies as they are generally considered to lower the ratio of misspellings and to increase the likelihood of tag reassignments. The design of a folksonomy tag recommender was one of the tasks of the ECML PKDD 2009 Discovery Challenge8. In the following sections, we describe our solution to this task as submitted.
Our approach is based on the observation that the tag vocabularies of users, their personomies, di er within a folksonomy. This heterogeneity is mainly caused by di erences in the tags users constantly assign to categorize content and the multilingualism of the user base, as apparent for Bibsonomy. To overcome the problems caused by this heterogeneity, we propose a tagging model that translates the personomy of each user to the folksonomy vocabulary and vice versa. We nd that our model is highly accurate as it characterizes an item by its tag spectrum before translating this spectrum to a user's personomy. We then combine the translational model with item-centric tag models to improve performance.
This paper is structured as follows: The introductory section presents a graph model for the underlying data structure and explains the actual goals of the challenge. This is followed by an analysis of di erent properties of the Bibsonomy dataset with respect to their impact on tag recommendation. Section 3 introduces and discusses the tag vocabularies found within folksonomies, before we present our recommendation algorithm and evaluation results. 1.1
According to [
The ECML PKDD 2009 Discovery Challenge consists of di erent tasks related to the problem of tag recommendation. Testbeds for all tasks are di erent snapshots of the Bibsonomy bookmarking service. Our solution contributes to the task of "Graph-Based Recommendations (Task 2)\ as it does not consider the content of the given resources. The recommendation task in this setting resembles the problem of link prediction within G given a user and an item node. The recommender thus needs to estimate P (tji; u), the probability of observing a given tag when a combination of user and item has been observed. 8 http://www.kde.cs.uni-kassel.de/ws/dc09 1.3
One of the rst works on tag recommendation in folksonomies is [
Further related work was presented by the participants of last years challenge
on tag recommendation. The authors of [
The Bibsonomy bookmarking service allows its users to bookmark URLs and publications in parallel. This hybrid approach makes Bibsonomy di erent from other bookmarking communities such as Delicious or CiteULike. For each web bookmark, participants are given the URL, the title and an optional description of the resource as provided by the user during the bookmarking process. Bookmarked publications generally come with information about the title, the authors, the abstract or other common bibliographic attributes. The completeness of this information is not guaranteed, and many attribute elds are left empty. Table 1 gives an overview of the node statistics found within the dataset for p-core levels one and two9.
For the construction of our recommender we ignore the meta-data attached
to the bookmarked content and only consider the graph G. Furthermore, we do
not distinguish between URLs and publications, but merge both node sets to
the item set I. Both decisions result in a loss of information which potentially
9 The p-core of a folksonomy graph has the characteristic that all contained nodes
appear in at least p bookmarks. See [
102node degree (a) 1-core 103 104 105 101
102node degree (b) 2-core 103 104 105 reduces the overall accuracy of our recommender. However, we believe this loss to be compensated by the general applicability of our approach and the improved validity of the presented results.
Figure 1 shows the node degree distributions of the full dataset and its
2core. As previously reported for other folksonomies (e.g. [
As users bookmark items only once10, we cannot estimate P (tji; u) directly from previous observations. Instead, we base our estimates on other distributions. The most basic sources are the overall tag distribution and the tags previously assigned by the user, or to the item.
Global tag distributions. This is the distribution of all observed tag assignments within the training data. By de nition, each tag of the test data has 10 Note that a small percentage of user item combinations found in the given dataset occur in more than one bookmark.
to occur within this distribution. A recommender that only considers the global tag distribution would assume P (tju; i) P (t). We will refer to such a recommender as MostPopular recommender.
Item tag distributions. This is the distribution of previously assigned tags
for a given item. It was shown that the tag distributions of items converge
to a characteristic tag spectrum over time. Furthermore, as reported by [
User tag distributions (Personomies). Each user develops his own
vocabulary of tags over time called his personomy. Users will generally be interested
in reassigning previously used tags as this will simplify content search later
on. The interest in tag convergence often results in the frequent assignment
of a limited number of category tags, and it was shown that user
vocabularies develop power law characteristics over time [
The authors of [
The design of our tag recommender is based on two intuitive assumptions:
1. Tags are personalized. Di erent users will assign di erent tags to the
same item. This e ect cannot only be explained by statistical variance.
Instead, we nd users developing their own category tags over time. One of the
implications for the tag recommendation task is the problem of
recommending the right version of a tag, especially in cases where synonymous tags
exist. This includes di erent spellings, such as "web20\ versus "web2.0\.
Even though semantically equal, these will be di erent for a user who
assigns tags for content categorization. Furthermore, especially in multilingual
folksonomies, we nd that users often assign keywords from their mother
tongue. This is of particular importance for Bibsonomy, where many users
seem to come from Germany, with the e ect that the tag distribution is a
mixture of German and English words. Whereas some users tagged a site
as "searchengine\ related we also nd the German translation
("suchmaschine\) among the frequent tags.
2. Tags describe items. The authors of [
These assumptions directly in uenced the basic design decisions for our recommender which suggests tags from a user's personomy with respect to the community opinion about the underlying item. 4.1
We assume that each user has a distinctive vocabulary of tags. These tags can be translated to the community tag vocabulary by looking at co-occurrences within the shared item space. We are thus interested in the probability P (tujt; u) that a user will assign a tag tu from his personomy as next tag given that the item was tagged as t by another user. Based on previous knowledge about the users tagging behavior we can estimate P (tujt; u) as (1) (2) P (tujt; u) = X P (tuji; u)P (ijt);
i2Iu where Iu is the set of items previously bookmarked by the user. Based on P (tujt; u) we can now translate the global folksonomy language to the personomy of a user.
For the recommendation task we are interested in the probability P (tuji; u) for previously unseen user item combinations. For a new item with an observed tag vocabulary of P (tji), the probability that a user will assign one of his tags next is given as
P (tuji; u) = X P (tujt; u)P (tji):
t2Ti
Note that Ptu2Tu P (tuji; u) = 1 is only true if all tags in Ti have a mapping in Tu which is rather unlikely. Instead we expect Ptu2Tu P (tuji; u) to decrease the more the given item deviates from the items previously bookmarked by the user. 4.2
The tag recommender we propose, selects tags coming from three sources: the personomy of a user where tags are weighted by P (tuji; u), the item vocabulary (P (tji)) and the global vocabulary (P (t)). Including the item vocabulary is important, as many tags may be item speci c and are thus unlikely contained within the personomy. We also include the global tag distribution P (t) for cases where little is known about user and item alike. We assume a weighted linear combination of sources and estimate P (tji; u) as
P (tji; u) uP (tuji; u) + iP (tji) + (1 u i)P (t); (3) with 0 u; i; u + i 1. We then recommend the N tags with highest probability P (tji; u), where N is a parameter that needs to be optimized together with u and i. Optimization can take place on a global or a user-centric scale. Global optimization. For the globally optimized model, we assume equal parameter settings for all users. As the Bibsonomy dataset is rather small, we can use a brute-force approach to nd the combination of N , u and i that maximizes the F-measure. We do so by performing a 10-fold cross-validation on the training data. We call this user-centric tag recommender with global optimization U CG.
User-centric optimization. As users are heterogeneous, it is not intuitive to assume shared parameter preferences. Instead, it seems straightforward to optimize parameters for each user separately. Once again, we do so by performing a cross-validation on the training data. We then use a brute-force approach to nd the combination of N , u and i that maximizes the F-measure of each user averaged over all folds. We will refer to the user-centric tag recommender with local optimization as U CL. 5
We trained the models of all recommender types on the 2-core version of the dataset. The parameters of the MostPopular2d, U CG and the U CL models were ne-tuned in a 10-fold cross-validation as described above. For the MostPopular2d recommender we found an value of 0:5 to perform best. For the usercentric tag recommender with global optimization the maximal F1 measure was achieved when setting u = 0:6 and i = 0:4. The weight of the global tag distribution thus resulted 0 which means that including the global vocabulary did not yield performance gains. For the MostPopular2d as well as the U CG recommender the best number of tags to recommend was 5. Evaluating the accuracy of all recommender types during the cross validation, we found the user-centric tag recommender with local optimization (U CL) to constantly outperform all other versions. We therefore submitted the predicted tags of the U CL approach as our solution to the challenge.
The released test dataset consists of 778 bookmarks from 136 users linking to 667 items. Table 2 presents the achieved F1 measures on the rst ve ranks for the various recommender types. The U CL recommender we submitted achieved a performance of 0:314. This result is somewhat disappointing as it is only slightly above the result of the simpler M ostP opular2d recommender. However, we nd that the approach of vocabulary translation is generally superior as the results of the U CG recommender are signi cantly better. We observe similar performance patterns when looking at the precision/recall curves plotted in Figure 2.
Investigating the reasons for the weak performance of the U CL recommender, we nd that the user distribution of the test set deviates from the trained one as shown in Figure 3. This deviation is likely to have a negative impact on the prediction quality as parameters have been tuned in expectation of a user distribution similar to the one of the training set. However, this problem is not 0.5 0.45 0.4 0.35 0.3 n o i ics0.25 e r P 0.2 0.15 0.05 00 UCG UCL MostPopular2dα=0.5 MostPopular2dα=0 MostPopular2dα=1 MostPopular 0.05 0.1 0.15 0.2 Recal 0.25 0.3 0.35 0.4 0.45 Fig. 2. Precision/Recall curves for various recommenders on the provided test data. The curve of the U CL recommender appears "shorter\ as this recommender suggests a variable number of tags.
0.12 0.1 unique to the U CL recommender but is expected to have a negative impact on the performance of all recommender types. Instead, we believe that the weak performance of the U CL recommender is caused by an inadequate parameter tuning for users less present in the training data but frequent in the test set. Tuning u, i and N for these users often results in bad estimates due to missing data. Whereas the implications of these shortcomings are rather minor when users are distributed as in the training data, they seem to become major for the test distribution.
The fact that the test set is dominated by users with rather small training vocabularies is also re ected by the performance of the M ostP opular2d recommenders with set to 0 and 1 as shown in Figure 2. Here, we nd that a recommender which only suggest tags from a user's personomy ( = 1) performs very bad, whereas an item based recommender ( = 0) achieves nearly as good results as the mixture model = 0:5. This implies, that most tags of the test data are not present within a user's personomy at training time or, less likely, that the tagging behavior of users drastically changed in the test phase.
The inadequate modeling of infrequent users (and items) is an expected shortcoming of a purely graph-based recommendation approach. This is especially true for our personomy translation approach which requires the tags of the given item to have a mapping within the conditional distribution P (tujt; u) (see equation 2). Incorporating the provided item meta-data may be a promising alternative to improve accuracy in scenarios where little is known about users and items from a graph perspective.
In this paper, we presented a novel approach to the challenge of graph-based tag recommendation in folksonomies. Building on the assumption that all users of a folksonomy have their own tag vocabulary, our approach translates the personomies of users to the global folksonomy vocabulary. Evaluation results show that this translation helps to signi cantly improve tag prediction performance. Furthermore, we ne-tuned our model by estimating parameters on a per user basis. Even though this user-centric approach performed rather disappointing during the challenge, we believe that user-level optimization will be essential for the success of future (tag) recommenders.