Social bookmarking websites allow users to store, organize, and search bookmarks of web pages. Users of these services can annotate their bookmarks by using informal tags and other metadata, such as titles, descriptions, etc. In this paper, we focus on the task of item recommendation for social bookmarking websites, i.e. predicting which unseen bookmarks a user might like based on his or her profile. We examine how we can incorporate the tags and other metadata into a nearest-neighbor collaborative filtering (CF) algorithm, by replacing the traditional usage-based similarity metrics by tag overlap, and by fusing tag-based similarity with usage-based similarity. In addition, we perform experiments with content-based filtering by using the metadata content to recommend interesting items. We generate recommendations directly based on KullbackLeibler divergence of the metadata language models, and we explore the use of this metadata in calculating user and item similarities. We perform our experiments on three data sets from two di erent domains: Delicious, CiteULike and BibSonomy.
Recommender systems belong to a class of personalized information filtering technologies that aim to identify which items in a catalog might be of interest to a particular user. Recommendations can be made using a variety of information sources related to 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. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
ACM RecSys ’09 Workshop on Recommender Systems and the Social Web October 25, 2009, New York, NY, USA.
Copyright 2009 by the author(s). both the user and the items: past user preferences, purchase history, demographic information, item popularity, the metadata characteristics of the products, etc. Social bookmarking websites, with their emphasis on open collaborative information access, o er an ideal scenario for the application of recommender systems technology. They allow users to manage their favorite bookmarks online through a web interface and, in many cases, allow their users to tag the content they added to the system with keywords. The aggregation of these tags, the folksonomy, is an extra annotation layer connecting users and items. The underlying application then makes all information sharable among users. The success of such websites partly depends on how the connections between users, items, and tags are exploited.
Social bookmarking websites also o er possibilities for
attaching item-specific metadata to each item, such as the item’s title or
summary. This additional metadata could also be used to support
the recommendation process. Using item metadata to boost
performance is not new in recommender systems research, but typically
such content-related information is attached to the items, and is
therefore the same across all users [
In this paper we focus on the question how we can make use the information represented by the folksonomy and the item metadata to boost the performance of traditional collaborative filtering algorithms. We make the following contributions. First, we examine di erent ways of extending the standard nearest-neighbor algorithm with information about tagging behavior. Second, we explore how best to use the metadata for recommendation by proposing four di erent algorithms. Finally, we perform our experiments on publicly available data sets with standardized evaluation metrics to promote verifiability. The remainder of this paper is structured as follows. We start by introducing our data sets and experimental setup in the next section. In Section 3 we describe and compare di erent CF algorithms that operate on the folksonomy to generate recommendations. Section 4 we describe how we exploit the metadata in our data sets to generate item recommendations. We describe the related work in Section 5 and conclude in Section 6. 2. 2.1
We base our experiments on four data sets that were collected from three di erent social bookmarking websites with di erent characteristics: CiteULike, BibSonomy, and Delicious. Two data sets correspond to the domain of Web page bookmarks (Delicious and BibSonomy) and the other two cover the domain of scientific articles (Delicious and BibSonomy).
CiteULike is a social bookmarking service that allows its users to add their academic reference library to an online profile1. Articles can be stored with their metadata, abstracts, and links to the papers at the publishers’ sites. Users can also add personal comments and tags. CiteULike o ers daily dumps of their core database. We used the dump of November 2, 2007 as the basis for our experiments. A dump contains all information on which articles were posted by whom, with which tags, and at what point in time. It does not, however, contain any other item metadata, so we crawled this ourselves from the CiteULike website using the article IDs. Articles are annotated using the standard BibTeX-like fields, such as title, author names, page numbers, publisher information, etc.
BibSonomy is a social bookmarking service for sharing Web
page bookmarks and reference lists of scientific articles2. Items
are stored and represented by their BibTeX metadata
representations. These can include abstracts and links to the papers at the
publishers’ websites. Users are able to tag their bookmarked content
and use these tags to browse and discover related references [
Delicious is a social bookmarking service for storing, sharing, and discovering web bookmarks. It allows its users to manage and tag URLs of web pages4. Unlike CiteULike and BibSonomy, Delicious does not o er data dumps of their databases, so we gathered our data set by crawling a subset of the Delicious website. Because of our focus on the task of item recommendation for users, our aim was to collect a balanced, unbiased set of user profiles, i.e. the complete set of bookmarks a user had posted to Delicious. From an earlier breadth-first crawl of Delicious we obtained a list of 300,000 users. We randomly selected around 18,000 of these users to match the size of our CiteULike data set, and crawled their entire profiles. 2.1.1
It is common practice in recommender system evaluation to
select realistic subsets of the data sets used to ensure that reliable
recommendations can be generated. This also allows for a fair
comparisons of di erent recommendation algorithms [
In order to evaluate and compare di erent recommender
algorithms, we need a proper framework for experimentation and
evaluation. Recommender systems evaluation—and the di erences with
IR evaluation—has been addressed by, among others, [
In our evaluation, we adopt an IR perspective by treating each of
the users as a separate query or topic. The 10 withheld items for
each user constitute the items for which we have relevance
judgments. Herlocker et al. [
We start by establishing some notation and definitions of the task
at hand, based in part on notation by [
In conventional recommender systems, the user-item matrix contains ratings information. These ratings can be explicit, when they are entered directly by the user, or implicit, when they are inferred from user behavior. In our case we have implicit, unary ratings where all items that were added by a user receive a rating of 1. We extract this ratings matrix R(uk; il) for all user-item pairs directly from the tripartite graph. We denote its individual elements by xk;l = f1; ;g. Each user is represented in this matrix as its user profile row vector uk, which lists the items that user added to his or her profile. Items are represented by the column vectors of R which represent the item profile vectors il that contain all users that have added that item. As shown in Figure 1, we can also extract a useritem matrix from D by aggregating over the tag dimension. We then u 1 u K i 1 items i L # users # items # tags # posts user-item sparsity avg # items per user avg # users per item avg # tags per user avg # users per tag avg # tags per item avg # items per tag users u 1 u K
items Σ
D i 1 items i L tags users
R binarize users
UI obtain the K L user-item matrix UI(uk; il) = PmM=1 D(uk; il; tm), specifying how many tags each user assigned to each item. Because we filtered our data sets to include only tagged content, our ratings matrix R is the same as a binary version of UI. Similar to the way we defined UI we can also aggregate the content of D over the user and the item dimensions. We define the K M user-tag matrix UT(uk; tm) = PlL=1 D(uk; il; tm), specifying how often each user used certain tag to annotate his or her items. Individual elements of UT are denoted by yk;m. We define the L M item-tag matrix IT(il; tm) = PkK=1 D(uk; il; tm), indicating how many users assigned a certain tag to an item. Individual elements of IT are denoted by zl;m. We also define binary versions of UT and IT as UTbinary and ITbinary. The row vectors of the UT and IT matrices represent the user tag profiles dk and item tag profiles fl respectively. They list what tags have been assigned by a user to his items, or to an item by its users. Formally, the goal of each of the recommendation algorithms discussed in this paper is to produce a ranking of all items l that are not yet in the profile of the active user uk (i.e., xk;l = ;). To this end, we predict a score bxk;l for each item that represents the likelihood of that item being relevant for the active user. The final recommendations for a user are generated by ranking all items il by their predicted score bxk;l. 3.1
A common and well-understood source of information for
recommendation is usage patterns of adding and rating items. The
class of algorithms that exploit such patterns for recommendation
purposes are called Collaborative Filtering algorithms (CF). In this
paper we focus on using and extending the k-Nearest Neighbor
(kNN) algorithm. We pick the k-NN algorithm because it is a well
understood algorithm that can intuitively be extended to include
other information in addition to transaction patterns [
In the first step of user-based filtering we calculate the
similarities between pairs of users to identify the most similar users for an
active user. Many di erent similarity metrics have been proposed
and evaluated over time, such as Pearson’s correlation coe cient
and cosine similarity [
The next step in user-based filtering is to determine the top N similar users (or items) for user uk. We denote this set as the Set of Similar Users SSU(uk), which are the top N users of the set of all users ua, ranked by their cosine similarity. For each user ua, we only consider those items that ua added to his profile (xa;l , ;). Using this set of nearest neighbors we generate the final prediction scores bxk;l for each unseen item il as bxk;l = Pua2SSU(uk) simcosine(uk; ua). Here, the predicted score of an item il is the sum of the similarity values (between 0 and 1) of all N nearest neighbors that actually added item il (i.e. xa;l , ;).
A recurring observation from the literature about CF algorithms
is that universally liked items are not as useful for capturing the
similarity between users as less common items, see e.g. [
The item-based k-NN algorithm operates analogously to the
userbased filtering algorithm [
The folksonomies present in our four data sets each constitute an extra layer of connections between user and items. We exploit this extra layer for determining another type of similarity between users or items. For instance, users that assign many of the same tags can be seen as similar, and items that are often assigned the same tags can also be seen as similar.
We restrict ourselves to comparing three common similarity metrics: Jaccard overlap, Dice’s coe cient, and the cosine similarity. We use these similarities as the basis for item recommendation. The only di erence between this approach and the standard CF algorithm is in the first step, where the similarities are calculated. For user-based filtering, we calculate tag overlap on the UT matrix or on the binarized version UTbinary, depending on the metric. Both the Jaccard overlap and Dice’s coe cient are set-based metrics, which means we calculate them on the binary vectors from the UTbinary matrix. The Jaccard Overlap simJaccard(dk; da) between two users dk and da is defined as jjddkk\[ddaajj . Dice’s coe cient simDice(dk; da) is defined as 2jdjdkkj+\jddDaajji.ceW’secroeefer to the user-based runs with the Jaccard overlap and cient as ut-jaccard-sim and ut-dicesim respectively. The cosine similarity is calculated in three different ways. First, we calculate it on the regular tag count vectors dk and da from UT as ut-tf-sim, and on the binary vectors from the UTbinary matrix as ut-bin-sim. In addition, we also experiment with idf-weighting of the tags in the user tag count vectors as we did before. We refer to this run as ut-tfidf-sim. The item-based versions of these similarity metrics are calculated on the IT and ITbinary matrices. We refer to these five item-based runs as it-jaccard-sim, it-dice-sim, it-bin-sim, it-tf-sim, and it-tfidf-sim. 3.3
Table 2 compares the results of our baseline CF runs that employ usage-based similarities to the runs that use overlap in tagging behavior as a source of user and item similarity. We see that the user-based filtering baseline outperforms item-based filtering on three of four data sets; only on CiteULike does item-based filtering work better, where this di erence is also statistically significant (p < 0:05). The other di erences between user-based and itembased filtering are not significant. There appears to be no clear or statistically significant advantage to applying idf-weighting to the profile vectors. An explanation for the advantage of user-based filtering is that, according to Table 1, the average number of items per user is much higher than the average number of users per item. Calculating a meaningful overlap between user profile vectors could therefore be more robust than between item profile vectors.
As for the results with tag overlap, we observe that item similarities based on tag overlap work well for item-based filtering, as three of our four data sets show considerable improvements over the best CF baseline runs. Performance increases range from 27% on Bibsonomy Articles to almost 120% on Delicious, but these are only statistically significant on the Delicious data set. We see the opposite trend for user-based filtering, where tag overlap results in significantly worse scores for almost all variants on all data sets, with performance decreases ranging from 40% to 63%. This means that using tag overlap in item-based filtering makes itembased filtering outperform user-based filtering on all four data sets. We believe that it is the reduction in sparsity from using tag overlap that causes this di erence in performance. On average, the number of tags assigned to an item is 2.5 times higher than the number of users who have added the item. This means that, on average, item profile vectors from the IT matrix are less sparse than item profile vectors from the UI matrix, making the possibility of overlap between vectors more likely. Using more values in the similarity calculation leads to a better estimate of the real similarity between two items.
For user-based filtering this di erence is not as well-pronounced: in some data sets users have more items than tags on average, and more tags than items in other data sets. This explains why we do not see the same performance increase for the user-based filtering runs based on tag overlap. The results of the di erent tag overlap metrics tend to be close together and di erences between them are not statistically significant. Even though the best-performing similarity metrics are dependent on the data set, we do see that the metrics operating on the binary vectors from the UTbinary and ITbinary matrices are consistently among the top performers.
In general, it appears that bookmark recommendation is more di cult than article recommendation. We believe this is due to a di erence in topic specificity. The Delicious and Bibsonomy Bookmarks data sets cover bookmarks of web pages, which encompass many more topics than scientific articles do. Users of Delicious and Bibsonomy Bookmarks can be expected to have more di erent topics in their profile, making it more di cult to recommend new, interesting bookmarks based on their profiles. We see evidence for this explanation in the average number of unique tags per user: 203.3 and 192.1 for Bibsonomy Bookmarks and Delicious respectively, which is markedly higher than the 79.2 and 57.3 for Bibsonomy Articles and CiteULike.
In addition to the folksonomic structure of the underlying network, social bookmarking services also o er users the possibility to annotate the content of their items with metadata. In this section we investigate the role such metadata can play in recommending interesting bookmarks or references. We propose two di erent approaches: content-based filtering and hybrid filtering. Before we move on to describing these in Sections 4.1 and 4.2, we first take a closer look at the metadata we have available.
In our approach we distinguish between item-intrinsic and itemextrinsic metadata. Item-intrinsic metadata fields relate directly to the content of the item being annotated. For the two data sets dealing with web bookmarks these include DESCRIPTION, TAGS, TITLE, and URL. The two scientific article data sets contain the additional intrinsic fields ABSTRACT ,AUTHOR, BOOKTITLE, EDITOR, JOURNAL, NOTE, and SERIES. The intuition behind assigning metadata fields to the item-intrinsic category is that these fields can be used as standalone sources for recommending other content. For instance, given a certain paper from a user’s profile, papers with similar abstracts, papers written by the same author, or papers published at the same workshop are likely to be relevant recommendations. In contrast, item-extrinsic metadata fields—such as MONTH or PAGES—cannot be used to directly generate appropriate recommendations. We performed experimental runs using the metadata of each of our intrinsic fields separately. In addition, we experimented with the combination of all intrinsic fields, and with runs that combined all intrinsic and extrinsic fields, resulting in a total of 34 runs per algorithm. We did not test the extrinsic fields separately. Due to space restrictions we only report the results of the best runs for each algorithm. 4.1
The first approach we propose is content-based filtering where the focus is on properly representing the content in our social bookmarking data sets. Based on these representations our aim is to construct an interest profile of an active user, and then use this profile to rank-order the unseen items by similarity to the profile, thereby approximating possible interest in those items. Figure 2 illustrates two di erent algorithms we propose for content-based filtering: profile-centric matching and post-centric matching.
The di erence between our two content-based filtering algorithms is the level of aggregation. In our profile-centric matching approach, we collate all of a user’s assigned metadata into a single user profile. The intuition here is that by aggregating all of the metadata assigned by a user we can completely capture his or her interests. Similarly, we construct item profiles that collate all of the metadata assigned to those items by all users in the training set. We then match the active user profiles against the item profiles on similarity to produce a ranking of all items, as illustrated in the top half of Figure 2. After removing the items already in the active user’s profile, we are left with the final rank-ordered list of recommendations.
In contrast, post-centric matching operates on the level of
individual posts. We match each of an active user’s posts separately
against all the other posts of unseen items in the training set, as
illustrated in the bottom half of Figure 2. This leads to a list of
matching posts in order of similarity for each of the active user’s
posts. Since retrieval scores are not directly comparable between
runs, we normalize the original similarity scores simorg into [
In both content-based filtering algorithms, we approach the
recommendation process from an IR perspective and restrict ourselves
to measuring textual similarity. We use the open-source retrieval
toolkit Lemur to calculate the similarities between the di erent
user and item profiles. The Lemur toolkit5 implements di erent
retrieval methods based on language modeling [
In addition to focusing solely on using the metadata for
recommendation, we also consider a hybrid approach that joins
contentbased filtering and CF, in the hope of combining the best of both
worlds. Many di erent combination methods have been proposed
in earlier work [
Hybrid filtering also consists of two steps: (1) calculating the most similar neighbors of the active user or his items, and (2) using those neighbors to predict item ratings for the active user. The latter prediction step is performed in the same manner as described 5Available at http://www.lemurproject.org earlier in Section 3.1. As in CF, with our hybrid filtering algorithms we also distinguish between user-based filtering, where we generate recommendations by determining the most similar users, and item-based filtering, where we recommend the items most similar to the items in the active user’s profile. Like in Section 4.1, we approach the first step from an IR perspective and calculate the textual similarities between users or items. For each user and each item we generate user and item profile representations, constructed as follows. All of the metadata text of a user’s posts is collated into a single “user profile” for that user. Similarly, for the item-based approach we create item profiles for each item by concatenating all of the metadata assigned to that item by all the users who have the item in their profile. This means that items are represented by their aggregated community metadata and not just by a single user’s data. Again, we used the open-source retrieval toolkit Lemur to calculate the similarities between the di erent metadata representations, with the same experimental settings as described in Section 4.1. 4.3
Table 3 contains the best runs for each of the four metadata-based algorithms, as well as our best CF run from Section 3. What we see, is that on three out of four data sets a recommendation algorithm that uses metadata is better than the best CF run using data from the folksonomy. All of our best metadata runs use the combined metadata fields. On their own, each field can be seen as an imperfect representation of the items and users, but combined they alleviate each others weak points and better represent the content than they do separately. Only on the Delicious data set do all metadata-based approaches perform significantly worse than the CF runs. Unfortunately, we do not have an explanation for this. When we compare the metadata-based approaches with each other, we see that most di erences are not statistically significant. On the Bibsonomy Articles data set, the item-centric hybrid filtering approach is significantly better than the user-centric approach (p < 0:05). On the CiteULike data set, the profile-centric approach also significantly outperforms the post-centric and user-centric approaches.
In general, we observe that the profile-centric approach tends to outperform the post-centric approach on three of our four data sets. This improvement is statistically significant for the CiteULike data set with an improvement of 117% (p < 10 6). Only on the Delicious data set does post-centric matching perform significantly better (p < 0:05). This advantage of the profile-centric approach is strongest on the article data sets where the profile-centric approach performs best for 75% of the all runs with di erent fields. In the case of hybrid filtering, the item-centric approach outperforms the user-centric approach on three of our four data sets. On the CiteULike and Bibsonomy Articles data sets these di erences are statistically significant and especially large at 268% (p < 0:05) and 112% respectively (p < 0:01).
While we do not have room to report the results of all individual intrinsic field runs, we can report on our general findings. For all four approaches, the best-performing single fields are AUTHOR, DESCRIPTION, TAGS, and TITLE, which provide the best individual results on all four data sets for all approaches. This is not surprising, as these fields are the least sparsely filled of all the intrinsic fields. In addition, these four fields are also aimed directly at describing the content of the items, more so than the conference or journal titles or the editors. Another interesting observation is that the TITLE field served as a better source of user and item similarity on the article data sets than on the bookmark data sets. This is because titles assigned to bookmarks are more variable than titles assigned to scientific articles, leading to this performance gap.
One of the first approaches to recommendation for social
bookmarking websites was presented by [
There have also been several adaptations of memory-based
algorithms that include information about the tags assigned by users to
items. Approaches that resemble our use of tag overlap for
calculating similarities between users and items include [
Symeonidis et al. [
While a significant amount of research has focused on
Collaborative Filtering for recommending interesting items, there has also
been considerable work on content-based filtering, which can be
seen as an extension of the work done on information filtering.
Content-based filtering has been applied to many di erent domains.
Early work on content-based filtering included the NewsWeeder
system by Lang et al. [
We are not the first to suggest the combination of CF with
contentbased filtering, as the advantages of both approaches are largely
complementary. CF is the more mature of the two approaches and
works best in a situation with a stable set of items and a dense user
base. Content-based filtering methods are better at dealing with
sparse, dynamic domains such as news filtering, and are better at
recommending for non-average users. Basu et al. [
In this paper we have presented a range of collaborative and content-based approaches to item recommendation on social bookmarking websites. Our algorithms were evaluated on four realistic data sets of di erent domains, and compared to two external, stateof-the-art approaches. Let us step back now and take stock of our findings. Tags represent an additional layer of information in the folksonomy that binds users and items together. These tags can be used successfully to improve the recommendations of standard nearest-neighbor algorithms, but this depends on the algorithm. For item-based filtering, using tags for calculating item similarity alleviates sparsity and results in better performance. At the user level, however, tags do not o er the same benefits.
Metadata can also be used successfully to generate item recommendations for social bookmarking websites. While the best approach seems to be dependent on the data set and the domain, aggregating all of the intrinsic metadata at the user and item level results in algorithms that outperform the algorithms using only information from the folksonomy.
For future work, we intend to examine the benefits of data fusion.
The tag-aware fusion approach by Tso-Sutter et al. [
The work described in this paper was funded by SenterNovem / the Dutch Ministry of Economics A airs as part of the IOP-MMI À Propos project, and by the Netherlands Organization for Scientific Research as part of the NWO Vernieuwingsimpuls program.