Graph-based collaborative ranking
Introduction
Collaborative filtering (CF) techniques are effective algorithms that help people by filtering irrelevant contents and providing personalized recommendation of useful services. These techniques seek to learn models to predict the services that a user will require in the future based on his preferences in the past.
Collaborative-filtering techniques can be categorized into two classes: rating-oriented and ranking-oriented algorithms. The goal of rating-oriented algorithms is to accurately predict a user's ratings and then, recommend the items with the highest predicted rating for him. On the other hand, ranking-oriented approach, called collaborative ranking, seek to directly predict the rankings of items from the viewpoint of a target user, without explicitly predict the ratings. It has been shown that ranking-oriented collaborative filtering approach is sometimes more intuitive and applicable. To see why, notice that, recommendation is naturally a ranking task and what a recommendation algorithm really needs is to improve the quality of Top-k ranking not predicting the rates (Liu and Yang, 2008, Shi et al., 2012, Shi et al., 2010, Shi et al., 2013b). Moreover, in many applications, all we have is a set of implicit feedbacks while no rating data is available and hence, rating based methods can't be used in such a situation. Note that despite rating and other kinds of explicit feedback, that require the user to explicitly assess the items, implicit feedback can be automatically gathered by tracking the user's interactions with the system (e.g. click, buy, like, etc.). Ranking oriented collaborative filtering can be applied in such situations as well.
Neighbor-based collaborative filtering, one of the main classes of collaborative filtering, estimates the ranking/rating of target user based on the behavior of similar users. Despite several researches in this class of algorithms, they still are not able to precisely calculate users’ similarities. The reason can be explained by sparsity problem which refers to the fact that in recommender systems, users have given feedback to a small proportion of items, and consequently, they rarely have enough common items or pairwise comparisons for estimation of their true similarities/ dissimilarities (Desrosiers & Karypis, 2011). One approach to overcome this issue, is graph-based recommendation that takes advantages of heterogeneous information networks, that are information networks containing different types of nodes and edges, to refine the similarity measures (Shang et al., 2008, Zhang et al., 2010, Zhou et al., 2007), expand the neighborhoods, and, directly calculate the closeness of users and items(Chiluka et al., 2011, Silva and Zaki, 2013, Xiang et al., 2010, Yao et al., 2013).
Graph-based recommendation algorithms represent the relations between users and items as a bipartite graph in which there is a weighted or unweighted link between a user and each item he has rated (Li and Chen, 2013, Shang et al., 2008, Shang et al., 2010, Ting et al., 2013, Xiang et al., 2010, Zhang et al., 2010, Zhou et al., 2007). Unfortunately, this approach is basically designed for rating/binary feedbacks and has crucial insufficiencies for ranking-oriented class of neighbor-based collaborative filtering.
The first problem is that current graph-based approaches are incompetent to capture the preference order of users. We refer to the example of Fig. 1a to illustrate this shortcoming. Mike and Lee have the same preference order for item A, and B, while Mike, and Martin have completely opposite preference orders on all items. Current graph-based algorithms represent this data as Fig. 1b (Sawant, 2013, Shang et al., 2008). Intuitively, under this graph modeling, most of well-known graph proximity measures (e.g. common neighbors, distance, Katz, and personalized PageRank) will suggest that Mike is much closer to Martin than Lee that is counterintuitive.
The second shortcoming of current graph-based approaches have been proposed for binary implicit feedback and that they cannot capture the pairwise preference (i.e. choice context) of user that is generated by different implicit feedbacks. It is clear that the choice context is a valuable piece of information that can be used to improve the recommendation quality. To see how such information is lost when data is modeled by current graph representations, you can observe in the example of Fig. 2 that John has preferred item A over B in one session and item B over C in another session, while, Jack has preferred item B over A. Current graph-based representation of implicit feedbacks, makes a link between the user and those items receiving the positive feedbacks (Chen et al., 2012, Xiang et al., 2010, Zhang et al., 2010). Therefore, these algorithms cannot differentiate heterogeneous implicit feedbacks (i.e. buy, click). More importantly, they are not able to clarify the fact that Jack and John disagree when it comes to comparison of items A and B, as illustrated in Fig. 2b.
This paper presents a novel framework, called GRank, that captures the preference of users using a new Tripartite Preference Graph (TPG) structure that demonstrates the relations between users, items, and pairwise preferences. GRank, also provides a new ranking algorithm, which extends personalized PageRank for top-k recommendation. To the best of our knowledge, this algorithm is the first graph-based approach that is able to capture the preference information provided by implicit feedbacks. Experimental results show higher accuracy of GRank compared to the state of the art collaborative ranking algorithms as well as available graph-based recommendation systems.
The rest of this paper is organized as follows. In Section 2, the related work on graph-based recommendation and collaborative ranking techniques are discussed; then, we present the details of GRank's framework in Section 3. The experimental results are presented and analyzed in Section 4. In Section 5, we discuss how GRank can address some the current shortcomings of collaborative ranking and graph-based recommendation methods. Finally, in Section 6 we conclude and introduce our future works.
Section snippets
Related work
The quality of recommendation can be analyzed from many different points of view including accuracy(Koren et al., 2009, Weimer and Karatzoglou, 2007), coverage (Bellogin and Parapar, 2012, Cacheda et al., 2011), diversity (Adomavicius and Kwon, 2012, Said et al., 2012, Zhou et al., 2010), serendipity(Lu et al., 2012, Xiao et al., 2014), uncertainty (Zhang, Guo, & Chen, 2015), shilling attack detection(Zhang & Kulkarni, 2014) and scalability (Jiang, Lu, Zhang, & Long, 2011). Although all these
GRank: a graph-based framework for collaborative filtering
It has been shown that heterogeneous information networks have strong capabilities to model the relationships among different entities of recommender systems (Cong, 2009, Sun et al., 2011, Yu et al., 2013, Yu et al., 2014). In this paper, we seek to propose an effective graph approach to ranking-oriented recommender systems, called Graph-based collaborative Ranking, or GRank. In the following, we first define the problem of graph-based collaborative ranking and its purposes. Then, we present
Experimental settings and results
We have conducted a series of experiments for evaluating GRank algorithm. Here, we will first give a detailed description of the experimental protocol. Then, we will analyze the ranking quality and scalability of GRank.
Discussion
GRank framework was introduced to resolve the sparsity problem of NCR techniques for similarity calculation. In the following, we briefly discuss how GRank is accomplished to resolve the issues.
- •
Using TPG, GRank implicitly aggregates different kinds of users’ similarities: One type of user similarities is calculated based on their common comparisons. This type of similarity is reflected by the paths following that connect two users through a pairwise comparison's node. Additionally, two
Conclusion
In this paper, we studied how a graph-based framework can be designed and exploited to address the shortcomings of current neighbor-based collaborative ranking algorithms. For this purpose, we suggested that modeling the preference data as a new tri-partite graph structure and then exploring it can help us to capture the different kinds of relations existing in a ranking preference dataset (e.g. users’ similarities, items’ similarities, etc.). We also proposed a random-walk approach to make
References (58)
- et al.
Leveraging multiviews of trust and similarity to enhance clustering-based recommender systems
Knowledge-Based Systems
(2015) - et al.
A recommender system using GA K-means clustering in an online shopping market
Expert Systems with Applications
(2008) - et al.
PathRank : ranking nodes on a heterogeneous graph for flexible hybrid recommender systems
Expert Systems with Applications
(2013) - et al.
Recommendation as link prediction in bipartite graphs: a graph kernel-based machine learning approach
Decision Support Systems
(2013) - et al.
List-wise probabilistic matrix factorization for recommendation
Information Sciences
(2014) - et al.
Adaptive Bayesian personalized ranking for heterogeneous implicit feedbacks
Knowledge-Based Systems
(2015) - et al.
Collaborative filtering with diffusion-based similarity on tripartite graphs
Physica A: Statistical Mechanics and Its Applications
(2010) - et al.
Unifying rating-oriented and ranking-oriented collaborative filtering for improved recommendation
Information Sciences
(2013) - et al.
Detection of Shilling attacks in recommender systems via spectral clustering
- et al.
Personalized recommendation via integrated diffusion on user–item–tag tripartite graphs
Physica A: Statistical Mechanics and Its Applications
(2010)