Tagging resources on the Web is a popular activity of standard users. Tag recommendations can help such users assign proper tags and automatically extend the number of annotations available in order to improve, for example, retrieval e ectiveness for annotated resources. In this paper we focus on the application of an algorithm designed for Entity Retrieval in the Wikipedia setting. We show how it is possible to map the hyperlink and category structure of Wikipedia to the social tagging setting. The main contribution is a time-based methodology for recommending tags exploiting the structure in the dataset without knowledge about the content of the resources.
Tagging Web resources has become a popular activity mainly due to the availability of tools and systems making it easy to tag and also due to the advantage users see in tagging their resources. People can for example get better search results, or they can get new resources recommended based on tags other people assigned. One particular problem is the one of recommending relevant tags to users for resources they have introduced in the system.
Being able to e ectively recommend tags would, rstly, simplify the tasks of the users on the web who want to tag resources (e.g., bookmarks, pictures, . . . ), and, secondly, would allow an automatic annotation of resources that enables, for example, a better search for resources or an improved resource recommendation.
When we want to assign a tag to a resource (or, to predict which tag a user would assign to a resource) a possible approach is to use the most popular tags for the given resource of the given user. Of course, this is not working well because users can tag resources which are di erent and people tag the same resource in di erent ways. For this reason most e ective approaches look at the content of the resources and perform more complex analysis of the structure connecting users, resources, and tags.
Previous approaches focus on the content for resources (e.g., textual content of a web page) or on the structure of the tripartite graph composed of users, resources, and tags. The approaches we propose in this paper do not take into account the content of the resources but only the connection structure in the graph. Additionally, we put more importance on more recent tags with the assumption that users' interests might change over time.
We adapt an algorithm proposed for ranking entities in Wikipedia [
The rest of the paper is structured as follows. In Section 2 we describe the proposed algorithms also showing the correspondence to the Wikipedia setting. In Section 3 we describe the experimental setting and results. In Section 4 we compare our work with previously proposed approaches and, nally, in Section 5 we conclude the paper. 2
In this section we describe the algorithms we designed and used for the graph based task that have been run at Discovery Challenge (DC) 2009. 2.1
Using the Resource-User Graph In both submitted approaches, starting from the input query post (i.e., the posts from the test le) we retrieve the resource it refers to. We call this resource the query resource. For the query resource we retrieve, using the train data, all the users that have annotated it in di erent posts. We call this set of users the direct user set. We then use this set of user as an input for the algorithm and retrieve all tags the users have assigned. In the second algorithm, in addition to the set of direct users, we also retrieve the user neighborhood (i.e., users that used at least once a tag in common with the given user). We then use the reunion of the two user sets as input for recommending tags. We call the reunion of the two user sets, the extended user set. As a third approach we have also retrieved just the tags that have previously been assigned to the resource as baseline for comparison.
As seen in Figure 1, by traversing the post - resource - users graph, we obtain the set of direct users that have annotated the resource given in the query post. The extended user set is obtained by adding also the neighborhood users to the direct user set, see Figure 2. We considered two users as being neighbors if they had common tags.
As a baseline approach we considered the recommendation of the most
popular tags for a resource, where we only kept the tags assigned by the direct users
to the resource of the query post.
The algorithms described in this paper are adapted from those developed for
nding relevant results for Entity Retrieval queries in the Wikipedia Setting [
In the Wikipedia setting we have as input a set of example entities. The goal is to extend such set with other relevant entities. If, for example, the initial set for the query \European Countries" contains Italy, Germany, and France, then the goal is to extend this list with entities such as Spain, Slovenia, Portugal, . . . Our approach is to retrieve other entities based on common assigned Wikipedia categories. We extract two sets of categories, hard categories as direct categories (similarly to the direct user set ) and soft categories from the neighboring entities (i.e., following hyperlinks between Wikipedia articles). As neighboring entities we considered the most frequent entities the example entities linked to (similarly to the extended user set ). In the Wikipedia setting entities link to entities via hyperlinks, and each entity has several categories assigned to it. Following the intuition that tags can get outdated over the years, and, thus, older assigned tags should be weighted less for recommendation, we introduced a time decaying function of posts. Scores are assigned to posts based on the time when they have been issued compared to the time the latest test post has been issued. The time decaying function is de ned by the following formula: (1) (2) (3) postScorei =
T imei with the decaying factor lambda being smaller than 1 and the time di erence being calculated in years. The tag scores are computed based on the tag speci city (i.e., how often they have been assigned) de ned as:
tagSpeci city i = log(50 + tagCounti) Given the di erent user sets for a query post, we extract from the training data the most frequent common tags the users have assigned. The tag score is computed based on the formula: tagScorei =
Pj (postScorej ) tagSpecif icityi where a post j was considered only if it was posted by one of the users from the direct user set for the rst approach and from the extended user set for the second approach. The tags are sorted based on this score and the top ve tags are kept and recommended.
As a baseline, we ranked the tags based on popularity within the resource (i.e., how often a tag has been assigned to a resource) also keeping into account when they had been assigned to the resource, based on the formula: tagScorei = X(postScorej) j (4) 3
Experiments were performed on the DC 2009 benchmark1 in order to evaluate the proposed algorithms.
Starting from the query posts in the test le we recommended for each post the top ve tags using the two described approaches and the baseline. In Figure 3 it is possible to see e ectiveness values for the two approaches when a di erent number of retrieved tags is considered. We can see that the direct user approach performs better. Figure 4 shows the same result with Precision/Recall curves of the two proposed approaches. 1 http://www.kde.cs.uni-kassel.de/ws/dc09
In Figures 5 and 6 we measure the impact of using the time information when recommending the most popular tags for a resource. With a value of 0.9 for , in the time decaying function, the scores were slightly lower than when using just the popularity information (Figure 5). When using a value of 0.95 for , there is a small improvement over the baseline when considering 4 and 5 tags (see Figure 6). We ran experiments also with values smaller than 0.9 for which have shown that Precision and F-measure decrease quite a lot (3% for F-measure with = 0:1). 4
Previous work on tag recommendation mainly distinguish between those looking at the content of the resources and those looking at the structure connecting users, resources, and tags.
Approaches looking at content of resources for tag recommendations are, for example, [5] which looks at content-based ltering techniques. In [6] the authors also look at collaborative tag suggestion in order to identify most appropriate tags.
A speci c area of this eld looks at recommending tags focusing on an individual user rather than providing general recommendation for a resource. In [4] they rst create a set of candidate tags to be recommended and then they
ler it based on the previous tag a particular user has assigned in the past. In
[
In this paper we presented our rst approaches for tag recommendation using graph information. We proposed two approaches, where, given a query post, we retrieve two sets of users. Based on the tags assigned by users in these sets we recommend new tags. The rst set of users, the direct user set, consists of the users that have tagged the resource referred to by the query post. The second set of user, the extended user set, consists of the direct user set as well as the users who are neighbours based on commonly assigned tags to the users in the direct set. The tag scores have been computed keeping into account also the time when they have been assigned.
With the proposed approaches, we evaluated the e ect of the tag posting time. We compared a time dependent ranking to a tag popularity. In the future, we aim at giving a higher importance to the user given in the query post than to the rest of the direct users.
Acknowledgments. This work is partially supported by the EU Large-scale Integrating Projects OKKAM2 - Enabling a Web of Entities (contract no. ICT215032), and LivingKnowledge3 (contract no. 231126) 2 http://fp7.okkam.org/ 3 http://livingknowledge-project.eu/ 4. Marek Lipczak. Tag recommendation for folksonomies oriented towards individual users. In Proceedings of ECML PKDD Discovery Challenge (RSDC08), pages 84{95, 2008. 5. Gilad Mishne. Autotag: a collaborative approach to automated tag assignment for weblog posts. In WWW '06: Proceedings of the 15th international conference on World Wide Web, pages 953{954, New York, NY, USA, 2006. ACM. 6. Zhichen Xu, Yun Fu, Jianchang Mao, and Difu Su. Towards the semantic web: Collaborative tag suggestions. In WWW2006: Proceedings of the Collaborative Web Tagging Workshop, Edinburgh, Scotland, 2006.