BiRank: Towards Ranking on Bipartite Graphs
- 20 September 2016
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 29 (1), 57-71
- https://doi.org/10.1109/tkde.2016.2611584
Abstract
The bipartite graph is a ubiquitous data structure that can model the relationship between two entity types: for instance, users and items, queries and webpages. In this paper, we study the problem of ranking vertices of a bipartite graph, based on the graph's link structure as well as prior information about vertices (which we term a query vector). We present a new solution, BiRank, which iteratively assigns scores to vertices and finally converges to a unique stationary ranking. In contrast to the traditional random walk-based methods, BiRank iterates towards optimizing a regularization function, which smooths the graph under the guidance of the query vector. Importantly, we establish how BiRank relates to the Bayesian methodology, enabling the future extension in a probabilistic way. To show the rationale and extendability of the ranking methodology, we further extend it to rank for the more generic n-partite graphs. BiRank's generic modeling of both the graph structure and vertex features enables it to model various ranking hypotheses flexibly. To illustrate its functionality, we apply the BiRank and TriRank (ranking for tripartite graphs) algorithms to two real-world applications: a general ranking scenario that predicts the future popularity of items, and a personalized ranking scenario that recommends items of interest to users. Extensive experiments on both synthetic and real-world datasets demonstrate BiRank's soundness (fast convergence), efficiency (linear in the number of graph edges), and effectiveness (achieving state-of-the-art in the two real-world tasks).Keywords
Funding Information
- National Key Research and Development Program of China (2016YFB1000905)
- NSFC (U1401256)
- National Research Foundation
- Prime Minister's Office, Singapore
This publication has 34 references indexed in Scilit:
- Do users rate or review?Published by Association for Computing Machinery (ACM) ,2014
- Comment-based multi-view clustering of web 2.0 itemsPublished by Association for Computing Machinery (ACM) ,2014
- A Random Walk Model for Item Recommendation in Social Tagging SystemsACM Transactions on Management Information Systems, 2013
- R -energy for evaluating robustness of dynamic networksPublished by Association for Computing Machinery (ACM) ,2013
- Using early view patterns to predict the popularity of youtube videosPublished by Association for Computing Machinery (ACM) ,2013
- Learning recommender systems with adaptive regularizationPublished by Association for Computing Machinery (ACM) ,2012
- Random walk based entity ranking on graph for multidimensional recommendationPublished by Association for Computing Machinery (ACM) ,2011
- Performance of recommender algorithms on top-n recommendation tasksPublished by Association for Computing Machinery (ACM) ,2010
- Predicting the popularity of online contentCommunications of the ACM, 2010
- Item-based collaborative filtering recommendation algorithmsPublished by Association for Computing Machinery (ACM) ,2001