The social web is characterized by a diversity of data types and relations. For example, the employment-oriented website LinkedIn contains information about individuals, companies, jobs and skills, and connections can be drawn among any of these entities. There are also discussion forums and user groups. Diversity of information means that there are many kinds of recommendation that can be made to users: other users with whom to connect, groups to join, skills to acquire, companies to follow, jobs to apply for, etc. At the same time, the complexity of information means that there are many more types of information that can be integrated into making recommendations: should the system recommend companies that have hired your friends, those that have many (or few) employees with your skills? Often building recommenders for such sites involves devising individual ad-hoc solutions for each recommendation problem.
To illustrate this problem, consider a user Alice who is a member of the Last.fm web site for music lovers, looking for a song to add to her current playlist:
Bad Girls Blood Orange 2
Under the Gun Supreme Beings of Leisure 3
The Sea Morcheeba 4
Paris Train Beth Orton
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.
Figure 1: Network schema for Last.fm
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 tag-Figure 2: Two-dimensional projections for a social tagging network ging systems [7]; here we show how the concept can be extended to more complex networks.
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: find 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 flexible and more accurate than integrative techniques that attempt to model all of the dimensions at once [7].
We extend this idea to more complex networks through the concept of the metapath [15]. A path in a network is a sequence of edges that can be traversed to move from one node to another. A metapath is an abstraction of a network path into a sequence of edge types. Navigating a metapath from a node reaches all destination nodes reachable by following edges with the appropriate type. For example, in the music recommendation scenario, we might have the SPU metapath song → playlist → user . This path goes from a song to all playlists into which it is a part and then to all users contributing those playlists. A different metapath would go from a song to all annotations in which it appears to all users creating such annotations: song → annotationS → user , denoted SAsU. Note that both the SPU and SAsU metapaths map songs to users, but they follow different routes through the network.
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 user → user → playlist → song .
The integration of social network data into recommender systems has been studied extensively in recent years [17], [4], [13], [14]. Most of this work has been focused on systemspecific solutions. For example, [10] shows a LastFM music recommendation based on combination of social data and annotation system. A similar system incorporating social data and tags has been used to recommend publications in the Bibsonomy dataset [3]. A more general technique is the multi-relational approach of [2] in which the heterogeneous network in Epinions is separated into multiple homogeneous networks and then an optimization approach is used to find the best combination of recommendations coming from the different networks. Kazienko and his colleagues [9] take a similar approach, treating the different kinds of relations in Flickr as "layers."
Our domain-independent approach for recommendation with social network data draws heavily on recent research in the area of complex heterogeneous information networks. According to Han [8], heterogeneous networks are "information systems which consist of a large number of interacting, multityped components". In particular, heterogeneous information networks involve multiple types of objects and multiple types of links denoting different relations [16].
Sun and Han [15] argue that information propagation across heterogeneous nodes and links can be very different from that across homogeneous nodes and links. To capture this diversity, the authors defined the concept of the "metapath". On top of the metapath abstraction, they were able to build algorithms operating on heterogeneous networks such as metapath-based similarity search.
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 gen-eral. Our results showed that it was at least as effective 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 [5,6,7] for more detail on this line of research.
There is a close relationship between recommendation in a network setting and link prediction, which is a standard problem in the computational study of networks [11]. For example, in our playlist example, if the system recommends a track and Alice adds it to her playlist, this will become a new playlist → song link in the network. However, there are some important distinctions between link prediction, as it is customarily studied, and the problem of recommendation. Foremost is the difference of emphasis demonstrated in the output of the system. In link prediction, the output of the system is a set of links likely to appear in the network.
In recommendation, we are suggesting items for an individual and personalization is therefore a key element. We could filter the link predictions just to those that apply to the current user, but it is important to recognize that link prediction techniques are not really designed or evaluated with personalized presentation in mind. Secondly, recommendation often involves a host of additional considerations (serendipity, diversity, etc.) that are not typically factors in link prediction analysises.
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 [1] s (u, i) =
where the si's are the recommendation components and αi's are the associated weights. To define a weighted hybrid, we need to specify its components and their weights.
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 identified 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 [7], the system used the following recommendation components:
• 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 find any benefit to make use of the count information: the number of tags that a user applied to a given resource. The matrix is therefore binary, reflecting 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 profiling resources. To make predictions, we use the adjusted cosine method from [12]. The predicted relevance of a resource is a function of the normalized tag counts of similar resources. Note that this component is not personalized: it will give the same predictions for all users.
• 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 [15], we define a heterogeneous information network as a directed graph G = (ν, ε) with an object type mapping function γ : ν → A and a edge type mapping function φ : ε → R where each object belongs to particular object type a ∈ A and each edge belongs to a particular relation type r ∈ R. Two edges of the same type by definition share the same object types at their originating and terminating points.
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 different 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 different 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 reflect 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 user → annotation → resource . 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: user → annotation → tag → annotation → resource or UTR for short. This path finds 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 simplified network with 3 users having tagged three music tracks.
The UR matrix for this network is as follows:
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 Of course, this process can be extended indefinitely: 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 [7].
• 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 [7]. All of the data sets were filtered as described in [7] to eliminate rare and idiosyncratic tags and resources.
• 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 [7].)
• LastFM users have music profiles and can create playlists. User may tag songs, albums and artists. This dataset contains 2,368 users, 2,350 resources and 1,141 tags.
For each data set, we divided the data randomly into five partitions each having equal numbers of annotations. The first 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 first 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 modification 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.
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 figures containing the 6 components used in [7], and an enhanced hybrid (labeled "HM") adding the three components using extended metapaths.
In all experiments we see that hybrid model that includes components with longer metapaths offers improved results. Figure 5a shows the results for Amazon dataset. This is one of the most difficult recommendation data sets in our evaluations: note the extremely low recall and precision results. We can see the HM model offers 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 offers 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 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 fixed 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 finding a metric with which to discriminate between components and filter out those unlikely to be useful, prior to the weight learning step. Limiting the number of components is key to making weight learning efficient. 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 effective 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 offer performance improvement in social tagging data, and offers significant potential for incorporating additional data dimensions.