In social networks, users and items are joined in a complex web of relations, which can be modeled as heterogeneous information networks. Such networks include a variety of object types and the rich relations among them. Recent research has shown that a hybrid recommendation approach combining components built from extended meta-paths in the network can improve the accuracy of recommendations in such networks. However most of this recent work is focused on unweighted heterogeneous networks, and simplifying relations by ignoring weight (including user ratings) loses important information. We propose a random walk based model to generate meta-paths in weighted heterogeneous network in which the frequency of edge sampling is a function of edge weight, and demonstrate that performance is improved using this method.
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 bene t has been
demonstrated with several di erent recommendation
algorithms including multi-relational matrix factorization [
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 di erently the paths starting from highly rated movies and the ones that are not as interesting to the user. 2.
Christo el et al.[
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 nd 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 e cient 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 [
Random walk meta-path expansion therefore uses the
process shown in Algorithm 1. The algorithm takes as input a
Algorithm 1 Random walk meta-path generation
Require: l [u] // Initialize path with starting node: user
Require: m metapath // Queue of edge types
function Generate(l,m)
if m 6= fg then
me pop(m); // Next edge type
n l[
hn; j; vi WSample(E) //weighted else
hn; j; vi USample(E) //uniform push(j; l); //Add node j to path
MPgenerate(l,m) else
return l 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 ew.
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) [
As anticipated, random sampling for meta-path generation is much faster than generating the full meta-path rela1http://grouplens.org/datasets/movielens/ tions. On our test machine, the random walk method takes less than 5% of the time required by the baseline technique to generate U M A and U M AM meta-paths. Since metapath generation is a major portion of the overall learning time for this system, the random sampling technique would be strongly preferred even if its accuracy were not better. 4.
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 e cient while not sacri cing 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).