Much research has been focused on recommender systems in heterogeneous networks using extended relations based on meta-paths, showing that accuracy can be improved over the use of simple direct relations. This benefit has been demonstrated with several different recommendation algorithms including multi-relational matrix factorization [7,8], weighted hybrid of low-dimensional components [2,1,6,5] and non-negative matrix factorization [9,10].
However, these models all assume a uniform preference associated with all relations in the network. In many networks, however, users provide rating values that can provide useful information. The lack of user rating values in generating meta-paths can be misleading. For example, in a movie recommender, if user u gave movie m1 the lowest possible rating of 1, then it would be unproductive to treat this connection as having the same value as another movie m2 to which the user gave a higher rating. So, where such information is available, it is essential to rank differently the paths starting from highly rated movies and the ones that are not as interesting to the user.
In general, if we know that some edges represent weaker connections and some edges represent stronger connections, it is sensible to treat the weaker connections differently to avoid adding noise to the recommendation model. The only previous work on weighed heterogeneous networks breaks each meta-path into various similar rated paths [10] then combines all of them together. Since generating those metapaths is computationally expensive in general, this method is fairly time consuming. In this work, we propose a random walk sampling method in a heterogeneous weighted graph in which meta-paths are generated using exponential sampling that prefers highly rated edges, and build a recommendation model from the resulting collection of paths.
Christoffel et al. [3] introduced a random walk sampling algorithms to calculate the transition probability in a random walk model to rank items and generate recommendation model. This model works from an unweighted bipartite graph which represents the binary relations among user and items. Building on this approach, we propose a method for generating meta-paths in a heterogeneous network using biased random walk sampling. This method has the advantage of creating greater efficiency in meta-path generation and allowing for sensitivity to user ratings.
The goal of meta-path generation is to create a relation based on paths through the network. For example, the extended user − movie − actor − movie − user meta-path enables the system to start with a given user and find other users that have watched movies containing actors in common with the user's movies. The semantics of this operation of meta-path expansion is that the end result is a set of destination nodes (in this case, users) weighted by how many of the expanded meta-paths reach that node. A random-walk version of this process chooses edges from the next relation in the meta-path randomly instead of following all possible paths. This is more efficient than generating all paths and the number of samples can be chosen to be large enough to provide a good estimate of what a full expansion would provide [3]. In this work, we look specifically at networks involving a single "rating" edge from user to item. In other words, the first connection from a user is assumed to be to an item and is assumed to have a weight that represents the user rating with higher rated items being more preferred. This construction is common in recommendation contexts where users' quantitative preferences can be gathered.
Random walk meta-path expansion therefore uses the process shown in Algorithm 1. The algorithm takes as input a list with a single user as the start node and returns a single random walk guided by the meta-path. The functions USample and WSample, which is omitted for reasons of space, each returns an edge from the list. In the case of USample all edges have equal probability. In the case of WSample, the edge is chosen with probability proportional to e w .
In order to test the meta-path algorithm and its impact on recommendation model we build a movie recommendation using multi-relational matrix factorization (DMF) [4,8] by incorporating additional relations built from extended metapaths. For this paper, we used randomly selected a 33% subset of the MovieLens 1M dataset1 . We generated four meta-path relations starting from the user(user → movie → actor, user → movie → director, user → movie → actor → movie, user → movie → director → movie). The models were optimized using BPR as the optimization criterion (BPR-opt), as described in [4]. Figure 1 shows the results for recall and precision on recommendation lists of length one through ten for the three recommendation models. DM F -rw ,the model using extended paths through random walk, outperforms other generated models. DM F -pc represents the model using meta-paths generated in a traditional way, finally DM F shows the result for models using just direct link of the network. As anticipated, random sampling for meta-path generation is much faster than generating the full meta-path rela-
We proposed a weighted sampling method to generate metapaths in weighted heterogeneous network. The results show multi-relational matrix factorization recommendation using those meta-paths can be enhanced comparing to previous method. Additionally, random walk based meta-path generation is more efficient while not sacrificing accuracy. As our future work, we will be exploring other multi-relational algorithms and hybrid model using weighted sampling and extend the application of weighted sampling to other types of weighted edges.
This work was supported in part by the National Science Foundation under Grant No. IIS-1423368 (Multi-dimensional Recommendation in Complex Heterogeneous Networks).