Graph-based collaborative ranking

https://doi.org/10.1016/j.eswa.2016.09.013Get rights and content

Highlights

  • GRank is a novel framework, designed for recommendation based on rank data.

  • GRank handles the sparsity problem of neighbor-based collaborative ranking.

  • GRank uses the novel TPG graph structure to model users’ choice context.

  • GRank directly ranks items for a target user using personalized PageRank in TPG.

  • GRank improves NDCG@10 up to 9% compared to other collaborative ranking methods.

Abstract

Data sparsity, that is a common problem in neighbor-based collaborative filtering domain, usually complicates the process of item recommendation. This problem is more serious in collaborative ranking domain, in which calculating the users' similarities and recommending items are based on ranking data. Some graph-based approaches have been proposed to address the data sparsity problem, but they suffer from two flaws. First, they fail to correctly model the users' priorities, and second, they can't be used when the only available data is a set of ranking instead of rating values.

In this paper, we propose a novel graph-based approach, called GRank, that is designed for collaborative ranking domain. GRank can correctly model users’ priorities in a new tripartite graph structure, and analyze it to directly infer a recommendation list. The experimental results show a significant improvement in recommendation quality compared to the state of the art graph-based recommendation algorithms and other collaborative ranking techniques.

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 UPU 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)

  • G. Adomavicius et al.

    Improving aggregate recommendation diversity using ranking-based techniques

    IEEE Transactions On Knowledge And Data Engineering

    (2012)
  • I. AvSegal et al.

    EduRank : a collaborative filtering approach to personalization in E-learning

  • S. Balakrishnan et al.

    Collaborative ranking

  • A. Bellogin et al.

    Using graph partitioning techniques for neighbour selection in user-based collaborative filtering

  • F. Cacheda et al.

    Comparison of collaborative filtering algorithms

    ACM Transactions on the Web

    (2011)
  • B. Chen et al.

    Personalized video recommendation through tripartite graph propagation

    ACM Transactions on Multimedia Computing, Communications and Applications

    (2012)
  • N. Chiluka et al.

    A link prediction approach to recommendations in large-scale user-generated content systems

  • N. Chowdhury et al.

    BoostMF : boosted matrix factorisation

  • K. Christakopoulou et al.

    Collaborative ranking with a push at the top

  • J. Cong

    RankClus : integrating clustering with ranking for heterogeneous information network analysis

  • C. Desrosiers et al.

    A comprehensive survey of neighborhood-based recommendation methods

    Recommender systems handbook

    (2011)
  • C. Dhanjal et al.

    Collaborative filtering with localised ranking

  • C. Fan et al.

    Collaborative ranking with ranking-based neighborhood

    Web technologies and applications

    (2013)
  • F. Fouss et al.

    Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation

    IEEE Transactions on Knowledge and Data Engineering

    (2007)
  • Z. Huang et al.

    Link Prediction approach to collaborative filtering

  • J. Jiang et al.

    Scaling-up item-based collaborative filtering recommendation algorithm based on hadoop

  • Y. Koren et al.

    Matrix factorization techniques for recommender systems

    Computer

    (2009)
  • L. Lerche et al.

    Using graded implicit feedback for Bayesian personalized ranking

  • N. Liu et al.

    EigenRank : a ranking-oriented approach to collaborative filtering

  • Cited by (0)

    View full text