Social tagging is a popular and convenient way to organize information. Automatic tag suggestion can ease the user's tagging activity. In this paper, we exam both content-based and graph-based methods for tag suggestion using the BibSonomy dataset, and describe our methods for ECML/PKDD Discovery Challenge 2009 submissions . In content-based tag suggestion, we propose a fast yet accurate method named Feature-Driven Tagging. In graph-based tag suggestion, we apply DiffusionRank to solve the problem, and get a better result than current state-of-the-art methods in cross-validation.
Social tagging, aka, folksonomy, is a popular way to organize resources like documents, bookmarks and photos. Resource, tag and user are three essential parts in a social tagging system, a user uses tags to describe resources. Tag suggestion system eases the process of social tagging. It can suggest tags to new resources based on previous tagged resources.
To promote related research, ECML/PKDD organizes a open contest of tag suggestion systems, named Discovery Challenge 2009 (DC09 in short). In this contest a snapshot of users, documents and tags in the online bookmarking system BibSonomy is provided. Each team trains their suggestion system on the snapshot, and test the performance on the same test dataset. There are 3 tasks in the contest. Task 1 focuses on suggesting tags by the content of the resources, i.e, content-based tag suggestion. Task 2 focuses on suggesting tags by the tripartite links between resources, tags and users, i.e., graph-based tag suggestion. Task 3 puts the suggestion system into real-life situation by integrating it with BibSonomy website, and see which system predicts the user’s intention best.
In this paper, we describe our methods for the three tasks. For Task 1 and 3, we propose a fast tag suggestion method called Feature-Driven Tagging (FDT). FDT indexes tags by features, where feature can be word, resource ID, user ID or others. For each feature, FDT keeps a list of weighted tags, the higher the weight, the more likely the tag is suggested by the feature. For a new resource, each feature in it suggests a list of weighted tags, the suggestions are combined according to the importance of features to get the final suggestion. Compared to other methods, FDT provides suggestions faster, and the speed is only related with the number of features in the resource(number of words in the content).
For Task 2, we apply two existing methods, most popular tags and FolkRank,
for graph-based suggestion. Furthermore, we propose to use a new graph-based
ranking model, DiffusionRank, for tag suggestion. The method of “most popular
tags” is the simplest collaborative-filtering based methods. It recommends the
most popular tags of the resources used by other users. FolkRank is based on
PageRank [
The paper is organized as follows. Section 2 formulates the problem of tag suggestion. Section 3 introduces our method for content-based tag suggestion. Section 4 introduces our method for graph-based tag suggestion. Section 5 describes the dataset, experiment settings and the result. Section 6 introduces related work on tag suggestion. Section 7 concludes the paper. 2
We adopt the model of social tagging proposed by Jaschke et al [
Resources, users and tags form a graph G = (V, E), where V = U S R S T , and E = {{u, t}, {u, r}, {r, t}|(u, t, r) ∈ Y }. The goal of tag suggestion is to predict the set of tags {t} for a given pair of user and resource (u, r).
In related literature, social tags are also called folksonomy, the pair of a resource and a user is also called a post. 3
In this section, we propose a content-based tag suggestion method named FeatureDriven Tagging(FDT). Briefly speaking, FDT is a voting model, where each feature in the resource votes for their favorite tags, and the final scores of tags are averaged by the importance of the features. Figure 1 illustrates the tagging procedure of FDT, it consists of 3 steps: feature extraction, feature weighting and tag voting. For a resource with content, FDT first extracts features from the content. Features include but are not limited to words, resource ID and user ID. Then, FDT weights each feature by their importance in the resource, we explain different ways to compute the importance of features later in this section. In the voting step, each feature contributes a weighted list of tags, the higher the weight, the more likely we should suggest the tag. Weight of a tag from different features are combined by the importance of each feature, thus creates the final weighted list of tags. In the tagging process, all parameters are indexed by feature, we do not need to iterate over all tags (as in text categorization approaches) or resources (as in neighborhood-based approaches), so it is called Feature-Driven Tagging.
UserID: 264 ResourceID: 43EFAD583EF Power management for portable devices, P2P Bittorrent Tribler, J.A. Pouwelse. We extract features from different sources. Word features are extracted from textual content of resources, we use them to capture the relationship between words and tags. For bibtex, the textual content is title + bibtexAbstract + journal + booktitle + annote + note + description; For bookmark, it is description + extended. We also include simhash1 and the user ID of a resource as a feature. The same publication or website share the same simhash1, we use it to capture the tags assigned by other users. We use user ID as a feature so as to model a user’s preferences of tagging. where |T | is the total number of tags, and ntag(f ) is the number of tags f has co-occurred with. ITF implies that the more tags a feature co-occurs with, the less specific and important the feature is. In FDT, each feature is associated with a weighted list of tags. We denote this as a matrix Θ, where θi,j is the weight of tag tj to feature fi, the size of Θ is |F | × |T |, F is the set of all features. Although Θ is large, it is extremely sparse, so each feature only associates with a small number of tags.
We use three different methods to compute Θ offline, they are co-occurrence count(CC), Mutual Information (MI) and χ2 statistics (χ2). Co-occurrence count is computed by |R| df (f )
+ 1) |T | ntag(f ) + 1) (1) (2) (3) (4)
CC(f, t) = n(f, t)/n(t) where n(f, t) is the number of co-occurrences of feature f and tag t, and n(t) is the total number of occurrences of tag t. CC is a naive way to find the most important tags for a feature.
In MI, we model each feature or tag as a binary-valued probabilistic variable, the value of which means occur in a document(1) or not(0). Then, we can compute the Mutual Information between a feature and a tag by M I(f, t) = X
X p(f ′, t′)log( f′∈f,f¯t′∈t,t¯ p(f ′, t′) p(f ′)p(t′) ) where f ′ = f means feature f occurs in the resource, and f ′ = f¯ means it doesn’t occur, the same is for t′. MI computes the shared information between f and t, the higher it is, the more correlated f and t are.
χ2 has been used for feature selection in text categorization [
N (AD − BC)2 χ2(f, t) = (5)
(A + C)(B + D)(A + B)(C + D) where A = n(f, t), B = n(f, t¯), C = n(f¯, t, D = n(f¯, t¯).
After we get Θ by one of the above methods, we make Θ sparse by picking the largest K values in Θ and set other values to 0. We test K = 30000, 50000 and 100000, as K increases, the F1 measure increases. When K > 50000, the F1-measure doesn’t change a lot, so we use K = 50000 in all experiments. For each row in Θ, we first find the largest value θi,max, then set all values in this row to θi,j = θi,j /θi,max. We compare the performance of these 3 methods in the experiment section.
FDT has low computation complexity when tagging. For a resource with n features, the complexity of tagging is O(nm), where m is the average tags for each feature in Θ. m is usually a small number, in our model it is 4.63 for bibtex and 5.81 for bookmark. Note that the complexity of FDT is not related to the total number of training documents, tags or users. Nearest neighbor methods have to search in the entire training data set, so the complexity is at least O(|R|). Multi-label classifier methods have to train a classifier for each one of tags, so the complexity is at least O(|T |). Furthermore, the model of FDT is related with K, which is around 105, it is small enough to load in the main memory. 4 4.1
The basic idea of graph-based tag suggestion is to construct a graph with users, resources and tags as vertices and build edges according to user tagging behaviors. After building the graph, we can adopt some graph-based ranking algorithms to rank tags for a specific user and resource. Then the top-ranked tags are recommended to users.
To describe the graph-based methods more clearly, we first give some mathematical notations. For the folksonomy F := (U, T , R, Y ), we firstly convert it into an undirected tripartite graph GF = (V, E). In GF, the vertices consists of users, resources and tags, i.e., V = U S R S T . For each tagging behavior of user u assigning tag t to resource r, we will add edges between u , r and t, i.e., E = {{u, r}, {u, t}, {r, t}|(u, t, r) ∈ Y }.
In GF, we have the set of vertices V = {v1, v2, · · · , vN } and the set of edges E = {(vi, vj ) | There is an edge between vi and vj }. For a given vertex vi, let N (vi) be the set of vertices that are neighbors of vi. We have w(vi, vj ) as the weight of the edge (vi, vj ). For an undirected graph, w(vi, vj ) = w(vj , vi). Let w(vi) be the degree of vi, and we have w(vi) =
X
Based on the graph, we can employ various graph-based ranking methods to recommend tags. In this paper, we first introduce two existing methods, including “most popular tags” and “FolkRank”. Furthermore, we propose to use a new ranking model, DiffusionRank, for graph-based tag suggestion. 4.2
We first introduce a simple but effective method for tag suggestion. Some
notations are given as below, which is identical with [
There are variants of “most popular tags” as shown in [
A reasonable variant of “most popular tags” is recommending the tags that globally are most specific to the resource. The method is named as most popular tags by resource: n T (u, r) = argmax(|Yt,r|)
t∈T
Since users might have specific preferences for some tags, which should have
been used by him/her, thus we can use the most popular tags by user. As shown
in [
n T (u, r) = argmax(|Yt,r| × |Yu,t|)
t∈T A(i, j) = ( 0
if (vi, vj) ∈/ E ww(v(iv,jv)j) if (vi, vj) ∈ E (7) (8) (9) 4.3
FolkRank is originally proposed in [
X where P R(vi) is the PageRank value and pvi is the preference to vi. Suppose we have an adjacent matrix A to represent the graph GF: With the matrix, we can rewrite the Equation 9 as: s = λAs + (1 − λ)p (10) where s is the vector of PageRank scores of vertices, and p is the vector of preferences of vertices.
A straightforward idea of graph-based tag suggestion is to set preference to
the user and resource to be suggested for, and then compute ranking values using
PageRank in Eq. (10). However, as pointed out in [
Based on above analysis, we described FolkRank as follows. To generate tags for user u and resource r, we have to: 1. Let s(0) be the stable results of Eq. (10) with p = 1, i.e., the vector composed by 1’s. 2. Let s(1) be the stable results of Eq. (10) with p = 0, but p(u) = 1 and p(r) = 1. 3. Compute s := s(1) − s(0).
Therefore, we can rank tags according to their final values in s, where the topranked tags are suggested to user u for resource r. 4.4
DiffusionRank was originally proposed for combating web spam [
For a graph G = {V, E}, denote fi(t) is the heat on vertex vi at time t, we construct DiffusionRank as follows. Suppose at time t, each vertex vi receives an amount of heat, M (vi, vj , t, Δt), from its neighbor vj during a period Δt. The received heat is proportional to the time period Δt and the heat difference between vi and vj , namely fj(t) − fi(t). Based on this, we denote M (vi, vj , t, Δt) as
M (vi, vj , t, Δt) = γ(fj(t) − fi(t))Δt where γ is heat diffusion factor, i.e. the thermal conductivity. Therefore, the heat difference at node vi between time t + Δt and time t is equal to the sum of the heat that it receives from all its neighbors. This is formulated as: fi(t + Δt) − fi(t) =
γ(fj(t) − fi(t))Δt
X The process can also be expressed in a matrix form: Solving this differential equation, we have f (t) = eγtHf (0). Here we could extend the eγtH as eγtH = I + γtH + γ2t2
γ3t3 H2 +
H3 + · · · 2! 3! The matrix eγtH is named as the diffusion kernel in the sense that the heat diffusion process continues infinitely from the initial heat diffusion.
γ is an important factor in the diffusion process. If γ is large, the heat will diffuse quickly. If γ is small, the heat will diffuse slowly. When γ → +∞, heat will diffuse immediately, and DiffusionRank becomes into PageRank.
As in PageRank, there are random relations among vertices. To capture these relations, we use a uniform random relation among different vertices as in PageRank. Let 1 − λ denote the probability that random surfer happens and λ is the probability of following the edges. Based on the above discussion, we can modify DiffusionRank into 1 f (t) = eγtRf (0), R = λH + (1 − λ) 1
N In application, a computation of eγtR is time consuming. We usually to approximate it to a discrete form f (t) = (I +
R)Mtf (0) f (1) = (I +
R)M f (0) γ M γ M Without loss of generality, we use one unit time for heat diffusion between vertices and their neighbors, we have We could iteratively calculate (I+ Mγ R)M f (0) by applying the operator (I+ Mγ R) to f (0). Therefore, for each iteration, we could diffuse the heat values at each vertices using the following formulation: s = (1 −
)s + γ M γ M
1 (λAs + (1 − λ) 1)
N
where M is the number of iterations. As analyzed in [
Different from FolkRank, in DiffusionRank we set the initial values f (0) for vertices to indicate the preferences. To suggest tags to user u for resource r, we set f (0) = 0, but for fu(0) = 1 and fr(0) = 1. After running DiffusionRank on the tripartite graph, we rank tags according to their ranking scores and the top-ranked tags are suggested to user u for resource r. 5
5.1
We use the given BibSonomy data set to validate our methods, it is a snapshot
of the BibSonomy system until Jan 1, 2009. The data set contains two parts,
bibtex and bookmark. In bibtex, the resources are citation of research papers or
books, with title, author and other information. In bookmark, the resources are
website URLs with a user-provided short description. Additionally, the contest
organizer provide two postcore-2 data sets. In the postcore-2 data sets, the
organizer removed all users, tags, and resources which appear in only one post. The
process was iterated until convergence and got a core in which each user, tag,
and resource occurs in at least two posts. Batagelj et al [
Name #posts #tags #users #words Mean Length Mean #tags/user bibtex 158,912 50,855 1,790 278,106 47.67 60.75 bookmark 263,004 56,424 2,679 293,026 11.83 57.78 bibtex(pcore2) 22,852 5,816 788 48,401 59.21 31.75 bookmark(pcore2) 41,268 10,702 861 47,689 12.23 60.26
To validate and tune our methods, we split each of the four dataset into 5 equal-sized subset randomly, and perform 5-fold cross validation on them. 5.2
We use precision, recall and F1 measure as the evaluation metrics. Precision is the number of correct suggested tags multiplied by the total number of tags suggested. Recall is the number of correct suggested tags multiplied by the total number of tags of original post. F1 measure is a geometry mean of precision and recall, F 1 = 2P recsion × Recall/(P recision + Recall). For each post, we only consider the first 5 tags suggested. To test the performance of our content-based method, we run 5-fold cross validation using the given training data. Additionally, for each fold, we remove all posts in the postcore set from the test data, since posts in postcore will not appear in the final test data. We remove stopwords, punctuation marks and all words shorter than 2 letters from the data set, and convert all text to lowercase. We remove words, resource IDs and user IDs appear in less than 5 post. We treat bibtex and bookmark separately.
We use search-based kNN as our baseline method, this is proposed by Mishne [
We list the mean precision, recall and F1 value for bibtex and bookmark data in Table 2 and 3 respectively. We experimented with the different combination of methods for weighting features and estimating Θ matrix.
In the bibtex dataset, FDT(TFITF+MI) has the similar performance as the search-based kNN methods. In the bookmark dataset, FDT(TFITF+MI) has the best performance, which is 3 percentage better than search-based kNN.
In the training data, the number of post from each user roughly follows the power law distribution, where most users have less than 100 posts, and the top 4 users have 50% of all posts. If we treat all posts as equal, then the model may bias to the preference of several super users. To know the performance of the methods on super users and common users, we run other two experiments. In the first experiment, we train the model using posts from all users, then check its performance on each of the top n users and all the rest users separately. In 1 http://lucene.apache.org the second experiment, we train and test models using only posts from each of the top n users and all the rest users separately. For bibtex dataset, we choose n = 4, for bookmark dataset, we choose n = 5. The results for bibtex and bookmark are listed in Table 4 and Table 5 respectively. In these experiments, we use FDT(TF*ITF+MI) for bibtex data and FDT(TF*IDF+CC) for bookmark data. In the result table, the column Trained(ALL) means all methods are trained on full training data. The column Trained(USER) means each method is trained using only posts from corresponding group of users. In the method name, kNN(2463) means the method used is search-based kNN, and test data set are all post of user 2463, rest means all other users. The same naming rule applies to FDT(xxxx).
For each group of test data, we have 4 different models, they are kNN trained by all users, kNN trained by this group, FDT trained by all users and FDT trained by this user. As the result shows, for groups of super users, kNN-based models have best performance. For common users (the rest group), FDT-based models performs better. This result follows our intuition. In this data set, super users have different tag preference than common users. kNN suggest tags using most similar resources, it is less affected by the overall distribution of resources, so it fits to the . FDT relies on the global statistics of feature-tag relationship, it is less effective to fit a special user’s preference. In practical situation, we can get the best performance by choosing different model for different group of users.
One interesting observation is about the user #2732. When trained with all posts, FDT performs much better(0.6308 vs 0.2300) on #2732 than trained with #2732’s own posts. We examined the posts of #2732, found that many posts contains only three tags: genetic, programming and algorithm, and the number of posts by #2732 is large. When we use all posts to train FDT(TFITF+MI), these three tags have a large Mutual Information value with many features, especially the user id feature “UID-2732”, so FDT can predict tags for posts of #2732 with high accuracy. When trained only with #2732’s posts, the Mutual Information between features and these three tags is much smaller, since these three tags appears everywhere and can be seen as stopwords in tags. Small Mutual Information of these three tags means FDT will make wrong prediction about most posts of #2732, which leads to a decreasing in F1-measure.
For final test, we use FDT(ITF+MI) for bibtex and FDT(IDF+CC) for bookmark. The test data of DC09 has a different distribution with the training data. Most top ranked users don’t appear in the test data. So we removed the top ranked users from the training data, use the rest group of users to train the model for final suggestion. The p/r/f1 on final test data are 0.1388/0.1049/0.1189 respectively. Compared to the cross validation results, the performance dropped a lot on final test data. One reason is that FDT does not suggest tags that are not in the training data. There are 93756 tags in the training data and 34051 tags in the test data, the overlapped tags are only 15194. To achieve better performance, suggesting new tags should be considered in the future. In experiments, we compare the results of three graph-based methods, most popular tags, FolkRank and DiffusionRank.
Here we first demonstrate the results using 5-fold cross validation on training dataset. In Table 6, we show the best performance of various methods on bibtex dataset. In this table, we also demonstrate the performance of the content-based method kNN , which achieves the best result when k = 2. For the method of most popular tags, we use “mpt+resource” to indicate most popular tags by resource, and “mpt+mix” to indicate most popular tags by mixing resource and user. For FolkRank, the best result is achieved when damping factor λ = 0.01 with 100 iterations. DiffusionRank obtains the best result when damping factor λ = 0.85, maximum number of iterations maxit = 10 and diffusion factor γ = 0.1. From the table, we can see that most popular tags by mix achieves the best F1measure, which has the largest precision. While for DiffusionRank, it achieves the best recall.
In Table 7, we show the best performance of various methods on bookmark dataset. kNN achieves the best performance when k = 2. For FolkRank, the best result is achieved when damping factor λ = 0.0001 with 10 iterations. DiffusionRank obtains the best result when damping factor λ = 0.85, maximum number of iterations maxit = 10 and diffusion factor γ = 0.01. Furthermore, we also restrict the scores of suggested tags should be no less than 1/5 of score of first-ranked tags. From the table, we can see that DiffusionRank achieves the best F1-measure, which has the largest precision.
From the above two tables, we find that on the bibtex dataset the method of most popular tags by mix is the best, and on bookmark dataset DiffusionRank achieves the best result. Therefore, for task 2 of rsdc’09, we use the two methods to train ranking models separately on bibtex and bookmark. Using the original result and evaluation program provided by the challenge organizer, we obtain the evaluation results on test dataset, as shown in Table 8. From the table, we find that the absolute values are much smaller than what are shown in Table 6 and 7.
Besides the above analysis, we want to investigate the performance of FolkRank and DiffusionRank as their parameters change.
In Table 9 and 10, we demonstrate the performance of FolkRank on bibtex training dataset and bookmark training dataset as its parameters, the damping factor λ and maximum number of iterations (denoted as “max-it” in tables) change. From the both tables, we find the performance of FolkRank improves as damping factor shrinks, which indicates the effect of preference values are growing larger. That is to say the generalization of FolkRank by passing values iteratively on graphs may harm the performance. Moreover, it seems that the maximum number of iterations of FolkRank does not effect the results significantly.
In Table 11 and 12, we demonstrate the performance of DiffusionRank on bibtex training dataset and bookmark training dataset as its parameters, the diffusion factor γ and maximum number of iterations (denoted as “max-it” in tables) change. Here the damping factor λ is set to 0.85. We also find that the performance of DiffusionRank improves as diffusion factor shrinks, which indicates the effect of initial values is growing larger. Similar to FolkRank, the generalization of DiffusionRank by passing values iteratively on graphs may also harm the performance. It is also the same as FolkRank that the maximum number of iterations of DiffusionRank does not effect the results significantly.
From the experiments on both bibtex and bookmark training datasets, we
can see that DiffusionRank always outperforms FolkRank with some specific
parameters, which is more significant on bookmark dataset. Although in this
dataset, FolkRank does not outperform the method of most popular tags, in [
Furthermore, the number of suggested tags should be specified in advance in
FolkRank and DiffusionRank. However in some conditions, we do not have to
recommend as many tags as specified. For DiffusionRank, we set the maximum
number of suggested tags is 5. If we further require the suggested tags should
have the ranking values no less than 1/5 of the ranking value of the first-ranked
tag, the performance of precision, recall and F1-measure will be improved to
0.3772, 0.3266 and 0.3501 on bookmark training dataset. Therefore, we use the
altered DiffusionRank for the bookmark test set of task 2 in rsdc’09.
Ohkura et al [
Another class of tag suggestion system is based on the links between users,
tags and resources, which does not take the content of resources into
consideration. Since the method of “most popular tags” also does not consider the
content of resources, in this paper we regard it as a member of graph-based tag
suggestion approach. Xu et al [
Recently, a new graph-based ranking method, DiffusionRank [
In this paper, we study the problem of tag suggestion and describe our methods for content-based and graph-based suggestion. For content-based tag suggestion, we propose a new method named Feature-Driven Tagging for fast contentbased tag suggestion. Cross validation on the training data shows that FDT outperforms wildly-used search-based kNN, especially when suggesting tags for long-tail users. For graph-based tag suggestion, we study most popular tags, FolkRank, and propose a DiffusionRank-based method. Experiments show that on bibtex dataset the method of most popular tags by mixing of user and resource performs best, and on bookmark dataset, DiffusionRank outperforms other methods.
Work remains to be done. First, currently we use empirical methods to estimate the parameters for FDT, like CC, MI and ITF. We will consider learn a Θ matrix directly by optimizing a tag-related loss function. Second, evaluation using final test data of DC09 shows that the F1 value drops a lot than cross validation on the training data, especially for content-based methods. This suggests we should pay attention to out-of-vocabulary tags. Third, more information should be considered, such like time-stamp, to suggest better tags in real-world situation.
This work is supported by the National Science Foundation of China under Grant No. 60621062, 60873174 and the National 863 High-Tech Project under Grant No. 2007AA01Z148.