=Paper=
{{Paper
|id=Vol-1688/paper-11
|storemode=property
|title=Weighted Random Walks for Meta-Path Expansion in Heterogeneous Networks
|pdfUrl=https://ceur-ws.org/Vol-1688/paper-11.pdf
|volume=Vol-1688
|authors=Fatemeh Vahedian,Robin Burke,Bamshad Mobasher
|dblpUrl=https://dblp.org/rec/conf/recsys/VahedianBM16
}}
==Weighted Random Walks for Meta-Path Expansion in Heterogeneous Networks==
https://ceur-ws.org/Vol-1688/paper-11.pdf
Weighted Random Walks for Meta-Path Expansion in
Heterogeneous Networks
Fatemeh Vahedian, Robin Burke & Bamshad Mobasher
Center for Web Intelligence, DePaul University, Chicago, IL 60604
{fvahedia, rburke, mobasher}@cs.depaul.edu
ABSTRACT In general, if we know that some edges represent weaker
In social networks, users and items are joined in a complex connections and some edges represent stronger connections,
web of relations, which can be modeled as heterogeneous it is sensible to treat the weaker connections differently to
information networks. Such networks include a variety of avoid adding noise to the recommendation model. The only
object types and the rich relations among them. Recent re- previous work on weighed heterogeneous networks breaks
search has shown that a hybrid recommendation approach each meta-path into various similar rated paths [10] then
combining components built from extended meta-paths in combines all of them together. Since generating those meta-
the network can improve the accuracy of recommendations paths is computationally expensive in general, this method
in such networks. However most of this recent work is fo- is fairly time consuming. In this work, we propose a random
cused on unweighted heterogeneous networks, and simpli- walk sampling method in a heterogeneous weighted graph in
fying relations by ignoring weight (including user ratings) which meta-paths are generated using exponential sampling
loses important information. We propose a random walk that prefers highly rated edges, and build a recommendation
based model to generate meta-paths in weighted heteroge- model from the resulting collection of paths.
neous network in which the frequency of edge sampling is a
function of edge weight, and demonstrate that performance 2. RANDOM WALK SAMPLING
is improved using this method.
Christoffel et al.[3] introduced a random walk sampling al-
gorithms to calculate the transition probability in a ran-
1. INTRODUCTION dom walk model to rank items and generate recommenda-
Much research has been focused on recommender systems tion model. This model works from an unweighted bipartite
in heterogeneous networks using extended relations based graph which represents the binary relations among user and
on meta-paths, showing that accuracy can be improved over items. Building on this approach, we propose a method
the use of simple direct relations. This benefit has been for generating meta-paths in a heterogeneous network using
demonstrated with several different recommendation algo- biased random walk sampling. This method has the advan-
rithms including multi-relational matrix factorization [7, 8], tage of creating greater efficiency in meta-path generation
weighted hybrid of low-dimensional components [2, 1, 6, 5] and allowing for sensitivity to user ratings.
and non-negative matrix factorization [9, 10]. The goal of meta-path generation is to create a relation
However, these models all assume a uniform preference based on paths through the network. For example, the ex-
associated with all relations in the network. In many net- tended user − movie − actor − movie − user meta-path en-
works, however, users provide rating values that can provide ables the system to start with a given user and find other
useful information. The lack of user rating values in generat- users that have watched movies containing actors in common
ing meta-paths can be misleading. For example, in a movie with the user’s movies. The semantics of this operation of
recommender, if user u gave movie m1 the lowest possible meta-path expansion is that the end result is a set of desti-
rating of 1, then it would be unproductive to treat this con- nation nodes (in this case, users) weighted by how many of
nection as having the same value as another movie m2 to the expanded meta-paths reach that node. A random-walk
which the user gave a higher rating. So, where such informa- version of this process chooses edges from the next relation
tion is available, it is essential to rank differently the paths in the meta-path randomly instead of following all possible
starting from highly rated movies and the ones that are not paths. This is more efficient than generating all paths and
as interesting to the user. 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
Copyright is held by the author(s). RecSys 2016 Poster Proceedings, September 15-19, user rating with higher rated items being more preferred.
2016, Boston, MA. This construction is common in recommendation contexts
where users’ quantitative preferences can be gathered.
ACM ISBN 978-1-4503-2138-9. Random walk meta-path expansion therefore uses the pro-
DOI: 10.1145/1235 cess shown in Algorithm 1. The algorithm takes as input a
Algorithm 1 Random walk meta-path generation tions. On our test machine, the random walk method takes
Require: l ← [u] // Initialize path with starting node: user less than 5% of the time required by the baseline technique
Require: m ← metapath // Queue of edge types to generate U M A and U M AM meta-paths. Since meta-
function Generate(l,m) path generation is a major portion of the overall learning
if m 6= {} then time for this system, the random sampling technique would
me ← pop(m); // Next edge type be strongly preferred even if its accuracy were not better.
n ← l[1] //Current node
E ← GetEdges(n, me) // Get edges of type me 4. CONCLUSION
if me = user-item then We proposed a weighted sampling method to generate meta-
hn, j, vi ← WSample(E) //weighted paths in weighted heterogeneous network. The results show
else multi-relational matrix factorization recommendation using
hn, j, vi ← USample(E) //uniform those meta-paths can be enhanced comparing to previous
push(j, l); //Add node j to path method. Additionally, random walk based meta-path gen-
MPgenerate(l,m) eration is more efficient while not sacrificing accuracy. As
else our future work, we will be exploring other multi-relational
return l algorithms and hybrid model using weighted sampling and
extend the application of weighted sampling to other types
of weighted edges.
list with a single user as the start node and returns a single
random walk guided by the meta-path. The functions US- Acknowledgments
ample and WSample, which is omitted for reasons of space,
each returns an edge from the list. In the case of USample This work was supported in part by the National Science
Foundation under Grant No. IIS-1423368 (Multi-dimension-
all edges have equal probability. In the case of WSample, al Recommendation in Complex Heterogeneous Networks).
the edge is chosen with probability proportional to ew .
5. REFERENCES
3. EXPERIMENTS AND RESULTS [1] R. Burke and F. Vahedian. Social web recommendation
In order to test the meta-path algorithm and its impact on using metapaths. In RSWeb@RecSys, 2013.
[2] R. D. Burke, F. Vahedian, and B. Mobasher. Hybrid
recommendation model we build a movie recommendation
recommendation in heterogeneous networks. In UMAP
using multi-relational matrix factorization (DMF) [4, 8] by 2014, pages 49–60, 2014.
incorporating additional relations built from extended meta- [3] F. Christoffel, B. Paudel, C. Newell, and A. Bernstein.
paths. For this paper, we used randomly selected a 33% Blockbusters and wallflowers: Accurate, diverse, and
subset of the MovieLens 1M dataset 1 . We generated four scalable recommendations with random walks. In
meta-path relations starting from the user(user → movie → Proceedings of the 9th ACM Conference on Recommender
actor, user → movie → director, user → movie → actor → Systems, RecSys ’15, pages 163–170, New York, NY, USA,
2015. ACM.
movie, user → movie → director → movie). The mod-
[4] L. R. Drumond, E. Diaz-Aviles, L. Schmidt-Thieme, and
els were optimized using BPR as the optimization crite- W. Nejdl. Optimizing multi-relational factorization models
rion (BPR-opt), as described in [4]. Figure 1 shows the for multiple target relations. In CIKM 2014, pages
191–200, New York, NY, USA, 2014. ACM.
[5] F. Vahedian. Weighted hybrid recommendation for
heterogeneous networks. In RecSys ’14, pages 429–432,
2014.
[6] F. Vahedian and R. D. Burke. Predicting component
utilities for linear-weighted hybrid recommendation. In
RSWeb 2014, 2014.
[7] F. Vahedian, R. D. Burke, and B. Mobasher.
Network-based extension of multi-relational factorization
models. In Poster Proceedings of the 9th ACM Conference
on Recommender Systems, RecSys 2015, Vienna, Austria,
September 16, 2015., 2015.
[8] F. Vahedian, R. D. Burke, and B. Mobasher. Meta-path
selection for extended multi-relational matrix factorization.
In Proceedings of the Twenty-Ninth International Florida
Figure 1: Recall vs. precision for MovieLens dataset Artificial Intelligence Research Society Conference,
FLAIRS 2016, Key Largo, Florida, May 16-18, 2016.,
results for recall and precision on recommendation lists of pages 566–571, 2016.
length one through ten for the three recommendation mod- [9] X. Yu, X. Ren, Y. Sun, Q. Gu, B. Sturt, U. Khandelwal,
els. DM F -rw ,the model using extended paths through ran- B. Norick, and J. Han. Personalized entity
dom walk, outperforms other generated models. DM F -pc recommendation: A heterogeneous information network
approach. In WSDM 2014, pages 283–292, 2014.
represents the model using meta-paths generated in a tradi-
[10] X. Yu, X. Ren, Y. Sun, B. Sturt, U. Khandelwal, Q. Gu,
tional way, finally DM F shows the result for models using B. Norick, and J. Han. Recommendation in heterogeneous
just direct link of the network. information networks with implicit user feedback. In
As anticipated, random sampling for meta-path genera- Proceedings of the 7th ACM Conference on Recommender
tion is much faster than generating the full meta-path rela- Systems, RecSys ’13, pages 347–350, New York, NY, USA,
2013. ACM.
1
http://grouplens.org/datasets/movielens/