Tag recommendation is a major aspect of collaborative tagging systems. It aims to recommend tags to a user for a given item. In this paper we propose an adaptation of the search algorithms proposed in [14, 1] to the tag recommendation problem. Our algorithm, called STRec, provides networkaware recommendations based on proximity measures computed on-the-fly in the network. STRec uses a bounded search to find good neighbors. On top of STRec, we apply a re-ranking scheme that improves the quality of the recommendations. We update the ranking according to the degree of association between the higher ranked tags and the lower ranked ones. This technique leads to better recommendations as we show in this paper and could be applicable on top of many recommender systems. The experiments we did on several datasets demonstrated the efficiency of our approach.
Social (i.e. collaborative ) tagging is the practice of
allowing users to annotate content. The users can organize, and
search content with annotations called tags. The growth of
popularity of social media sites has made the area of
recommender systems for social tagging systems an active and
growing topic of research [
Tag recommendation aims to infer the most suited tags to a
user for tagging a given item. It is a salient part of the Web
2.0 where applications are user-centered. We present, in
this paper, an efficient tag recommender algorithm named
STRec. Our algorithm adapts the search algorithms
proposed in [
A folksonomy is a system of classification that allows users to annotate and categorize content by the way of creating and managing tags. It is related to the event of social tagging systems1 and can be defined as a collection of: a set of users U , a set of tags T , a set of items I, and a ternary relation between them S ⊆ U × I × T .
A tagging triple (u; i; t) ∈ S means that user u has tagged an item i with the tag t. A user can tag an item with one 1http://en.wikipedia.org/wiki/Social bookmarking or more distinct tags from T . We denote by T (u; i) the set of all distinct tags used by a user u to tag an item i
T (u; i) = {t ∈ T |∃(u; i; t) ∈ S} On top of this folksonomy, we consider an undirected weighted graph of users G = (U; E; ) called the social network. In G, the nodes represent the users and is a function that associates to each edge e = (u; v) ∈ E a value, (u; v) ∈ [0; 1], called the proximity (or social) score between u and v. We assume that a user can tag an item with a given tag at most once. The interest of a tag t for a given user u and an item i can be estimated by a score function score(t|u; i). The score function depends on the recommender’s model. Then the ”Top-K” highest scoring tags are recommended by T op(u; i; K) = argKmax score(t|u; i)
t∈T
We first present the score function and the extended
proximity we use in our algorithm, as they were defined in [
They model for a user, an item, and a tag triple (u; i; t), the score score(t|u; i) of tag t for the given user u and item i by score(t|u; i) = h(f r(t|u; i)) where f r(t|u; i) is the overall tag’s frequency of tag t for user u and item i, and h is a positive monotone function. The overall tag’s frequency function f r(t|u; i) is defined as a combination of a network-dependent component and an item-dependent one, as follows: f r(t|u; i) = × tf (t; i) + (1 − ) × sf (t|u; i) (3) The first component, tf (t; i), is the tag’s frequency of t for i, i.e., the number of times i was tagged with t. The sf component stands for social frequency, an important measure that depends on the neighborhood of user u. In Equation 3, the parameter allows to tune the relative importance of the social component with respect to tag’s frequency. When is valued 1, the score becomes network-independent. Reversely, when is valued 0 the score depends exclusively on the social network. Let us notice that we use, as a social network, a similarity network (weighted graph) inferred from the tagging behaviour of the users. The weight associated to each edge is a value between 0 and 1 representing the degree of similarity between two users.
Considering that each user brings her own weight (proximity) to the score of a tag, the measure of tag’s social frequency is defined as follows: sf (t|u; i) =
∑ v∈{U|(v;i;t)∈S} (u; v) (4) In this formula, v stands for a neighbor of user u who tagged item i with tag t, and (u; v) is the proximity (edge weight) between u and v.
Extended proximity. The above scoring model takes into
account only the neighborhood of a given user (the users
directly connected to her). But, this can be extended to deal
also with users that are indirectly connected to this user,
following a natural interpretation that user links (e.g.,
similarity) are, at least to some extent, transitive. An extended
proximity + can be deduced from for any pair of users
connected by a path in the network. Then, + can replace
in the definition of social frequency considered before
(Equation 4), yielding an overall tag scoring scheme that depends
on the entire network instead of only the directly connected
neighbors. In the rest of the paper, we consider this
extended proximity and denote by user’s proximity vector, the
list of all her neighbors v (of course we consider (u; v) > 0)
ordered in descending order of their proximity values.
The STRec algorithm, as the TOPKS algorithm proposed in
[
Inspired by studies in the area of trust propagation for belief
statements, the weights on a given path p = (u1; :::; un)
between u1 and un is aggregated by multiplying them [
(ui; ui+1) i The multiplication function is monotonically decreasing over any path it is applied to, when draws values from the interval [0; 1]. Thus given a social network G and a path p = (u1; :::; un) ∈ G, we have +(u1; :::; un−1) ≥ +(u1; :::; un). We can define + for any pair of connected users (u; v) in the network by taking the maximal weight over all their connecting paths. More formally, +(u; v) is defined as +(u; v) = max { +(p)|u →p v}
p∈G
A greedy approach is applicable to allow browsing the
network of users on the fly, at recommendation time, visiting
them in the order of their proximity with respect to a given
user (for whom we want to make recommendations). More
precisely, by generalizing Dijkstra’s algorithm [
Algorithm 1: Relaxation 1 if ( +(u; x) × (x; v)) > +(u; v) then 2 +(u; v) ← ( +(u; x) × (x; v)) 3 end greedy procedure for iterating over the network is used in our recommendation algorithm.
As already introduced in previous sections, the networkdependent component is an important part of the STRec algorithm.We mostly focus on the computation of the social frequency, sf (t|u; i), as it is a key parameter in the scoring function of tags.
First, a list D of top-k candidate tags is kept and sorted in descending order of their minimal possible scores (we define shortly). A tag becomes candidate when it is met for the first time in a tagged triple.
The algorithm 2 presents the computation of the STRec network-dependent component for a given user u for whom we want to recommend tags for an item i. For each of her (direct or indirect) neighbors v on the social network we retrieve the list of tags this neighbor employed for the item i. Then for each of these tags t , we update its social frequencie sf (t|u; i) and we add it in D, as candidate tags if it is not already in the top-k candidates list (lines 1 to 8). We assume that, for item i, we have an inverted list IL(i) of the tags t used to tag i, along with the corresponding tag frequencies tf (t; i) in a descending order of these frequencies. Starting from the top most frequent tag, this list will be consumed one tag at a time, whenever the current tag becomes candidate for the top-k result (lines 9 to 17). By CIL(i) we denote the tags already consumed in IL(i) (as known candidates), by top tag(i) we denote the tag present at the current (unconsumed) position of IL(i), and we use top tf (i) as a short notation for the tag’s frequency associated with this tag.
By unseen users(t; i) we denote the maximum number of yet unvisited users who may have tagged item i with t . This is initially set to the maximum possible tag’s frequency of i over all tags (a value that is available at the current position of the inverted list of IL(i), as top tf (i)).
Each time we visit a user v who tagged item i with t, we (i) update sf (t|u; i) (initially set to 0) by adding to it +(u; v), and (ii) decrement unseen users(t; i). We obtain the final social frequency value sf (t|u; i) when unseen users(t; i) reaches 0.
Lines 18 to 19 are an important part of the algorithm. We avoid expensive and hardly updatable pre-computations of the proximity values by the relaxation (see Section 3.1). Thus the proximity computation in the social network is computed on-the-fly.
In the rest of this section, we detail the STRec algorithm
Data: (u; i) ∈ U × I, the user u whom we want recommend tags for the item i; v ∈ U , current (direct or indirect) neighbor while scanning the social network 1 forall the tags t ∈ T (v; i) do 2 sf (t|u; i) ← sf (t|u; i) + +(u; v) 3 if t ∈= D then 4 add t to D 5 unseen users(t; i) ← top tf (i) /*initialization*/ 6 end 7 unseen users(t; i) ← unseen users(t; i) − 1 8 end 9 while IL(i) ̸= ∅ AND (t ← top tag(i)) ∈ D do 10 tf (t; i) ← toptf (i) /*t’s frequency in i is now known*/ 11 advance IL(i) one position 12 ∆ ← tf (t; i) − top tf (i) 13 forall the tags t′ ∈ D=CIL(i) do 14 unseen users(t′; i) ← unseen users(t′; i) − ∆ 15 end 16 add t to CIL(i) 17 end 18 forall the users v′ s:t: (v; v′) ∈ E do 19 RELAX(u; v′) 20 end (Algorithm 3). First, let us remind that we maintain a maxpriority queue H whose top element top(H) will be at any moment the most relevant unvisited user on the network. At each step in the network, the top of the queue is extracted (visited) and its unvisited neighbors (adjacent nodes) are added to the queue (if not already present) and then relaxed (Algorithm 1). However, at any time of the running of the algorithm, an optimistic overall score M axScore(t|u; i) of any tag t that has already been seen in D is estimated as: (1 − ) × (top(H) × unseen users(t; i) + sf (t|u; i)) + max(tf (t; i); top tf (i)) × Symmetrically, we estimate M inScore(t|u; i), a pessimistic overall score, as: (1 − ) × sf (t|u; i) +
× max(tf (t; i); partial tf (t)) where partial tf represents the count of visited users who tagged i with t, which is used as a lower-bound for tf (t; i) when it is not yet known. The list of candidate tags D is sorted in descending order by this lowest possible score. An upper-bound score, M axScoreU nseen, for the unseen tags is also estimated using the following value as overall frequency for each tag t:
× top tf (i) + (1 − ) × top(H) × top tf (i)
The running of the algorithm terminates when this
upperbound score and the maximal optimistic score of tags, that
are already in D but not in its top-k, are less than the
pessimistic score of the last element in the current top-k of D
(i.e., D[k]). This is because we have the guarantee that the
top-k can will no longer change as it is explained in [
Data: u ∈ U , i ∈ I: the user u whom we want recommend tags for the item i +(u; v)), 1 forall the (v; i; t) ∈ S do 2 +(u; v) ← −∞ 3 sf (t|u; i) ← 0 4 set IL(i) position on first entry; CIL(i) ← ∅ 5 end 6 +(u; u) ← 0; D ← ∅ /*candidate tags*/ 7 H ← max-priority queue of nodes u (sorted by initialized with u 8 while H ̸= ∅ do 9 CHOOSEBRANCH() 10 if social branch then 11 v ← EXT RACT M AX(H) 12 SOCIAL P ROCESS(u; i; v) 13 else 14 if IL(i) ̸= ∅ then 15 t ← top tag(i) 16 if t ∈= D then 17 add t to D and CIL(i) 18 end 19 tf (t; i) ← top tf (i) 20 advance IL(i) one position 21 else 22 break 23 end 24 25 end if M inScore(D[k]|u; i) > maxl>k(M axScore(D[l]|u; i)) AND M inScore(D[k]|u; i) > M axScoreU nseen then break The CHOOSEBRAN CH() method considers the tag t′, which has the highest potential score, and we choose the branch that is the most likely to refine the score of t′.
t′ = D[argmaxl>k(M axScore(D[l]|u; i)]
We set M axT extual to × top tf (i) if the tag’s frequency
tf (t′; i) is not yet known, and to 0 otherwise. For the
social part of the score, we set M axSocial = (1 − ) ×
unseen users(t′; i) × top(H). Then, we follow the social
branch if M axSocial is greater than M axT extual.
The result re-ordering step
STRec returns a list D of candidate tags sorted in
descending order of their scores. The k first tags of this list (D[
Fixing the first tag t = D[
We chose five datasets from four online systems: del.icio.us2, Movielens3, Last.fm4, and BibSonomy5.
We take the ones of del.icio.us, movielens, and last.fm from
HetRec 2011 [
To evaluate STRec, we used a variant of the leave-one-out
hold-out estimation called LeavePostOut [
T (u; i) ∩ Tˆ(u; i)
Tˆ(u; i) T (u; i) ∩ Tˆ(u; i)
|T (u; i)| precision = recall = 1
∑ precision(u; i) |(u; i)| (u;i) 1
∑ recall(u; i) |(u; i)| (u;i) For each dataset, we average these values over all (u; i) in the test set: and compute the F1-measure value as follows
F 1 = 2 × precision × recall
precision + recall This process was repeated ten times for each dataset (except dc09), each time with another item and the same user, to further minimize the variance. In the sequel, the listed F1measure values are thus always the averages over all ten runs.
4.3.1 Comparison with the results of the Task 2 of
ECML PKDD Discovery Challenge 2009
The Task 2 of the ECML PKDD Discovery Challenge 2009
was especially intended for the methods relying on the graph
structure of the training data. The user, item, and tags of
each post in the test data are all contained in the training
data’s post-core at level 2. There were 21 participants to this
(7)
(8)
(9)
(10)
(11)
task. Table 2 shows the scores of our approach in this task,
compared to the scores of the other participants. STRec
reaches the eleventh place with a score of 0.30566. When we
apply the re-ranking step (STRec++), with adaptive
recommendations length as the others in the challenge, we improve
noticeably our score up to be at the fourth place in the final
result. This corresponds of an improvement of 5.53%, which
confirms the efficiency of STRec++. The next experiment
shows the benefits we gained on the five datasets.
4.3.2 Benefit of sorting candidate tags relatively to
the first of them
As we mentioned in Section 3.2, STRec returns a list of tags
sorted by their lowest possible scores M inScore(t|u; i). The
top-k of this list is the recommendation result that is given
to the user. STRec++ adds a re-ranking step that ensures
some consistency of the vocabulary (i.e. tags’ co-occurence).
Table 3 shows the improvements brought by STRec++ on
all the datasets we used.
We see that the re-ordering phase improves up to 5.6% the
F1-measure of STRec for the datasets dc09 and del:icio:us.
The average benefit is 3.17%. But as one can notice, the
importance of the gain obtained by STRec++ varies from one
dataset to another. This is due to the fact that the
confidence scores we compute in the re-ordering phase depend on
the number of co-occurrences of the tags (co-occurrence with
the highest ranked tag). Therefore, when the users have in
average a small number of posts, they share a few number of
common tagged items which leads to low confidence scores.
Table 4 below confirms this analysis. It shows that for the
datasets where the user’s average number of posts is greater
than 50 (i.e. del:icio:us and dc09), the gain obtained by
STRec++ exceeds 5%. But, this gain remains slight when
the user’s average number of posts is small (e.g., less than
40).
4.3.3 Contribution of the bounded search on the
computation time
In Section 3.2, we talked about the estimation of an
optimistic overall score M axScore(t|u; i) of a tag t that has
already been seen in D and its pessimistic score M inScore(t|u; i).
We also introduced an upper-bound score, M axScoreU nseen,
on the yet unseen tags. This upper-bound score allows us
to determine if an unseen tag may be in the top-k. Our
algorithm terminates when this upper-bound score and the
maximal optimistic score of tags that are already in D, but
not in its top-k, are less than the pessimistic score of the last
element in the current top-k of D (i.e., D[k]). Thus, we are
guaranteed that the top-k can no longer change as exposed
in [
We measured the contribution of this optimisation which
allows us to limit the search space. For this, we executed
STRec without it. In other words, we search and compute
the score of all the tags then we make the top-k. We call
this variant STRec unbounded. Table 5 lists the gains in
terms of execution time obtained by the bounded search on
different datasets. As one can see, the gain is significant.
For instance, it reaches 35 minutes on the dataset lastf m,
where the unbounded search takes 1 hour and 50 minutes.
4.3.4 A weakness of STRec: the non consideration
of user’s tag frequency
As Table 5 shows, the STRec algorithm, as the initial search
algorithms of [
To evaluate the importance of user’s tag frequency, we compared STRec with three baseline tag recommenders. Our first baseline recommender, userPT, computes all user’s tag frequencies then recommends the most frequent tags. The second one, itemPT, uses item’s tag frequencies instead of user’s tag frequencies. Finally the last baseline recommender, userItemPT, computes a linear no-weighted combination of the two previous frequencies.
On Table 6, we can see that STRec outperforms the two first baselines. The network-dependant component of STRec clearly brings some advantages comparing to itemPT which is limited to item’s tag frequency. But, we see that STRec fails to obtain better results than the combined frequencies userItemPT, except on the dc09 dataset. So, we can conclude that user’s tag frequency play a role in this difference. 4.3.5 Importance of the network similarity measure In the previous experiments, the social network is based on a similarity measure between the users. In the following, we try to analyse the impact of the network type (kind of similarity we consider) on the quality of the recommendations. Thus, we used for each training set three different social networks (SNitem; SNtag; SN(item;tag)), based respectively on (i) the Dice coefficient of common items (same item tagged by two users), (ii) common tags (similar vocabulary between two users), and (iii) common couple (tag, item) between the users. Except the case of del:icio:us dataset, the networks built on users’ common tagged items give the best results. In contrast, the networks relying on common tags give the worst results due to probably the fact that the users do not share enough vocabularies (i.e. tags).
Many researchers have investigated graph-based tag
recommenders which rely on links between user, items, and/or
tags, to make recommendations [
In [
Association rules mining can be used to extract from the
folksonomy useful knowledge on the way users assign tags to
items [
In this paper, we presented STRec an algorithm for tag
recommendation, and an optimized variant of the algorithm
STRec++ that improves the quality of the
recommendations. STRec transposes the search algorithm proposed in
[