The social web is characterized by a wide variety of connections between individuals and entities. A challenge for social web recommendation is make the most e ective use of a diverse set of relations. Typically, researchers focus on a limited set of relations (for example, person to person ties for user recommendation or annotations in social tagging recommendation). In this paper, we propose a general approach to recommendation in social networks that can incorporate multiple relations in combination. A key feature of this approach is the use of the metapath, an abstraction of a large class of paths in the network in which edges of di erent types are traversed in a particular order. As a preliminary demonstration, we show that our approach yields improvements over a state-of-the-art technique on several social tagging datasets.
We might expect that a suitable song would also be mellow electronica featuring a female vocalist but there will be a very large number of tracks with these characteristics. We can discriminate among these tracks using data from the Last.fm social network, as summarized in the schema in Figure 1. As the schema shows, a given song may have many possible associations. It may appear on multiple playlists; it may have been tagged by one or more users (AnnotationS); it may be associated with one or more artists. We can select any of these data sources, and build a recommender system with that basis. For example, using a user-based collaborative approach we could look at similarities across playlists or across tagging histories. Any such choice inevitably excludes a great deal of possibly-relevant knowledge.
Ideally, we would like a recommendation method that is
integrative { bringing all of the available data to bear. In this
paper, we describe one such technique: the Weighted
Hybrid of Low-Dimensional Recommenders (WHyLDR). The
WHyLDR technique was originally developed for social
tagging systems [
The key insight of the WHyLDR design is that a complex network structure can be viewed as a set of two-dimensional projections from nodes of one type to nodes of another. Figure 2 illustrates this idea in the case of social tagging systems. The tagging system on the left has annotations consisting of user, tags and web resources the users have tagged. One projection (the UT projection) maps each user to the set of tags that user has applied. Another projection (UR) maps the user to the resources he or she has tagged. Other projections link resources to tags and to users: six such projections in total.
Given a two-dimensional representation, such as user
represented by tags, it is quite straightforward to apply standard
collaborative recommendation methodology: nd
neighborhoods of similar users and make recommendations on that
basis. with a hybrid recommendation approach, it is not
necessary to choose just one of these projections as the source
of data: a recommendation can be made by combining the
results of recommendation components built from these
lowdimensional projections. Our previous work has shown that
a linear weighted hybrid build of such components is more
exible and more accurate than integrative techniques that
attempt to model all of the dimensions at once [
A metapath can be used to generate a two-dimension projection where each originating node is mapped to all of the terminating nodes reachable by following the path. For example, the SPU metapath can be used to generate an itembased matrix where each song is represented in terms of the users that have incorporated it into a playlist.
A metapath can be arbitrarily long although we anticipate very long paths may not be very useful. Metapaths may also contain multiple occurrences of the same object type. For example, the songs on the playlists of the user's friends of friends can be expressed via the UUPS metapath huser ! user ! playlist ! songi.
The integration of social network data into recommender
systems has been studied extensively in recent years [
Sun and Han [
As discussed above, this work is an extension of research
applying linear weighted hybrids to recommendation problems
in social tagging systems. This work employed a collection of
recommendation components including the two-dimensional
projection components built as described above and used
random-restart hill climbing to optimize the contribution of
each component. This technique is both simple and
general. Our results showed that it was at least as e ective
as other, more computationally-sophisticated techniques for
the well-studied problem of tag recommendation, with the
added advantages that it could be applied to a wider
variety of recommendation problems and could be more easily
updated. See [
For the present discussion, we assume that a recommender is
a function that takes a user as input and returns a ranked list
of recommended items. One common way to implement such
a recommendation function is to build it on top of a scoring
function s(u; i), where u is a user and i is an item. If we can
calculate a score for each item available for recommendation,
we can sort the items and present the best items to the user.
A weighted hybrid recommender is therefore a scoring
function that forms a weighted sum of the results of its
constituent components [
The components needed for a hybrid recommender are a function of the recommendation task and the data available to support recommendation. In our work on social tagging systems, we identi ed a number of recommendation tasks appropriate to that context, including tag recommendation, resource recommendation, resource recommendation by example, user recommendation, and others. Resource recommendation is the task of identifying items of interest for a user in social tagging system based on tagging behavior. Note that these items may or may not be items that the user \likes" { a user may frequently tag disliked items with deprecatory tags, for example.
In the experiments reported in [
Popular: A non-personalized recommender that scores resources based on their overall popularity.
User-based kNN, user-tag matrix (kNNUT): A
userbased collaborative recommendation component in which
users are compared by their usage of tags. The entries
in this matrix are normalized counts { the fraction
of annotations in which a user has employed a given
tag. Pearson correlation is used to compare users and
Resnick's algorithm is used to compare predictions.
User-based kNN, user-resource matrix (kNNUR): As
above, but where users are compared on the basis of
which resources they have tagged. In this matrix, we
did not nd any bene t to make use of the count
information: the number of tags that a user applied to
a given resource. The matrix is therefore binary,
reecting whether or not the user tagged a particular
resource. Predictions are computed as with kNNUT.
Item-based kNN, resource-tag matrix (kNNRT):
Itembased collaborative recommendation in which resources
are compared on the basis of the tags that have been
associated with them. This matrix is similar to kNNUT,
but instead of users, we are pro ling resources. To
make predictions, we use the adjusted cosine method
from [
Item-based kNN, resource-user matrix (kNNRU): Itembased collaborative recommendation in which resources are compared on the basis of the users who have tagged them. This matrix is the transpose of the UR matrix, and is also binary. Adjusted cosine is used here as well. Cosine: In this component, the user is represented as the vector of tags they have applied, normalized as in kNNUT and each resource is represented as a vector of tags that have been applied to it as in kNNRT. The scoring of a resource for a user is done by computing the cosine between the two vectors.
Following Sun and Han [
A heterogeneous network is one where there are multiple object types and/or multiple edge types { typically both. For example, the music example above is clearly a hetereogeneous network. There are multiple types of nodes (artists, users, songs, etc.) and multiple types of relations (user-user, user-playlist, artist-song, etc.). A network schema, such as that shown in Figure 1, gives an overview of a heterogeneous network by indicating the di erent object types and the relations that exist between them. A metapath in a heterogeneous network is a path over the network schema, a sequenced composition of relations between two object types.
A social tagging system can be viewed as a heterogeneous network with four di erent types of nodes (users, tag, resources, and annotations). See Figure 3. With this in mind, consider the UR projection on which the kNNUR component is built. This is a matrix in which the rows correspond to users and the columns correspond to resources, and the entries re ect the whether or not the user has tagged that particular resource. We can generate the same matrix using the schema shown in Figure 3 by following the metapath huser ! annotation ! resourcei. Since the schema has a simple star structure, we will omit the reference to the central annotation node (all navigation must go through it) and refer to this as the UR metapath. Adopting the metapath formalism allows us to express a much wider set of possible projections. We can expand the set of resources by which a user is represented by following an extended metapath: huser ! annotation ! tag ! annotation ! resourcei or UTR for short. This path nds all tags a user has employed and then all annotations including those tags (even those not created by the user) and then the resources for that larger set of annotations. This can be seen as a kind of "query expansion" of the resource space by considering other users' annotations of the same resources. To see how this process works, consider Figure 4, which shows a simpli ed network with 3 users having tagged three music tracks.
There are four annotations (A1...A4) because Carol has created two. Note that Bob and Alice have no tagged tracks in common.
However, if we follow the UTR metapath, the fact that Bob and Alice have both used the tag \Relaxing" means that the UTR metapath yields both Track2 and Track3 for these users. The resulting matrix shows a similarity between these two users that was not present in the UR version.
Bob
Alice
Of course, this process can be extended inde nitely: UTTR,
UTTTR, etc. We can envision in addition a wide variety of
other metapaths: for example, UTUR would be all resources
tagged by users who share tags with the target user. For
our preliminary investigation of this style of
recommendation, we opted to explore only a few possible components
using short metapaths. We created three additional
components to augment the six already incorporated in the system
described in [
User-based kNN with the user-tag matrix formed by following the URT metapath: kNNURT.
User-based kNN with the user-resource matrix formed by following the UTR metapath: kNNUTR.
A version of the Cosine metric above in which the vector of tags for a user is formed using the URT metapath: Cosine-M.
For our experiments, we used three social tagging networks
from the data sets studied in [
Bibsonomy which enables users to tag URL bookmark and journal articles. This dataset contains 357 users, 1.783 resources and 1,573 tags.
Amazon includes 4817 users, 5801 resources
(products on the Amazon.com web site) and 3201 tags. (Note
that this is a subset of the full network from [
For each data set, we divided the data randomly into ve partitions each having equal numbers of annotations. The rst partition is used to learn the weights for each component. The other partitions are used for cross validation: three partitions are used as training data and the fourth is used to test the system's predictions.
The values in Equation 1 are learned empirically from the rst data partition. We choose a random set of values and calculate the F-measure for the hybrid using these weights. Then we adjust one weight at random and re-compute the F-measure over the same data partition. If it increases, the change is accepted and the process repeats. Otherwise, the change is rejected and another random modi cation is proposed. When the values stabilize, another random starting point is chosen. The weights leading to the highest Fmeasure are then chosen for the rest of the experiment and the data is discarded.
To measure the quality of recommendations, the remaining partitions are used for four-fold cross validation. For each user in the test partition, we calculate recommendation lists Recu of size 1 through 10 and compare these results with the resources Ru tagged by that user in the test partition, calculating precision and recall as below.
recall = jRu \ Recuj
jRuj precision = jRu \ Recuj jRecuj (2) (3) The recall and precision are calculated for each user and averaged across all users, and then averaged across the four folds.
We evaluated two recommendation hybrids: the original
hybrid (labeled \H") in the gures containing the 6 components
used in [
In all experiments we see that hybrid model that includes components with longer metapaths o ers improved results. Figure 5a shows the results for Amazon dataset. This is one of the most di cult recommendation data sets in our evaluations: note the extremely low recall and precision results. We can see the HM model o ers better results than the original hybrid method.
Looking at the performance of the individual components, we see that the components with longer metapaths are not better than their shorter-path counterparts. kNNUR is the top individual component but kNNUTR is a distant third. Cosine-M and kNNURT appear to be about the same as the non-extended versions.
Figure 5b shows the results for the Bibsonomy dataset. The metapath enhanced HM hybrid shows a slight improvement over original hybrid model for this dataset. Most interesting are the characteristics of the URT and UTR components. Unlike the Amazon results, the kNNURT component o ers higher precision across almost the whole range of recall values and the kNNUTR component is roughly comparable to the kNNUR one, with slightly higher precision at lower recall. Finally, the Last.fm results are shown in Figure 5c. One well-known characteristic of this data set is the high degree of noise associated with the tags. Users often apply vague tags such as \rock" or (worse) \favorite song" to music tracks on this site. Again the HM hybrid is superior. The UT and URT components are both equally bad { not surprising given the characteristics of the tag dimension. The UR and UTR components are quite similar in performance, which is rather surprising, given that the UTR metapath makes use of these same problematic tag links.
Figure 6 shows the learned weights for the components in the recommendation experiments. In each graph, the grey bar represents the weights of the components in the original hybrid and the striped bars are the weights for the HM algorithm. The rst set of results in Figure 6a are for the Amazon.com data. In this data, the Cosine component is a strong contributor to the hybrid. When we add the longer metapaths Cosine-M also proves useful. kNNUR also has relatively high weight in the original version. The extended version of this component via the UTR metapath gets some weight in the HM model. Most surprisingly, UT, which has very low weight in the original model, becomes the single most heavily-weighted component in the HM model. This is the only data set where the simple popularity recommender has a relatively large weight.
Figure 6b shows the weight contribution of recommender components learned for the Bibsonomy dataset. The original hybrid showed a very strong contribution from the kNNUR component, which in the HM model is dispersed to the longer metapath components kNNURT and kNNUTR. Interestingly, the contribution of the Cosine component drops by more than 50%, while the extended version Cosine-M barely makes a showing. It seems that perhaps the components with longer metapaths are doing a better job of capturing the tag-based connections between users and resources, rendering the Cosine component less valuable. We will need to do additional experimentation to characterize this phenomenon.
The learned weights for the two hybrids on the Last.fm data appear in Figure 6c. kNNUTR and kNNUR have similar weights in the larger hybrid. Again, the Cosine metric loses weight in the HM model, as the Cosine-M gains comparable weight.
The work described here is very preliminary. While our aim is to explore recommendation is data sets with complex network schemas, to date we have only extended our prior work on social tagging systems. The results are very encouraging, however, showing improvement on the baseline system using a few components based on deeper paths into the same network. We expect that the incorporation of additional object types and relations will yield even more improvement in recommendation accuracy.
One important question is whether the hybrid weights can be predicted or at least estimated from the characteristics of the data. This issue takes on greater urgency when we consider the fact that the set of metapath-based components is unbounded { it is always possible to consider more friends of friends or to follow a link back and forth again: UTR, UTTR, UTTTR, etc. Intuitively, the value of longer paths should be less in the limit { eventually there will be a xed point. But, as the results here show, under some conditions components built with longer metapaths are actually more successful than those with shorter paths, so we cannot assume that weights will decrease monotonically with path length.
We are experimenting with entropy-based measures of the contribution of each component, with the aim of nding a metric with which to discriminate between components and lter out those unlikely to be useful, prior to the weight learning step. Limiting the number of components is key to making weight learning e cient. In the experiments reported here, we found that adding three more components (50% increase) quadrupled the amount of training time required to learn the values. So it is not possible add components indiscriminately. In addition, a weight estimator might be useful for providing an initial seed for the hillclimbing step. All of these questions will be explored in future work.
One of the key challenges in social web recommendation is the e ective integration of the many dimensions of the available data. In this paper, we describe a linear-weighted hybrid approach that generalizes our prior work on social tagging systems to a larger space of heterogeneous networks. We show that this more general approach can o er performance improvement in social tagging data, and o ers signi cant potential for incorporating additional data dimensions. (b) Bibsonomy dataset